14.1.2014
Čtrnáctá kapitola Dostatečně všeobecné teorie řízení, první část textu. Doporučuji materiálu věnovat zvýšenou pozornost, i když se zpočátku může dostavit pocit "a s čím to má co společného?"... má, a velmi. Brzy bude zveřejněn text o praktickém využití této metody Puškinem v jeho tvorbě.
Verze ke stažení (text + poznámky pod čarou): DVTR Kapitola 14-1.pdf
Online verze (neobsahuje poznámky pod čarou):
14. Metóda dynamického programovania ako algoritmické vyjadrenie
dostatočne všeobecnej teórie riadenia
Pri vy-svetlo-vaní podstaty metódy dynamického programovania sa opierame o knihu „Kurz teórie automatického riadenia“ („A Course in Automatic Control Theory” autor Robert Pallu de La Barrière, vydanie z r. 1966), aj keď priamo neopakujeme jeho formulácie. Jednotlivé teorémy (poučky, tézy) sú prevzaté aj z publikácie „Operačná analýza“ od J. P. Zajčenka (Kyjev, Vysoká škola r. 1979).
Metóda dynamického programovania je funkčná, pokiaľ formálna interpretácia reálnej úlohy umožňuje splniť nasledujúce podmienky:
-
Skúmaná úloha môže byť formulovaná ako N-krokový proces, opísateľný vzťahom:
Xn + 1 = f(Xn, Un, n), kde
n — číslo jedného z množstva možných stavov systému, do ktorého on prechádza po
zavŕšení n-tého kroku;
Xn — stavový vektor systému patriaci spomínanej n-tej množine (n-tej v poradí množine);
Un — riadenie, vypracované v kroku n (krokové riadenie), prevádzajúce systém z jeho
možného stavu v n-tej množine v jeden zo stavov (n + 1) množiny. Pre názornú
predstavu je potrebné si pozrieť obr. 4., o ktorom sa budeme baviť neskôr.
-
Štruktúra úlohy sa nesmie meniť pri zmene predpokladaného počtu krokov N.
-
Rozmer priestoru parametrov (t.j., doplnenie, alebo odobratie ďalšej veličiny, príp. veličín (teploty, farby, afinity, lásky...) znamená vznik novej situácie, iného stavového modelu systému), opisujúceho stav systému, sa nesmie meniť v závislosti od množstva krokov N.
-
Výber riadenia na ľubovoľnom kroku (z N-krokov) nesmie popierať (negovať) voľbu riadenia na predchádzajúcich krokoch.(zákon zachovania kontinuity).
Inými slovami: optimálny výber, po prvé - cieľov a po druhé - spôsobu riadenia v ľubovoľnom z možných stavov, musí byť podmienený (určený) parametrami skúmaného stavu, a nie parametrami procesu, priebehom ktorého systém do skúmaného stavu prišiel.
Čisto formálne:
Ak jednému stavu zodpovedajú rôzne jemu predchádzajúce deje jeho vzniku, vplývajúce na nasledujúci výber optimálneho riadenia, tak metóda umožňuje začleniť (zahrnúť) popis predchádzajúcich dejov do stavového vektora. To vedie k zväčšeniu rozmeru stavového vektora (matice = 2D, tenzoru pri 3D) systému. Po tejto operácii sa to, čo bolo do jej prebehnutia opisované ako jeden stav, stáva množinou stavov, odlišujúcich sa jeden od druhého komponentami stavového vektora, opisujúceho predchádzajúce deje vývoja procesu.1
-
Kritérium optimálneho výberu následnosti (schémy, eng. “managing schedule“) krokových (pre jednotlivé kroky) riadení Un a zodpovedajúcej trajektórie v priestore formálnych parametrov má tvar (formu mier): V = V0(X0, U0) + V1(X1, U1) + …+ VN - 1(XN- 1, UN - 1) + VN(XN)
Kritérium V nazývame plnou výhrou (ú-Spěchom)2, a ju tvoriace (do nej zarátavané) súčasti - krokovými výhrami (splnenými čiastkovými cieľmi)3. Pri úlohe je potrebné nájsť postupnosť krokových riadení Un a trajektóriu, ktorým zodpovedá maximálna z možných plných výhier. Vo svojej podstate, plná „výhra“ V, je mierou CELKOVEJ kvality riadenia procesu. Výhry (úspechy) pri jednotlivých krokoch, aj keď sú súčasťou miery kvality celkového riadenia procesu, však vo všeobecnosti nie sú mierami kvality riadenia na im prislúchajúcich krokoch. Uvedená metóda je totiž predurčená k optimalizácii celkového riadenia procesu. Preto sú efektívne krokové riadenia s veľkou krokovou (momentálnou) výhrou, ale ležiace mimo optimálnej trajektórie (cesty), nezaujímavé. Štruktúra metódy NEzakazuje v nevyhnutnosti použiť pre každý krok iné kritérium stanovenia (definovania) krokovej výhry Vn, odlišné od kritérií prijatých pri druhých krokoch.
Index n je ukazovateľ určujúci početnosť (množstvo jednotlivých položiek, parametrov) možných stavových vektorov. V praktických úlohách s ním môže byť zviazaná nejaká premenná (premenlivý parameter), napr.: čas, dráha, sila, spotreba zdrojov, farba, nervozita, atď.
T.j., metóda je použiteľná nie len na optimalizáciu riadenia procesov plynúcich v „čase“, ale aj k úlohám optimalizácie mnohovariantného jednorázového (súčasného, momentálneho, paralelného s aktuálnym časom), alebo čas nevnímajúceho (neberúceho čas do úvahy, na čase nezávislého, resp. nereagujúceho na časovo4 podmienené zmeny) riešenia. Samozrejme za predpokladu, že takéto „bezčasové“ (nadčasové), „neprocesné“ úlohy pripúšťajú ich viackrokovú interpretáciu.
Teraz sa obrátime k obrázkom 4 – 6, opakujúcim vzájomne previazané (súvisiace) obr. 40, 41, 42 z kurzu teórie automatického riadenia R. P. de La Barrièra.
Obr. 4. K podstate metódy dynamického programovania.
Mat(r)ica možností.
Na obr. 4 sú znázornené:
«0» - počiatočný stav systému.
«1», «2», «3» - množiny jeho možných následných stavov, a taktiež možné prechody
z každého možného stavu do druhých možných stavov.
To vše rovněž připomíná mapu (ve smyslu šachovnice) stolní dětské hry, po které se přemísťují žetóny: každému přechodu - kroku odpovídá jeho kroková výhra, a v proces ukončující třetí množině, každému ze stavů systému je přidáno jeho vyhodnocení, umístěno v obdélníku.
Zásadní rozdíl od hry je v tom, že hádání výběru cesty v dětské hře, prováděno házením kostkami nebo točením se káči (vĺčka) a pod., je v reálném řízení nepřípustné, nakolik je to – postoupení (předání) účelového řízení těm silám, které jsou schopny řídit (ovládat) padání kostek, točení se káči a pod., t.j. těm silám, pro které je ve hře vybraný „generátor nahodilostí“ dostatočně (ve vztahu k jejich cílům) říditelné zařízení (mechanismus).
Jestli máme vybrat optimální řízení na prvním kroku, tak je nevyhnutné předvídat všechny jeho důsledky v následujících krocích. Proto popis algoritmu metody dynamického programování často začíná z popisu výběru řízení na posledním kroku vedoucím do jedného z dokončujících stavů procesu. V tomto případě poukazují na „pedagogickou praxi“, která dokazuje, že argumentace při popisu algoritmu od konečného stavu k počátečnímu se lehčeji chápe. Opírá se totiž o jako kdyby už poskladané (vzniklé, existující) podmínky (okolnosti, situace) k počátku skoumaného kroku, pričemž jsou zároveň možné varianty ukončení procesu taktéž stanovené.
Obrázek 5. K podstatě metody dynamického programování.
Analýza přechodů.
Na obr. 5 se v souladu s tím analyzují možné přechody do konečné množiny stavů „3“ z každého možného stavu v jemu předcházející množině stavů „2“, jako kdyby celá předcházející dráha byla už u konce a zůstalo by posledním výběrem optimálního krokového řízení celý proces završit. Při té příležitosti se pro každý ze stavů v množině „2“ definují (stanovují) všechny plné výhry (s-/na-plnení konečných cílů) jako součet = „hodnota (vyhodnocení) přechodu“ + „hodnota (vyhodnocení) záverečního stavu“. V množině5 „2“ ze získaných pro každý ze stavů, v něm možných plných výher, se určuje a zapamatovává maximální plná výhra a jemu přislouchající přechod (fragment trajektorie). Maximální plná výhra pro každý ze stavů v množině „2“ je umístěna do pravoúhlého rámečku a jemu přislouchající přechod je označen šipkou. Takových optimálních přechodů jednoho stavů do jiných, kterým přináleží jedno a totéž označení plné výhry, se v zásadě může vyskytnout i několik. V tom případě jsou všechny v metode nerozeznatelné a jeden ekvivalentní druhému, ve smyslu postaveného kritéria optimálnosti výběru trajektorie v prostoru parametrů, kterými se opisuje systém.
Poté množinu „2“, předcházející množině „3“, která proces zakončuje, možno skoumat jako (v kvalitě) zakončující, jelikož jsou známé vyhodnocení každého z její možných stavů (maximální plné výhry - koncové výstupy). Další optimalizace posloupnosti krokových řízení a výběr optimální trajektorie mohou být uskutečněny jenom na ještě neprozkoumaných množinách, které v optimalizačním procesu předchází úrovni „2“ (t.j. na úrovních množin „0“ a „1“).
Proces (procedúra), který(ou) ilustruje obr. 5 je tímto způsobem funkční na každém algoritmickém kroku metody při přechodech z n-té do (n–1)-té množiny, počínaje od zakončující N-té množiny do počátečního stavu systému.
V důsledku postupného párovýho (sekvenčního) skoumání množin, při procházení celého jejich souboru se projevuje optimální posloupnost návaznosti jedotlivých krokových řízení, maximálna možná plná výhra a jim přislouchající trajektorie. Na obr. 6 je zesílenou linií znázorněna optimální trajektorie pro rozebíraný případ.
Obr.6 K podstate metódy dynamického programovania
Optimálna trajektória
V skúmanom prípade je kritériom optimálnosti súčet krokových výhier. Kritérium optimálnosti však môže byť konštruované aj ako vytvorenie (strojenie, súčin) v každom prípade nezáporných sú-činiteľov (koeficientov).
Z matematiky na základnej škole vieme, že výsledok (súčet, alebo súčin) sa nemení pri zmene postupnosti operácií so sčítancami, alebo sú-činiteľmi. Preto je algo-rytmus funkčný aj pri preberaní (kontrole) množín možných stavov v poradí, inverznom (opačnom) k vyššie rozoberanému, t.j. od východiskového – pôvodného, ku konečnému - záverečnému. T.j. pri pohľade na situáciu „z opačného konca“, obrátenie situácie „z východu na západ“, od začiatku ku koncu, k záverečnej množine (úrovni) možných stavov... od konca k začiatku situácie = re-flexia, k(a)atar(a)zia chronologickej priority... inak aj tzv.“Cestovanie v čase“.
Ak sú množiny (úrovne vývoja) možných stavov usporiadané v chronologickej postupnosti, môže byť schéma výpočtu zostrojená jak z prítomnosti (aktuálneho stavu) smerom do prognostikovateľnej jednoznačnej budúcnosti, tak aj z prognostikovateľnej jednoznačnej budúcnosti do aktuálnej objektívnej reality (prítomnosti). Táto okolnosť (podmienenosť) hovorí o 2 neformálnych vzťahoch v praktickom živote, nachádzajúcich sa mimo uvedeného algoritmu:
-
Metóda dynamického programovania (MDP) je formálne-algoritmicky necitlivá k charakteru príčinno-dôsledkových podmieneností. Konkrétne: MDP nerozlišuje príčiny od následkov. Z tohto dôvodu by sa mala každá konkrétna interpretácia (vy-svetlenie) Metódy v praktických úlohách formovať s neformalným zohľadnením skutočných podmieneností dôsledkov príčinami.
-
NEEXISTUJE MANAŽÉRSKY VÝZNAMNÝ ROZDIEL MEDZI REÁLNOU PRÍTOMNOSŤOU A VYBRANOU BUDÚ-CNOSŤOU, za predpokladu, že prognostika je v súlade s hierarchicky vyšším objemnejším riadením a do neho vložené (IT: zapuzdrené) čiastkové riadenie je uskutočňované kvalifikovane. T.j., ak proces čiastkového (v rámci celku) riadenia plynie v súlade s hierarchicky vyšším objemnejším riadením.
Proces je celostný (komplEXno-komplETný). Z tohto dôvodu chráni, ešte z nejakej príčiny neuskutočnená, avšak už morálne vybraná a objektívne Zhora NEzakázaná budú-cnosť v realizovanej prítomnosti tých, ktorí ju tvoria (s-Troja) na všetkých úrovniach:
Počínajúc od ochrany psychiky pred pokušeniami (klamom), až po ochranu pred cieľavedomou „fyzickou“ agresiou6. T.j., pokiaľ je matrica možných stavov (ona ale je matricou možných prechodov) vybraná v súlade s hierarchicky vyšším objemnejším riadením, je ona sama ochranou a zbraňou, prostriedkom riadenia, na ktoré je automaticky uzavretých (napojených a „zamknutých“) všetkých 6 priorít prostriedkov zovšeobecnených zbraňových systémov a riadenia (manažmentu).
Objektívna existencia mat(r)íc možných stavov a prechodov sa prejavuje v tom, že v slepote možno „zablúdiť“ do nejakých matríc prechodu a pocítiť na sebe ich objektívne vlastnosti. Subjektívne ich posudzujeme, v závislosti od vzťahu k týmto vlastnostiam, ako obdobia:
-
výnimočného (jedinečného, zriedkavého) šťastia, či
-
nudného „kolotoča“ stereotypov, alebo
-
krutého, surového nešťastia.
No, pre používanie MDP (metódy dynamického programovania) a jej osvojenie sprevádzajúcich algorytmicky neformalizovaných prejavov mat(r)íc prechodu v každodennom živote, je nevyhnutné DODRŽAŤ TO HLAVNÉ z podmienok:
V úlohách optimalizácie procesov riadenia je MDP - metóda dynamického programovania
V skutočnosti (v realite) by tento zavŕšujúci (vrcholný, koncový) určitý stav mal byť vedome udržateľným a prijateľným procesom, ktorý objíma a zahŕňa uvedenou metódou optimalizovaný čiastkový proces. Avšak výber a definovanie (presné určenie) príslušných charakteristík procesu, do ktorého má riadený (manažovaný) systém po zavŕšení algoritmu danej metódy vojsť, sa nachádza v oblasti „mystiky“, alebo v oblasti metód, vyvinutých vo svojej podstate v NEmatematických náukach a remeslách (po h´ellénsky: „techné“).
„Nech akýkoľvek by bol stav systému pred nasledujúcim krokom, je nevyhnutné vyberať riadenie na tomto kroku tak, aby výhra (úspech) na danom kroku plus optimálna výhra (úspech) na všetkých následných krokoch bola MAXIMÁLNA“ - cit.: E.S.Wentcel „Operačná analýza. Úlohy, princípy, metodológia.“(M.,“Science“, r. 1988, str.109)
Neschopnosť určiť (definovať) cieľový vektor riadenia (ktorého dosiahnutím sa má zavŕšiť danou metódou optimalizovaný proces) a (alebo) neschopnosť zistiť východzí stav objektu riadenia, neumožňuje postupovať podľa tohto, vyššie v citáte uvedeného, odporúčania. Zároveň táto neschopnosť objektívne uzaviera možnosti využitia metódy dynamického programovania, keďže začiatok a koniec procesu (presnejšie jeho konkrétnej sekvencie) musia byť určené v priestore parametrov, na ktorých je zostrojený matematický (alebo iný) model metódy. Ten zas má byť metodologicky udržateľný (v zmysle predikcie - predpovedateľnosti), čo je základom jeho vzťahu s realitou.
Je to vo vzťahu k nasledujúcim mnohovariantným krokovým prechodom o to spravodlivejšie, čím viac mat(r)ica možných stavov spadá pod známe ľudové príslovie: “Všetky cesty vedú do „Ríma“, a ktoré do „Ríma“ nevedú, nevedú nikam... t.j. vedú do „nebytia“ – do neexistencie. Ak je pre takýto druh procesov vybraný udržateľný cieľ, ku ktorému vedie množstvo trajektórii (ciest), tak sa pri udržateľnom krokovom riadení „rozptyl“ (rozostup) medzi optimálnymi trajektóriami (idúcimi k rovnakému cieľu z rôznych počiatočných pozícii) zmenšuje. Prebieha nevyhnutná aproximácia (krokové približovanie) až do úplného zjednotenia optimálnych trajektórií v istom konkrétnom, matematicky predpovedateľnom kroku. Toto tvrdenie je tým spravodlivejšie, čím lepšie určíme v objektívnom priestore tendencií vývoja parametrov stav konkrétneho vektora zavŕšujúceho zvolený proces. Ako analógiu by sme v ma-thématike vyššie uvedený jav mohli nazvať asymptotickou množinou trajektórií ...a asymptotičnosť množiny trajektórií je vyjadrená tým, že: „všetky cesty vedú do „Ríma“ – v „RIM“...“
...