II-2.5.4. Принцип оптимальности Беллмана

Рассмотрим марковский управляемый детерминированный многошаговый процесс (II.8) и задачу его оптимизации (II.9) с аддитивной функцией цели (II.10).

Преположим, что задача (II.9) с целевой функцией (II.10) имеет решение. Тогда справедлив принцип оптимальности Беллмана:

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

Доказательство. Обозначим через

(II.13)

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

(II.14)

отвечающую ей оптимальную траекторию.

Выберем на оптимальной траектории некоторую точку (состояние системы) и рассмотрим –шаговый процесс, начинающийся из состояния :

(II.15)

эффективность управления которым будем оценивать целевой функцией

(II.16)

где, - управление (стратегия) – шаговым процессом (II.15). В частности, при принятии в состоянии управляющего решения система перейдёт в состояние

Задача оптимизации на процессе (II.15) ставится так же, как и задача для всего процесса (II.8).

Обозначим через

(II.17)

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

составили оптимальную стратегию для N-k - шагового процесса, начинающегося из состояния . Допустим, что это утверждение неверно, т.е. стратегия оптимальна для – шагового процесса (II.15), а управление – шаговым процессом не оптимально относительно его начального состояния

Это означает, что существует такое управление N-k - шаговым процессом , начинающимся из состояния , что

(II.18)

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

(II.19)

Сравнивая крайние члены полученного строгого неравенства, получаем, что стратегия лучше стратегии , а это противоречит предположению об оптимальности стратегии . Таким образом, предположение о неоптимальности стратегии является неверным. Утверждение доказано.