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

Раздел математического программирования, в котором процесс принятия решения разбивается на этапы.

Постановка задачи

Рассматривается система S, которая с течением времени может менять состояние. Говорят, что в системе протекает процесс. Процесс является управляемым. Управление – способ воздействия на систему.
Процесс принятия решения можно разбить на n шагов.
 - состояние системы после i-ого шага.
 - начальное состояние системы (может быть элементом множества начальных состояний ).
 - конечное состояние системы (может быть элементом множества конечных состояний ).
 - управление на i-ом шаге.
 - вектор управления.
Под действием  система переходит из  в .

С переходом из  в связана заинтересованность с помощью критерия .

Среди всех возможных управлений , переводящих систему из  в  выбрать то, которое доставляет максимум функции .

Задачи динамического программирования решаются методом прямой прогонки и методом обратной прогонки.
Процесс нахождения решения разбивается да две стадии:
условная оптимизация;
безусловная оптимизация.
На стадии условной оптимизации определяются условные оптимальные выигрыши и условные оптимальные управления.
Прямая прогонка:              от первого шага к последнему.
Обратная прогонка:          от последнего шага к первому.
На стадии безусловной оптимизации строится оптимальное решение исходной задачи и определяется max (min).
Прямая прогонка:              от последнего шага к первому.
Обратная прогонка:          от первого шага к последнему.

Рассмотрим метод обратной прогонки.

В основе метода лежит принцип оптимальности Беллмана:
Управление на каждом шаге нужно выбирать так, чтобы сумма выигрыша на данном шаге и оптимального выигрыша на всех последующих шагах была максимальна.

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

Условная оптимизация

  - основное функциональное уравнение.

 - функциональное уравнение для последнего шага.

Безусловная оптимизация

Если начальное состояние задано, то .
Если начальное состояние не задано, но сказано, что оно принадлежит какому-либо множеству, то .