На цьому етапі ми визначаємо мінімальні витрати для перших двох періодів за умови, що на кінець другого запаси повинні бути рівні нулю. У цьому випадку можливі два варіанти розв’язку:
- поставка продукції для двох періодів здійснюється на початку першого періоду (тобто остання поставка здійснюється в першому періоді);
- поставки здійснюються таким чином: у першому - для першого, у другому - для другого (тобто остання поставка здійснюється у другому періоді).
У першому випадку сумарні витрати складаються з витрат на поставку необхідної продукції для перших двох періодів (A1) і витрат на зберігання в першому періоді, продукції, споживаної в другому періоді (h1·d2).
Якщо період останньої поставки – другий, то сумарні витрати складаються з витрат за перший період (f1(0)) і витрат на поставку продукції в другому періоді (A2) (витрати на зберігання дорівнюють нулю).
Крок k | Номер періоду останньої поставки): j | {} | ||
f0(0) + A1 +h1·d2 =0+50+40=90 min f1(0) + A2+ 0 =50+50+0=100 |
Як бачимо, f2(0) досягає мінімуму у випадку, коли поставка продукції для двох періодів здійснюється на початку першого періоду (відповідна поставка окреслена). Аналогічно робимо на кроках 3-6. Повний процес розв’язання задачі наведений у табл. 9 (при цьому, оператор взяття мінімуму на кожній ітерації опускаємо).
Таблиця 9
Крок k | Можливі розв’язки (номер періоду останньої поставки): j | Вартість розв’язку: (вартість зберігання) | Умовно оптимальний розв’язок | |
f0(0) + A1 +0= 0+ 50 +0 =50 | ||||
f0(0) + A1 +h1·d2 =0+50+40=90 | 1 | 90 | ||
f1(0) +A2 + 0 =50+50+0=100 | ||||
f0(0) +A1+h1(d2+d3)+h2·d3=0+50+5·28+5·20=290 | 3 | 140 | ||
f1(0) +A2+ h2· d3 =50+50+100=200 | ||||
f2(0) + A 3+0 =90+50=140 | ||||
f2(0) + A3 + h3·d4=90+50+55=195 | ||||
f3(0) + A4 + 0 =140+50=190 | ||||
4 | f3(0) + A4+h4·d5=140+50+40=230 | 4 | 230 | |
f4(0) +A5+ 0 =190+50=240 | ||||
f3(0) +A4+h4(d5+d6)+h5·d6=140+50+115+75=380 | ||||
f4(0) +A5+ h5·d6 =190+50+75=315 | ||||
f5(0) + A6+ 0 =230+50=280 | 6 | 280 |
Порядок формування відповіді показаний стрілками. Отже, поставки повинні здійснюватися в першому, третьому, четвертому і шостому періодах. Виконаємо перевірку. Для цього випишемо кінцевий вираз для f6(0):
f6(0) = f5(0) + A6+ 0 = (f3(0) + A4+h4·d5)+ A6+ 0 =
= ((f2(0) + A 3+0)+ A4+h4·d5)+ A6+ 0 =
= (((f0(0) + A1 +h1·d2)+ A 3+0)+ A4+h4·d5)+ A6+ 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; рівні запасів: і ; попит у періодах: d1 =10; d2 = 100; d3 = 60; d4 = 30; d5 =115; d6 = 70; витрати на зберігання : h1 = 2, h2 = 3, hk = 1; ; витрати на доставку (виробництво) продукції: A1= A2 = A4= A6 =150, A3 =200, A5 =250.
Процес розв’язку задачі наведений у табл. 10
Таблиця 10
Крок k | Можливі розв’язки (номер періоду останньої поставки): j | Вартість розв’язки: (вартість зберігання) | Умовно оптимальний розв’язок | |
f0(0) + A1 +0= 0+ 150 + 0 =150 | 1 | 150 | ||
f0(0) + A1 +h1·d2 =0+150+200=350 | 2 | 300 | ||
2 | f1(0) + A2 +0 =150+150+0=300 | |||
f1(0) + A2 +h2·d3 =150+150+180=480 | ||||
f2(0) +A3 +0=300+200 + 0 =500 | ||||
f1(0) + A2+h2(d3+d4)+ h3·d4=150+150+270+30=600 | ||||
3 | f2(0) + A3+h3·d4=300+200+30=530 | 3 | 530 | |
f3(0) +A4+0=480+150 + 0 =630 | ||||
f2(0) + A3 +h3(d4+d5)+h4·d5 =760 | ||||
f3(0) + A4 +h4·d5 =480+150+115=745 | ||||
f4(0) + A5 + 0 =530+250 + 0 =780 | ||||
f3(0) + A4 +h4·(d5+ d6)+ h5·d6=480+150+185+70=885 | ||||
5 | f4(0) + A5 +h5·d6=530+250+70=850 | 5 | 850 | |
f5(0) + A6 + 0 =745+150 + 0 =895 |
Отже, поставки мають здійснюватися в першому, другому, третьому й п'ятому періодах. (Порядок формування відповіді показаний стрілками).
| Хоча при знаходженні (мінімальних витрат за умови, що маємо всього п'ять періодів і на кінець п'ятого запаси мають бути нульовими) оптимальна стратегія така, що продукція, споживана в п'ятому періоді, повинна поставлятися в четвертому періоді, в остаточному (оптимальному) розв’язку продукція, споживана в п'ятому періоді, повинна поставлятися в цьому ж п'ятому періоді. Аналогічно, хоча мінімум досягається за умови, що продукція, споживана в третьому періоді, поставляється в другому, в остаточному розв’язку продукція, споживана в третьому періоді, повинна поставлятися в цьому ж третьому періоді. |
Випишемо кінцевий вираз для f6(0):
f6(0) = f4(0) + A5 + h5·d6 =
= (f2(0) + A3 + h3·d4)+ A5 + h5·d6 =
=((f1(0) + A2 +0) + A3+h3·d4)+ A5 + h5·d6 =
=(((f0(0) + A1 + 0)+ A2 +0) + A3+h3·d4)+ A5 + h5·d6=
= 0+150+0+150+0+200+1·30+250+1·70=850.
Відповідь:Мінімальні витрати становлять: = 850 (од. вартості). Об'єми поставок:
==10; ==100;
==90; =0;
= =185; =0.