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

Постановку задачи динамического программирования рас­смотрим на примере инвестирования, связанного с распределе­нием средств между предприятиями. В результате управления инвестициями система последовательно переводится из началь­ного состояния S0 в конечное Sn. Предположим, что управление можно разбить на П Шагов и решение принимается последователь­но на каждом шаге, а управление представляет собой совокуп­ность П Пошаговых управлений. На каждом шаге необходимо определить два типа переменных - переменную состояния систе­мы SK и переменную управления Хk. Переменная SK определяет, в каких состояниях может оказаться система на рассматриваемом K-м шаге. В зависимости от состояния S на этом шаге можно при­менить некоторые управления, которые характеризуются переменной ХK Которые удовлетворяют определенным ограничениям и называются допустимыми.

Допустим,  - управление, переводящее систему из состояния S0 в состояние Sn , а Sn  — есть состояние сис­темы на K-м шаге управления. Тогда последовательность состоя­ний системы можно представить в виде графа, представленного на рис. 41.

Применение управляющего воздействия Хk  На каждом шаге переводит систему в новое состояние S1(S, Xk) И приносит некото­рый результат Wk(S, Xk). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оп­тимальное управление Xk*, такое, чтобы результат, который дос­тигается за шаги с  K-го по последний N-й, оказался бы оптималь­ным. Числовая характеристика этого результата называется фун­кцией Беллмана Fk(S) и зависит от номера шага K И состояния системы S.

Задача динамического программирования формулируется следующим образом: Требуется определить такое управление , переводящее систему из начального состояния S0 в конечное со­стояние Sn, при котором целевая функция принимает наиболь­шее (наименьшее) значение .

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

1) задача оптимизации формулируется как конечный многоша­говый процесс управления;

2) целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага:

3) выбор управления ХK на каждом шаге зависит только от со­стояния системы K этому шагу Sk-1 и не влияет на предшеству­ющие шаги (нет обратной связи);

4) состояние системы Sk после каждого шага управления зави­сит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Хk (отсутствие последей­ствия) и может быть записано в виде уравнения состоя­ния:

;

5) на каждом шаге управление ХK зависит от конечного числа уп­равляющих переменных, а состояние системы зависит Sk — от конечного числа параметров;

6) оптимальное управление представляет собой вектор , оп­ределяемый последовательностью оптимальных пошаговых управлений: Число которых и опреде­ляет количество шагов задачи.

< Предыдущая		Следующая >