Принцип оптимальности. Функциональные уравнения Беллмана

В основе вычислительных алгоритмов динамического программирования лежит принцип оптимальности, сформулированный Беллманом: каково бы ни было состояние системы S в результате i–1 шагов, управление на i-ом шаге должно выбираться так, чтобы оно в совокупности с управлениями на всех последующих шагах от (i+1)-го до n-го оптимизировало функцию цели.

Схема решения ЗДП состоит из двух частей:

1) обратный ход: от последнего шага к первому получают множество возможно оптимальных управлений («условно-оптимальных»);

2) прямой ход: от известного начального состояния к последнему из полученного множества «условно-оптимальных» управлений составляется искомое оптимальное управление для всего процесса в целом.

Принцип оптимальности Беллмана можно записать в математической форме следующим образом. Обозначим через – «условно-оптимальные» значения приращений целевой функции на последнем шаге, двух последних, …, на всей последовательности n шагов, соответственно. Тогда для последнего шага:

,

где – множество допустимых управлений на n-ом шаге, – возможные состояния системы перед n-ым шагом.

Для двух последних шагов:

.

Для k последних шагов:

.

Для всех n шагов:

.

Полученные рекуррентные соотношения называются функциональными уравнениями Беллмана.

Безусловно-оптимальное значение целевой функции для всего n-шагового процесса ; искомое оптимальное управление .