Programowanie dynamiczne (Cd)

Ogólnie zadanie programowania dynamicznego można sformułować następująco:

Wyznaczyć takie wartości zmiennych decyzyjnych
, dla których funkcja F (zakładamy, że funkcja jest addytywna) osiąga ekstremum, co zapisujemy:

znaleźć ekstremum funkcji

gdzie:

x_i - dopuszczalna decyzja w i-tym etapie, przy czym x_i należy do zbioru X_i decyzji dopuszczalnych dla i-tego etapu,
,

s_i - stan dopuszczalny w jakim może się znaleźć proces na początku i-tego etapu,

- rezultat decyzji x_i uwzględniającej stan procesu s_i na początku i-tego etapu.

Wartości funkcji v_i, a w konsekwencji i wartość funkcji F zależą od wyboru zmiennych decyzyjnych x_i. Wybór ten nie jest dokonywany jednorazowo, lecz kolejno dla poszczególnych etapów procesu decyzyjnego.

Wyznaczenie ekstremum funkcji F jest realizowane według procedury opartej na zasadzie optymalności R. E. Bellmana:

.......................................................

x_i należy do zbioru X_i decyzji dopuszczalnych dla i-tego etapu

.......................................................

Należy tutaj wyraźnie podkreślić, że w oznaczeniach niniejszego rozdziału (poza jednym wyjątkiem) przyjęto numerację „od końca”. To znaczy etap ostatni jest numerowany jako pierwszy.

Problem zarządzania produkcją i zapasami

Rozważmy problem zarządzania zapasami i produkcją w określonym okresie czasu (okres czasu analizy dzieli się odpowiednio na etapy np. miesiące, tygodnie itp.) z punktu widzenia istniejącego i mogącego się zmieniać z okresu na okres: popytu na określony produkt, ograniczonych zdolności produkcyjnych danych produktów, oraz zdolności magazynowania tych produktów.

Przykład:

Przedsiębiorstwo w ciągu czterech miesięcy powinno pokryć zapotrzebowanie na dany produkt, przy następujących założeniach:

• zapotrzebowanie na produkt w każdym miesiącu wynosi 3 jednostki,

• w każdym miesiącu, jeżeli zaistnieje taka konieczność, zakład może uruchomić produkcję tego produktu. Koszt uruchomienia produkcji wynosi np. 13 tys. zł,

• moce produkcyjne zakładu wynoszą 5 jednostek,

• koszty wytwarzania kolejnych jednostek są zróżnicowane i wynoszą:

1-szej jednostki - 3 tys. zł,

2-giej - 2 tys. zł,

3-ciej i 4-tej - po 1 tys. zł,

5-tej - 4 tys. zł,

• zapas na początek i koniec analizowanego okresu = 0,

• koszty magazynowania jednej jednostki wynoszą 2 tys. zł,

• pojemność magazynu wynosi 4 jednostki.

Koszty k(x) produkcji x jednostek podano w Tablicy poniżej.

Tablica: Funkcja k(x) kosztów produkcji

x	0	1	2	3	4	5
k(x)	0	16	18	19	20	24
		(13+3)	(16+2)	(18+1)	(19+1)	(20+4)

Zgodnie z zasadą programowania dynamicznego wprowadzimy następujący zapis formalny rozważanego problemu:

Przyjmijmy:

x_n - ilość produktu wytworzonego w miesiącu n,

s_n - zapas na koniec miesiąca n. Jednocześnie s_n-1 oznacza stan zapasów na początek n-tego miesiąca.

Zmianę stanów zapasów można zapisać:

,

s₀ - zapas na początku rozważanego okresu,

- optymalna wielkość produkcji w miesiącu n przy zapasie na początku miesiąca
.

Koszty ponoszone w danym miesiącu są sumą kosztów wytwarzania x_n oraz magazynowania
jednostek w ciągu jednego miesiąca, tzn.:

, (n = 1, 2, 3,4)

s_o i s₄=0 (s₄ - zapas na koniec kwietnia)

(s_o - zapas na początek stycznia)

Wreszcie:

- możliwości produkcyjne (całkowitoliczbowe),

- możliwości magazynowania.

Należy zminimalizować
przy spełnieniu wyżej wymienionych warunków.

Uwaga: wyjątkowo w tym przykładzie odeszliśmy od przyjętej konwencji numerowania od końca.

Sposób rozwiązywania

Analizujemy ostatni miesiąc, czyli kwiecień (n = 4)

- decyzja dotycząca wielkości produkcji w zależności od s₃ (stan s₄=0, czyli s₃+x₄-3=0. A stąd wynika podana zależność na x₄). Wyniki analizy ostatniego miesiąca przedstawiono w Tablicy poniżej.

Tablica Wyniki analizy miesiąca kwietnia

s3
0	19	3
1	18	2
2	16	1
3	0	0

Analizujemy teraz łącznie miesiące n = 4 (kwiecień) i n - 1 = 3 (marzec).

Koszty poniesione w marcu wynoszą
.

Zatem minimalny koszt poniesiony w marcu i kwietniu przy zapasie
na początku marca wynosi:

Sposób wyznaczania funkcji
ilustruje Tablica poniżej.

Tablica: Wyniki analizy miesiąca marzec i kwiecień

S2\x3	0	1	2	3	4	5
0	-	-	-	19+0+19	20+2+18	24+4+16	38	3
1	-	-	18+0+19	19+2+18	20+4+16	24+6+0	30	5
2	-	16+0+19	18+2+18	19+4+16	20+6+0	-	26	4
3	0+0+19	16+2+18	18+4+16	19+6+0	-	-	19	0
4	0+2+18	16+4+16	18+6+0	-	-	-	20	0

Sposób wyznaczania funkcji
obejmującej kwiecień, marzec i luty oraz wyznaczenie optymalnej decyzji
ilustruje z kolei Tablica poniżej.

Tablica: Wyniki analiz miesięcy: luty, marzec i kwiecień

S1\x2	0	1	2	3	4	5
0	-	-	-	19+0+38	20+2+30	24+4+26	52	4
1	-	-	18+0+38	19+2+30	20+4+26	24+6+19	49	5
2	-	16+0+38	18+2+30	19+4+26	20+6+19	24+8+20	45	4
3	0+0+38	16+2+30	18+4+26	19+6+19	20+8+20	-	38	0
4	0+2+30	16+4+26	18+6+19	19+8+20	-	-	32	0

Funkcja
obejmuje styczeń, luty, marzec i kwiecień w sposób analogiczny jak funkcje poprzednie. Należy tylko pamiętać o założeniu, że zapas początkowy w styczniu czyli 
jest równy 0. Analizujemy, więc tylko sytuację dla
(patrz Tablica).

Tablica Wyniki analizy całego rozważanego okresu:

S0\x1	0	1	2	3	4	5
0	-	-	-	19+0+52	20+2+49	24+4+45	71	3 lub 4

Optymalny ciąg decyzji dla czterech miesięcy wyznaczamy rozpoczynając analizę od ostatniej Tabeli.

Minimalny koszt poniesiony w ciągu czterech miesięcy wyniósł 71 tys. zł. Zgodnie z przeprowadzoną wyżej analizą koszt ten poniesiono wytwarzając w styczniu 3 albo 4 jednostki wyrobu. Wskazuje to na wystąpienie dwóch różnych możliwości rozwiązania problemu dających ten sam wynik.

Jeżeli przyjąć, że:

(optymalna wielkość produkcji w styczniu) to:

.

Jeżeli
to z Tablicy obejmującej luty, marzec i kwiecień mamy

Luty, marzec, kwiecień.

S1\x2	0	1	2	3	4	5
0	-	-	-	19+0+38	20+2+30	24+4+26	52	4
1	-	-	18+0+38	19+2+30	20+4+26	24+6+19	49	5
2	-	16+0+38	18+2+30	19+4+26	20+6+19	24+8+20	45	4
3	0+0+38	16+2+30	18+4+26	19+6+19	20+8+20	-	38	0
4	0+2+30	16+4+26	18+6+19	19+8+20	-	-	32	0

stąd,

.

Jeżeli
to z analogicznej Tablicy odczytujemy

Marzec, kwiecień:

S2\x3	0	1	2	3	4	5
0	-	-	-	19+0+19	20+2+18	24+4+16	38	3
1	-	-	18+0+19	19+2+18	20+4+16	24+6+0	30	5
2	-	16+0+19	18+2+18	19+4+16	20+6+0	-	26	4
3	0+0+19	16+2+18	18+4+16	19+6+0	-	-	19	0
4	0+2+18	16+4+16	18+6+0	-	-	-	20	0

Przy
, optymalna wielkość produkcji wynosi 0. Kwiecień:

s3
0	19	3
1	18	2
2	16	1
3	0	0

Zgodnie z powyższą analizą przedsiębiorstwo powinno produkować:

• w styczniu 3 jednostki,

• w lutym 4 jednostki,

• w marcu 5 jednostek,

• w kwietniu 0 jednostek.

-------------------------------------------------------------

Jak będzie wyglądało rozwiązanie gdyby przyjąć, że
w styczniu produkujemy 4 sztuki wyrobu?

19

---