3. Пусть стоимость хранения запаса определяется средним его объемом на протяжении периода. Получите соответствующее рекуррентное уравнение для алгоритма прямой прогонки.

4. Получите рекуррентное уравнение для алгоритма обратной прогонки и с его помощью решите задачу из примера 11.3.2.

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

Алгоритм динамического программирования для задачи с постоянными или невозрастающими предельными затратами. Рассмотренную выше модель динамического программирования можно использовать при любых функциях затрат. Важным частным случаем этой модели является такая модель, в которой на этапе i как стоимость закупки единицы продукции, так и затраты на ее хранение - невозрастающие (вогнутые) функции объема закупаемой и хранимой продукции соответственно. Такая же ситуация возникает, когда функция стоимости, отнесенная к единице продукции, является постоянной или когда предоставляется оптовая скидка.

При указанных выше условиях можно доказать следующее.5

1. При заданном начальном нулевом уровне запаса (д:, = 0) для любого этапа I оптимальной стратегией является удовлетворение спроса за счет либо новой закупленной продукции, либо запаса, но не обоих источников, т.е. г1х1 = 0. (При положительном начальном уровне запаса (хх > 0) этот объем может быть списан из спроса последующих этапов, пока он не исчерпается.)

2. Оптимальный объем заказа zt на любом этапе i должен либо равняться нулю, либо в точности соответствовать спросу одного или более последующих этапов.

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

Пример 11.3.3

Рассмотрим четырехэтапную модель управления запасами при следующих исходных данных.

Период / Спрос, D, (единицы) Затраты на оформление заказа, К, (долл.)

1 76 98

2 26 114

3 90 185

4 67 70

5 Подробное доказательство изложено в работе Wagner Н. and Whitin Т. Dynamic Version of the Economic Lot Size Model , Management Science, Vol. 5, 1958, pp. 89-96. Доказательство получено при ограничивающем предположении, что затраты на единицу продукции постоянны и идентичны на всех этапах. Этот результат в дальнейшем был обобщен А. Вейноттом (A. Veinott) из Стэнфордского университета для вогнутых функций затрат, имеющих место на каждом этапе.

Начальный уровень запаса равен х, = 15 единиц. Затраты на закупку единицы продукции и ее хранение в течение одного периода для всех этапов одинаковы и составляют 2 и 1 долл. соответственно. (Затраты на закупку и хранение единицы продукции приняты одинаковыми для всех этапов исключительно в целях упрощения.)

Решение определяется обычным алгоритмом прямой прогонки, за исключением того, что величины хм и 2, допускают общие платежи, как это следует из свойств функции затрат. Так как начальный запас хг = 15, спрос на первом этапе уменьшается на эту величину и составляет 76 - 15 = 61 единицу.

Этап 1.D, = 61.

Ci(zi) + Л1Х2 Оптимальное

Оптимальная стратегия на основе приведенных таблиц определяется следующим образом.

(х6 = 0) [z4 = 67] (х4 = О) [z8 = О] -* (х8 = 90) - [z2 = 116] (х2 = 0) - [z, = 61]. Отсюда получаем решение: z\ =61, zj = 116, zj = 0 и zj =67 при суммарных затратах 860 долл.

Решение в Excel задачи управления запасами с постоянными или невозрас-тающими предельными затратами. Шаблон Excel chllWagnerWhitin.xls, предназначенный для решения этих задач, подобен шаблону chllDynamicInventory.xls, описанному выше. Различие между ними заключается только в том, что в шаблоне chllWagnerWhitin.xls используются общие платежи для состояний х и альтернативных значений г. Для упрощения расчетов оптовые скидки не допускаются. На рис. 11.11 показаны вычисления первого периода для задачи из примера 11.3.3. Шаблон ограничен максимум 10 периодами.

Wagner-Whitin (Forward) Dynamic Programming Inventory Model

Рис. 11.11. Вычисления в Excel первого периода для задачи из примера 11.3.3

УПРАЖНЕНИЯ 11.3.4

1. С помощью шаблона chllWagnerWhitin.xls решите задачу из примера 11.3.3, предполагая, что начальный запас - 80 единиц.

2. Решите следующую 10-этапную детерминированную задачу управления запасами, предполагая, что исходный запас - 50 единиц.

Этап 4. Dt = 67.