15. Модель з витратами на оформлення замовлення

У розглядуваній моделі передбачається, що дефіцит не допускається і витрати на оформлення замовлення враховуються кожного разу, коли починається виробництво нової партії продукції. Тут будуть розглянуті два методи розв’язання цієї задачі: точний метод динамічного програмування й евристичний.

Дана задача управління запасами схематично представлена на рис. 5.7. На цьому рисунку використані позначення наступних величин, визначених для кожного етапу i, i=1,2,...,n.

– кількість замовленої продукції (обсяг замовлення),

– потреба в продукції (попит),

– обсяг запасу на початок етапу i.

Рис. 5.7

Вартісні елементи в задачі, що розглядається визначаються так:

– витрати на оформлення замовлення,

– витрати на збереження одиниці продукції, що переходить з етапу i в етап i+1.

Відповідна функція виробничих витрат для етапу i задається формулою

де – функція граничних виробничих витрат при заданому значенні .

Алгоритм динамічного програмування із загальною функцією вартості. Оскільки дефіцит не допускається, задача управління запасами зводиться до знаходження значень , що мінімізують сумарні витрати, які пов'язані з розміщенням замовлень, закупівлею і збереженням продукції протягом n етапів. Витрати на збереження на i-му етапі для простоти вважаються пропорційними величині , яка представляє собою обсяг запасу, що переходить з етапу i в етап i+1.

Для побудови моделі динамічного програмування можна скористатися рекурентними співвідношеннями процедури прямої або зворотної прогонки. Ми скористаємося рекурентними співвідношеннями процедури прямої прогонки, оскільки вони більш ефективні при аналізі важливого часткового випадку розглянутої задачі, пов'язаного з незростаючими граничними витратами.

Для рекурентного рівняння процедури прямої прогонки стан на етапі (періоді) i визначається як обсяг запасу на кінець етапу, де, як випливає з рис. 5.7, .

Ця нерівність означає, що в граничному випадку запас може задовольнити попит на всіх наступних етапах.

Нехай – мінімальні загальні витрати на етапах 1,2,...,i при заданій величині запасу на кінець етапу i. Тоді рекурентне рівняння алгоритму прямої прогонки буде записано таким чином.

,

.

Приклад 5.4-2

Потрібно знайти оптимальну стратегію в трьохетапній системі управління запасами, що формулюється нижче. Початковий запас дорівнює одиниці продукції. Передбачається, що граничні витрати на придбання продукції складають 10 доларів за кожну одиницю для перших трьох одиниць і 20 доларів – за кожну додаткову одиницю.

Період i	Попит, (одиниці)	Витрати на оформлення замовлення, ($)	Витрати на збереження, ($)
1	3	3	1
2	2	7	3
3	4	6	2

Функція виробничих витрат для періоду i дорівнює для , де

Етап 1. .

									Оптимальний розв’язок
			3	4	5	6	7	8
			33	53	73	93	113	133
0	0	23							23	2
1	1		34						34	3
2	2			55					55	4
3	3				76				76	5
4	4					97			97	6
5	5						118		118	7
6	6							139	139	8

Оскільки , мінімальне значення дорівнює .

Етап 2. .

									Оптимальний розв’язок
			1	2	3	4	5	6
			17	27	37	57	77	97
0	0	0+55=55	17+34=51	27+23=50					50	2
1	3	3+76=79	20+55=75	30+34=64	40+23=63				63	3
2	6	6+97=103	23+76=99	33+55=88	43+34=77	63+23=86			77	3
3	9	9+118=127	26+97=123	36+76=112	46+55=101	66+34=100	86+23=109		100	4
4	12	12+139=151	29+118=147	39+97=136	49+76=125	69+55=124	89+34=123	109+23=132	123	5

Етап 3. .

							Оптимальний розв’язок
			1	2	3	4
			16	26	36	56
0	0	0+123=123	16+100=116	26+77=103	36+63=99	56+50=106	99	3

Оптимальний розв’язок визначається наступними значеннями шуканих змінних: , і . При цьому загальні витрати складають 99 доларів.

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

При вказаних вище умовах можна довести наступне.

1. При заданому початковому нульовому рівні запасу ( ) для любого етапу i оптимальною стратегією є задоволення попиту за рахунок або нової закупленої продукції, або запасу, але не з обох джерел, тобто . (При додатному початковому рівні запасу ( ) цей об’єм може бути списаний з попиту наступних етапів, поки він не вичерпається.)

2. Оптимальний об’єм замовлення на будь-якому етапі i повинен або дорівнювати нулю, або точно відповідати попиту одного чи більшої кількості наступних етапів.

Використання вказаних двох властивостей з рекурентним рівнянням для алгоритму прямої прогонки динамічного програмування дозволяє спростити схему обчислень.

Пример 5.4–3

Розглянемо чотирьохетапну модель управління запасами при наступних вихідних даних.

Період i	Попит, (одиниці)	Затрати на оформлення замовлення, ($)
1	76	98
2	26	114
3	90	185
4	67	70

Початковий рівень запасу дорівнює одиниць. Затрати на закупівлю одиниці продукції і її зберігання протягом одного періоду для всіх етапів однакові і складають 2 долара і 1 долар відповідно. (Затрати на закупівлю і зберігання одиниці продукції прийняті однаковими для всіх етапів виключно з метою спрощення.)

Розв’язок визначається звичайним алгоритмом прямої прогонки, за виключенням того, що величини і допускають "загальні" платежі, як це випливає із властивостей функції затрат. Оскільки початковий запас , попит на першому етапі зменшується на цю величину і складає 76–15=61 одиницю.

Етап 1. .

						Оптимальний розв’язок
			87	177	244
			272	452	586
0 26 116 183	0 26 116 183	220 –– –– ––	–– 298 –– ––	–– –– 568 ––	–– –– –– 769	220 298 568 769	61 87 177 244
Замовлення на етапі 1 для етапів		1	1,2	1,2,3	1,2,3,4

Етап 2. .

						Оптимальний розв’язок
			26	116	183
			166	346	480
0	0	0+298=298	166+220386	––	––	298	0
90	90	90+568=658	––	436+220=656	––	656	116
157	157	157+769=926	––	––	637+220=857	857	183
Замовлення на етапі 2 для етапів		––	2	2,3	2,3,4

Етап 3. .

					Оптимальний розв’язок
			90	157
			365	499
0	0	0+656=656	365+298=663	––	656	0
67	67	67+857=924	––	566+298=864	864	157
Замовлення на етапі 3 для етапів		––	3	3,4

Етап 4. .

				Оптимальний розв’язок
			67
			204
0	0	0+864=864	204+656=860	860	67
Замовлення на етапі 4 для етапів		––	4

Таким чином, оптимальна стратегія задається наступними значеннями: , , і при сумарних затратах 860 доларів.

Частковим випадком описаної моделі с незростаючою (опуклою) функцією затрат є модель, де виробничі затрати на етапі i визначаються лінійною функцією

,

при . При цих умовах алгоритм прямої прогонки можна модифікувати таким чином, щоб забезпечувати подальше скорочення об’єму обчислень.

Модифікований алгоритм пов’язує Етап i с відповідним періодом планування, коли замовлення на всіх попередніх етапах робляться для наступних, включаючи поточний Етап i. Математично це виражається наступнім чином:

де – мінімальні сумарні затрати на етапах від 1-го до i-го включно, i=1,2,...,n, – сумарні затрати на розміщення замовлення, плюс затрати на етапі k на закупівлю продукції в об’ємі для етапів від k-го до i-гo, .

В модифікованому алгоритмі стан системи не визначається, так як він в точності відповідає числу попередніх етапів i.

При використанні модифікованого алгоритму об’єм обчислень можна додатково скоротити на основі наступної теореми.

Теорема про горизонт планування. Якщо на етапі мінімум затрат досягається таким чином, що попит на етапі задовольняється за рахунок розміщення замовлення на попередньому етапі , то для всіх наступних етапів достатньо визначити оптимальну стратегію управління запасами, що ґрунтується на розміщенні замовлень тільки на етапах . Зокрема, якщо оптимальна стратегія вимагає розміщення замовлення на етапі для задоволення попиту цього ж етапу (тобто ), то для будь-якого наступного етапу завжди оптимально розміщувати замовлення на етапі , не враховуючи попит в майбутньому. В цьому випадку – початок горизонту планування.

Приклад 5.4-4

Розглянемо задачу визначення оптимальної стратегії в шестиетапній моделі управління запасами з наступними даними.

Період i	Попит, (одиниці)	Затрати на оформлення замовлення, ($)	Затрати на зберігання, ($)
1	10	20	1
2	15	17	1
3	7	10	1
4	20	18	3
5	13	5	1
6	25	50	1

Закупівельна ціна одиниці продукції дорівнює 2 долара на всіх етапах.

Результати обчислень для цього прикладу наведені в табл. 5.2. Вони виконуються порядково, починаючи з рядка 1. Кожен стовпець представляє альтернативний розв’язок, що визначає етап k, на якому задовольняється попит для етапів k, k+1,..., та i. Кожен рядок представляє граничний етап, до якого задовольняється попит. Таким чином, при кожному i оптимальне значення отримується шляхом аналізу всіх допустимих альтернативних розв’язків k (≤i) і наступного вибору альтернативи, що забезпечує мінімальні сумарні затрати. Так, наприклад, при i=3 існує три альтернативи: замовляти на етапі 1 для етапів 1, 2 і 3; на етапі 2 – для етапів 2 і 3; на етапі 3 – для етапу 3. Елементи табл. 5.2, які розміщені над головною діагоналлю, недопустимі, оскільки дефіцит в даному випадку не дозволяється.

Таблиця 5.2

	k=1а		k=2	k=3	k=4	k=5	k=6
i=1	(1)б (2) (3) (4)	20 102=20 0 0 f1→40*
i=2	(1) (2) (3) (4)	20 (10+15)2=50 151=15 0 f1→85*	17 152=30 0 f1=40 87
i=3	(1) (2) (3) (4)	20 (10+15+7)2=64 221+71=29 0 113	17 (15+7)2=44 71=7 f1=40 f3→108*	10 72=14 0 f2=85 109
i=4	(1) (2) (3) (4)		17 (15+7+20)2=84 271+201=47 f1=40 188	10 (7+20)2=54 201=20 f2=85 169	18 202=40 0 f3=108 f4→166*
i=5	(1) (2) (3) (4)				18 (20+13)2=66 133=39 f3=108 231	5 132=26 0 f4=166 f5→197*
i=6	(1) (2) (3) (4)					5 (13+25)2=76 251=25 f4=166 f6→272*	50 252=50 0 f5=197 297

^а Розміщення замовлень на етапі k для етапів по i-й включно.

^б (1) Затрати на оформлення замовлення, (2) затрати на закупівлю, (3) затрати на зберігання, (4) оптимальні сумарні затрати попередніх етапів.

Підтвердженням положень теореми про горизонт планування служить поява в рядку 3 (i=3) на етапі 2 (k=2). Це означає, що оптимальним розв’язком для етапу 3 (і етапу 2) є розміщення замовлення на етапі 2. Це еквівалентно тому, що і . Згідно сформульованої теореми, всі обчислення для наступних рядків (i>3) можна виконувати починаючи з другого етапу. Таким чином, етап 2 відповідає початку підгоризонту. При переходе до рядка 4 бачимо, що величина з’являється на етапі 4, а значить, оптимальний розв’язок передбачає розміщення замовлення для етапу 4 на самому етапі 4. Отже, значення та i=4 визначають початок горизонту планування. Тому в наступних рядках 5 і 6 елементи для етапів 1–3 обчислювати не потрібно. Продовжуючи аналогічним чином, ми бачимо з табл. 5.2, що новий горизонт планування починається на етапі 5. В результаті, обчислення в рядку 6 необхідно виконувати тільки для етапів 5 і 6. Таким чином, етапи 1, 4 та 5 визначають початок трьох горизонтів планування задачі.

Перевага теореми про горизонт планування тепер очевидна, оскільки немає необхідності проводити обчислення в незаповнених клітинках під головною діагоналлю таблиці. Це свідчить про те, що об’єм обчислень зменшився, і, отже, обчислення стали більш ефективними.

Оптимальну стратегію управління запасами отримаємо при розгляді останнього рядка табл. 5.2. Величина показує, що оптимальним є розв’язок про розміщення на етапі 5 замовлення об’ємом одиниць для задоволення попиту на етапах 5 і 6. Далі із рядка 4 (=5–1) у відповідності з випливає, що потрібне розміщення замовлення тільки для етапу 4. В рядку 3 (=4–1), згідно значення , на другому етапі потрібно розмістити замовлення розміром одиниці для задоволення попиту на етапі 2 і 3. І на завершення, на першому етапі розміщується замовлення . При цьому сумарні затрати складають 272 долара.

Евристичний підхід Сільвера-Міла. Даний підхід застосовується до розв’язання тільки тих задач управління запасами, в яких затрати на закупівлю одиниці продукції постійні і однакові для всіх етапів. Тому евристичний підхід намагається збалансувати лише вартості розміщення замовлення і затрати на зберігання.

Евристичний метод визначає наступні етапи, потреби яких можна задовольнити за рахунок розміщення замовлення на протязі поточного періоду. Задача планування полягає в мінімізації затрат, які пов’язані з розміщенням замовлення і зберіганням продукції і віднесені до одного періоду.

Припустимо, на етапі i розміщується замовлення для періодів i, i+1, ..., і t (i≤t). Нехай TC(i,t) – відповідна вартість розміщення замовлень і зберігання продукції для цих же етапів. З використанням позначень, прийнятих для моделей динамічного програмування, математично це можна виразити наступним чином.

Позначимо далі через TCU(i,t) відповідні затрати за період, тобто

.

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

Функція TC(i,t) визначається с допомогою рекурентних співвідношень.

,

Алгоритм евристичного методу складається з наступних кроківв.

Крок 0. Кладемо i=1.

Крок 1. Визначаємо локальний мінімум функції TCU(i,t), який повинен задовольняти нерівностям

,

,

Тоді відповідно до евристичного підходу на етапі i розміщується замовлення об’ємом ( ) для етапів i,i+1,..., .

Крок 2. Кладемо . Якщо i>n, обчислення закінчуються; розглянутий весь плановий період. Інакше потрібно перейти до кроку 1.

Приклад 5.4-5

Застосуємо евристичний метод для розв’язання задачі із прикладу 5.4–4, в якому вартість закупівлі одиниці продукції дорівнює 2 долара для всіх етапів, а вартість зберігання одиниці продукції – 1 долар для всіх етапів, крім четвертого, де вона дорівнює 3 долара.

Ітерація 1 (i=1, доларів).

Функція ТС(1,t) визначається рекурентно по t. Наприклад, при заданому значенні ТС(1,1)=$20, .

Етап t	Dt	TC(1,t)	TCU(1,t)
1	10	20	20/1=20.00
2	15	20+115=35	35/2=17.50
3	7	35+(1+1)7=49	49/3=16.33
4	20	49+(l+1+1)20=109	109/4=27.25

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

Ітерація 2 (i=4, доларів).

Етап t	Dt	TC(4,t)	TCU(4,t)
4	10	18	18/1=18.00
5	13	18+313=57	52/2=28.50

Значення означає, що на четвертому етапі необхідно розмістити замовлення об’ємом 20 одиниць для етапу 4. Кладемо i=4+1=5.

Ітерація 3 (i=5, доларів).

Етап t	Dt	TC(5,t)	TCU(5,t)
5	13	5	5/1=5
6	25	5+125=30	30/2=15

Так як , на п’ятому етапі замовляється 13 одиниць для етапу 5. Кладемо далі i=5+1=6. Так як i=6, то це останній етап планування. Ми повинні замовляти на шостому етапі 25 одиниць для цього ж етапу.

В наступній таблиці порівнюються розв’язки, отримані евристичним методом і точним методом динамічного програмування. Ми виключили із частини таблиці, що містить результати динамічного програмування, вартість закупівлі одиниці продукції, оскільки цей параметр в обчисленнях с допомогою евристичного методу не враховується.

Етап	Евристичний метод		Метод динамічного програмування
	Закуплено одиниць	Вартість ($)	Закуплено одиниць	Вартість ($)
1	32	49	10	20
2	0	0	22	24
3	0	0	0	0
4	20	18	20	18
5	13	5	38	30
6	25	50	0	0
Всього	90	122	90	92

Вартість виробничого плану, запропонованого евристичним методом, приблизно на 32% перевищує вартість аналогічного плану, отриманого методами динамічного програмування (122 долара проти 90). "Неадекватність" результату евристичного методу може бути обумовлена даними, які використовувались у задачі. Зокрема, причиною цього може бути надзвичайна нерівномірність вартостей розміщення замовлень для етапів 5 і 6. Не дивлячись на це, цей приклад показує, що евристичний метод не володіє властивістю "бачити наперед" в пошуках кращого виробничого плану. Наприклад, розміщення на п’ятому етапі замовлень для етапів 5 і 6 (замість окремого їх розміщення) може зекономити 25 доларів, що зменшить сумарні затрати виробничого плану, запропонованого евристичним методом, до 97 доларів.