Реферат Курсовая Конспект
Планування кроку 2. - раздел Философия, ЗАГАЛЬНА ХАРАКТЕРИСТИКА ДИНАМІЧНОГО ПРОГРАМУВАННЯ На Цьому Етапі Ми Визначаємо Мінімальні Витрати Для Перших Двох Періодів За У...
|
На цьому етапі ми визначаємо мінімальні витрати для перших двох періодів за умови, що на кінець другого запаси повинні бути рівні нулю. У цьому випадку можливі два варіанти розв’язку:
- поставка продукції для двох періодів здійснюється на початку першого періоду (тобто остання поставка здійснюється в першому періоді);
- поставки здійснюються таким чином: у першому - для першого, у другому - для другого (тобто остання поставка здійснюється у другому періоді).
У першому випадку сумарні витрати складаються з витрат на поставку необхідної продукції для перших двох періодів (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.
– Конец работы –
Эта тема принадлежит разделу:
ЗАГАЛЬНА ХАРАКТЕРИСТИКА ДИНАМІЧНОГО ПРОГРАМУВАННЯ... Геометрична інтерпретація задач ДП... Приклад багатоетапної операції...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Планування кроку 2.
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов