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

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

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

Пусть W – показатель эффективности задачи в целом, а φ_i – показатели эффективности на отдельных шагах (i= ).

Если W обладает свойством аддитивности, то есть

, (9.1)

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

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

В задачах динамического программирования критерий эффективности называется выигрышем.

Переменная х_i, от которой зависят выигрыш на i–ом шаге, и следовательно, выигрыш в целом, называется шаговым управлением.

Управление процессом в целом – это последовательность шаговых управлений x=(x₁, x₂, ... , x_m).

Оптимальное управление х* – это значение управления х, при котором значение W(х*) является максимальным

W*=W(x*)= , (9.2)

где Х – область допустимых управлений.

Оптимальное управление х* определяется последовательностью оптимальных шаговых управлений x*=(x₁*, x₂*, ... , x_m*).

В основе метода динамического программирования лежит принцип оптимальности Беллмана.

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

Свойства задачи динамического программирования:

1) в многошаговых процессах все шаги зависят друг от друга

(данное свойство обеспечивается тем, что оптимизация проводится от конца процесса к началу);

2) при выборе управления на i-ом шаге следует учитывать возможные варианты окончания (i – 1)-го шага

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