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

Динамическое программирование - метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разбит на отдельные шаги (этапы).

В основе метода лежит принцип оптимальности, сформулированный Р. Бэллманом: «Каково бы ни было начальное состояние, на любом шаге решение должно приниматься с учетом оптимальных решений на последующих шагах, т.е. должно выбираться решение лучшее не для данного шага, а для оптимизируемого процесса в целом».

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

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

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

,     (9)

n        - номер рассматриваемого шага, нумерация шагов осуществляется с конца, т.е. n = 1 присваивается последнему шагу оптимизируемого процесса, с которого и начинается решение;

y_n        -возможное состояние процесса на начало n -го шага (зависит от x_n+1 и y_n+1);

x_n      - решение, возможное на n-ом (от конца процесса) шаге;

f_n(x_n) - значение критерия на n-ом шаге при принятии решения x_n;

F_n(y_n) - суммарное экстремальное значение критерия за n шагов, при условии что n-ый шаг начинается при состоянии y_n; F₀ = 0.

Процесс построения рекуррентных соотношений для решения конкретных задач сводится к следующим основным элементам:

• выбирается деление процесса на шаги;

• устанавливаются параметры состояния и их возможные значения на начало каждого шага;

• устанавливаются возможные решения для каждого шага;

• записывается уравнение состояния;

• описывается критерий на одном шаге;

• записывается рекуррентное соотношение.

Решение задачи начинается с последнего шага, т.е. при n = 1. Для этого шага обычно:

,

где x₁ связан однозначно с y₁.

Затем отыскивается F₂(y₂) и т.д. до F_N(y_N) (N - общее число шагов).

Поскольку y_n обычно известно из условий задачи, постольку расчет F_N(y_N) обеспечивает выборx_N* - полностью оптимального решения (а не условно-оптимального). Зная уравнение состояния, можно найти y_n-1, для которого уже известно условно-оптимальное решение x_n-1, которое и оказывается полностью оптимальным; и т.д. до x₁.

Решение обычно осуществляется в табличном виде. Число таблиц определяется числом шагов в задаче.

Таблица для решения задачи имеет вид:

xn yn	xn1	…	xnе	xn* (yni)	Fn (yni)
yn1 . . . ynk	a11 . . . ak1	… aij …	a1е . . . akе

к          - число возможных состояний процесса на начало n-го шага;

у_пi        - возможное (i-ое) состояние на n-ом шаге (i = 1,...,к);

е         - число возможных решений на n-ом шаге;

x_nj        - возможное (j-ое) решение на n-ом шаге (j = 1,...,е);

x*_n{y_nj) - оптимальное решение на n-ом шаге при условии, что y_n состояние процесса на начало n-го шага;

F_n (y_ni) - условно оптимальное суммарное значение критерия, соответствующего x_n*:

, где           (10)

,                  (11)

При n = 1 в связи с однозначной зависимостью решения от состояния, таблица имеет вид:

При n = N в связи с тем, что начальное состояние процесса известно, таблица имеет только одну строку.