Приклади розв’язання ЗУЗ

Задача 1. Визначити об'єми поставок у кожному з періодів, щоб повністю задовольнити попит кожного періоду і мінімізувати сумарні витрати на поставку і зберігання продукції в наступній ЗУЗ: кількість періодів планування: n = 6; рівні запасів: і ; попит у періодах: d₁ =15; d₂ = 8; d₃ = 20; d₄ = 11; d₅ =8; d₆ = 15; витрати на зберігання: h_k = 5; ; витрати на доставку (виробництво) продукції: A ₁= A ₂ =…= A ₆=50.

Планування кроку 1.

На цьому етапі ми визначаємо мінімальні витрати для першого періоду за умови, що на його кінець запаси повинні бути рівними нулю. Оскільки , то ми обов'язково повинні виконати поставку необхідної в першому періоді кількості одиниць продукції (d ₁). При цьому , витрати на поставку продукції рівні A ₁, а тому що нічого “зайвого” не зберігаємо, то витрати на зберігання продукції рівні 0. Таблиця заповнюється в такий спосіб:

Крок k	Можливі розв’язки (номер періоду останньої поставки): j	Вартість розв’язку: { } (вартість зберігання)	Умовно оптимальний розв’язок
		min f0(0) + A1 + 0= 0+ 50+0 =50

Планування кроку 2.

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

- поставка продукції для двох періодів здійснюється на початку першого періоду (тобто остання поставка здійснюється в першому періоді);

- поставки здійснюються таким чином: у першому - для першого, у другому - для другого (тобто остання поставка здійснюється у другому періоді).

У першому випадку сумарні витрати складаються з витрат на поставку необхідної продукції для перших двох періодів (A ₁) і витрат на зберігання в першому періоді, продукції, споживаної в другому періоді (h₁·d₂).

Якщо період останньої поставки – другий, то сумарні витрати складаються з витрат за перший період (f ₁(0)) і витрат на поставку продукції в другому періоді (A ₂) (витрати на зберігання дорівнюють нулю).

Крок k	Номер періоду останньої поставки): j	{ }
		f 0(0) + A 1 +h 1 ·d 2 = 0+50+40=90 min f 1(0) + A 2+ 0 =50+50+0=100

Як бачимо, f ₂(0) досягає мінімуму у випадку, коли поставка продукції для двох періодів здійснюється на початку першого періоду (відповідна поставка окреслена). Аналогічно робимо на кроках 3-6. Повний процес розв’язання задачі наведений у табл. 9 (при цьому, оператор взяття мінімуму на кожній ітерації опускаємо).

Таблиця 9

Крок k	Можливі розв’язки (номер періоду останньої поставки): j	Вартість розв’язку: (вартість зберігання)	Умовно оптимальний розв’язок
		f 0(0) + A 1 + 0= 0+ 50 +0 =50
		f 0(0) + A 1 +h 1 ·d 2 = 0+50+40=90	1	90
		f 1(0) +A 2 + 0 =50+50+0=100
		f 0(0) +A 1 +h 1(d 2 +d 3) +h 2 ·d 3=0+50+5·28+5·20=290	3	140
		f 1(0) +A 2 + h 2 · d 3 =50+50+100=200
		f 2(0) + A 3+0 =90+50=140
		f 2(0) + A 3 + h 3 ·d 4=90+50+55=195
		f 3(0) + A 4+ 0 =140+50=190
	4	f 3(0) + A 4 +h 4 ·d 5=140+50+40=230	4	230
		f 4(0) +A 5+ 0 =190+50=240
		f 3(0) +A 4 +h 4(d 5 +d 6) +h 5 ·d 6=140+50+115+75=380
		f 4(0) +A 5 + h 5 ·d 6 =190+50+75=315
		f 5(0) + A 6+ 0 =230+50=280	6	280

Порядок формування відповіді показаний стрілками. Отже, поставки повинні здійснюватися в першому, третьому, четвертому і шостому періодах. Виконаємо перевірку. Для цього випишемо кінцевий вираз для f ₆(0):

f ₆(0) = f ₅(0) + A ₆+ 0 = (f ₃(0) + A ₄ +h ₄ ·d ₅) + A ₆+ 0 =

= ((f ₂(0) + A ₃+0) + A ₄ +h ₄ ·d ₅) + A ₆+ 0 =

= (((f ₀(0) + A ₁ +h ₁ ·d ₂) + A ₃+0) + A ₄ +h ₄ ·d ₅) + A ₆+ 0 =

= 0 + 50 + 5·8 + 50 + 0 +50 + 0 + 5·8 + 50 + 0 = 280.

Відповідь: Мінімальні витрати становлять: = 280 (од. вартості). Об'єми поставок:

= =15+8=23; = 0;

= =20; = =11+8=19;

=0; = =15.

Задача 2. Визначити об'єми поставок у кожному з періодів, щоб повністю задовольнити попит кожного періоду й мінімізувати сумарні витрати на поставку й зберігання продукції: кількість періодів планування: n = 6; рівні запасів: і ; попит у періодах: d₁ =10; d₂ = 100; d₃ = 60; d₄ = 30; d₅ =115; d₆ = 70; витрати на зберігання: h ₁ = 2, h ₂ = 3, h_k = 1; ; витрати на доставку (виробництво) продукції: A ₁= A ₂ = A ₄= A ₆ =150, A ₃ =200, A ₅ =250.

Процес розв’язку задачі наведений у табл. 10

Таблиця 10

Крок k	Можливі розв’язки (номер періоду останньої поставки): j	Вартість розв’язки: (вартість зберігання)	Умовно оптимальний розв’язок
		f0 (0) + A 1 +0= 0+ 150 + 0 =150	1	150
		f 0(0) + A 1 +h 1 ·d 2 = 0+150+200=350	2	300
	2	f 1(0) + A 2 +0 =150+150+0=300
		f 1(0) + A 2 +h 2· d 3 =150+150+180=480
		f 2(0) +A 3 +0=300+200 + 0 =500
		f 1(0) + A 2 +h 2(d 3 +d 4) + h 3· d 4=150+150+270+30=600
	3	f 2(0) + A 3 +h 3· d 4=300+200+30=530	3	530
		f 3(0) +A 4+0=480+150 + 0 =630
		f 2(0) + A 3 +h 3(d 4 +d 5) +h 4· d 5 =760
		f 3(0) + A 4 +h 4· d 5 =480+150+115=745
		f 4(0) + A 5 + 0 =530+250 + 0 =780
		f 3(0) + A 4 +h 4·(d 5+ d 6)+ h 5· d 6=480+150+185+70=885
	5	f 4(0) + A 5 +h 5· d 6=530+250+70=850	5	850
		f 5(0) + A 6 + 0 =745+150 + 0 =895

Отже, поставки мають здійснюватися в першому, другому, третьому й п'ятому періодах. (Порядок формування відповіді показаний стрілками).

!

Хоча при знаходженні (мінімальних витрат за умови, що маємо всього п'ять періодів і на кінець п'ятого запаси мають бути нульовими) оптимальна стратегія така, що продукція, споживана в п'ятому періоді, повинна поставлятися в четвертому періоді, в остаточному (оптимальному) розв’язку продукція, споживана в п'ятому періоді, повинна поставлятися в цьому ж п'ятому періоді. Аналогічно, хоча мінімум досягається за умови, що продукція, споживана в третьому періоді, поставляється в другому, в остаточному розв’язку продукція, споживана в третьому періоді, повинна поставлятися в цьому ж третьому періоді.

Випишемо кінцевий вираз для f ₆(0):

f ₆(0) = f ₄(0) + A ₅ + h ₅· d ₆ =

= (f ₂(0) + A ₃ + h ₃· d ₄) + A ₅ + h ₅· d ₆ =

=((f ₁(0) + A ₂ +0) + A ₃ +h ₃· d ₄) + A ₅ + h ₅· d ₆ =

=(((f₀ (0) + A ₁ + 0) + A ₂ +0) + A ₃ +h ₃· d ₄) + A ₅ + h ₅· d ₆=

= 0+150+0+150+0+200+1·30+250+1·70=850.

Відповідь: Мінімальні витрати становлять: = 850 (од. вартості). Об'єми поставок:

= =10; = =100;

= =90; =0;

= =185; =0.