Задать вопрос юристу

18 Метод функциональных уравнений.

Применение данного метода оказалось весьма эффектным при решении задач нелинейного программирования, у которых целевая функция выпукла (вогнута), т.е. относящихся к задачам выпуклого программирования.

В этих задачах рассматривались сепарабельные (состоящие из нескольких частных функций) функции двух типов:

аддитивные ;мультипликативные .

Для реализации этапов метода динамического программирования Ричардом Беллманом в 1960 г. определил первый принцип, лежащий в основе метода динамического программирования – принцип оптимальности: необходимо всегда обеспечить оптимальное (в смысле принятого критерия) продолжение процесса относительно уже достигнутого его состояния. Т.е. каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным. Дадим его математическую интерпретацию для сепарабельной аддитивной целевой функции.

Принцип оптимальности имеет простую математическую интерпретацию, выражающуюся в составлении определённых рекуррентных соотношений и отыскании среди них наибольшей суммы, соответствующей оптимальному, из множества возможных значений, управлению: (1)

которое называется основным функциональным уравнением динамического программирования (уравнением Беллмана), первое слагаемое которого определяет шаговый эффект перехода динамической системы из одного состояния в другое под воздействием соответствующего управления. Второе слагаемое определяет потенциал состояния, в которое возможен переход системы на данном шаге.

В этом уравнении приняты следующие обозначения:

- si – состояние динамической системы S, число i возможных состояний которой изменяется ;

- uij – управляющее воздействие, поданное на i-ю систему для её перевода из si -го состояния в следующее, количество j которых изменяется ;

- Wγ – получаемый эффект от перевода системы из одного состояния в другое на g-м шаге, число которых изменяется .

Из принципа поэтапного построения оптимального управления следует, что критерий эффективности F должен обладать свойством аддитивности:

Вспоминаем граф переходов. Короче начинаем с конца потом для каждого состояния si вычисляем значение функционального ур (1). запоминаем (записываем) максимальное если равны то оба. Таким образом, на этапе условной оптимизации получили следующие условно оптимальные управления: U = < u*68; u*46; u*36; u*13; u*24; u*02 > Далее следуем из состояния s0 составляем путь из условно оптимальных управлений. Таким образом, оптимальный вектор управления многошаговым процессом имеет следующий вид: U* = < u*02; u*24; u*46; u*68 >

В заключении необходимо отметить, что алгоритм решения задачи методом ДП для сепарабельной мультипликативной функции аналогичен, с той лишь разницей, что уравнение Беллмана принимает несколько иной вид:

При этом, очевидно, что потенциал конечного состояния как некоторая вероятность равна единице.

<< | >>
Источник: Шпаргалка по дисциплине Методы оптимизации. 2017
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме 18 Метод функциональных уравнений.:

  1. Метод функциональных уравнений.
  2. Решение уравнений методом подбора как средство понимания учащимися смысла понятий «ур-я», «решение уравнений».
  3. 1. Системы линейных алгебраических уравнений. Их равносильность. Элементарные преобразования. Метод Гаусса решения систем линейных уравнений.
  4. 1. Системы линейных алгебраических уравнений. Их равносильность. Элементарные преобразования. Метод Гаусса решения систем линейных уравнений.
  5. 3,4.Явные и неявные методы численного решения систем диф. уравнений. Одношаговые и многошаговые методы.
  6. 4. Численные методы решения систем линейных алгебраических уравнений. Метод Гаусса.
  7. 5. Решение системы нелинейных уравнений методом Ньютона (алгоритм, выбор начального приближения, сходимость метода).
  8. §1. Системы линейных уравнений: метод простых итераций, метод Зейделя
  9. 32. Анализ безубыточности производства: математический метод (метод уравнения).
  10. 44. Метод Ньютона и аналоги метода Зейделя решения системы нелинейных уравнений.
  11. 6. Численные методы решения задачи Коши для обыкновенных дифференциальных уравнений (методы Рунге-Кутта и Адамса).
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -