14.Методы решения. Динамическое программирование
Метод динамического программирования основан на принципе оптимальности, который. Следуя Беллману, сформулируем на примере дискретного и детерминированного процесса принятия решений.
Рассматривается некоторая физическая система, состояние которой в любой момент времени определяется вектором . Комопоненты вектора называются фазовыми переменными.
Введём
в рассмотрение также семейство
преобразования
,
где векторная переменная
называется вектором решения.
На
каждом шаге можно выбрать значение
из набора допустимых векторов так, что
изменяется состояние физической системы
и определяющий её вектор:
,
,
. . . . . .
.
Процесс,
состоящий из выбора
решений,
называется
шаговым
процессом. Для оценки последовательности
решений
и
введём скалярную функцию
,
которая называется критерием или
функцией дохода. Будем полагать, что
после
шагов принятия решений влияние оставшихся
шагов процесса на функцию критерия
зависит только от состояния системы в
конце
го
решения и от последующих решений
.
Задача заключается в выборе такой последовательности решений, которая доставляет максимальное значение функции критерия. Последовательность допустимых решений называется стратегией (политикой). Стратегия, которая максимизирует функцию критерия, называется оптимальной стратегией. Согласно принципу оптимальности Беллмана, оптимальная стратегия обладает тем свойством, что, каковы бы ни были первоначальное состояние и первоначальное решение, последующее решение должно определять оптимальную стратегию относительно состояния, полученного в результате первоначального решения.
Рассмотрим пример применения принципа оптимальности к задаче о максимизации функции дохода вида
.
Максимальное
значение функции дохода, которое зависит
только от начального состояния
и числа шагов
,
обозначим через
.
Принцип
оптимальности позволяет сделать вывод,
что при любом начальном решении
и
имеем
.
Учитывая, что соотношение (14.1) справедливо для всех начальных решений , для нахождения максимального дохода нужно найти максимум выражения (14.1) по .
Таким образом, принцип оптимальности позволяет получить основное функциональное уравнение в виде
,
где
.
Перейдём от дискретного многошагового процесса к непрерывному процессу с помощью предельного перехода.
Рассмотрим функцию дохода
,
где
бесконечно
малая величина, и преобразование вида
.
Допустим,
что решения принимаются в дискретные
моменты времени
Обозначим
.
Если максимум функции дохода обозначить
через
,
то согласно (14.2) можно записать
.