Пусть рассматривается задача, распадающаяся на т шагов или этапов, например планирование деятельности предприятия на несколько лет, поэтапное планирование инвестиций, управление производственными мощностями в течение длительного срока.
Пусть W – показатель эффективности задачи в целом, а φi – показатели эффективности на отдельных шагах (i= ).
Если W обладает свойством аддитивности, то есть
, (9.1)
то можно найти оптимальное решение задачи методом динамического программирования.
Динамическое программирование – это метод оптимизации многошаговых или многоэтапных процессов, критерий эффективности которых обладает свойством (1). Данные процессы управляемы и от правильного выбора управления зависит величина выигрыша.
В задачах динамического программирования критерий эффективности называется выигрышем.
Переменная хi, от которой зависят выигрыш на i–ом шаге, и следовательно, выигрыш в целом, называется шаговым управлением.
Управление процессом в целом – это последовательность шаговых управлений x=(x1, x2, ... , xm).
Оптимальное управлениех* – это значение управления х, при котором значение W(х*) является максимальным
W*=W(x*)= , (9.2)
где Х – область допустимых управлений.
Оптимальное управление х* определяется последовательностью оптимальных шаговых управлений x*=(x1*, x2*, ... , xm*).
В основе метода динамического программирования лежит принцип оптимальности Беллмана.
Принцип Беллмана: управление на каждом шаге надо выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге.
Свойства задачи динамического программирования:
1) в многошаговых процессах все шаги зависят друг от друга
(данное свойство обеспечивается тем, что оптимизация проводится от конца процесса к началу);
2) при выборе управления на i-ом шаге следует учитывать возможные варианты окончания (i – 1)-го шага
(данное свойство учитывается за счет того, что на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и условная оптимизация проводится для каждого варианта).