Úvod do dynamického programování

Mezi problémy vyřešené pomocí matematického programování můžeme vymezit samostatnou třídu problémů, které vyžadují optimalizaci vícestupňových (vícestupňových) procesů. Takové úkoly se vyznačují schopností rozdělit řešení na několik vzájemně propojených kroků. Pro řešení těchto problémů se používá dynamické programování nebo, jak se také nazývá, vícestupňové programování. Jeho metody jsou optimalizovány pro nalezení optimálního řešení vícestupňových problémů, které lze rozdělit do několika etap, kroků atd.

Původ pojetí

Použití slova "dynamické" v názvu původně předpokládalo, že rozdělení na dílčí úkoly by se objevilo hlavně v čase. Při použití dynamických metod k řešení výrobních, obchodních a jiných úkolů, v nichž se jedná o časový faktor, není rozdělení do samostatných etap těžké. Je však možné použít techniku ​​dynamického programování v úlohách, kde jednotlivé fáze nejsou časově souvislé. Vždy ve víceúrovňovém úkolu můžete vybrat parametr nebo vlastnost, podle které můžete rozdělit jednotlivé kroky.

Algoritmus (metoda) pro řešení vícestupňových problémů

Algoritmus nebo Dynamická programovací metoda je založena na použití principu sekvenční optimalizace problému, kdy řešení obecného problému je rozděleno na řadu řešení jednotlivých dílčích úkolů s následnou integrací do jediného řešení. Velmi často jsou jednotlivé dílčí úkoly stejné a jedno společné řešení významně snižuje čas výpočtu. Funktem metody je autonomie řešení problému v každé samostatné fázi, tj. Bez ohledu na to, jak byl proces optimalizován a vyřešen v předchozí fázi, aktuální výpočet používá pouze parametry procesu, které ho v současné době charakterizují. Například řidič řidičem na silnici rozhodne o aktuální jízdě bez ohledu na to, kolik nebo kolik jel dříve.

Metoda uvedená výše a níže uvedená metoda

Navzdory skutečnosti, že při výpočtu v samostatné fázi řešení problému jsou použity parametry procesu pro aktuální okamžik, výsledek optimalizace v předchozím stupni ovlivňuje výpočty následujících etap, aby bylo dosaženo nejlepšího výsledku obecně. Dynamické programování volá takový rozhodovací princip metodou optimality, která určuje, že optimální strategie pro řešení problému bez ohledu na počáteční rozhodnutí a podmínky musí představovat optimální strategii pro počáteční stav v dalších etapách. Jak vidíme, proces řešení problému je průběžná optimalizace výsledku v každém jednotlivém stupni od prvního až po poslední. Tato metoda se nazývá nejvyšší programovací metoda. Obrázek znázorňuje schematický algoritmus řešení shora dolů. Existuje však řada vícestupňových problémů, u nichž je již známý maximální efekt již v poslední fázi, například jsme již dorazili z bodu A do bodu B a teď chceme vědět, jestli jsme byli správně v každé předchozí fázi, nebo kdybychom mohli udělat něco optimálnějšího. Objevuje se rekurzivní posloupnost stupňů, tj. Jdeme jako "z opačné". Tato metoda řešení se nazývá "spodní programovací metoda".

Praktická aplikace

Dynamické programování lze použít v libovolném oblasti činnosti kde existují procesy, které mohou být na jakémkoli parametru (čas, množství, teplota apod.) rozděleny do několika stejných malých stupňů. Nejvíce používané dynamické metody řešení byly získány v teorii řízení a ve vývoji výpočetních systémů.

Vyhledejte nejlepší cestu

Pomocí dynamické optimalizace je možné vyřešit širokou třídu problémů s nalezením nebo optimalizací nejkratší cesty a dalších problémů, při nichž "klasická" metoda výčtu možných řešení vede ke zvýšení výpočetního času a někdy je obecně nepřijatelná. Klasickým problémem dynamického programování je problém s batohem: určitý počet objektů s určitou hmotností a cenou je dán a je třeba vybrat soubor objektů s maximální hodnotou a hmotností, která nepřesáhne objem batohu. Klasické vyjmenování všech možností při hledání optimálního řešení bude trvat značnou dobu a pomocí dynamických metod je problém vyřešen v přiměřené době. Úkolem nalezení nejkratší cesty pro dopravní logistiku jsou základní a dynamické metody řešení jsou optimálně vhodné pro jejich řešení. Nejjednodušším příkladem takového úkolu je konstrukce nejkratší trasy pomocí GPS navigátoru.

Výroba

Dynamické programování se široce využívá při řešení různých výrobních úkolů, jako je řízení zásob, kdykoli k udržení požadovaného počtu komponent, plánování výrobního procesu, údržby zařízení a generálních oprav, jednotného zatížení personálu, nejúčinnějšího přidělování investičních fondů apod. K vyřešení problémů při výrobě pomocí dynamických programovacích metod byly vyvinuty speciální softwarové balíčky a Integrované do populárních systémů řízení podniku, jako je SAP.

Vědecká oblast

Metody dynamického programování jsou široce používány v různých vědeckých studiích. Například se úspěšně používají v algoritmech rozpoznávání řeči a obrazu při zpracování velkých datových polí v sociologii a hospodářské činnosti.