Dynamické programování diskrétních rozhodovacích procesů a jeho aplikace (optimální rozdělování zdrojů, optimální průchod sítí, strategie obnovy)

Dynamické programování diskrétních rozhodovacích procesů a jeho aplikace (optimální rozdělování zdrojů, optimální průchod sítí, strategie obnovy)

Optimální rozdělování zdrojů

Nechť je dáno omezené množství p jistého ekonomického zdroje (p je celé nezáporné číslo). Ekonomickým zdrojem může být např. surovina, pracovní síly, stroje, investice apod. Nechť každá jednotka tohoto množství může být použita právě jedním z n různých způsobů. Je-li x_i část tohoto množství, použité i-tým způsobem (i = 1,2,,n), pak daná funkce g (x ) vyjadřuje výsledný efekt z tohoto způsobu použití. Celkový efekt z množství p necht je vyjádřen funkcí

(1)

Hledejme optimální rozdělení množství p, tj. takové celočíselné nezáporné hodnoty proměnných (x₁, x₂, …, x_n), které maximalizují hoře uvedenou funkci za podmínky

(2)

Zaveďme předpoklad, který bývá v praxi často splněn, že funkce g jsou neklesající, a že platí

g_i(0) = 0

Předpokládejme, že jednotlivé části množství p přidělujeme pro různá možná použití postupně; nejprve přidělíme jistou část pro n-tý způsob, pak pro (n - 1)-ní atd. Řešení úlohy lze tedy chápat jako optimalizaci rozhodovacího procesu, u něhož je stav systému v daném okamžiku roven největší části množství p takové, že žádná její složka nebyla do tohoto okamžiku přidělena pro kterýkoliv z uvedených způsobů použití. Rozhodovací proměnné jsou q_i = x_n-1 a transformace je ve tvaru p_i+1 = T(p_i ,q_i ) = p_i q_i (i = 0,1,,n 1). Je-li tedy počátečním stavem p, pak po provedení počátečního rozhodnutí obdržíme stav p₁ = p - x_n , kde pro rozhodovací proměnnou x_n platí podmínka x S(p) = . Následující transformace změní stav na

p₂ = p₁ – x_n-1 = p – x_n – x_n-1 , kde analogicky x_n-1   S(p₁) = . Konečný stav bude

p_n = p_n-1 – x₁ = p - , kde x₁ S(p_n-1) = .

Účelová funkce tohoto procesu je dána v (1). Maximální hodnotu účelové funkce, vyjadřující celkový efekt z množství ξ (ξ je celé nezáporné číslo), rozděleného pro n různých způsobů použití, přes všechny možné způsoby rozdělení, označme f_n (ξ). Z principu optimality plynou rovnice

Dynamické programování je matematický přístup k optimalizaci více etapových rozhodovacích procesů, založený na použití rekurentních funkcionálních vztahů, které plynou z Bellmanova principu optimality. Tohoto přístupu lze použít k optimalizaci procesů deterministických i stochastických, diskrétních i spojitých. Při formulaci každé konkrétní úlohy je nutno nejprve stanovit, co budeme nazývat stavem systému, transformací a rozhodnutím, stanovit množiny přípustných stavů a přípustných rozhodnutí, a určit počet etap procesu. Pak je nutno se rozhodnout, co budeme považovat za účelovou funkci procesu, tj. dle jakého kriteria budeme chtít optimalizovat.

Jakmile máme základní veličiny definovány, můžeme sestavit příslušné funkcionální rovnice a provést důkaz existence a jednoznačnosti jejich řešení. Poté jsme postaveni před otázky, zda můžeme získat jednoduchá analytická vyjádření pro optimální účelovou funkci a pro optimální strategii, nebo zda můžeme získat numerické řešení pomocí počítače, a můžeme-li získat přesné nebo jen přibližné řešení. Dynamické programování má široké aplikace v oblastech ekonomie, automatické regulace, matematiky, fyziky, chemie a techniky.

Optimální průchod sítí

Úkolem je najít co možná nejkratší vzdálenost mezi body. Časové konstanty mezi uzly mohou znamenat čas potřebný pro projití mezi dvěma body, náklady na pohonné hmoty, vzdálenost mezi body, náklady. Tato metoda byla použita u stavění tunelů na Bílovice nad Svitavou J

Počítá se to postupnou aproximací:

*** vynechává z důvodu z výchozího do koncového bodu je cesta = 0.

Př.:dostat se z bodu 1 do bodu 5, N=5

Dále podobně pokračujeme s třetím krokem. Kdy vyjdou úplně stejné výsledky jako u , což asi znamená že máme nalezenu optimální cestu. Pote se pokračuje analogicky z první rovnice nám vyjde pokračování na bod 3 což je 3 rovnice, z té následně min. vzdálenost je na bod 2. To odpovídá druhé rovnici u které je min u . To ukazuje na 5 rovnici a to už je náš cíl J

Strategie obnovy

(Strategie obnovy strojového parku)

Předpokládejme, že nějaký typ stroje je charakterizován nákupní cenou p a roční ziskovou funkcí n(t), kde n(t) = zisk z provozu stroje od okamžiku, kdy je starý t roků, do okamžiku, kdy je starý t+1 roků, t = 0,1,2, .

Tato funkce je nerostoucí funkcí argumentu t. Předpokládejme, že stroj je natolik specializovaný, že nemá žádnou prodejní cenu. Na začátku každého roku se činí rozhodnutí, zda se má tento stroj ponechat v provozu, nebo nahradit novým strojem téhož typu. Naším cílem je stanovit nahrazovací strategii, která způsobuje maximální celkový zisk z K-letého provozního období. Jinými slovy, zjišťujeme, zda máme nahradit nebo ponechat stroj, který je t roků starý, má-li ještě dalších K roků tento pracovní proces trvat. Problém řešíme pro všechna K = 1,2,,

t = 0,1,2,. Zaveďme optimální účelovou funkci f_K (t), která je rovna celkovému zisku z K-letého procesu, na jehož počátku je stroj t roků starý, a během něhož je používáno optimální nahrazovací strategie.

Z principu optimality dostáváme funkcionální rovnici

  (1)

Pro jednoletý proces máme

f₁ (t) = max (2)

První člen v závorce na pravé straně (1) představuje součet bezprostředního zisku z rozhodnutí ponechat stroj v provozu a maximálního zisku ze zbytku procesu, na jehož počátku je tentýž stroj o jeden rok starší. Druhý člen vyjadřuje zaplacení nákupní ceny za nový stroj, zisk z jeho provozu v nejbližším roce a zisk ze zbytku procesu na jehož počátku je tento stroj starý jeden rok.

Abychom se přesvědčili, že rovnice (1) je ekvivalentní základní rovnici dynamického programování, uvedeme ji na tvar

f_K (t) = max [n((1 q)t) qp+f_K-1 ((1 q)t+1)] ,   (3)

q

kde q je rozhodovací proměnná, která může nabývat pouze hodnot 0 nebo 1. Přitom q = 0 odpovídá případu, kdy stroj ponecháváme v provozu, q = 1 případu, kdy stroj nahrazujeme. Dosadíme-li q = 0 resp. q = 1 do výrazu v hranaté závorce (3), bude tento výraz roven prvnímu resp. druhému členu v závorce na pravé straně v (1).

Vidíme, že f_K (t) je maximální účelová funkce (K - 1)-etapového procesu, jehož stav je dán diskrétní hodnotou času t, transformace je dána vztahem T(t,q) = (1 - q)t+1, tj. stáří stroje se za jeden rok od provedení rozhodnutí buďto zvětší o 1, nebo se stane rovným jedné. Složce g(t,q) účelové funkce zde odpovídá výraz

n((1 - q)t) - qp.

Je-li dáno

n(t) = 10 – t pro t = 0,1,2,,10

n(t) = 0 pro t = 11,12,,

p = 10,

pak rovnice (1), (2) dávají

f_K (t) = max , (4)

f₁ (t) = max = n(t). (5)

Zkoumejme např. případ K = 4, t = 3.Hledáme tedy strategii obnovy stroje, která maximalizuje zisk ze čtyřletého provozního období, je-li na počátku tohoto období stroj 3 roky starý. Hledaný maximální zisk je f₄ (3). Z předchozích rovnic je patrno, že např. f₄ (3) lze vyjádřit pomocí f₃ (4), f₃ (1). Tyto funkce vyjadřujeme pomocí dalších funkcí. Postupným dosazováním do (4) dostáváme vyjádření uvedených funkcí:

f₂ (5) = max = max = 9

f₂(1) = max = max = 17

f₂ (2) = max = max = 15

f₃ (4) = max = max = 17

f₃ (1) = max = max = 24

f₄ (3) = max = max = 24

Hodnotu hledaného optimálního zisku f₄ (3) = 24 poskytuje poslední rovnice. Poněvadž oba členy, přes něž maximalizujeme, jsou v ní stejně velké, vidíme, že nezáleží na tom, zda na počátku prvního roku provozu stroj obnovíme, nebo nikoliv. Neobnovíme-li ho, začínáme na počátku druhého roku proces se strojem, který je starý 4 roky. Tento proces má trvat již jen 3 roky. Maximální zisk z tohoto procesu určuje funkce f₃ (4),uníž je maximum dle 4.řádku tvořeno druhým členem, takže optimální rozhodnutí na začátku druhého roku způsobí obnovení stroje. Nový stroj bude na začátku třetího roku 1 rok starý. Tehdy bude zbývat dvouletý proces se ziskem f₂ (1), který je dle vztahu na 2. řádku maximalizován prvním členem, má tedy být stroj na začátku třetího roku ponechán. Ke čtvrtému, tj. poslednímu roku provozu se vztahuje zisk f₁ (2), který dle (4.61) je maximalizován prvním členem, má tedy být stroj na počátku čtvrtého roku ponechán v provozu. Spočívá tedy optimální strategie v tom, že stroj je obnoven až nazačátku druhého roku, načež nový stroj pracuje bez obnovy až do konce zkoumaného období.

Poněvadž na začátku prvního roku jsou optimální obě možná rozhodnutí, lze stejným způsobem ukázat, že existuje ještě druhá optimální strategie, která poskytuje stejný zisk f₄ (3) = 24 jako první, a která spočívá v tom, že stroj je obnoven již na začátku prvního roku a nový stroj pak pracuje bez obnovy do konce celého čtyřletého období. Vidíme, že výpočet maximálního zisku z celého procesu probíhá postupným dosazováním do rovnic v pořadí shora dolů, načež lze určovat optimální strategii zpětným hledáním v těchto rovnicích ve směru zdola nahoru.