Динамическое программирование

Динамическое программирование Рассмотрим некоторый управляемый экономический процесс. В результате управления система переводится из начального состояния конечное . При этом управление проходит в в шагов, и решение принимается последовательно на каждом шаге, то есть управление представляет собой поша- говых управлений. На каждом шаге необходимо определить два типа переменных: переменную состояния системы переменную управления Переменная состояния система на ; (управляющее воздействие). определяет, в каких состояниях может оказаться - ом шаге. В зависимости от состояния системы на этом шаге можно принять некоторое управление, характеризующееся переменной управления , такое управление должно удовлетворять определѐнным условиям и называется допустимым. Применение управляющего воздействия в новое состояние и даѐт некоторый результат на - ом шаге приводит систему . При этом из всех воз- можных управлений на рассматриваемом шаге выбирают оптимальное, то есть такое, для которого выполняется принцип Беллмана (результат управления с того по - - ый шаг должен быть оптимальным). Числовая характеристика такого результата называется функцией Беллмана и зависит от номера шага и от состояния системы . Таким образом, необходимо определить оптимальную стратегию управления , переводящую систему из начального состояния ное состояние в конеч- , при которой целевая функция (функция Беллмана) принимает наибольшее (наименьшее) значение, то есть . Оптимальную стратегию управления можно получить, если найти сначала оптимальную стратегию управления на - ом шаге, затем на двух последних ша- гах, затем на трѐх последних шагах и так далее, вплоть до первого шага. 1 Для того, чтобы найти оптимальное решение на последнем, - ом шаге, нужно сделать все возможные предположения о том, как мог завершиться последний шаг, и с учѐтом этого выбрать управление ное значение функции результата управление обеспечивающее оптималь- . При этом говорят, что оптимальное на последнем шаге определяется функцией Беллмана: или . Дальнейшие вычисления производят согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с той же функцией, вычисленной на предыдущем шаге: или . Эта часть исследования называется условной оптимизацией. Следующий этап – безусловная оптимизация. Учитывая, что известно начальное состояние системы , можно найти оптимальное управление на первом шаге, то есть решение, которое доставляет оптимальный результат на следующем – втором шаге. В результате такого управления система перейдет в другое состояние , зная которое, аналогичным образом находят оптимальное управление на втором шаге и так далее – до последнего – го шага. 2