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

Очень часто в экономических задачах  приходится принимать решение поэтапно, шаг за шагом, а не дискретно и  разово, как например в задачах  ЛП. В этом случае применяют так  называемое динамическое программирование (ДП).

Метод ДП основан на принципе оптимальности Беллмана и бал впервые опубликован в начале 60-х годов.

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

V₀ – начальная скорость, h₀ – начальная высота.

Самолет должен достичь h_кон и v_кон.

Для простоты будем считать, что: интервалы скорости и высот разбиты на равные части, и самолет может на каждом отдельном разбиении набирать либо скорость, либо высоту.

Считаем известным расход горючего при изменении  скорости «на одну клетку» и изменении  высоты «на одну клетку».

Необходимо  найти такую траекторию движения, что суммарный расход горючего наименьший.

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

Таким образом, целевая функция является аддитивной. Если есть аддитивность, то есть ДП и если нет аддитивности, то нет и ДП. 

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

Теперь  осуществляется прямой ход. Начав движение с начальной точки (v₀, h₀) мы должны двигаться на каждом отрезке по условно оптимальным направлениям, выявляя оптимальную траекторию. Такой путь – единственный.

В ДП условно  оптимальное управление часто выбирается из так называемой «розы направлений».

Пусть W – показатель эффективности всего процесса и пусть j_i – показатель эффективности на i-ом шаге. Аддитивность критерия будет означать W = Sj_i .

Пусть Х_i – переменная, от которой зависит выигрыш на i-ом шаге (управление). В нашей задаче это были «вправо-вверх». При выборе шагового управления необходимо учитывать возможные исходы предыдущего и влияние выбираемого управления на все оставшиеся до конца процесса.

Пусть S – состояние системы (у нас это были 2 координаты: v_i и h_i).

С введенными обозначениями тесно связано  само состояние математической модели. 

Всего можно выделить 7 этапов:

1. Разбиение задачи на шаги (шаг не должен быть слишком крупным, но и не следует мельчить. При уточнении возможно дробление шага.)
2. Выбор переменных, характеризующих состояние s перед каждым шагом. (прибыль, остаток средств и т.п.).
3. Определение множества шаговых управлений x_i и налагаемых на них ограничений.
4. Определение выигрыша j_i (s_i, x_i), который принесет управление x_i при состоянии системы s_i.
5. Определение состояния s’, в которое переходит система из состояния s под действием управления x_i, т.е. s’ = f(S_i, X_i), где f – функция перехода.
6. Составление уравнения, определяющего условный оптимальный выигрыш на последнем шаге для состояния s моделируемого процесса.

(*)  W_m(s) = max{j_m (s_i, x_m)}, x_mÎX.

7. Рекуррентное соотношение Беллмана. Оно определяет условный оптимальный выигрыш для данного состояния s с i-го шага и до конца процесса через уже известный оптимальный выигрыш с (i+1)-го шага и до конца процесса.

(**) W_i(s) = max {j_i (s_i, x_i) + W_i+1(f(s_i, x_i))} 

Задача  о распределении  инвестиций между  m предприятиями с целью обеспечения максимальной суммарной прибыли. 

Инвестор выделяет D средств, которые должны быть распределены между m предприятиями, каждое из которых приносит прибыль j_i (x), где х – количество вкладываемых в него средств.

Нужно определить оптимальное распределение инвестиций дабы получить максимальную суммарную от всех предприятий прибыль W.

Обозначим: W* - оптимальная прибыль, Х* - оптимальное распределение средств. 

Построение математической модели:

1. Число шагов – m. Столько, сколько предприятий.
2. Состояние системы S характеризуется количеством средств s, имеющихся перед данным шагом. s£D.
3. Выбор шагового управления. Управлением на этом шаге будем считать x_i – количество средств, инвестируемых в i-е предприятие.
4. W = Sj_i – функция выигрыша.
5. Функция перехода в новое состояние f_i(s,x) = s – x. Если на i-ом шаге система находится в состоянии s и выбрано управление x, то далее система будет находиться в состоянии s – x, т.е. для дальнейшего инвестирования остается s – x условных единиц.
6. Составление функции управления. Для m-го шага мы имеем W_m(s) = j_m (s), x_m(s) = s.

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

7. Составление рекуррентного соотношения Белмана.

Функциональное  уравнение примет вид:

W_i(s) = max{j_i (x) + W_i+1(s - x)}, xÎs, W_i(s) – выигрыш на i-м шаге.

Пояснения:

Перед i-м шагом у инвестора осталось s условных единиц, тогда эти x_i условных единиц он может вложить в i-е предприятие, при этом получаем доход j_i (x), а остальные s – x единиц в остальные предприятия с (i+1)-го до m-го.

Условный оптимальный  выигрыш - W_i+1(s-x).

Оптимальным будет  такое вложение, когда сумма в  фигурных скобках будет максимальной.