МЕТОД ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Р. БЕЛЛМАНА

Запишем задачу динамического программирования в виде, несколько отличающемся от (4.1.1), но по сути эквивалентном:

(4.2.1)

Будем считать допустимыми к использованию только управления, принадлежащие множеству допустимых управлений, которое определяется следующим образом:

(4.2.2)

Введем функцию Беллмана , которая при определяется выражением

, (4.2.3)

а при рекуррентным соотношением

. (4.2.4)

Выражение (4.2.4) при может быть записано также в виде:

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

Введем понятие условно оптимального управления Беллмана, представляющего собой совокупность допустимых управлений, на которых достигается максимум (4.2.4):

Здесь управление оптимально при условии, что значение , соответствующее моменту времени , также оптимально.

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

1) ;

2) ;

3) ,

где . В результате имеем функцию .

Конкретные траектории состояния и управлений системы определяют следующим образом. Сначала находят решение оптимизационной задачи и в качестве управления в начальный момент времени используют условно оптимальное управление . Тогда . Затем в качестве следующего управления принимают и определяют . Процесс продолжается вплоть до нахождения и . В общем виде для процесса определения траектории системы можно записать:

Изложенный метод построения траектории системы носит название метода Беллмана.

Теорема 4.2.1

Траектория , построенная методом Беллмана, является оптимальной.

Доказательство. Траектория является допустимой, поскольку она удовлетворяет ограничениям задачи (4.2.1) и условию (4.2.2). По построению справедливы равенства:

Сложим эти равенства:

(4.2.5)

Здесь при записи последнего слагаемого учтено равенство (4.2.3). Полученное выражение по смыслу является значением целевой функции задачи (4.2.1). Рассмотрим некоторую произвольно выбранную допустимую траекторию и покажем, что она не лучше траектории . Тем самым будет доказана оптимальность последней. Из соотношения (4.2.4) вытекает справедливость неравенств: