5.5.2. Динамическое программирование как метод решения

Для минимизации L воспользуемся методом динамического программирования. Будем последовательно минимизировать затраты за 1,2 и т.д. интервалов на основе принципа оптимальности Р. Беллмана:

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

Минимальные затраты за последний период

LriZn) - тп [Cn{Sn - Zn) + hn{Sn - Хгг)].

Затраты за два последних периода

L2T{zn-i) - mill {cn-i[Sn-\ - Zn-\)

Sn-l >Zn-l

+ hn-i{Sn-i - Xn-l) + Ьт{Зп-1 - Xn-l)]. Вообще для 2, 3,..., 7i

Lkrin+i-k) = min [cn.i-k{Sn-\-i-k - n+i-k)

-}-hn-\.l-k{Sn + l-k - Xn + l-k) + L(k-l)T{Sn-\-l-k - Xn + l-k)]-

В процессе минимизации затрат для поиска {Sk} необходимо использовать свойства функций {ck} и {hk} . В типичном для практики случае, когда {с} и {hk} -возрастающие функции своих аргументов, равные нулю при нулевом аргументе, оптимальный запас для последнего периода

g ( Хп при Zn < Хп, ~ \zn при Zn > Хп.

Отсюда легко найти LT{zn)

Можно показать, что для любого периода оптимальная стратегия имеет вид

( Sk при Zk < Sk, ~ \ zk при Zk> Sk,

причем функция Ькт{хп+1-к) достигает минимума при Zn--i-k - Sk •

Полученные соотношения позволяют построить простой алгоритм численного решения задачи. Установим диапазоны изменения для Sk и Zk . Очевидно, что Xk < Sk < Y=:k - (запас на каждый период должен быть не меньше спроса в этом периоде, но не больше спроса за все оставшееся время). Из этого требования вытекает и условие для остатков: О < Zk < Yl?=k • Разобьем эти диапазоны на интервалы с некоторым шагом Л и для всех допустимых {zk} рассчитаем оптимальные Sk и Lxizk) Далее, численно минимизируя суммы

Cn-l{Sn-l - Zn-i) -f hn-i{Sn-i - Xn-i) 4- LT(Sn-i - n-l)

no Sn-\ с использованием полученной на предыдущем шаге таблицы т(-п) . получим новую таблицу функции Lorl-n-i) и связанную с ней 5n-i(n-i) , и т.д. Результатом очередного шага явятся, наконец, таблицы Ь(п 1)т(2) и 52(2) • Минимум суммы

- zx) -f - xi) -h L(n i)T(.Si - xx)

даст нам итоговое значение затрат LnT{z\) и укажет оптимальный запас в первом периоде S\ . Теперь, просматривая таблицы {Skiz)] в обратном порядке, легко получить оптимальную последовательность нормативных запасов: аргумент Zk , по которому выбирается Sk для к > 2 , равен Sk-i - Xk-i .

Заметим, что на каждом этапе минимизации необходимо иметь только одну таблицу LkT(zn-i-k) , полученную на предыдущем шаге; ранее найденные {L(k-i)T] более не нужны, а таблицы {5} используются только на заключительном этапе вычислений. Это позволяет легко разместить все требуемые результаты в оперативной памяти ЭВМ.

С общематематических позиций динамическое программирование решает задачу рекурсивно - как набор подзадач для ограничений вида С < С (например, по стоимости запасов) и к < п , причем последняя задача {к = 1) имеет тривиальное решение. Важные особенности метода:

• Функции затрат {Ь{} не обязаны быть дифференцируемыми и могут задаваться таблично.

• Гарантируется получение глобального минимума, причем наличие локальных минимумов не создает никаких трудностей.

• Дополнительные ограничения только облегчают получение решения, поскольку сужают пространство поиска.

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

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

• Используя часть полученных таблиц, можно решить задачу с меньшим числом периодов.

• Метод может быть обобщен на многоресурсные задачи (в частности, с предварительным распределением затрат по уровням).

Динамическое программирование применяется и в других задачах многоэтапного распределения ресурсов (например, между отдельными номенклатурами, складами и т.п.). Абстрактный термин «ресурс» может относиться к деньгам, весу, объему. Заданный ресурс оптимальным образом распределяется между указанным числом «активностей» (например, общий запас - по иерархическим уровням системы). Предполагается, что эффекты всех назначений могут быть измерены некоторой общей мерой, а общий эффект измеряется их суммой (произведением). Если фиксирована общая сумма, то задача одномерная, если фиксированы суммы по уровням системы - многомерная. Если мерой эффективности служит число случаев дефицита на нижнем уровне или ожидаемые задержки поставок, то это аддитивные монотонно убывающие функции уровней запаса. Эффективность метода зависит от порядка, в котором рассматриваются «активности».

Схема динамического программирования может быть легко переформулирована для задач максимизации.

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