A Bellman Optimalitási Elve 1
A személy megtanulhatja a képességeket, csak miután megpróbálta beilleszteni őket. (Seneca)
A Bellman optimális elve lehetővé teszi, hogy megoldja vagy megértse a valós életben felmerülő számos érdekes problémát, például egy generáló vállalat (CHPP, HPP) racionális működésének problémáját, az egységek gazdaságos összetételének megválasztását,
A vízerőművekben és a hőerőművekben történő üzemeltetés során szükségessé válik az egységek rendszeres leállítása, amikor a terhelés csökken, és a tartalékos egységek be vannak kapcsolva, ha a terhelés nő. Az egyes aggregátumok működésbe való bevonása befolyásolja a rendszer tartalékainak összegét és elhelyezését, az elektromos hálózat módját, a rendszerközi vezetékek áramlását, az üzemanyag-fogyasztást stb.
Ha az állomáson n egységek vannak, és mindegyik lehet be- vagy kikapcsolva, akkor az összes lehetőség az egész hatalommal történő működtetéshez 2 az n erejéig.
Még n = 50 esetén az opciók száma nagyon nagy lesz!
Általában ezek a problémák nem lineárisak, egészek, több szélsőségek, az aggregátumok összetételét befolyásolja az elektromos hálózatok módja, amelyet statisztikai módszerekkel kell értékelni és előrejelezni. Az ilyen problémák megoldásához egy közönséges matematikai berendezés nem alkalmas.
Különleges esetekben a dinamikus programozás módszerei hasonló problémák megoldását teszik lehetővé a 20-30-as sorszámú aggregátumok számával.
Példákat adunk olyan problémákra, amelyekben a dinamikus programozás elve hatékonyan működik, és lehetővé teszi számunkra, hogy megtaláljuk az optimális megoldást.
A műveleti ütemtervre vonatkozó feladat egy erőmű. Az állomásnak L egysége van, egy egység teljesítménye és a generált villamos energia egységára.
A fizetett villamos energia ütemezése be van állítva, a redundánsan generált villamos energiát nem fizetik.
A munkakörülmények karbantartására, a megőrzési költségekre és az induló költségekre vonatkozóan vannak ismert kiadások. Meg kell határozni az optimális üzemmódot.
A beruházások és a források elosztásának problémái érdekesek.
A beruházások elosztásának problémája: több vállalkozás van, amelyek között meg kell osztani ezt a befektetési összeget. Ismeretes, hogy ez a pénzösszeg befektetése minden vállalkozásban hatékony.
Az erőforrás-allokáció problémája: vannak N vállalkozók, amelyek mindegyik bevételt hoznak, attól függően, hogy milyen arányban vannak az elosztott erőforrások. A legegyszerűbb mód az, ha egy korlátozott erőforrást egy x 1. xN (x 1 ≥ 0. xN ≥ 0, x 1 +. + X N ≤ a) töredékkel osztunk el közöttük.
A legjobb szállítási teher feladata: szállítás, teherbírással a. terhelt N típusok. Minden típusú rakománynak yi és zi súlya van.
Meg kell találni az optimális rakodási opciót, amelyben a fedélzeten vett tárgyak költsége maximális.
A kocsit felváltó feladat: egy tehergépkocsi-vállalat azt tervezi, hogy megvásárol egy autót és működtetik N évig.
Vásárolhatsz egy új autógyártást x 0 = 0 év és költség p. vagy az üzemi életkora 0 x 0 év volt, a működési idő függvényében.
Az autó működtetési mutatói a következők: f (t) - az évente gyártott termékek költsége a t évig tartó berendezéseknél; r (t) - a t évjáratú autó működésének költsége.
A működés folyamán az autót folyékony áron lehet értékesíteni, és újat vásárolhat. Az élet végén az autót folyékony áron is értékesítik. Határozza meg az autó optimális életkorát vásárláskor és az optimális ütemtervet a cserére.
Mindezek és sok más probléma megoldható Bellman optimalitásának elve alapján.
Hivatalosan leírjuk a Bellman-elvet és magyarázzuk meg a jelentését.
A kulcs a kezelt objektum fogalma, amelyre a Bellman-elv alkalmazható.
Legyen egy időben változó objektum, amelyen egy u (t) külső műveletet vagy vezérlést hajtunk végre. és x (t) e tárgy leírása t időpontban.
Ha a vezérlés addig ismert, amíg t1. tudva az x (t) leírását a t időpontban. egyedileg meghatározhatjuk az x (t) értékét bármely t> t1 esetén. akkor egy ilyen leírás teljesnek nevezhető.
A teljes leírást államnak hívják. a lehetséges állapotok halmaza - az állami tér.
Maga az objektum, amellyel a teljes leírás lehetősége ismeretes, dinamikus rendszer.
Csak az idők különálló pillanataira gondolunk, és ezekben a pillanatokban irányítják a rendszert.
Az xk állapotból a következő állapotba történő átmenethez olyan költség függvény társul, amely az xk állapotától függ. idő és alkalmazott kontroll.
Meg kell találnia egy ilyen kezdeti állapotot és olyan elfogadható szabályozást, amely a rendszert áthelyezi az egyik végső állapotba, így a teljes költség - amely egy adalékköltség függ az egyes lépésekben - minimális.
Tehát minden egyes lépésnél díjat fizetünk a választott kontrollhoz, majd összefoglaljuk és összefoglaljuk az egyes lépésekben elkészített táblát.
Ezért azt szeretnénk kezelni az objektumot, hogy a teljes költség minimális.
Ez a dinamikus programozás vagy a dinamikus rendszer vezérlése általános problémája.
Más szóval, mindegyik lépésben cselekvési programra van szükségünk, amely lehetővé teszi számunkra a költségek minimalizálását.
Az általános elv a következőképpen fogalmazódik meg: függetlenül attól, hogy a k lépésben ellenőrzött folyamat hogyan került az xk állapotba. Továbbá szükséges, hogy az optimális vezérlést az adott állapotra az utolsó (N - k) lépésben, az optimális folytatást figyelembe véve alkalmazzák.
Ez egyike a Bellman-elv lehetséges formuláinak, megfelelő állapotban.
Legyen Yk azoknak az állapotoknak a halmaza, ahonnan (az elfogadható kontrollok használatával) pontosan k léphetünk az X N végső készlet egyik állapotába.
Feltételezhetjük, hogy Y 0 = X N.
Vegyünk egy tetszőleges xN -k ∈Yk és hagyja Sk (xn -k) függvény írja le a függőség az optimális költség az állam xN -k k az utolsó lépéseket, amelyekkel a rendszer xn -k X N.
Az ilyen funkciókat Bellman-függvényeknek hívják.
Mivel az Y 1-es készlet xN -1 állapotában az XN-re való átmenet egy lépésben történik, az S 1 (x N -1) optimális költségfüggvény a következőképpen írható:
A második korlátozás szükséges egy adott végső XN elérésének garantálása érdekében.
Az uN értéke. amelynél a kapcsolat minimális értékét elérjük, az u * N (xN-1) értékkel jelöljük.
Könnyű megérteni (csináld!) Hogy az összes következő probléma Sk +1 (xN -k -1) optimális költsége rekurzívan fejeződik ki az előző Sk (xN -k)
u * N -k (xN -k-1) az a vezérlés, amelynél a (2) -ban szereplő minimális költségeket elérik.
Az u * k (xk-1) kifejezés minden pillanatra meghatározza az optimális vezérlési szabályokat a dinamikus folyamat aktuális állapotából származó függvények formájában, meghatározza az optimális szabályozási törvényt az optimális szabályozó állapot szerint.
Az optimális x * 0 alapállapot a következő probléma megoldásából nyerhető:
A (1) - (3) rendszert ismétlődő Bellman-egyenleteknek nevezzük.
Az optimális szabályozás explicit formában történő értékeit a következőképpen lehet meghatározni:
Az x0 kezdeti állapotból indulunk ki.