Принцип оптимальности Беллмана

Вычислим суммарную эффективность при оптимальной стратегии.

.

Учитывая, что второе слагаемое в скобках равно , получаем

, (5.1)

т.е. одна сложная задача сведена к двум задачам меньшей размерности.

При получим уравнение Беллмана:

. (5.2)

Уравнение (5.2) называется основной рекуррентной формулой для метода динамического программирования. Рассмотрим оптимальную стратегию .

По определению имеем

.

Отсюда получаем

, (5.3)

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

Сущность динамического подхода состоит в замене решения данной
-шаговой задачи последовательностью задач: одношаговой, двухшаговой и т.д. Отметим основные свойства задач, к которым применим данный подход.

1. Задача должна допускать интерпретацию как -шаговый процесс принятия решения.

2. Задача должна иметь структуру, не зависящую от числа шагов (числом шагов можно регулировать точность вычислений).

3. Формулировка задачи предполагает, что состояние системы должно описываться параметрически.

4. Выбор управления на k-м шаге не должен оказывать влияния на предыдущие решения, кроме необходимого пересчета переменных.