Полученные соотношения позволяют построить простой алгоритм численного решения задачи. Установим диапазоны изменения для 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) имеет тривиальное решение. Важные особенности метода:

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

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

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

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

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

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

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

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

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

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

5.6. Случайный спрос,

периодическая стратегия

в § 4.3 [56] приведены результаты классических исследований по типам оптимальных периодических стратегий при вероятностном спросе и показано, что при весьма общих допущениях (в частности, для линейных функций затрат) оптимальна стратегия с критическим уровнем. Рассмотрим типичные задачи этого класса.

5.6.1. Непрерывный спрос

Однопериодная задача со случайным спросом и мгновенной поставкой часто называется задачей газетчика (спрашивается, сколько газет должен взять распространитель, чтобы минимизировать убытки от возврата непроданных экземпляров и упущенной выгоды при неудовлетворенном спросе). Столь же популярным ее приложением является задача о новогодних елках. В [89, с. 252] она иллюстрируется также на продаже радиоприемников (стоимость каждого 40 долл.; неудовлетворенная заявка обходится магазину в 20 долл. из-за потери предпочтения плюс потеря 25 долл. валового дохода; стоимость подачи заказа оценивается в 3 долл.). Наконец, приведем из того же источника хлебную задачу: в универсаме необходимо определить, сколько хлеба нужно заказать на день. Спрос за день можно считать случайной величиной, подчиненной нормальному закону со средним 300 и среднеквадратиче-ским отклонением 50. Один батон продается за 25 центов, себестоимость для магазина 19 центов, весь непроданный хлеб сбывается на следующий день по цене 15 центов за штуку (оптимально S = 313, доход L* = 16.07; при заказе по средней потребности S = 300, L* = 16.01). Заметим, что довольно заметное отклонение решения от оптимума очень слабо повлияло на ожидаемые затраты.

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