410 411

410 Programowanie dynamiczne

Przedstawione powyżej równania optymalności oraz ich rozwiązania pozwalają na znalezienie rozwiązania optymalnego. Zadanym stanem początkowym jest stan yf = 1. Korzystając z równania optymalności dla tego stanu, stwierdzamy, że decyzją optymalną jest xf = 2. Proces przechodzi na początku etapu 2 do stanu yf = 0. Optymalną decyzją dla tego stanu (co wynika z rozwiązania odpowiedniego równania optymalności) jest jcf = 3. Proces znajdzie się wówczas na początku etapu 3 w stanie yf = 0. Kolejną decyzją optymalną jest e* = 3. Stan końcowy procesu jest wówczas równy yf=0.

Przedstawione powyżej obliczenia możemy zestawić następująco:

yf = 1,	jcT(D = 2,
yf = 1 +2-3=0,	jcf (0) = 3.
yf = 0 + 3 —3=0,	Jtf(0) = 3.
yf = 0 + 3 —3 = 0.

Rozpatrywane w tym podrozdziale równania optymalności można zapisać w sposób ogólny:

•    dla t= 3:

gHOb) = min {/,(y_3> x₃): x₃e X₃(y,)},

•    dla 1 = 2:

g?(y₂) = min {J₂(y₂, x₂) + ^(y₂+x₂-d₂y. x₂e X₂(y₂)},

•    dla 1=1:

gf(yi)= min {/,(y„ *,) + #?(y, +x,-d,): x, e X|(y,)).

9.2.5. Reguły postępowania przy rozwiązywaniu zadań programowania dynamicznego

Opisane w poprzednim podrozdziale wykorzystanie zasady optymalności Bellmana do znalezienia strategii optymalnej i optymalnej realizacji procesu wieloetapowego stanowi przykład zastosowania metody programowania dynamicznego. Podstawowe kroki postępowania w tej metodzie przedstawiono poniżej.

1.    Ustalamy liczbę etapów T rozpatrywanego procesu.

2.    Definiujemy zmienne stanu y, (dla 1 = 1, ..., T+l) i zmienne decyzyjne x, (dla r=l, ..., T).

3.    Dla f= 1, ..., T określamy postać funkcji przejścia: y,₊ i=£2r0\> *,)•

4.    Identyfikujemy zbiór stanów początkowych K, i zbiór stanów końcowych Y_r+i procesu.

5.    Dla etapu t (f=l, .... T):

a)    określamy zbiór stanów dopuszczalnych Y„

b)    dla każdego stanu y,e Y, określamy zbiór decyzji dopuszczalnych

c)    dla każdego stanu y,e Y, i każdej decyzji x,e X,(y,) określamy wartości funkcji korzyści etapowych /,(y„ x,).

6.    Korzystając z zasady optymalności Bell mana, konstruujemy równania optymalności i je rozwiązujemy.

a)    Etap T:

Przypuśćmy, że na początku etapu T rozpatrywany proces znalazł się w ustalonym stanie y_T. Równanie optymalności ma wówczas postać:

gf(y_T) = max (/r(», X,): x_re X_r(y_r)}.

Znajdujemy decyzję xf(y_T), która spełnia to równanie. Jest ona częścią poszukiwanej strategii optymalnej. Jeżeli takich decyzji jest więcej niż jedna, zapamiętujemy wszystkie te decyzje.

Postępowanie to powtarzamy dla wszystkich stanów dopuszczalnych ze zbioru Y_r.

b)    Etap t {t=T— 1..... 1):

Przypuśćmy, że na początku etapu / rozpatrywany proces znalazł się w ustalonym stanie y,. Równanie optymalności ma wówczas postać:

g* (y<) = ^max \J; (y„ x,) + g* , (y,+,): x, e X,(y,)),

przy czym y,_{+ l}=Q,(y„ x,).

Znajdujemy decyzję X? (y,), która spełnia to równanie. Jest ona częścią poszukiwanej przez nas strategii optymalnej. Jeżeli takich decyzji jest więcej niż jedna, zapamiętujemy wszystkie te decyzje.

Postępowanie to powtarzamy dla wszystkich stanów dopuszczalnych ze zbioru Y,.

7.    Ciąg {jcf(y,): y,e K„ t=l, ..., T] decyzji optymalnych, wyznaczonych w krokach 6a i 6b, stanowi strategię optymalną. Jeżeli wszystkie rozpatrywane równania optymalności miały dokładnie jedno rozwiązanie, to istnieje dokładnie jedna strategia optymalna. Jeżeli przynajmniej jedno równanie miało więcej niż jedno rozwiązanie optymalne, to strategii optymalnych jest więcej. Możemy je wyznaczyć po kolei, uwzględniając wszystkie otrzymane rozwiązania równań optymalności.

8.    Znajdujemy optymalny stan początkowy yf. porównując ze sobą wartości gf(y,) w następujący sposób:

gfO'*) = max {gf(y,): y, 6 K,).    (9.1)

Jeżeli zbiór dopuszczalnych stanów początkowych P, jest jedno-elcmenlowy, wynik jest oczywisty. Jeżeli ze związku (9.1) otrzymamy więcej niż jeden optymalny stan początkowy, to dalszą część postępowania powtarzamy dla każdego z otrzymanych stanów yf.