Практические рекомендации при постановке задач динамического программирования

Прежде чем перейти к описанию блок-схемы алгоритма метода динамического программирования, сделаем ряд замечаний:

1. Отметим основные свойства задач, к которым возможно применить метод линейного программирования:

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

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

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

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

Алгоритм метода динамического программирования:

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

2. Разбить операцию на шаги.

3. Определить набор шаговых управлений u_i для каждого шага и налагаемые на них ограничения.

4. Определить, какой выигрыш приносит на i шаге управление u_i, если перед этим система была в состоянии s, т.е. записать функцию выигрыша:

W_i = f_i(s, u_i). (11.4)

5. Определить, как изменяется состояние s системы S под влиянием управления u_{i, если} на i шаге оно переходит в новое состояние:

s’ = j_i(s, u_i). (11.5)

6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш W_i(s) (начиная с i шага и до конца) через уже известную функцию W_i+1(s):

W_i(s) = max {f_i(s,u_i) + W_i+1(j_i(s, u_i))}. (11.6)

7. Произвести условную оптимизацию последнего m шага, задаваясь гаммой состояний s, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш

W_m(s) = max {f_m(s,u_i)} (11.7)

и находя условное оптимальное управление u_m(s), для которого этот максимум достигается.

8. Произвести условную оптимизацию (m-1) шага по (11.6), полагая в ней i=(m-1), (m-2),... и для каждого из этих шагов указать условное оптимальное управление u_i(s), при котором максимум достигается. На первом шаге варьировать состояние системы не нужно: W^* = W₁(s_o).

9. Произвести безусловную оптимизацию управления, считывая соответствующие рекомендации на каждом шаге: взять найденное оптимальное управление на первом шаге u₁^* = u₁(s_o); изменить состояние системы по (11.6); для вновь найденного состояния найти оптимальное управление на втором шаге u₂^* и т.д. до конца.