Промежуточные вычислении 18 страница

Этап 2. Д, = 2, 0 < я, < 4.

_ C2(z2) + h2x3 + f 1 (хЗ + D2 - z2) _Оптимальное

Z2 = 0 1 2 3 4 5 6 решение

хЗ h2x3 C2(z2) = 0 17 27 37 57 77 97 f2(x3) _z"

		0 + 55 = 55	17 + 34 = 51	27 + 23 = 50
		3 + 76 = 79	20 + 55 = 75	30 + 34 = 64	40 + 23 = 63
		6 + 97 = 103	23 + 76 = 99	33 + 55 = 88	43 + 34 = 77	63 + 23 = 86
		9 + 118 = 127	26 + 97 = 123	36 + 76 = 112	46 + 55 = 101	66 + 34 = 100	86 + 23 = 109
		12 + 139 = 151	29 + 118 = 147	39 + 97 = 136	49 + 76 = 125	69 + 55 = 124	89 + 34= 109 + 23 123 =132

ЭтапЗ. D, = 4, я₄ = 0.

	Сз(гз) + л3х4 + f2(Xi + D3-Z3)		Оптимальное
	гз = 0 1 2 3		решение
*4 л3л4	Сз(гз) = 0 16 26 36		z\
0 0	0 + 123= 123 16 + 100 = 116 26 + 77 = 103 36 + 63 = 99	56 + 50 = 106	99 3

Оптимальное решение определяется следующим образом:

(я₄ = 0) -> [2₃ = 3] -> (я₄ = 0 + 4 - 3 = 1) -> [г₂ = 3] -> (я₂ = 1 + 2 - 3 = 0) -> [z, = 3]. Отсюда получаем решение^-. ^ =2, г_г = Ъ тл ц=Ъ, при этом общие затраты состав­ляют 99 долл.

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

Решение задачи динамического программирования с общей функцией стоимо­сти в Excel. Шаблон Excel chllDynamicInventory.xls создан для решения общих за­дач управления запасами с произвольной функцией стоимости. Этот шаблон похож на шаблон chlOKanpsack.xls, описанный в разделе 10.3.1. В частности, шаблон chllDynamicInventory.xls выполняет вычисления только для одного периода и для вычислений следующего периода пользователь должен произвести некоторые под­готовительные операции.

На рис. 11.10 показано применение описываемого шаблона для решения задачи примера 11.3.2. Исходные данные надо вводить для каждого периода в отдельности (после вычислений очередного периода). Эти данные следует вводить в выделенные цветом ячейки. Коэффициенты функции затрат с,(г,) вводятся в строке 3: G3 = 10, НЗ = 20, 13 = 3. Это означает, что удельные затраты для первых трех единиц про­дукции составляют 10 долл., а для последующих — 20 долл. Отметим, что из зна­чения D, необходимо вычесть значение начального запаса (= 3 - х₁ = 3 - 1 =2), эта разность вводится в ячейку С5. Также необходимо вручную ввести возможные зна­чения переменной 2,. Шаблон автоматически проверит правильность этих значений и выведет соответствующие сообщения в строке 6.

После ввода всех данных, необходимых для вычислений первого периода, рабочий лист пересчитывается автоматически, показывая оптимальные значения f, и 2, в столб­цах S и Т. Далее следует полученное решение (x_v f_t, z) переписать в область итоговых оптимальных решений в столбцах U:Z. Для этого, скопировав нужные данные и выде­лив диапазон ячеек, куда будут перенесены эти данные, надо выполнить команду Правка^Специальная вставка^Значения — по этой команде будут скопированы только значения (без формул), по которым они вычислены. (Более подробно эта операция пред­ставлена в разделе 10.3.1 при описании работы с шаблоном chlOKanpsack.xls.)

Далее для выполнения вычислений следующего периода надо скопировать зна­чения f_t в столбец А, как показано на рис. 11.10, и ввести в ячейку Н2 номер оче­редного периода.

УПРАЖНЕНИЯ 11.3.3

1. Вернитесь к задаче из примера 11.3.2.

a) Имеет ли смысл рассматривать значение x_t > 0?

b) Для каждого из следующих случаев определите допустимые интервалы значений для 2,, г_г, г_ъ, х,, х_г и х₃. (Полезно представить каждый случай графически, как на рис. 11.9.)

i) xl = 4, остальные исходные данные не меняются,

ii) xl = 0, Dl = 5, D2 = 4 и D3 = 5.

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

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

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

Период 1

в

C D

E

F

G

H

I

J

К

IS'T

U V W X

beiieral (Forward) D. iismic P

oqrjmming Inventory Model

Number of periods, N

Current period-

Optimum solution

K1-

3 | h1-

dill)-

Summary

Period

1 2

X f z

X

f z

£

D(1 to 3)=

2 I 2

Период 1

"б

An zl values correct?

ш\Щ

Optimum

□ 23 2

Period 0

z1-

Б

Penodl

1 34 3

fO

C1(z1)=

fl z1

2 55 4

x2= 0

23 2

3 76 5

x2= 1

34 3

4 97 Б

x2= 2

55 4

5 '118 7

J2

x2= 3

76 5

6 139 8

x2= 4

97 Б

x2= 5

118 7

x2= E

139 8

Период 2

в

C

D

E

F

G

H

1 к

1 % T

IJ I V W

X

' 1

General (Forward) Dynamic Programming Inventory Model

Number of periods, N=

Current period^

Optimum solution

J_K!z

M=

^1(z1)

Summarv

Period I 1

X f z

X

f z

I D(1 to 3)=

Пеои! ц 1

Период 2

Б

,Are zl vafuet romcff

yei

ies

e

\es

Optimum

0 23 2

50 2

1 Period 1

z2-

e

Period2

1 34 3

63 3

~8

I 11

C2(z2)=

f2 z2

2 55 4

77 3

x3=

□

50 2

3 76 5

100 4

x3=

Б4

63 3

4 97 Б

123 5

x3=

77 3

5 118 7

x3=

100 4

Б 139 8

x3=

123 5

15

Период 3

в

С D

F

G '

H

! is т

U ' W

Ix

General (Forward) Dynamic Programming Inventory Model

Number of periods, N

Current period

Optimum solution

K1-

Б | Ы

tf(zlH 10

Summary

Period

1 2

X f z

X

f z

I

D(1 to 3)-

2 I?

4 | I_

Период 1

Период 2

Б

Are zl value* correct?

It

>•(

m«

>es

Optimum

0 23 2

50 2

Period 2

z3=

' Penod3

1 34 3

63 3

f2

C3(z3)=

f3 z3

2 55 4

77 3

j

x4= 0

11Б

99 3

3 76 5

100 4

i

БЗ

4 97 Б

123 5

5 118 7

Период 3

Ц

6 139 8

99 3

1 i

if

Puc. 11.10. Решение e Excel задачи примера 11.3.2

Затраты на приобретение первых шести единиц продукции составляют 1 долл. за каждую единицу и 2 долл. за каждую дополнительную единицу.

Проверьте вычисления, выполненные вручную, с помощью шаблона ch 11 Dy namicln ven tory. xls.

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

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

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

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

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

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

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

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

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

Пример 11.3.3

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

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

1 76 98

2 26 114

3 90 185

4 67 70

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

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

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

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

Этап 1.D, = 61.

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

	Z, =61	87 177				решение
х2 л,х2	C,(z,) = 220	272 452				<
0 0						220 61
26 26						298 87
116 116						568 177
183 183						769 244
Заказ на этапе 1 для этапов		1,2 1,2,3		1, 2, 3, 4
Этап 2. D2 = 26.
		Сг{2г) + Л2Х3 + Шз + Ог -	■а)		Оптимальное
	Z2 = 0					решение
Хз Л2Х3	Сг(2г) = 0					Ш z\
0 0	0 + 298 = 298	166 + 220 = 386				298 0
90 90	90 + 568 = 658	436 + 220	= 656		656 116
157 157	157 + 769 = 926			637 + 220 =	= 857 857 183
Заказ на этапе 2 для этапов	—		2,3		2, 3, 4
Этап 3. £»3 = 90.
	С3(2з) + Л3Х4 + fe(x4 + Оз				Оптимальное
	2з = 0					решение
Хл Л3Х4	Сз(2з) = 0					Н(хл) г;
0 0	0 + 656 = 656	365 + 298 = 663				656 0
67 67	67 + 857 = 924		566 + 298 = 864		864 157
Заказ на этапе 3 для этапов	—			3, 4

11.3. Динамические задачи экономичного размера заказа 499 Этап 4. D_t = 67.

	C4(z4) + л4х5 + /з(х5 + DA - 24)	Оптимальное
	z4 = 0		решение
Xs л4х5	C4(z4) = 0		*4(Х5) z\
0 0	0 + 864 = 864	204 + 656 = 860	860 67
Заказ на этапе 4 для этапов	—

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

(х₆ = 0) [z₄ = 67] (х₄ = О) [z₈ = О] -* (х₈ = 90) -»[z₂ = 116] (х₂ = 0) [z, = 61]. Отсюда получаем решение: z\ =61, z\ = 116, zj = 0 и =67 при суммарных за­тратах 860 долл.

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