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

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

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

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

Постановку задачи (ДП) рассмотрим на примере инвестирования, связанного с распределением средств между предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S₀ в конечное S_n. предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных – переменную состояния системы S_k и переменную управления Х_k. все Х_k должны удовлетворять некоторым ограничениям.

Допустим, Х = (х₁,х₂,… х_n) – управление, переводящее систему из состояния S₀ в состояние S_n, а состояние S_k - есть состояние системы на к-ом шаге управления. Тогда последовательность состояний системы можно представить в виде графа:

x₁ x₂ x_k x_k+1 x_n

Рис.1.

Применение управляющего воздействия х_k на каждом шаге переводит систему в новое состояние S¹(S,x_k) и приносит некоторый результат W_k(S,x_k), для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление х^*_k, такое, чтобы результат, который достигается за шаги с к – го по последний n – ный, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана F_k(S) и зависит от номера шага к и состояния системы S.

Задача (ДП) формулируется следующим образом: требуется найти такое управление Х^*,переводящее систему из начального состояния S₀ в конечное состояние S_n, при котором целевая функция принимает наибольшее (наименьшее) значение

F(S_0,X^*)-->extr

Особенности математической модели (ДП) заключаются в следующем:

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

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

_n

F=SF(S_k-1,x_k)-->extr

^k=1

3) выбор управления х_k на каждом шаге зависит только от состояния системы к этому шагу S_k-1 и не влияет на предшествующие шаги (нет обратной связи).

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

S_k=f_k(S_k-1,x_r), k=1,n

5) на каждом шаге управление х_k зависит от конечного числа управляющих переменных, а состояние системы S_k зависит от конечного числа параметров.

6) оптимальное управление представляет собой вектор Х^*, определяемый последовательностью оптимальных пошаговых управлений: Х^* = (х^*₁,х^*₂,… х^*_k,… х^*_n), число которых и определяет количество шагов задачи.

2.2.2. Принцип оптимальности и математическое описание динамического процесса управления

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

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

Условная оптимизация

Определяются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-ом шаге оптимальное управление -- х^*_n определяется функцией Беллмана

F(S)=max{W_n(S,x_n)} x_kÎX

В соответствии с которой максимум выбирается из всех возможных значений х, причем x_kÎX.

Дальнейшие производятся согласно рекуррентному соотношению:

F_n(S)=max{W_n(S,x_n)+F_k+1(S¹(S,x_k))} x_kÎX

Этот максимум (или минимум) определяется по всем возможным для к и S значениям переменной управления Х.

Безусловная оптимизация.

Пользуясь тем, что на первом шаге (к=1) состояние системы известно – это ее начальное состояние S₀, можно найти оптимальный результат за все n шагов и оптимальное управление на первом шаге х₁, после применения этого управления система перейдет в другое состояние S¹(S,x^*₁), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге х^*₂, и так далее до последнего n-го шага.