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 {/,(y3> x3): x3e X3(y,)},
• dla 1 = 2:
g?(y2) = min {J2(y2, x2) + ^(y2+x2-d2y. x2e X2(y2)},
• 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 Yr+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 yT. Równanie optymalności ma wówczas postać:
gf(yT) = max (/r(», X,): xre Xr(yr)}.
Znajdujemy decyzję xf(yT), 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 Yr.
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.
Wyszukiwarka
Podobne podstrony:
STATOM KOLORY NAZWY bmp Poniższa tabela przedstawia 16 nazw kolorów oraz ich kody RGB, które rnogą
406 407 406 Programowanie dynamiczne9.2.4. Zasada optymalności Bellmana i równania optymalności Rozw
418 419 4
DSC70 (11) Identyfikacja Element dynamiczny II rzędu Równanie różniczkowe obiektu II rzędu można pr
img156 (3) II. TREŚĆ I STRUKTURA PROGRAMU „Wesołe przedszkole i przyjaciele. Program wychowania i ed
img315 Wyliczone wartości własne pokazane są na rysunku 15.1. Z przedstawionej powyżej tablicy wynik
Dziecięca Kraina Kreatywności Sprawozdanie z realizacji programu DKKGminne Przedszkole w
stawie przedstawionych powyżej przemyśleń). Przy pomocy tego instrumentu każda cecha systemu
OMiUP t1 Gorski9 W odniesieniu do przedstawionych powyżej rozważań, jak również tych z dalszej częś
IMG&57 5. Spośród informacji przedstawionych powyżej, wybierz dwie, które świadczą 0 n sowaniu mszak
skanuj0014 4 1.4. Elementarne cele i zadania pracy socjalnej Z przedstawionych powyżej określeń prac
Skan C.Zastosowanie zewnętrznej siły wymuszającej do układu przedstawionego powyżej Modyfikując tłu
więcej podobnych podstron