Hubert Skrzypulec 21.11.2008r.
ZiIP 3.2 Zabrze
POLITECHNIKA ŚLĄSKA W GLIWICACH
WYDZIAŁ ORGANIZACJI I ZARZĄDZANIA
Katedra Informatyki i Ekonometrii
BADANIA OPERACYJNE
Projekt nr 4
Metody programowania dynamicznego
Treść zadania
Przedsiębiorstwo branży spożywczej „Frost” jest producentem głęboko mrożonych zestawów obiadowych. Chce opracować program produkcji na najbliższe 3 miesiące (od stycznia do marca). Wiadomo, że popyt na produkty tego przedsiębiorstwa jest stały i wynosi 1200 szt. zestawów obiadowych. Moce wytwórcze pozwalają na skierowanie do sprzedaży 2000 sztuk miesięcznie. Koszt produkcji zależnie od ilości wyprodukowanych zestawów przedstawia tabela 1.
Tabela 1
Ilość wyprodukowanych zestawów |
0 |
400 |
800 |
1200 |
1600 |
2000 |
Koszt (zł) |
0 |
2500 |
2900 |
3300 |
3700 |
4100 |
Koszt przechowywania produktów w chłodni wynosi miesięcznie 150zł od 400 sztuk. Chłodnia jest w stanie pomieścić maksymalnie 1600 zestawów obiadowych. Obecnie w magazynie znajduje się 800 sztuk. Na zakończenie planowanego okresu magazyn ma zostać pusty. Należy zminimalizować koszty.
W trakcie rozwiązywania posługuję się ciągiem równań funkcyjnych Bellmana.
Oznaczenia
Dla uporządkowania procesu rozwiązania zagadnienia dynamicznego wprowadzam oznaczenia:
x1 - ilość wyprodukowanych zestawów obiadowych w styczniu
x2 - ilość wyprodukowanych zestawów obiadowych w lutym
x2 - ilość wyprodukowanych zestawów obiadowych w marcu
si - poziom zapasów na początku i-tego miesiąca
p - popyt
ki(j) - koszty magazynowania j elementów (0 ≤ j ≤ 1600) w i-tym miesiącu
fi(xi,si) - koszty produkcji i magazynowania w i-tym miesiącu
fi(xi,si) = ki(xi) + ki(si+1)
łączne koszty produkcji i magazynowania z każdego miesiąca wynoszą:
f1(x1,s1) + f2(x2,s2) + f3(x3,s3)
W tym miejscu warto zauważyć pewną zależność pomiędzy produkcją, stanem magazynowym i popytem, z której będę korzystał na dalszych etapach rozwiązania:
0 ≤ si + xi - p ≤ 1600
Wiemy, że na początku roku, gdy rozpoczynamy planowanie znany jest stan magazynowy, oraz założenie mówiące o pustym magazynie na koniec okresu planowania.
Stąd:
s1 = 800
s4 = 0
Rozwiązanie
Sztucznie dzielę proces produkcji na 3 etapy:
Etap 1 - wyprodukowanie x1 zestawów w styczniu.
Etap 2 - wyprodukowanie x2 zestawów w lutym.
Etap 3 - wyprodukowanie x3 zestawów w marcu.
Krok 1 Etap 3 (Marzec)
g3(s3) = min(f3(x3,s3))
funkcja g3(s3) mówi nam o kosztach ponoszonych na produkcje i magazynowanie. Założeniem zadania jest minimalizacja kosztów, stąd szukamy minimalnej wartości funkcji f3. Założenie to jest obowiązujące na wszystkich etapach rozwiązywania rozpatrywanego problemu dynamicznego.
Wykorzystując zależność produkcji, stanów magazynowych i popytu otrzymuję:
s4= 0 s3 + x3 - p = 0 0 ≤ x3 = p - s3 0 ≤ s3 ≤ 1600 |
0 ≤ s3 + x3 - p ≤ 1600 0 ≤ s3 + x3 - 1200 ≤ 1600 x3 ≤ 2800 - s3 0 ≤ s3 ≤ 1600 |
Wyznaczam minimalny koszt produkcji i utrzymania zapasów w marcu.
Tabela 2
s3 |
x3 |
s4 |
f3(x3,s3) |
g3(s3) |
0 |
1200 |
0 |
3300+0 |
3300 |
400 |
800 |
0 |
2900+0 |
2900 |
800 |
400 |
0 |
2500+0 |
2500 |
1200 |
0 |
0 |
0 |
0 |
Krok 2 Etap 2 (Luty)
g2(s2) = min(f2(x2,s2)+ g3(s3))
Wykorzystując zależność produkcji, stanów magazynowych i popytu otrzymuję:
1200 - s2 ≤ x2 ≤ 2800 - s2 0 ≤ s2 ≤ 1600 |
0 ≤ s2 + x2 - p ≤ 1600 0 ≤ s2 + x2 - 1200 ≤ 1600 1200 - s2 ≤ x2 ≤ 2800 - s2 |
Tabela 3
s2 |
x2 |
s3 |
f2(x2,s2) |
g3(s3) |
f2(x2,s2)+ g3(s3) |
g2(s2) |
0 |
1200 |
0 |
3300 + 0 |
3300 |
6600 |
6600 |
0 |
1600 |
400 |
3700 + 150 |
2900 |
6750 |
|
0 |
2000 |
800 |
4100 + 300 |
2500 |
6900 |
|
400 |
800 |
0 |
2900 + 0 |
3300 |
6200 |
|
400 |
1200 |
400 |
3300 + 150 |
2900 |
6350 |
|
400 |
1600 |
800 |
3700 + 300 |
2500 |
6500 |
|
400 |
2000 |
1200 |
4100 + 450 |
0 |
4450 |
4450 |
800 |
400 |
0 |
2500 + 0 |
3300 |
5800 |
|
800 |
800 |
400 |
2900 + 150 |
2900 |
5950 |
|
800 |
1200 |
800 |
3300 + 300 |
2500 |
6100 |
|
800 |
1600 |
1200 |
3700 + 450 |
0 |
4150 |
4150 |
1200 |
0 |
0 |
0 + 0 |
3300 |
3300 |
3300 |
1200 |
400 |
400 |
2500 + 150 |
2900 |
5500 |
|
1200 |
800 |
800 |
2900 + 300 |
2500 |
5700 |
|
1200 |
1200 |
1200 |
3300 + 450 |
0 |
3750 |
|
1600 |
0 |
400 |
0 + 150 |
2900 |
3050 |
3050 |
1600 |
400 |
800 |
2500 + 300 |
2500 |
5300 |
|
1600 |
800 |
1200 |
2900 + 450 |
0 |
3350 |
|
Krok 3 Etap 1 (styczeń)
g1(s1) = min(f1(x1,s1)+ g2(s2))
400 ≤ x1 ≤ 2000 s1 = 2 |
0 ≤ s1 + x1 - p ≤ 1600 0 ≤ s1 + x1 - 1200 ≤ 1600 0 ≤ 2 + x1 - 1200 ≤ 1600 |
Tabela 4
s1 |
x1 |
s2 |
f1(x1,s1) |
g2(s2) |
f1(x1,s1) + g2(s2) |
g1(s1) |
2 |
400 |
0 |
2500 + 0 |
6600 |
9100 |
|
2 |
800 |
400 |
2900 + 150 |
4450 |
7500 |
|
2 |
1200 |
800 |
3300 + 300 |
4150 |
7750 |
|
2 |
1600 |
1200 |
3700 + 450 |
3300 |
7450 |
7450 |
2 |
2000 |
1600 |
4100 + 600 |
3050 |
7750 |
|
Odpowiedź i interpretacja wyników.
x1 = 1600 x2 = 0 x3 = 1200 |
s2 = 1200 s3 = 0 |
Najniższy koszt wytwarzania uzyskamy produkując w styczniu 1600 sztuk zestawów obiadowych. W tej sytuacji stan magazynowy na początku lutego wyniesie 1200 sztuk. W lutym najlepszym rozwiązaniem jest wstrzymanie produkcji na miesiąc. Dzięki temu magazyn na początku marca będzie pusty. W marcu, jako że mamy pusty magazyn, a popyt jest stały produkujemy właśnie tyle ile wynosi wartość popytu, czyli 1200 sztuk. Dzięki temu osiągniemy najniższy z możliwych kosztów zorganizowania produkcji wynoszący 7450 zł
Strona 4 z 6