A dinamikus programozási módszer lényege. Dinamikus programozás és optimális vezérlés. A dinamikus programozás ötlete
A dinamikus programozási módszer lényege…………………………..4
Példa egy probléma megoldására a dinamikus programozási módszerrel…………………………………………………………7
Felhasznált források listája…………………………………………11
Dinamikus programozás. Alapfogalmak.
Dinamikus programozás (DP) a számítógépes rendszerelméletben az összetett problémák egyszerűbb részfeladatokra bontásával történő megoldásának módja. Alkalmazható az optimális alstruktúrával kapcsolatos problémákra, amelyek átfedő részproblémák halmazának tűnnek, amelyek összetettsége valamivel kisebb, mint az eredeti. Ebben az esetben a számítási idő a „naiv” módszerekhez képest jelentősen csökkenthető.
Ha mindegyik műveletet egy lépésre állítjuk, akkor meghatározzuk a két sor közötti szerkesztési távolságot. Rekurzív algoritmust definiálhatunk azzal a megfigyeléssel, hogy a karakterlánc utolsó karakterét egyeztetni, lecserélni, beilleszteni vagy törölni kell. A karakterek letiltása az utolsó szerkesztési műveletben azt eredményezi, hogy a párosítási műveletben egy pár kisebb sor marad. Ha ismernénk három pár kisebb sor szerkesztésének költségét, el tudnánk dönteni, melyik opciót eredményezi a legjobb megoldásés ennek megfelelően választja ezt a lehetőséget.
A dinamikus programozás kulcsgondolata meglehetősen egyszerű. Általános szabály, hogy egy adott probléma megoldásához a feladat egyes részeit (részfeladatokat) kell megoldani, majd a részfeladatok megoldásait egy általános megoldássá kell összevonni. Sok ilyen részfeladat gyakran megegyezik. A dinamikus programozási megközelítés szerint minden részproblémát csak egyszer kell megoldani, ezzel csökkentve a számítások számát. Ez különösen akkor hasznos, ha az ismétlődő részfeladatok száma exponenciálisan nagy.
Ezt az értéket egy csodálatos dologon keresztül ismerhetjük meg, amely rekurzív. Ez az algoritmus helyes, de hihetetlenül lassú is. Exponenciális időbe telik, mert újra és újra és újra újraszámolja az értékeket. Hogyan tehetjük tehát gyakorlatiassá az algoritmust? Fontos megjegyzés, hogy a legtöbb ilyen rekurzív hívás olyan dolgokat számít ki, amelyeket korábban már kiszámítottak. honnan tudjuk?
Ha az egyes párok értékeit táblázatban tároljuk, elkerülhetjük az újraszámítást, és szükség szerint egyszerűen megkereshetjük őket. A dinamikus programozási verzió három különbséggel rendelkezik a rekurzív verziótól. Először is, a rekurzív hívások helyett táblázatkeresések segítségével kapja meg köztes értékeit.
A dinamikus programozás egy olyan matematikai berendezés, amely egy bizonyos osztályú probléma megoldását úgy közelíti meg, hogy azokat kisebb vagy kisebb részekre bontja. összetett feladatok. Ugyanakkor megkülönböztető vonás a feladatok szakaszos, meghatározott időközönkénti, időszakonkénti megoldása, amely meghatározta a dinamikus programozás kifejezés megjelenését. Megjegyzendő, hogy a dinamikus programozási módszereket sikeresen alkalmazzák olyan problémák megoldásában is, amelyeknél az időtényezőt nem veszik figyelembe. Általánosságban elmondható, hogy a matematikai apparátus lépésről lépésre vagy lépésről lépésre programozható. A problémák dinamikus programozási módszerekkel történő megoldása az R. E. Bellman által megfogalmazott optimalitás elve alapján valósul meg: az optimális viselkedésnek az a tulajdonsága, hogy bármilyen legyen is a rendszer kezdeti állapota és a kezdeti megoldás, a későbbi megoldásnak kell meghatároznia az optimális viselkedést. a kezdeti megoldás eredményeként kapott állapothoz képest. Ebből az következik, hogy az egyes lépések tervezését a teljes folyamat befejezésekor elért összesített haszon figyelembevételével kell elvégezni, amely lehetővé teszi a végeredmény optimalizálását a kiválasztott kritérium szerint.
Ez lehetővé teszi számunkra, hogy ezt az eljárást a problémák szélesebb osztályára alkalmazzuk. Itt a legoptimálisabb részeredmények összegyűjtéséhez szükséges konkrét elemzés az, ami a megoldást "dinamikussá" teszi. Alternatív, teljes megoldás ugyanarra a problémára. Ez is "dinamikus", bár a kivitelezése más.
A fenti kép sokat beszél a dinamikus programozásról. Tehát jó dolog megismételni valamit, amire már van válasz? Erről szól a dinamikus programozás. Mindig emlékezzen azokra a részproblémákra, amelyeket már megoldott. lesz bizonyos pillanatokat, amikor a rendszer állapotát befolyásoló döntést kell meghoznunk, ami lehet, hogy előre nem ismert. Ezek a döntések vagy változtatások egyenértékűek az állapotváltozók transzformációjával.
Tehát a tágabb értelemben vett dinamikus programozás egy folyamat optimális vezérlése a szabályozott paraméterek minden lépésben történő megváltoztatásával, és ezáltal a folyamat előrehaladásának befolyásolásával, minden lépésben megváltoztatva a rendszer állapotát. Általánosságban elmondható, hogy a dinamikus programozás egy harmonikus elmélet, amely megérthető, és elég egyszerű ahhoz, hogy kereskedelmi tevékenységekben használhassuk lineáris és nemlineáris problémák megoldása során.
A dinamikus programozási probléma megfogalmazása
A korábbi döntéseink eredményei segítenek a jövőbeli döntések meghozatalában. Mit gondolunk ebből? Egy problémát egymást átfedő részproblémák sorozatára kell bontanunk, és megoldásokat kell alkotnunk az egyre nagyobb problémákra. Néhány jól ismert dinamikus programozási algoritmus.
A dinamikus programozás alapötlete az ismétlődő munka elkerülése a részeredmények emlékezésével, és ez a koncepció számos valós helyzetben alkalmazható. A dinamikus programozás csak egy divatos módja annak, hogy emlékezzen a dolgokra, hogy később időt takarítson meg!
A dinamikus programozás az optimális programozás egyik ága. Sajátos módszerek és technikák jellemzik olyan műveletekre, amelyekben a döntéshozatali folyamat szakaszokra (lépésekre) van felosztva. A dinamikus programozási módszerekkel variáns-optimalizálási problémákat oldanak meg adott optimalitási kritériumok mellett, a változók és a célfüggvény közötti bizonyos összefüggésekkel, amelyeket egyenletrendszerrel vagy egyenlőtlenségekkel fejeznek ki. Ebben az esetben, mint a lineáris programozási módszerekkel megoldott problémáknál, a korlátozásokat egyenlőségek vagy egyenlőtlenségek formájában is megadhatjuk. Ha azonban a lineáris programozási feladatokban a feltételfüggvény és a változók közötti függőségek szükségszerűen lineárisak, akkor a dinamikus programozási feladatokban ezek a függőségek nemlineárisak is lehetnek. A dinamikus programozás felhasználható mind a folyamat vagy rendszer dinamikájával kapcsolatos problémák megoldására, mind a statikus, például erőforrás-allokációval kapcsolatos problémák megoldására. Ez jelentősen kibővíti a dinamikus programozás hatókörét a vezérlési problémák megoldására. A megoldási folyamat egyszerűsítésének lehetősége pedig, amelyet a vizsgált terület és szám korlátozásával érünk el, amikor a lehetőségek következő szakaszára lépünk, növeli ennek a módszerkészletnek az előnyeit.
Dinamikus programozás és rekurzió. A dinamikus programozás alapvetően rekurzió, plusz a józan ész használata. Ez azt jelenti, hogy a rekurzió lehetővé teszi egy függvény értékének kifejezését a függvény egyéb értékeivel. Ha a józan ész azt súgja, hogy ha a funkcióját úgy valósítja meg, hogy a rekurzív hívások előre megtörténjenek és tárolva legyenek a könnyű hozzáférés érdekében, az felgyorsítja a programját.
Két különböző állapotú megoldás
A dinamikus programozás intuíciója az, hogy a teret időre cseréljük, pl. azt mondani, hogy ahelyett, hogy az összes állapotot kiszámolnánk, ami sok időt, de nem helyet foglal el, helyet foglalunk el az összes részfeladat eredményének tárolására, hogy később időt takarítsunk meg.
Egy időben dinamikus programozás Vannak hátrányai is. Először is, nincs egyetlen univerzális megoldási módszer. Szinte minden ezzel a módszerrel megoldott problémát saját jellemzői jellemeznek, és a megoldáshoz a legmegfelelőbb módszerkészletet kell keresni. Ezen túlmenően, a sok állapotú, többlépéses problémák megoldásának nagy mennyisége és összetettsége alacsony dimenziós problémák kiválasztásának vagy tömörített információ használatának szükségességét eredményezi. Ez utóbbi a lehetőségek elemzésére és az állapotlista feldolgozására szolgáló módszerekkel érhető el.
Próbáljuk megérteni ezt a Fibonacci-számok példáján keresztül. Kódolása tiszta rekurzió használatával. Más ismétlődési relációt használunk a két kódban? Mást csinálunk a két kódban? A rekurzív kódban sok érték többször újraszámításra kerül. Minden egyedi mennyiség kiszámítását csak egyszer tudtuk kezelni. Vessen egy pillantást a képre, hogy megértse, hogyan számoltak újra bizonyos értékeket rekurzív módon.
A legtöbb dinamikus programozási probléma két típusra osztható. Az optimalizálási problémák elvárják, hogy egy elfogadható megoldást válasszon a szükséges függvény értékének minimalizálására vagy maximalizálására. A kombinatorikus problémák megkívánják, hogy kitaláljuk, hány módot kell tenni valamire, vagy mekkora valószínűséggel történik valami.
A folyamatos idejű folyamatok esetében a dinamikus programozás a diszkrét megoldási séma korlátozó változatának tekinthető. Az ebben az esetben kapott eredmények gyakorlatilag egybeesnek L. S. Pontryagin vagy Hamilton-Jacobi-Bellman maximális módszereivel kapott eredményekkel.
A dinamikus programozás olyan problémák megoldására szolgál, amelyekben lépésről lépésre lehetséges az optimum keresése, például a szűkös tőkebefektetések elosztása új felhasználási területek között; igény- vagy készletgazdálkodási szabályok kidolgozása, amelyek meghatározzák az utánpótlás pillanatát és a pótlási rendelés nagyságát; a termelés ütemezésének és a foglalkoztatás kiegyenlítésének elveinek kidolgozása változó termékkereslet mellett; naptári tervek készítése a berendezések aktuális és nagyjavítására, illetve cseréjére; a legrövidebb távolságok keresése a közlekedési hálózaton; egy kereskedelmi művelet fejlesztési sorrendjének kialakítása stb.
Klasszikus dinamikus programozási problémák
Minden dinamikus programozási problémához tartozik a következő diagram. Határozza meg rekurzív módon a megoldás értékét úgy, hogy a kisebb részproblémák optimális megoldásaival fejezi ki.
- Mutassuk meg, hogy a probléma optimális részproblémákra bontható.
- Számítsa ki az optimális megoldás értékét alulról felfelé!
- A kiszámított információkból készítsen optimális megoldást!
- Beruházás allokációs probléma. Négy vállalkozás termelésének rekonstrukciójára és korszerűsítésére különítve el készpénz C = 80 den. egységek Minden egyes vállalkozás esetében ismert a kibocsátás lehetséges f i (x) (i = 1, 4) növekedése, az allokált összegtől függően.
Dinamikus programozási problémákban gazdasági folyamat időtől (vagy több időszaktól) függ, ezért számos olyan optimális megoldás születik (az egyes szakaszokra egymás után), amelyek biztosítják a teljes folyamat egészének optimális fejlődését. A dinamikus programozás egy matematikai berendezés, amely lehetővé teszi a szabályozott folyamatok és az időfüggő folyamatok optimális tervezését. A lépésről lépésre történő optimalizálást többlépcsős döntéshozatali folyamatnak nevezzük. Egy gazdasági folyamatot irányítottnak nevezünk, ha lehetséges befolyásolni fejlődésének menetét.
Hátránya, hogy egyedi megoldást kell kitalálni, ami működik. A dinamikus programozást táblázatkitöltő algoritmusként is felfoghatja: tudja, milyen számításokat kell elvégeznie, így kiválasztja a legmegfelelőbb végrehajtási sorrendet, és figyelmen kívül hagyja azokat, amelyeket nem kell kitöltenie.
Nézzük a mintaproblémát. Az utolsó ismétlés lesz. Minden borát el akarja adni, de ettől az évtől pontosan egy bort szeretne eladni évente. További korlátozás, hogy minden évben csak a polcon lévő bal vagy jobb szélső bort szabad eladni, és a polcon lévő borokat nem szabad átrendelni.
A dinamikus programozási (DP) módszer a szekvenciális optimalizálás elvén alapul: az eredeti nagydimenziós optimalizálási probléma megoldását felváltja a kisdimenziós optimalizálási feladatok sorozatának megoldása. A DP-módszer alkalmazhatóságának fő feltétele, hogy a döntéshozatali folyamat több hasonló lépésre vagy szakaszra bontható, amelyek mindegyikét külön-külön, de a többi lépésben elért eredmények figyelembevételével tervezzük. Például egy iparág tevékenysége több üzleti éven keresztül, vagy a berendezések vezérléséhez használt tesztek sorozata stb. Egyes folyamatok (műveletek) természetesen lépésekre oszlanak, de vannak olyan műveletek, amelyeket fel kell osztani mesterségesen fokozatos, például a célpontra irányító rakéták irányítását.
Ez az elv biztosítja, hogy a bármely lépésben választott szabályozás ne lokálisan a legjobb, hanem a folyamat egésze szempontjából a legjobb legyen, mivel ezt a vezérlést a következő lépések következményeinek figyelembevételével választják ki.
Szeretné tudni, hogy mennyi a maximális profit, amit akkor érhet el, ha az optimális sorrendben értékesíti a borokat? Miután egy darabig játszol a problémával, valószínűleg úgy fogod érezni, hogy az optimális megoldás a nagy értékű borok minél későbbi értékesítése. Talán kitalálhatja a következő mohó stratégiát.
Évente kettőnél kevesebb bort adjon el. Bár a stratégia nem említi, hogy mit kell tenni, ha két bor ugyanannyiba kerül, ez a stratégia helyesnek tűnik. De sajnos ez nem így van, amint azt a következő példa mutatja. Amikor megoldást talál egy probléma helyettesítésére, kezdje a megoldással visszacsatolás amely megtalálja a helyes választ.
Mérlegeljük általános leírás dinamikus programozási problémák.
A többlépcsős döntéshozatali folyamatot lebontjuk n lépéseket. Jelöljük ε 0-val a rendszer kezdeti állapotát, ε 1, ε 2, … ε n– a rendszer állapota az első, második után, n-adik lépés. Általában az állam
ε k– vektor (ε k 1 , …, ε k s).
Menedzsment többlépéses folyamatban megoldások (vezérlőváltozók) halmazát hívják u k = (u k 1 , ..., u k r) minden lépésnél kés a rendszer átvitele az ε állapotból k-1 = (ε k- 1 1 , …, ε k -1 s) ε állapotba k = (ε k 1 , …, ε k s).
A gazdasági folyamatokban a gazdálkodás a pénzeszközök minden szakaszban történő elosztásából és újraelosztásából áll. Például bármely vállalkozás termékeinek előállítása ellenőrzött folyamat, mivel azt a berendezések összetételének változásai, a nyersanyagellátás mennyisége, a finanszírozás mértéke stb. határozzák meg. Kezdetben hozott döntések összessége év, a tervezési időszak, a vállalkozás nyersanyagellátása, eszközcseréje, illetve a finanszírozás mértéke stb. a gazdálkodás. Úgy tűnik, hogy a maximális teljesítmény elérése érdekében a legegyszerűbb módja a lehető legnagyobb összegű források befektetése és a berendezések teljes kapacitással történő használata. Ez azonban a berendezések gyors kopásához, és ennek következtében a termelési kibocsátás csökkenéséhez vezetne. Ezért a termék kibocsátását úgy kell megtervezni, hogy elkerüljük a nemkívánatos hatásokat. Intézkedéseket kell hozni annak biztosítására, hogy a berendezést az elhasználódásuk során, azaz időnként fel kell tölteni. Ez utóbbi, bár a kibocsátás kezdeti volumenének csökkenéséhez vezet, lehetőséget ad a jövőbeni termelés bővítésére. Így a termelés gazdasági folyamata több szakaszból (lépésből) állónak tekinthető, amelyek mindegyike befolyásolja annak fejlődését.
Az ellenőrzött folyamat szakaszának (lépésének) kezdetének tekintjük a döntéshozatal pillanatát (a tőkebefektetés mértékéről, a berendezések cseréjéről). bizonyos típus stb.). Egy szakaszon általában üzleti évet értünk.
Általában minden lépésnél kézben tartva u k bizonyos korlátozások érvényesek. Azokat a vezérlőket, amelyek megfelelnek ezeknek a korlátozásoknak, hívják elfogadható.
Feltéve, hogy a teljesítménymutató k a folyamat th lépése a lépés kezdeti állapotától függ k-1 és a vezérléstől ebben a lépésben u k, megkapjuk a teljes többlépcsős folyamat célfüggvényét a következő formában: 
.
Alkalmazott dinamikus programozási problémák
A függvény által használt összes nem lokális változót olvasható változóként kell használni, pl. egy függvény csak a helyi változókat és argumentumait tudja megváltoztatni. Ennek egy olyan függvénynek kell lennie, amely rekurzió segítségével számítja ki a választ. . Ez a megoldás egyszerűen kipróbálja az összes lehetséges érvényes borértékesítési rendelést. Ezért, bár most megkapjuk a helyes választ, az algoritmus időbonyolultsága exponenciálisan növekszik. Egy megfelelően megírt visszakövető függvénynek mindig válasznak kell lennie egy jól megfogalmazott kérdésre.
Fogalmazzuk meg most a dinamikus programozási problémát: „Határozza meg a megengedett vezérlők készletét ( u 1 , …, u n), átviszi a rendszert az ε 0 kezdeti állapotból az ε végállapotba nés a hatékonysági mutató maximalizálása vagy minimalizálása F».
A funkció maximumát (minimumát) elérő vezérlés F hívott optimális szabályozás u * = (u 1* ,…, u n *).
Ha vezérlő változók u k vegyen diszkrét értékeket, akkor a DP modellt hívják diszkrét. Ha a változók u k folyamatosan változik, akkor a DP modellt hívják folyamatos.
Az állapotparaméterek számától függően sés a vezérlőváltozók száma r megkülönböztetni egydimenziósÉs többdimenziós DP feladatok.
Egy feladat lépéseinek száma lehet végső vagy végtelen.
A dinamikus programozási probléma általános megfogalmazása
Mindig meg kell próbálnia létrehozni egy ehhez hasonló kérdést a visszatérési függvényhez, hogy megnézze, jól tette-e, és pontosan megértse, mit csinál. Meg kell próbálnunk minimalizálni a függvényargumentumok állapotterét. Ezen a ponton fontolja meg, hogy a függvénynek átadott argumentumok közül melyik redundáns. Vagy összeállíthatjuk őket más érvekből, vagy nincs is rájuk szükségünk. Ha vannak ilyen argumentumok, ne adja át őket a függvénynek. Csak számítsa ki őket a függvényen belül.
Alkalmazott dinamikus programozási problémák
- létesítmények építésének tervezésének problémája.
