5. DYNAMICKÉ PROGRAMOVÁNÍ Dynamické programování je považováno za jednu z obecných metod navrhování optimálního řízení různých reálných objektů. Někdy je výraz dynamické programování nahrazován výrazem dynamické plánování. Teorie dynamického programování byla rozvíjena zejména v oblasti technicko-ekonomických úloh, např. jak nejlépe využívat zařízení, jaké jsou optimální zásoby. Nejčastěji je dynamické programování spojováno se jménem Richarda Bellmana, kterému v roce 1957 vyšla kniha Dynamic Programming. 5.1 Úloha dynamického programování Dynamické programování umožňuje návrh optimálního řízení procesů, které mohou být v čase diskrétní nebo spojité, také jejich řízení může mít diskrétní nebo spojitý charakter. Abychom mohli úlohu optimálního řízení matematicky popsat musíme zavést kriteriální funkci Z, její hodnota bude charakterizovat kvalitu a úspěšnost operace. Veličina Z může být vybrána různým způsobem. Při plánování činnosti výrobní organizace to může být objem výroby za jednotku času, u dopravní organizace počet tunokilometrů nebo střední cena za tunokilometr. Z teorie řízení jsou známá kriteria minimální plochy kvadrátu odchylky, nejkratší doba dosažení zadaného tolerančního pásma při dalším setrvání v tomto pásmu a pod. Úlohou optimálního řízení je nalezení takové posloupnosti řídících zásahů, aby hodnota kriteriální funkce Z byla maximální (nebo minimální) ve srovnání s jakoukoliv jinou posloupností. U spojitého řízení je posloupnost nahrazena průběhy hodnot řídících proměnných. Úlohu vedoucí k minimalizaci hodnoty Z lehce převedeme např. změnou znaménka na úlohu maximalizace, budeme proto v dalším hovořit pouze o maximalizaci kriteria. Označíme-li řídící proměnnou u (může to být i vektor s více složkami), řekneme, že cílem je nalezení takového řízení u, při kterém hodnota Z bude maximální. Specifikou dynamického programování je rozkládání řízeného procesu na řadu po sobě jdoucích kroků nebo etap. Některé procesy jsou víceetapové již svým charakterem, u jiných je možno rozložení na více kroků realizovat uměle. Také proces hledání optimálního řízení je víceetapový a rozvíjí se postupně. Přirozeně víceetapovým je např. proces výroby probíhající ve směnách, dnech, týdnech, měsících a rocích. Podobně let vícestupňové rakety, dopravní procesy rozložitelné na pohyby od jednoho dopravního uzlu ke druhému, obchodní i vojenské operace sestávající z jednotlivých akcí, šachové úlohy s posloupností tahů, Rubikova kostka atd. Spojité procesy rozkládáme uměle na takový počet etap, aby vyhovovala přesnost výsledku. Předpokládejme, že řídicí proměnná je vektorem s n složkami a v i-tém kroku bude použito řízení 1
2
3
n
ui = ( xi, xi, xi,..., xi). Úplné řízení během m-etapového procesu vyjádříme pomocí řady u1, u2,..., ui,... um Kriteriální funkce Z je tedy závislá na uvedené řadě a hledání jejího optima je hledáním posloupnosti m bodů v n-rozměrném prostoru nebo jinými slovy hledáním bodu v prostoru m x n s maximální hodnotou Z. Funkce Z však nebývá jednoduchá a hledání maxima klasickým způsobem (první derivace podle jednotlivých proměnných rovna nule atd.) vede málokdy k cíli. Maximum může být na okraji prostoru m x n , v řadě případů se funkce Z = Z(u) ani derivovat nedá. Hledání maxima pomocí variačního počtu převádí obvykle danou úlohu na úlohy,které nejsou jednodušší. Hlavní myšlenkou DP je převedení úlohy nalezení maxima funkce velkého počtu proměnných na vícenásobně opakovanou úlohu hledání maxima funkce s menším počtem proměnných, která je podstatně jednodušší. V dalším se budeme zabývat systémy, u kterých bude součtová (additivní) kriteriální funkce. Nejedná se o velké omezení, u většiny systémů a problémů je additivnost při posuzování optima charakteristickou vlastností. Spotřeba zdrojů, finančních prostředků ,dosažený čas a pod. jsou dány pro celý proces součtem položek za jednotlivé etapy. Také multiplikativní kriteria (např. pravděpodobnost úspěšného přechodu je dána součinem pravděpodobností dílčích přechodů) je možno převést na additivní pomocí logaritmů. Budeme tedy předpokládat, že Z = z1+ z2+ z3+ ...+ zm
5.2 Princip dynamického programování Dynamické programování převádí úlohu nalezení maxima Z na mnohonásobně opakovanou úlohu hledání maxima pro jednotlivé etapy. Přitom se však nezapomíná na ostatní etapy. Naopak, řízení v každém kroku je vybíráno s ohledem na všechny možné důsledky v budoucnosti. Dynamické programování je tedy možno považovat za plánování s uvažováním perspektivy, tedy plánování vycházející ze širších zájmů celého procesu. Mezi všemi etapami existuje však jedna, u které úzké zájmy jednoho kroku se ztotožňují se zájmem celého procesu. Je to etapa poslední. Jestliže je tato optimálně navržena, můžeme se zabývat rozšířením problému o etapu předposlední, později o etapu předcházející atd. Proto se proces dynamického programování vždy z hlediska času rozvíjí od konce k počátku. Nejprve se plánuje poslední etapa. Protože však není známo, jak skončila předposlední etapa, musíme udělat o výsledku předposlední etapy celou řadu předpokladů. Pro každý z předpokladů pak musíme určit optimální řízení v poslední etapě. Toto můžeme nazvat podmíněným optimálním řízením. Princip dynamického programování požaduje nalezení podmíněného optimálního řízení pro libovolný možný výsledek předchozího kroku. Procesy a jejich stavy charakterizujeme celou řadou proměnných. Množinu hodnot těch proměnných, které ovlivňují budoucí chování procesu nazveme stav procesu (řízené soustavy). Například při řízení dopravního prostředku můžeme za stavové proměnné považovat: polohu, orientaci v prostoru, rychlost, hmotnost prostředku, otáčky motorů, zařazený rychlostní stupeň a podobně. Chceme-li vysokou přesnost, pak se počet proměnných vztahujících se k požadovaným veličinám může zvýšit (teplota, vlhkost, atd.). Do charakterizované soustavy je účelné zahrnout i vlivy nejbližšího okolí, které chování ovlivňuje. Pokud bude počet složek vektoru stavu nedostatečný, projeví se to tím, že při opakovaných pokusech se stejným výchozím stavem a při stejném řízení se nebude soustava pokaždé chovat stejně. Toto bude signalizovat nutnost najít další proměnnou, jejíž hodnoty chování ovlivňují. Stavem procesu v určitém čase budeme tedy rozumět vektor z hodnot jednotlivých stavových proměnných. Stav m-etapového procesu po i-té etapě označíme si. Jednotlivé hypotézy o tomto stavu označíme 1si, 2si, ... . Předpokládejme, že pro každý hypotetický stav po předposlední etapě (tedy s indexem m-1) jsme našli podmíněné optimální řízení v poslední etapě s označením ( * bude označovat optimálnost): um*(1sm-1), um*(2sm-1), ... ., um*(jsm-1) Tedy poslední etapa je optimalizována pro libovolný stav po etapě předposlední. Můžeme přejít k určení optimálního řízení v předposlední etapě. Znovu vytvoříme hypotézy o stavu po ukončení etapy s indexem "m-2". Podmíněné optimální řízení v předposlední etapě však musíme navrhnout tak, aby - současně s již vybraným řízením v poslední etapě zajistilo optimální řízení z hlediska maxima kriteriální funkce ve dvou posledních etapách. Tedy musíme pro každý hypotetický stav před předposlední etapou: Zjistit možná řízení a na základě hodnoty kriteriální funkce v předposlední etapě a optimální hodnoty kriteriální funkce pro poslední etapu (pro stav, do kterého se soustava dostane na základě předposledního řízení) stanovit možnou hodnotu kriteriální funkce pro obě poslední etapy. Budeme ji označovat pomocí " + ": Zm-1,m+(sm-2, um-1) = zm-1(sm-2, um-1) + Zm*(sm-1) Z možných řízení vybrat takové, aby hodnota kriteriální funkce pro předposlední etapu byla maximální: Zm-1,m*(sm-2) = max {Zm-1, m+(sm-2, um-1)} um-1 Podobně postupujeme při hledání optimálního řízení ve 3. etapě od konce atd. U první etapy je situace jednoduchá, protože známe výchozí stav a nemusíme vytvářet hypotézy. Výsledkem je u determinovaných procesů jedna nebo několik optimálních stavových trajektorií přechodu z počátečního do konečného stavu (v krozměrném prostoru, kde k je počet stavových proměnných) a stejný počet optimálních trajektorií řízení ( v nrozměrném prostoru). U procesů s náhodnými prvky je výsledkem celá řada pravděpodobnostních trajektorií stavů a tabulka přiřazující všem možným stavům, do kterých se proces může dostat, optimální řízení v nejbližší etapě. Tuto část uzavřeme intuitivním principem optimálního chování, tak jak jej formuloval R. Bellman:
Pro jakýkoliv počáteční stav a řízení před daným okamžikem, rozhodnutí v daném okamžiku musí vycházet ze stavu soustavy v tomto okamžiku. Leží-li na optimální stavové trajektorii z počátečního do konečného stavu bod A, potom optimální trajektorie z bodu A do konečného stavu je totožná s původní optimální trajektorií mezi bodem A a konečným stavem.
5.3 Optimální zvyšování rychlosti a výšky Optimální režim přechodu letounů na novou rychlost a výšku při minimální spotřebě paliva může být řešen pomocí rovněž dynamickým programováním. Uvažujme nejprve maximálně zjednodušenou úlohu. Nechť je počáteční výška h0 a rychlost v0, konečné hodnoty hkon a vkon. Předpokládejme 4 etapy, ve kterých se bude měnit jen výška a 4 etapy jen se změnou rychlosti, celkem tedy 8 etap, ve kterých se bude měnit výška nebo rychlost. Je dána poslední část tabulky spotřeby paliva při jednotlivých změnách h nebo v pro 24 možných výchozích stavů. 1s hkon
...
• 14 •
…
14
…
• 11 •
…
11
…
•
…
8
…
•
…
9
…
•
12
15
•
13
•
8
•
•
14
•
13
• •
17
•
11
•
17
•
15
•
2s
7
•
3s
6
9 20
8 13
• 12
10 15
• 14
12
11 12
•
s8
7
13
11
10 10
15
13
10 11
• 14
12 9
1s
6
• 7
15
•
….……………………………………. h0 v0
vkon
Předposlední etapa může letoun přivést do stavu 1s7 nebo 2s7. V prvním případě je zjevné optimální řešení "zvýšit rychlost", ve druhém "zvýšit výšku". K uvedeným stavům bychom mohli připsat spotřebu: 17 a 14. Před předposlední etapou bude letoun ve stavu 1s6, 2s6 nebo 3s6. V prvním případě je jediná možnost "zvýšit rychlost", ve třetím "zvýšit výšku". Celkové spotřeby za dvě poslední etapy jsou 32 a 26. Ze stavu 2s6 jsou 2 možnosti: "zvýšit výšku" - pak je celková spotřeba 30 nebo "zvýšit rychlost"- pak bude spotřeba 31. Minimální je varianta "zvýšit výšku" s hodnotou 30. Podobně bychom řešili 6. etapu a potom 5., 4. a další až k první. Označíme-li dílčí rozhodnutí "zvýšit rychlost" pomocí r a druhé rozhodnutí pomocí v, dostaneme optimální trajektorii řízení (v, v, r, r, r, r, v, v). Předpokládejme nyní, že obě proměnné se mohou měnit současně. Dostaneme rozšířenou tabulku, ve které budou i spotřeby pro povel rv. Postup se změní jen v tom, že v případech používání povelu rv budeme navazovat nikoliv na stavy další etapy, ale na stavy po dvou "jednoduchých" etapách. Například při řešení optima ze stavu 2s budeme vybírat ze tří variant: 30, 31 nebo spotřeba při povelu rv a přecházet do stavu s nebo s . 6 7 8 K danému příkladu můžeme vytvořit i obrácenou úlohu, ve které bychom hledali optimální přechod ze stavu s8 do stavu s0 a tabulkové hodnoty by byly stejné. Tedy původní úlohu můžeme v tomto případě řešit i postupem "od počátku ke konci".
5.4 Optimální rozdělování zdrojů Uvažujme 2 odvětví výroby I a II a celkové období m let, ve kterém chceme optimálně rozdělit zdroje mezi obě odvětví. Prostředky x, vložené do oblasti I dají za jeden rok zisk f(x) = x2, hodnota prostředků za jeden rok klesne na p(x) = 0,75x. Prostředky y vložené do oblasti II dají za jeden rok zisk g(y)= 2y2, hodnota těchto prostředků klesne na r(y) = 0,3y. Výchozí celkové prostředky označíme s0, celkové prostředky před poslední etapou sm-1, před předposlední etapou sm-2, atd. Prostředky vložené do odvětví I v poslední etapě označíme xm, v předposlední xm-1, atd. Podobně pro II odvětví budeme mít ym, ym-l atd. V tomto případě budou fáze řešení odpovídat etapám procesu od konce, obrácený postup možný není. Pro poslední etapu bude optimální hodnota xm*(řízení v poslední etapě) dána hodnotou xm, při které bude mít zisk v této etapě maximální hodnotu: Zm*(sm-1) =
max
{zm(sm-1, xm)}
0 ≤ xm ≤ sm-1
kde zm(sm-1, xm) = xm2 + 2(sm-1- xm)2 Poslední závorka vyjadřuje prostředky pro ym. Hodnota prostředků po poslední etapě nás již nezajímá. Z průběhu funkce vyplývá, že maximum je v krajním bodě pro xm = 0 = xm*. Tedy v poslední etapě musí být všechny prostředky vloženy do odvětví II. Zisk bude Zm*= 2sm-12. Přejdeme k problému předposledního roku. V předposledním roce bude řízením xm-1, které se může pohybovat v rozmezí 0 až sm-2. Maximální zisk za poslední 2 roky bude dán vztahem: Zm,m-1*(sm-2) = max {xm-12+ 2(sm-2 - xm-1)2 +Zm*(sm-1)} 0 ≤ xm-1≤ sm-2 Jak vyplývá z výrazů pro p(x) a r(y) platí sm-1 = 0,75xm-1 + 0,3(sm-2 - xm-1) Zisk v poslední etapě tedy bude Zm*(sm-1) = 2(0,75xm-1+0,3(sm-2 - xm-1))2. Po dosazení posledního vztahu do rovnice pro Zm,m-1*(sm-2) dostaneme celkový výraz pro proměnnou xm-1 a z grafu funkce vyplyne, že maximum je opět na levém okraji tj. pro xm-1= 0 = xm-1*. Pro tuto hodnotu dostáváme maximální zisk ze dvou posledních etap Zm,m-1*= 2,18 sm-22. Přejdeme k plánování pro rok m-2. Dostaneme obdobně: Zm-2,m-1,m* = max {xm-22+ 2 (sm-3 - xm-2)2 + 2,18 ( 0,75xm-2+ xm-2 + 0,3(sm-3 - xm-2))2} Pro tento případ platí xm-2* = sm-3 , tedy všechny prostředky budou vloženy do prvního odvětví. Dále platí Zm-2,m-1,m* (sm-3) = 2,23 sm-32 Podobným způsobem bychom zjistili, že i pro všechna předcházející období je optimální vkládat všechny prostředky pouze do prvního odvětví. Tedy optimální rozdělování je dáno sekvencí (..., I, I, I, II, II). Například při pětiletém období by původní prostředky s0 po prvním roce klesly na 0,75s0, po druhém na 0,56s0, po třetím na 0,42s0, po čtvrtém na 0,13s0 a po pátém na 0,04s0. Celkový zisk by byl za 5 let 2,27 s0.
5.5 Nejvýhodnější cesta Uvažujme síť cest s 9 uzly a těmito spoji, které nejsou orientované: AB(doba trvání přesunu 9 jednotek času), AC(11), AD(4), BF(8), BC(1), CF(5), CG(3), CE(1), DE(2), EG(6), EI(12), FH(2), FI(2), GH(4), HI(2). Chceme přejít z A do I, počet etap může být 3 nebo větší. Jednotlivé fáze hledání tedy nemůžeme přiřadit etapám cesty. Můžeme však postupovat takto: 1. Přiřadíme dobu přesunu všem místům, ze kterých se můžeme dostat do I jedním krokem. 2. Přiřadíme nejkratší dobu přesunu všem místům, ze kterých se dostaneme do I jedním nebo dvěma kroky. 3. Přiřadíme nejkratší dobu přesunu všem místům, ze kterých se dostaneme do I jedním, dvěma nebo třemi kroky. ….. Postup budeme opakovat tak dlouho, až se dostaneme i do bodu A a další fáze nepřinese zkrácení celkového ani dílčích časů. Při uvedeném postupu vždy účelně použijeme výsledků předchozí fáze. Výsledky postupu jsou v tabulce. Tento případ se dá řešit i obráceně tj. od A do I. 1. fáze doba směr
2. fáze doba směr
3.f áze doba směr
4. fáze
5. fáze
6. fáze
doba směr
doba směr
doba směr
A
-
-
-
-
18
D
17
B
14
D
14
D
B
-
-
10
F
8
C
8
C
8
C
8
C
C
-
-
7
F
7
F
7
F
7
F
7
F
D
-
-
14
E
14
E
10
E
10
E
10
E
E
12
I
12
I
8
C
8
C
8
C
8
C
F
2
I
2
I
2
I
2
I
2
I
2
I
G
-
-
6
H
6
H
6
H
6
H
6
H
H
2
I
2
I
2
I
2
I
2
I
2
I
Jak vyplývá ze sloupců pro 6. fázi je optimální cesta dána posloupností (A, D, E, C, F, I). Také zpáteční cesta stejnou trasou je nejkratší.
5.6 Stochastické procesy Ve všech předcházejících případech se jednalo o řízení v otevřené smyčce, řízení jednoznačně určovalo výsledek každé etapy, nebylo nutné zjišťovat případné odchylky od předpokladu. Šlo tedy o determinované procesy na které nepůsobila ani statická poruchová veličina. Optimální trajektorie (jedna nebo i více se stejnou optimální hodnotou kriteriální funkce Z) udávaly rozhodování v každém uzlu nebo etapě. U stochastických procesů je situace odlišná. V každé etapě, i při optimálním řízení, víme jen přibližně do jakého stavu se řízená soustava může dostat. Na základě celé řady pokusů však často můžeme stanovit, pro každý stav a použité řízení, pravděpodobnosti přechodu do všech dalších stavů, případně i pravděpodobnosti dosažení určité hodnoty kriteriální funkce Z. Budeme se zabývat zjednodušeným případem pouze s konečným počtem variant, které mohou při každém stavu a použitém řízení nastat. U každého stavu budeme uvažovat několik možných řízení , které označíme 1u, 2u, 3u atd. Každému z uvedených řízení bude přiřazena množina trojic (nový stav, dílčí hodnota kriteriální funkce, pravděpodobnost přechodu do uvedeného stavu s uvedenou hodnotou kriteriální funkce). Například bude známo, že ze stavu A se při řízení 2u dostane soustava s pravděpodobností 0,2 do stavu B za cenu 3,2, s pravděpodobností 0,3 do B za cenu 5,4 a s pravděpodobností 0,5 do stavu C za cenu 7,1, atd. Z uvedeného je zřejmé, že u stochastických procesů nebude existovat jedna, stále stejná, optimální trajektorie stavů. Také nebude existovat stále stejná posloupnost optimálních řídících povelů. Pro každý stav, do kterého se
může stochastický proces dostat ve kterékoliv etapě, však můžeme určit optimální řízení pro nejbližší etapu. Výsledkem tedy bude optimální přiřazení řízení všem možným stavům soustavy. Pokud na základě experimentu zjistíme, že pro daný stav a dané řízení soustava s pravděpodobností 0,5 přejde do jiného stavu X a že tento přechod je s pravděpodobností 0,2 za cenu 5, s pravděpodobností 0,4 za cenu 7 a s pravděpodobností 0,4 za cenu 10, potom bude účelné přiřadit danému stavu a řízení střední hodnotu ceny, kterou označíme Z. Bude platit Z = 0,2 . 5 + 0,4 . 7 + 0,4 . 10 = 7,8 Z uvedeného vyplývá, že i u výše uvedeného příkladu se spokojíme s přechodem z A do B s pravděpodobností 0,5 za cenu se střední hodnotou 4,52. Protože střední hodnota součtu náhodných proměnných je rovna součtu středních hodnot jednotlivých proměnných, bude pro celkovou hodnotu kriteriální funkce Z pro additivní kriterium platit Z = z1 + z2 + z3 + ...+ zm. V první fázi řešení pomocí dynamického programování se budeme zabývat poslední etapou procesu. Pro každý předpokládaný stav po předposlední etapě najdeme řízení s maximální hodnotou Zm. Můžeme psát Zm*(sm-1) = max {Zm(sm-1, um)} um Ve druhé fázi řešení se budeme zabývat předposlední a poslední etapou procesu. Pro každý předpokládaný stav sm-2 najdeme optimální řízení s maximální hodnotou Zm,m-1 podle vztahu Zm,m-1*(sm-2) = max {Zm(sm-2, um-1) +sZm*(sm-2, um-1)} um-1 * kde sZm je představitelem střední hodnoty středních hodnot Zm pro různé stavy sm-1, které při konkrétním řízení um-1 nastávají s určitými pravděpodobnostmi po předposlední etapě. V obecné fázi řešení pro etapy i, i+1, ..., m procesu budeme hledat pro všechny předpokládané stavy si-1 optimální řízení podle vztahu Zi,i+1,..,m*(si-1) = max {Zi(si-1, ui) + sZi+1,..,m*(si-1, ui)} ui Také v tomto případě poslední člen v rovnici reprezentuje "dvojnásobnou" střední hodnotu s uvážením pravděpodobností přechodů do stavů si při daném řízení ui. 5.7 Příklad stochastického procesu Uvažujme proces se stavy A, B, C, D, E, F. Při řízeních 1u až 6u dochází k přechodům do nových stavů s určitým ziskem a pravděpodobností podle tabulky:
A B C D E
1u B 7/0,4 C 4/0,6
2u B 6/0,7 C 3/0,3
3u
D E D E
5/0,3 7/0,7 4/0,4 6/0,6
4u
5u
6u
D 2/0,6 E 5/0,4 D 4/0,7 E 5/0,3 F 3/0,6 F 6/0,4 F 4/0,5 F 10/0,5
F 4/0,7 F 8/0,3 F 4/0,8 F 8/0,2
Hledáme trajektorii s maximálním ziskem, m = 3. Platí: Z3(D,5u) = 3 . 0,6 + 6 . 0,4 = 4,2 Z3 (D, 6u) = 4 . 0,7 + 8 . 0,3 = 5,2 Z3*(D, u3) = 5,2 / 6u Z3*(E, u3) = 7/ 5u Z2,3(B,3u) = 5 . 0,3 + 7 . 0,7 + 0,3 . 5,2 + 0,7 . 7 = 12,86 Z2,3(B,4u) = .... = 9,12 Z2,3*(B, u2) = 12,86 / 3u Z2,3*(C, u2) = 11,48 /3u Z1,2,3(A,1u) = 7 . 0,4 + 4.0,6 + 0,4 . 12,86 + 0,6 . 11,48 = 17,232 Z1,2,3(A,2u) = ... = 17,546 Z1,2,3*(A, u1) = 17,546 / 2u Dostáváme tak tabulku optimálního řízení: A
B
C
D
E
2u
3u
3u
6u
5u
Budeme-li vycházet z uvedené tabulky, pak při mnohonásobně opakovaném průchodu z A do F budeme mít průměrný zisk blížící se vypočítané hodnotě.
