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

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:

x₁ – ilość wyprodukowanych zestawów obiadowych w styczniu

x₂ – ilość wyprodukowanych zestawów obiadowych w lutym

x₂ – ilość wyprodukowanych zestawów obiadowych w marcu

s_i – poziom zapasów na początku i-tego miesiąca

p – popyt

k_i(j) – koszty magazynowania j elementów (0 ≤ j ≤ 1600) w i-tym miesiącu

f_i(x_i,s_i) – koszty produkcji i magazynowania w i-tym miesiącu

f_i(x_i,s_i) = k_i(x_i) + k_i(s_i+1)

łączne koszty produkcji i magazynowania z każdego miesiąca wynoszą:

f₁(x₁,s₁) + f₂(x₂,s₂) + f₃(x₃,s₃)

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 ≤ s_i + x_i – 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:

s₁ = 800

s₄ = 0

Rozwiązanie

Sztucznie dzielę proces produkcji na 3 etapy:

Etap 1 – wyprodukowanie x₁ zestawów w styczniu.

Etap 2 – wyprodukowanie x₂ zestawów w lutym.

Etap 3 – wyprodukowanie x₃ zestawów w marcu.

Krok 1 Etap 3 (Marzec)

g₃(s₃) = min(f₃(x₃,s₃))

funkcja g₃(s₃) 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 f₃. 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 = s3 + x3 – p 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

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)

g₂(s₂) = min(f₂(x₂,s₂)+ g₃(s₃))

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

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ń)

g₁(s₁) = min(f₁(x₁,s₁)+ g₂(s₂))

400 ≤ x1 ≤ 2000 s1 = 2	0 ≤ s1 + x1 – p ≤ 1600 0 ≤ s1 + x1 – 1200 ≤ 1600 0 ≤ 2 + x1 – 1200 ≤ 1600

Tabela

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ł