Wagner-Whitin (Forward) Dynamic Programming Inventory Model

Number of periods N=

Current period^

Period

c(1to4)-

Optimum Solution

K(1 to 4) -

Summary

h{1to4)-

X

f

z

X

f

z

D(1 to 4) -

Current

period 1

Are xl values co<'r ^'

" ^

I ИИ

| optimum

220, 61

1 Period 0

z1-

Period 1

^298~ 87"

1f0

C1(z1)=

f1 I z1

116"

x2=

22(Г"

183u

x2=

M11111

298 Г 87

x2=

" 116

111111'

(111111

568 i 177

x2=

" 183

1111111_,

769 1 244

-

—

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

УПРАЖНЕНИЯ 11.3.4

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

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

Глава 11. Детерминированные модели управления запасами

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

3. Определите оптимальную стратегию управления запасами в следующей 5-этапной задаче. Стоимость единицы продукции равна 10 долл. для любого периода. Стоимость хранения единицы продукции на протяжении периода равна 1 долл.

Этап /'	Спрос, D, (единицы)	Затраты на оформление заказа, К, (долл.)
Определите оптимальную стратегию управления запасами в следующей 6-этап-
ной задаче. Стоимость единицы продукции равна 2 долл. для любого периода.
Этап /'	О, (единицы)	К, (долл.)	hi (долл.)

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

Эвристический метод определяет последующие этапы, потребности которых можно удовлетворить за счет размещения заказа на протяжении текущего периода. Задача планирования заключается в минимизации затрат, которые связаны с раз­мещением заказа и хранением продукции и отнесены к одному периоду.

Предположим, на этапе / размещается заказ для периодов i, i + t (i<t).

Пусть TC(i, t) — соответствующая стоимость размещения заказов и хранения

11.3. Динамические задачи экономичного размера заказа

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

{К,, t = i.

^rC(''^f) к, + h,D_M +(/*,. + h_M)D_M +... + (/*,. + Л_м1 +... + V,) Д, г > /. Обозначим далее через TCU(i, t) соответствующие затраты за период, т.е.

тс (и)

TCU{i,t) =

/-/4-1

Таким образом, для заданного текущего этапа / эвристический метод определяет t, которое минимизирует функцию TCU(i, t).

Функция TC(i, t) определяется с помощью рекуррентных соотношений.

TC(i, i) = К,,

TC(i, t) = TC{i, * - 1) + (Л, + Vi + ••• + *,-i)A. t=i + l,i + 2, n. Алгоритм эвристического метода состоит из следующих шагов.

Шаг О. Пусть i = l.

Шаг 1. Определяем локальный минимум t функции TCU(i, t), который должен удовлетворять неравенствам

TCU(i,t'-l)>TCU(i,t

TCU{i,t+l)>TCU(i,t').

Тогда в соответствии с эвристическим подходом на этапе i разме­щается заказ объемом (Д 4- Д_м + ... + Д.) для этапов /4-1, t .

Шаг 2. Пусть i = t+ l. Если I > п, вычисления заканчиваются; рассмот­рен весь плановый период. Иначе следует перейти к шагу 1.

Пример 11.3.4

Найдем оптимальную стратегию управления запасами в следующей 6-этапной за­даче. Стоимость единицы продукции равна 2 долл. для любого периода.

Этап i	D, (единицы)	К, (долл.)	h, (долл.)

Итерация 1 (i — 1, Jf, = 20 долл.). Функция ТС(1, t) определяется рекуррентно по t. Например, при заданном значении 742(1, 1) = 20 долл., 742(1, 2) = 742(1, 1) 4- h,D₂ = = 20 4- 1 х 15 = 35 долл.

Глава 11. Детерминированные модели управления запасами

Этап f	D,		ТСЦ1, f)
			20/1 = 20,00
		20 + 1 х 15 = 35	35/2 = 17,50
		35+ (1 +1)х7 = 49	49/3 = 16,33
		49+ (1 +1 +1)х20 = 109	109/4 = 27,25

Локальный минимум достигается при t* = 3, что означает необходимость размеще­ния на первом этапе заказа объемом 10 + 15 + 7 = 32 единицы для этапов 1, 2, 3. Полагаем i = t +1 = 3 + 1=4.

Итерация 2 (<	= 4, Kt = 18 долл.)
Этап t	D,	Щ4, 0	TCU(4, f)
			18/1 = 18,00
		18 + 3x13 = 57	52/2 = 28,50

Значение £* = 4 означает, что на четвертом этапе необходимо разместить заказ объ­емом 20 единиц для этапа 4. Полагаем i = 4 + 1 = 5.

Итерация 3 (i = 5, К_ь = 5 долл.)

Этап f	D,	Щ5, 0	TCU(5, 0
			5/1 =5
		5 + 1 х 25 = 30	30/2 = 15

Так как t = 5, на пятом этапе заказывается 13 единиц для этапа 5. Полагаем далее г = 5 + 1 = 6. Так как i = 6, то это последний этап планирования. Мы должны зака­зать на шестом этапе 25 единиц для этого же этапа.

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

 

Этап	Эвристический метод	Метод динамического программирования
Закуплено единиц	Стоимость (долл.)	Закуплено единиц	Стоимость (долл.)
Всего

Стоимость производственного плана, предложенного эвристическим методом, примерно на 32 % превышает стоимость аналогичного плана, полученного метода­ми динамического программирования (122 долл. против 90). "Неадекватность" результата эвристического метода может быть обусловлена данными, которые ис­

11.3. Динамические задачи экономичного размера заказа

пользовались в задаче. В частности, причиной этого может быть чрезвычайная не­равномерность стоимостей размещения заказов для этапов 5 и 6. Тем не менее этот пример показывает, что эвристический метод не обладает способностью "смотреть вперед" в поисках лучшего производственного плана. Например, размещение на пятом этапе заказов для этапов 5 и 6 (вместо размещения их в отдельности) может сэкономить 25 долл., что уменьшит суммарные затраты производственного плана, предложенного эвристическим методом, до 97 долл.

Реализация в Excel эвристического подхода Сильвера-Мила. Шаблон Excel chllSilverMealHeuristic.xls разработан для получения решения на основе эвристи­ческого подхода Сильвера-Мила. Процесс решения задачи начинается со ввода всех необходимых данных, включая значения величин К, й и D для каждого периода и значение N — количество периодов. (Ячейки рабочего листа для входных данных выделены цветом.) Затем пользователь должен инициировать вычисления для каждой итерации вручную.

На рис. 11.12 показано применение этого шаблона для решения задачи из приме­ра 11.3.4. Первая итерация инициируется путем введения значения 1 в ячейку F11, это означает что на первой итерации выполняются вычисления для первого периода. Excel выведет столько строк расчетных значений, сколько указано в ячейке G3 как общее число периодов (в данном примере это число равно 6). Номера периодов вы­водятся в диапазоне G11:G16. Далее проверяем вычисленные значения TCU в столбце L (этот столбец выделен зеленым цветом) и находим минимальное значе­ние. В данном случае локальному минимуму соответствует t = 3 (третий период) со значением TCU = 16,33. Отсюда следует, что следующая итерация должна начаться

О Р О R ^