univerzita komenského v bratislave
fakulta matematiky, fyziky a informatiky
PÍSOMNÁ PRÁCA
K DIZERTAČNEJ SKÚŠKE
2011
Mgr. Martin LAUKO
univerzita komenského v bratislave
fakulta matematiky, fyziky a informatiky
Katedra aplikovanej matematiky a štatistiky
Stochastické úlohy optimálneho riadenia
PÍSOMNÁ PRÁCA
K DIZERTAČNEJ SKÚŠKE
Študijný odbor: 9.1.9 Aplikovaná matematika
Školiteľ: Doc. RNDr. Margaréta Halická, CSc.
Bratislava 2011
Mgr. Martin LAUKO
Obsah
1 Úvod
3
2 Teoretické základy
6
2.1
Stochastické úlohy optimálneho riadenia . . . . . . . . . . . . . . . . . .
6
2.2
Ohraničenie na koncový stav . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.3
Formulácia úlohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.4
Rovnica dynamického programovania . . . . . . . . . . . . . . . . . . . .
14
3 Numerické príklady
20
3.1
Úloha predavača reďkoviek . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.2
Stochastické optimálne riadenie . . . . . . . . . . . . . . . . . . . . . . .
21
3.3
Stochastické programovanie . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.4
Porovnávanie kvality riešení . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.5
Konkrétne výsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4 Prehľad literatúry
31
4.1
Témy stochastických úloh . . . . . . . . . . . . . . . . . . . . . . . . . .
31
4.2
Metódy riešenia úloh . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
5 Projekt dizertačnej práce
40
5.1
Teoretické otázky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
5.2
Numerické experimenty . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
Literatúra
44
2
Kapitola 1
Úvod
Koľko reďkoviek má predavač objednať, keď dopyt po nich je náhodný a reďkovky sa
rýchlo kazia? V reálnych problémoch, v ktorých chceme správne rozhodnúť, sa veľmi
často stretávame s nejakou formou náhody. Či už táto vyplýva z nepredvídateľnosti
budúceho vývoja, nezohľadnenia všetkých rizík alebo nepresných informácií o aktuálnom
stave, musíme sa s ňou nejako vysporiadať. Ešte komplikovanejšie je to v problémoch,
v ktorých sa môžeme rozhodovať opakovane, na začiatku každej etapy.
Potrebný matematický základ pre takéto rozhodovanie zohľadňujúc náhodné vplyvy
ponúkajú hneď dve oblasti matematiky - stochastické optimálne riadenie a stochastické
programovanie. Oba prístupy umožňujú takéto problémy efektívne sformulovať a obsahujú nástroje, ktorými sa dajú riešiť. Pritom však prešli úplne nezávislým vývojom, na
čo poukazuje Dupačová v [14].
Obe disciplíny sa začali rozvíjať v rovnakom období 1955–1965, vychádzali z rovnakých základných myšlienok a tiež formulovali a riešili podobné problémy z praxe,
v ktorých sa vyžadovalo dynamické a stochastické rozhodovanie. Keďže išlo o dve nezávisle klasifikované oblasti matematiky, prípadné vzájomné porovnania výhod a nevýhod
boli skôr zriedkavé.
3
1 ÚVOD
Ťažisko tejto práce budú tvoriť práve stochastické úlohy optimálneho riadenia. S ohľadom na vyššie uvedené však získané výsledky porovnávame aj so stochastickým programovaním, keďže našim cieľom je hľadať efektívne spôsoby riešenia reálnych problémov,
v ktorých hľadáme čo najlepšie rozhodnutia v neistých situáciách.
Vráťme sa ešte k optimálnemu riadeniu. Hoci prvé úlohy riešil už Johann Bernoulli
v roku 1696, optimálne riadenie v dnešnej podobe sa vyvinulo až v 20. storočí. Teória
úloh optimálneho riadenia s diskrétnym časom bola motivovaná hlavne ekonomickými
aplikáciami. Tejto oblasti sa venoval americký matematik Richard Bellman, ktorý prišiel
s rekurzívnou metódou výpočtu optimálneho riadenia pomocou rovnice dynamického
programovania, podrobnejšie informácie možno nájsť v jeho monografii [1].
Teórii optimálneho riadenia sa venoval aj Dimitri Bertsekas, autor publikácii [2]
a [3]. V dvoch dieloch sa podrobne venuje problematike diskrétnych aj spojitých úloh
optimálneho riadenia, ich súčasťou sú aj najnovšie vedecké výsledky. Napríklad kapitolu o aproximovanom dynamickom programovaní sústavne dopĺňa. Bertsekas je tiež
spoluautorom knihy [4], ktorá sa zaoberá práve stochastickými úlohami.
Základom pre túto prácu je tiež učebnica [15], ktorej autori Brunovský, Halická
a Jurča vykladajú teóriu diskrétnych úloh optimálneho riadenia za pomoci mnohých
praktických príkladov. Osobitnú kapitolu venovali práve stochastickým úlohám.
V rámci tejto práce sa zameriavame na stochastické úlohy optimálneho riadenia,
v ktorých vystupuje ohraničenie na koncový stav. Toto ohraničenie najskôr musíme
vhodným spôsobom naformulovať. Preto začnime sumarizáciou existujúcich poznatkov
pre stochastické úlohy a ich riešenie. Hlavným cieľom potom bude zovšeobecniť odvodenie rovnice dynamického programovania tak, aby sme ju mohli využiť aj pre úlohy
s ohraničením na koncový stav, príp. ďalšie špeciálne úlohy.
Ďalším cieľom práce je numerické overenie teoretické výsledkov. Pokúsime sa porovnať stochastické optimálne riadenie so stochastickým programovaním. V stochastickom
programovaní ohraničenie na koncový stav nepredstavuje nevýhodu, na rozdiel od stochastického OR, kde to tak môže byť. Oproti tomu má riešenie optimálneho riadenia
tvar spätnej väzby, čo môže byť výhodnejšie. Preto nie je jasné, ktorá metóda bude
úspešnejšia.
Popri tom chceme popísať súčasný vývoj cez prehľad aplikácií stochastických metód
v literatúre a tiež identifikovať problémy, ktorým sa budeme môcť neskôr venovať v rámci
pripravovanej dizertačnej práce.
4
1 ÚVOD
Predstavme si teraz štruktúru tejto práce. Po tomto úvode (prvej kapitole) nasleduje
kapitola 2, v ktorej popisujeme východiská pre riešenie stochastických úloh optimálneho
riadenia, hlavne rovnicu dynamického programovania. V tejto časti zároveň odvodzujeme
jej tvar pre úlohu s ohraničením na koncový stav v tvare strednej hodnoty.
V ďalšej kapitole overujeme teoretické poznatky v praxi - numericky riešime problém predavača reďkoviek, pričom porovnávame riešenie získané optimálnym riadením
(dynamickým programovaním) a stochastickým programovaním. Pri testovaní volíme
rôzne parametre modelu s cieľom kvantifikovať hodnotu riešenia získaného pomocou
stochastického optimálneho riadenia.
Štvrtá kapitola obsahuje prehľad vybraných článkov zo stochastického optimálneho
riadenia a stochastického programovania. Zameriavame sa v ňom na široké spektrum reálnych problémov a aplikácií oboch metód, uvádzame stručný popis riešených problémov
a bližšie popisujeme spôsoby riešenia úloh.
Záverečná piata kapitola sa venuje projektu dizertačnej práce. Formulujeme tu jej
hlavné ciele v oblasti teoretického výskumu, ako aj ďalšie úlohy pri numerickom overovaní a porovnávaní riešení, ktoré sme sformulovali počas tvorby tejto písomnej práce.
Na tomto mieste by som sa ešte rád poďakoval pani docentke Halickej, za odborné
vedenie, cenné rady a pripomienky k tejto práci, ako aj všetkým ostatným, ktorí ma pri
písaní tejto práce podporovali.
5
Kapitola 2
Teoretické základy
Táto kapitola predstavuje stručný úvod k diskrétnym stochastickým úlohám optimálneho riadenia. Pôjde o úlohy, v ktorých je správanie systému popísané diferenčnou rovnicou, ktorá však závisí aj od náhodnej premennej. Pritom nás špeciálne zaujímajú úlohy,
v ktorých vystupuje podmienka na koncový stav - pokúsime sa zvoliť vhodný tvar tejto
podmienky a odvodiť rovnicu dynamického programovania pre takéto úlohy.
2.1 Stochastické úlohy optimálneho riadenia
Úlohy optimálneho riadenia s diskrétnym časom (ďalej diskrétne úlohy) vo všeobecnosti
riešia nasledujúci problém: Majme objekt (systém), ktorého stav popisuje stavová premenná xi . Systém sa správa podľa diferenčnej rovnice, do ktorej vstupuje aktuálny stav
a vonkajšie riadenie. Našou úlohou je počas k časových etáp tento systém „riadiťÿ, teda
voliť také hodnoty riadenia ui , aby sme maximalizovali, resp. minimalizovali účelovú
funkciu
k−1
X
fi0 (xi , ui ).
i=0
Vždy na začiatku i-tej etapy (i = 0, 1, . . . , k − 1) poznáme aktuálny stav systému
xi ∈ Xi (zadaná množina možných stavov systému). Ak Xi obsahuje len spočítateľne veľa
6
2.1 STOCHASTICKÉ ÚLOHY OPTIMÁLNEHO RIADENIA
hodnôt, ide o úlohu s diskrétnym stavom, ak je to interval v R, je to úloha so spojitým
stavom.
Vývoj systému môžeme ovplyvniť voľbou riadenia ui spomedzi prípustných hodnôt
Ui . Nový stav systému xi+1 je potom jednoznačne určený diferenčnou rovnicou xi+1 =
fi (xi , ui ). Spravidla máme zadaný začiatočný stav systému x0 = a a požadujeme, aby
xk patrilo do cieľovej množiny C. Keďže počet etáp k je zadaný, hovoríme o úlohách
s pevným časom.
Stochastické úlohy
Stochastické úlohy sú rozšírené o náhodné vplyvy, ktoré reprezentuje náhodná premenná
zi so známym rozdelením. V tejto práci sa pre zjednodušenie obmedzujeme na úlohy,
v ktorých má náhodná premenná diskrétne rozdelenie. Predpokladajme tiež, že konkrétnu realizáciu náhodnej premennej zi v i-tej etape spoznáme až po stanovení hodnoty
riadenia ui .
Náhodná premenná sa môže prejaviť v diferenčnej rovnici pre xi+1 (dodatočná náhodná zmena stavu systému), ako aj v účelovej funkcii fi0 . Tým pádom nemôžeme maximalizovať priamo účelovú funkciu (závislú od realizácie zi ), maximalizovať budeme
preto strednú hodnotu účelovej funkcie cez náhodné premenné z0 , . . . , zk−1 .
Definujme štandardnú stochastickú úlohu optimálneho riadenia podľa knihy [15]:
" k−1
#
X
maximalizovať
E
fi0 (xi , ui , zi )
i=0
pri ohraničeniach
xi+1 = fi (xi , ui , zi ),
i = 0, . . . , k − 1,
(2.1)
x0 = a,
u i ∈ Ui ,
i = 0, . . . , k − 1,
zi ∈ Zi ,
i = 0, . . . , k − 1.
V ďalšom texte budeme (programovým) riadením nazývať postupnosť hodnôt riadiacich premenných U = {u0 , u1 , . . . , uk−1 }. Konkrétne realizácie náhodnej premennej
zi označíme Z = {z0 , z1 , . . . , zk−1 }. Potom odozvou X na riadenie U pri realizácii náhodných premenných Z chápeme postupnosť X = {x0 , x1 , . . . , xk }, kde x0 je zadané
a xi = xi (U, Z) je riešením diferenčnej rovnice v úlohe (2.1). Predpokladáme pritom, že
riadenia ui spĺňajú ui ∈ Ui a realizácie náhodných premenných zi zodpovedajú rozdeleniu Zi .
7
2.1 STOCHASTICKÉ ÚLOHY OPTIMÁLNEHO RIADENIA
Programové riadenie má zmysel uvažovať, keď chceme riadenie pre všetky etapy zvoliť
vopred. Často však máme možnosť pozorovať stav systému a riadenie voliť v každom
kroku, keď už poznáme nový (náhodný) stav systému x, ako ui = vi (x).
Optimálne riešenie takejto úlohy je preto výhodnejšie hľadať ako spätnú väzbu vi :
Xi → Ui , kde vi (x) je funkcia aktuálneho stavu. Potom V = {v0 , v1 , . . . , vk−1 } nazývame
stratégia. Stratégia je prípustná, ak pre každé i a xi ∈ Xi bude ui = vi (xi ) ∈ Ui , teda
patriť do množiny prípustných hodnôt riadení.
Pre konkrétnu stratégiu V a danú realizáciu náhodnej veličiny Z už môžeme jednoznačne vypočítať hodnotu účelovej funkcie J:
J(V, Z) :=
k−1
X
fi0 (xi , vi (xi ), zi ),
i=0
kde xi+1
x0
(2.2)
= fi (xi , vi (xi ), zi ),
i = 0, . . . , k − 1,
= a.
Teraz môžeme definovať aj optimálnu stratégiu a hodnotovú funkciu pre systém úloh
Dj (x) stochastického OR.
Definícia 2.1 (Optimálna stratégia) Stratégia V je optimálna na množine prípustných stratégií S, keď maximalizuje výraz
max E J(V, Z).
V∈S
Definícia 2.2 (Systém úloh) Pre pevné j, 0 ≤ j ≤ k − 1 a ľubovoľné x ∈ Xj budeme
úlohou Dj (x) rozumieť úlohu
max Jj (x, Vj , Zj ) :=
k−1
X
fi0 (xi , vi (xi ), zi ),
i=j
kde
(2.3)
xi+1
= fi (xi , vi (xi ), zi ),
xj
= x,
i = j, . . . , k − 1,
pričom sme označili použitú stratégiu Vj = {vj , . . . , vk−1 } a realizáciu náhodnej premennej Zj = {zj , . . . , zk−1 }. Množinu všetkých úloh Dj (x) pre j = 0, . . . , k − 1 potom
nazveme systém úloh D.
Keďže E chápeme ako strednú hodnotu cez postupnosť náhodných premenných Z =
{z0 , z1 , . . . , zk−1 }, pre zjednodušenie ďalšieho zápisu zaveďme označenie Ei, j pre i ≤ j
ako strednú hodnotu cez náhodné premenné zi , . . . , zj . Pre i = j budeme písať len Ei .
8
2.2 OHRANIČENIE NA KONCOVÝ STAV
Definícia 2.3 (Hodnotová funkcia pre D) Funkciu Vj : Xj → R nazývame hodnotovou funkciou pre systém úloh Dj (x), keď platí
Vj (x) = max Ej, k−1 Jj (x, Vj , Zj )
Vj
pre každé x ∈ Xj a pre pevné j. Potom postupnosť funkcií V = {V0 , . . . , Vk−1 } nazývame
hodnotovou funkciou pre systém úloh D.
Podobne ako v prípade deterministických úloh, aj optimálne riešenie štandardnej
stochastickej úlohy možno nájsť pomocou rovnice dynamického programovania. Dôkaz
nasledujúcej vety (za istých technických predpokladov) možno nájsť v [15, Veta 2.7].
Veta 2.4 (Rovnica dynamického programovania) Majme úlohu (2.1). Potom V =
{V0 , . . . , Vk−1 } je hodnotová funkcia a Vˆ = {ˆ
v0 , . . . , vˆk−1 } optimálna stratégia práve
vtedy, keď Vj , vˆj , j = 0, . . . , k − 1, spĺňajú pre každé j a x rovnicu dynamického programovania:
Vj (x) = max Ej fj0 (x, u, zj ) + Vj+1 (fj (x, u, zj ))
u∈Ui
= Ej fj0 (x, vˆ(x), zj ) + Vj+1 (fj (x, vˆ(x), zj )) ,
Vk (x) = 0,
(2.4)
pre každé x.
Rovnica dynamického programovania z vety 2.4 nám pre úlohu typu (2.1) dáva zároveň konkrétny návod na výpočet riešenia - optimálnej stratégie a hodnotovej funkcie rekurzívne od konca. Týmto spôsobom možno jednoducho riešiť stochastickú úlohu OR
aj s pomocou počítača, napr. v programe Matlab.
2.2 Ohraničenie na koncový stav
V rámci tejto práce sa zameriavame na úlohy, v ktorých vystupuje ohraničenie na koncový stav. V prípade deterministických úloh optimálneho riadenia ohraničenie na koncový stav typu xk ≥ µ nepredstavuje podstatnú komplikáciu. Môžeme ho chápať ako
určité obmedzenie pri výbere riadenia.
Prípustné hodnoty riadenia budú len také ui ∈ Ui , ktoré spolu so svojou odozvou
spĺňajú koncovú podmienku. Označme Γi (x) množinu prípustných hodnôt riadení v čase
i pre daný stav x. V rovnici dynamického programovania sa toto obmedzenie prejaví tak,
že namiesto max budeme hľadať max .
ui ∈Ui
ui ∈Γi (x)
9
2.2 OHRANIČENIE NA KONCOVÝ STAV
Technicky môžeme toto obmedzenie realizovať aj voľbou cieľovej množiny C, keďže
od prípustného riadenia požadujeme xk ∈ C. Definujeme
C = x k ∈ Xk x k ≥ µ
a potom zvolíme hodnotovú funkciu Vk (x) ako
(
0,
x ∈ C ⇔ x ≥ µ,
Vk (x) =
−∞, inak.
(2.5)
Všimnime si, že takto sme sa efektívne vysporiadali aj s neprípustnosťou riadení: v čase
k − 1 pre pevné xk−1 volíme také uk−1 , aby sme maximalizovali f 0 + Vk (xk ), kde xk =
f (xk−1 , uk−1 ). Ak pre všetky uk−1 ∈ Uk−1 bude Vk (xk ) = −∞, tak aj Vk−1 (xk−1 ) = −∞ a
teda neprípustnosť stavu xk−1 sa prenesie. Naopak, pre nejaké uk−1 bude Vk (xk ) 6= −∞,
tak sa takéto uk−1 môže zvoliť ako optimálne a optimálna hodnota Vk−1 (xk−1 ) bude
určite konečná.
To vedie k tomu, že ak existuje prípustná hodnota riadenia ui ∈ Γi (x) pre každé i a
x, tak aj optimálna hodnota riadenia získaná RDP bude taká, že jeho odozva xk splní
xk ∈ C, resp. ekvivalentne Vk (xk ) 6= −∞. Teda koncová podmienka bude splnená.
Koncová podmienka v stochastických úlohách
V stochastických úlohách je situácia opäť komplikovanejšia, keďže xk závisí nielen od
zvoleného riadenia, ale aj od realizácie náhodnej premennej zk−1 . Preto by bolo logické
zadať ohraničenie koncového stavu v tvare strednej hodnoty
Ek−1 [ xk ] ≥ µ,
(2.6)
kde xk = fk−1 (xk−1 , vk−1 (xk−1 ), zk−1 ) pre zvolenú stratégiu vk−1 (·).
Takáto podmienka však ovplyvní aj prípustnosť stratégií. Kým v štandardnej úlohe
sme mohli zvoliť ľubovoľnú postupnosť {v0 , v1 , . . . , vk−1 } funkcií spĺňajúcich vi (x) ∈ Ui ,
v úlohe s ohraničením na koncový stav to neplatí. Potrebujeme vylúčiť stratégie, ktorými
by sme nesplnili podmienku (2.6). Vychádzame pri tom z definície prípustnej stratégie
podľa článku [8].
V poslednom kroku i = k − 1 a stave systému xk−1 môžeme pri výbere povoliť len
také vk−1 (xk−1 ) ∈ Uk−1 , pre ktoré bude splnená podmienka
Ek−1 [ xk ] = Ezk−1 [ fk−1 (xk−1 , vk−1 (xk−1 ), zk−1 ) ] ≥ µ.
10
2.2 OHRANIČENIE NA KONCOVÝ STAV
Pre danú hodnotu x = xk−1 môžeme množinu prípustných hodnôt stratégie vk−1 označiť
ako Wk−1 (x) a definovať nasledovne:
Wk−1 (x) = vk−1 (x) ∈ Uk−1 | Ek−1 fk−1 (x, vk−1 (x), zk−1 ) ≥ µ .
Zrejme pre niektoré x môže byť Wk−1 (x) prázdna (čo znamená, že pre dané x neexistuje
taká prípustná hodnota riadenia, aby bola splnená koncová podmienka). Takémuto x sa
však musíme vyhnúť už v predchádzajúcom kroku, definujme teda prípustné x v (k − 1)
kroku ako:
Xk−1 = x | Wk−1 (x) 6= ∅ .
Pre i < k − 1 definujme induktívne množiny prípustných hodnôt riadení a stavov:
Wi (x) = vi (x) ∈ Ui | fi (x, vi (x), zi ) ∈ Xi+1 pre všetky zi
(2.7)
Xi = x | Wi (x) 6= ∅
Poznámka 2.5 Nemusí byť celkom zrejmé, prečo sme v rovnici (2.7) pre Wi nepoužili
podmienku na strednú hodnotu. Intuitívne by mohlo stačiť, aby u spĺňalo
Ei fi (x, u, zi ) ∈ Xi+1 ,
teda aby sme sa „priemerneÿ dostali do prípustného stavu. Potom by sme sa však pre
nejaké zi (s nenulovou pravdepodobnosťou) dostali mimo množiny prípustných stavov
v ďalšom kroku Xi+1 , teda k neprípustnému riešeniu. Preto má naša definícia zmysel.
Funkcia koncového stavu
Keď uvažujeme o podmienke na koncový stav, má zmysel uvažovať aj prípadnú funkciu
koncového stavu v účelovej funkcii. Teda v štandardnej úlohe rozšírime účelovú funkciu
o člen ϕ(xk ) na tvar:
max
ui
E
" k−1
X
#
fi0 (xi , ui , zi ) + ϕ(xk )
(2.8)
i=0
Na základe toho môžeme pri numerických experimentoch ohraničenie nahradiť napr.
penalizáciou v prípade nesplnenia podmienky a porovnať výsledky.
Podobne aj v deterministickom prípade, ani tu nedochádza k veľkým komplikáciám
a stačí v RDP definovať hodnotovú funkciu Vk (x) nasledovne:
(
ϕ(x),
x ∈ C,
Vk (x) =
−∞,
inak.
11
(2.9)
2.3 FORMULÁCIA ÚLOHY
2.3 Formulácia úlohy
Na základe predchádzajúcich úvah v tejto kapitole sformulujeme stochastickú úlohu OR
s ohraničením na koncový stav v tvare strednej hodnoty a ukážeme, že takto definovaná
úloha je ekvivalentná s úlohou s hodnotami stratégií vi (x) ∈ Wi (x).
Definícia 2.6 Pod úlohou (UE) rozumieme nasledovnú úlohu s koncovou podmienkou
v tvare strednej hodnoty:
" k−1
#
X
0
max
E
fi (xi , vi (xi ), zi ) + ϕ(xk )
V={v0 ,...,vk−1 }
i=0
xi+1 = fi (xi , vi (xi ), zi ),
i = 0, ..., k−1,
x0 = a,
(UE)
vi (xi ) ∈ Ui ,
i = 0, ..., k−1,
zi ∈ Zi ,
i = 0, ..., k−1,
h
i
Ek−1 fk−1 (xk−1 , vk−1 (xk−1 ), zk−1 ) ≥ µ.
Prípustnou stratégiou v tejto úlohe rozumieme takú postupnosť V = {v0 , . . . , vk−1 }, že
pre každú realizáciu náhodnej premennej Z bude podmienka na strednú hodnotu splnená.
Poznamenajme, že v (UE) funkcie vi (x) nemusia byť definované pre všetky x ∈ X,
stačí pre tie, ktoré sa dosiahnu pre niektoré realizácie zi . Na definícii vi (x) v ostatných
bodoch nezáleží.
Definícia 2.7 Úlohou (UW) budeme označovať úlohu s ohraničenou množinou prípustných stratégií v tomto tvare:
" k−1
#
X
max
E
fi0 (xi , vi (xi ), zi ) + ϕ(xk )
V={v0 ,...,vk−1 }
i=0
xi+1 = fi (xi , vi (xi ), zi ),
i = 0, ..., k−1,
(UW)
x0 = a,
vi (xi ) ∈ Wi (xi ),
i = 0, ..., k−1,
zi ∈ Zi ,
i = 0, ..., k−1.
V tejto časti množiny Wi , Xi definujeme nasledovne:
Wi (x) = vi (x) ∈ Ui | fi (x, vi (x), zi ) ∈ Xi+1 ∀zi ,
i = 0, ..., k−2,
Wk−1 (x) = vk−1 (x) ∈ Uk−1 | E fk−1 (x, vk−1 (x), zk−1 ) ≥ µ ,
Xi = x | Wi (x) 6= ∅ ,
i = 0, ..., k−1.
12
(2.10)
2.3 FORMULÁCIA ÚLOHY
Definované úlohy (UE) a (UW) s ohraničením (2.10) sú rovnaké až na koncové ohraničenie, resp. množinu prípustných stratégií. V nasledujúcej vete dokážeme, že množiny
prípustných stratégií sú v oboch úlohách ekvivalentné.
Veta 2.8 (Ekvivalencia úloh) Stratégia V = {v0 , v1 , . . . , vk−1 } je prípustná v úlohe
(UE) práve vtedy, keď je prípustná v úlohe (UW) s ohraničením (2.10).
D ô k a z. Ukážeme oba smery implikácie pre každé vi (x), i = 0, . . . , k − 1.
„⇒ÿ Pre vk−1 (xk−1 ) ∈ Uk−1 musí platiť v každom xk−1 :
Ek−1 fk−1 (xk−1 , vk−1 (xk−1 ), zk−1 ) ≥ µ,
teda môžeme zvoliť len takú hodnotu stratégie vk−1 (xk−1 ), aby bola splnená podmienka
na strednú hodnotu fk−1 . Pre pevné xk−1 musí preto platiť
vk−1 (xk−1 ) ∈ Uk−1 ∩ {u | Ek−1 fk−1 (xk−1 , u, zk−1 ) ≥ µ} = Wk−1 (xk−1 ).
Prípustné stavy označme Xi - to sú tie x, pre ktoré v čase i existuje aspoň jedna
možná hodnota riadenia vi (x) ∈ Wi (x), Wi (x) 6= ∅. Pre každé x a každé i < k−1 musí byť
hodnota vi (x) ∈ Ui a navyše sa v najbližšom kroku nemôžeme dostať do neprípustného
stavu nezávisle od konkrétnej realizácie zi . Preto pre vi (x) musí pre všetky zi platiť:
fi (x, vi (x), zi ) ∈ Xi+1 ,
čím sme sa dostali k induktívnej definícii Wi (x) pre i < k − 1 podľa rovnice (2.10). Preto
(UE) prípustnosť implikuje (UW).
„⇐ÿ Keďže vi (x) ∈ Wi (x), tak aj vi (x) ∈ Ui pre každé i a x. Zároveň je vk−1 (xk−1 )
je také, že pre každé prípustné xk−1 platí
E [ fk−1 (xk−1 , vk−1 (xk−1 ), zk−1 ) ] ≥ µ.
Keďže do neprípustných xk−1 sa nemôžeme dostať (z vlastnosti vi pre i < k − 1), týmto
sme ukázali prípustnosť úlohy (UE). Tým sme dokázali ekvivalenciu množín prípustných
riešení oboch úloh.
Dôsledok 2.9 Keďže množiny prípustných riešení ako aj účelové funkcie úloh (UE),
(UW) sú rovnaké, tak aj optimálne riešenie úlohy (UW) sa zhoduje s optimálnym riešením úlohy (UE).
13
2.4 ROVNICA DYNAMICKÉHO PROGRAMOVANIA
Na základe dôsledku (2.9) budeme v ďalšom texte uvažovať, že stratégia V, resp.
vi je prípustná, ak platí vi (x) ∈ Wi (x) pre každé x. Pritom sa nemusíme obmedzovať
iba na vyššie uvedenú definíciu Wi , ďalšie odvodenia budú platiť pre ľubovoľnú pevne
zvolenú množinu prípustných stratégií Wi (x).
2.4 Rovnica dynamického programovania
V nasledujúcej časti odvodíme a dokážeme rovnicu dynamického programovania pre
úlohu s ohraničeniami (UW) v zmysle definície 2.7. Pritom Wi (x) chápeme všeobecne,
ako obmedzenú množinu prípustných stratégii pre daný stav x v kroku i. (Podľa potreby
môžeme zvoliť Wi v tvare (2.10), teda tak, aby bola splnená koncová podmienka na
strednú hodnotu.)
Postupujeme podľa knihy [15], podľa odvodenia rovnice dynamického programovania
pre úlohu bez ohraničení. Začíname potrebnými označeniami a pomocnými tvrdeniami.
Analogicky ako v definícii 2.2 označme účelovú funkciu úlohy (UW) od času j (tzv.
cost-to-go funkciu) pre konkrétnu stratégiu Vj a realizáciu náhodnej premennej Zj ako
Jj (x, Vj , Zj ):
Jj (x, Vj , Zj ) =
k−1
X
f 0 (xi , vi (xi ), zi ) + ϕ(xk ).
i=j
Potom môžeme úlohu (UW) zaradiť medzi úlohy Wj (x) do systému úloh W:
Wj (x) :
max
Vj ={vj ,...,vk−1 }
Ej, k−1 Jj (x, Vj , Zj )
xi+1 = fi (xi , ui , zi ),
i = j, ..., k−1,
(2.11)
xj = x,
vi (xi ) ∈ Wi (xi ),
zi ∈ Zi ,
∀xi ,
i = j, ..., k−1,
i = j, ..., k−1.
Kvôli zjednodušeniu ďalších úvah zavedieme jeden technický predpoklad a analogicky
k definícii 2.3 definujeme aj hodnotovú funkciu aj pre systém úloh Wj (x).
Predpoklad 2.10 Pre každé j = 0, . . . , k − 1 existuje optimálna stratégia Vj pre každú
úlohu Wj (x), kde x ∈ Xj (množina prípustných stavov). Teda existuje Vˆj také, že
max Ej, k−1 Jj (x, Vj , Zj ) = Ej, k−1 Jj (x, Vˆj , Zj )
Vj
pre každé x ∈ Xj .
14
2.4 ROVNICA DYNAMICKÉHO PROGRAMOVANIA
Definícia 2.11 (Hodnotová funkcia pre W) Funkciu Vj : Xj → R nazývame hodnotovou funkciou pre systém úloh Wj (x), keď platí
Vj (x) = max Ej, k−1 Jj (x, Vj , Zj )
Vj
pre každé x ∈ Xj a pre pevné j. Potom postupnosť funkcií V = {V0 , . . . , Vk−1 } nazývame
hodnotovou funkciou pre systém úloh W.
Kvôli dôkazu RDP pre úlohu s ohraničeniami (UW) dokážeme dve pomocné tvrdenia.
Tvrdenia aj dôkazy sú spracované podľa knihy [15], platia rovnako aj v prípade úlohy
s ohraničeniami.
Tvrdenie 2.12 Označme Vj = {vj , Vj+1 } prípustnú stratégiu pre Wj (xj ) a definujme
Ij (xj , Vj ) = Ej, k−1 [Jj (xj , Vj , Zj )].
Potom platí
Ij (xj , Vj ) = Ej fj0 (xj , vj (xj ), zj ) + Ij+1 (fj (xj , vj (xj ), zj ), Vj+1 ) .
(2.12)
D ô k a z. Označíme xj+1 = fj (xj , vj (xj ), zj ) a upravujeme výraz Ij (xj , Vj ):
Ij (xj , Vj ) = Ej, k−1 [Jj (xj , Vj , Zj )]
(2.13)
= Ej Ej+1, k−1 [fj0 (xj , vj (xj ), zj ) + Jj+1 (xj+1 , Vj+1 , Zj+1 )]
(2.14)
= Ej [fj0 (xj , vj (xj ), zj ) + Ej+1, k−1 Jj+1 (xj+1 , Vj+1 , Zj+1 )]
= Ej fj0 (xj , vj (xj ), zj ) + Ij+1 (fj (xj , vj (xj ), zj ), Vj+1 )
(2.15)
(2.16)
Rovnosť (2.14) vyplýva z rozpísania strednej hodnoty viacroznernej náhodnej premennej na vnorené stredné hodnoty, nasledujúca (2.15) využíva fakt, že fj0 nezávisí od
zj+1 , . . . , zk−1 . V poslednom riadku sme len prepísali označenie Ij+1 , čím je tvrdenie
dokázané.
15
2.4 ROVNICA DYNAMICKÉHO PROGRAMOVANIA
Veta 2.13 (Princíp optimality) Pre každé j = 0, . . . , k−1 platí: Nech Vj = {vj , Vj+1 }
je optimálna stratégia pre úlohu Wj (xj ) a xˆj+1 = fj (xj , vj (xj ), zˆj ) pre ľubovoľne zvolené
zˆj ∈ Zj . Potom Vj+1 je optimálna stratégia pre úlohu Wj+1 (ˆ
xj+1 ).
D ô k a z. Ukážeme, že ak by veta neplatila pre nejaké j, dôjdeme k sporu. Predpokladajme teda, že pre nejaké j, xj a zˆj veta neplatí. Potom existuje taká optimálna
stratégia Vˆj = {ˆ
vj , Vˆj+1 } pre úlohu Wj (xj ) taká, že Vˆj+1 nie je optimálnym riešením
úlohy Wj+1 (ˆ
xj+1 ), pričom xˆj+1 = fj (xj , vˆj (xj ), zˆj ) pre dané zˆj .
Označme V¯j+1 optimálnu stratégiu pre úlohu Wj+1 (ˆ
xj+1 ), táto existuje podľa predpokladu 2.10. Pre optimálnu stratégiu V¯j+1 musí ∀zj ∈ Zj platiť:
Ij+1 (xj+1 , V¯j+1 ) ≥ Ij+1 (xj+1 , Vˆj+1 ),
xj+1 = fj (xj , vˆj (xj ), zj ).
(2.17)
Zároveň aspoň pre zˆj , xˆj+1 = fj (xj , vˆj (xj ), zˆj ) musí platiť ostrá nerovnosť
Ij+1 (ˆ
xj+1 , V¯j+1 ) > Ij+1 (ˆ
xj+1 , Vˆj+1 ),
(2.18)
pretože stratégia Vˆj+1 nie je optimálna pre úlohu Wj+1 (ˆ
xj+1 ).
Skonštruujme teraz nové riadenie
V¯j = (ˆ
vj , V¯j+1 ),
označme xj+1 = fj (xj , vˆj (xj ), zj ) a počítajme:
Ij (xj , V¯j ) = Ej fj0 (xj , vˆj (xj ), zj ) + Ij+1 (xj+1 , V¯j+1 )
> Ej fj0 (xj , vˆj (xj ), zj ) + Ij+1 (xj+1 , Vˆj+1 ) = Ij (xj , Vˆj ).
(2.19)
Ostrá nerovnosť v (2.19) vyplýva z neostrej nerovnosti (2.17) pre všetky zj ∈ Zj a ostrej
(2.18) minimálne pre zˆj . Keďže Zj je diskrétna náhodná premenná, každá hodnota sa
nadobúda s kladnou pravdepodobnosťou a preto sa ostrá nerovnosť prenesie (zosumuje)
aj do strednej hodnoty Ezj .
Nerovnosť Ij (xj , V¯j ) > Ij (xj , Vˆj ) je však v spore s tým, že Vˆj je optimálnym riešením
úlohy Wj . Preto platí pôvodné tvrdenie.
Teraz už môžeme prejsť priamo k formulácii a dôkazu rovnice dynamického programovania pre úlohu s ohraničeniami (UW). Dôkaz podľa [15, Dôkaz Vety 2.7] platí len
s malými zmenami. Využijeme v ňom pomocné tvrdenie a princíp optimality.
16
2.4 ROVNICA DYNAMICKÉHO PROGRAMOVANIA
Formulácia a dôkaz rovnice dynamického programovania
Veta 2.14 (RDP pre úlohu s ohraničením) Majme úlohu (UW) spĺňajúcu predpoklad 2.10. Potom V = {V0 , . . . , Vk−1 } je hodnotová funkcia a Vˆ = {ˆ
v0 , . . . , vˆk−1 } optimálna stratégia práve vtedy, keď Vj , vˆj , j = 0, . . . , k − 1, spĺňajú pre každé j a x rovnicu
dynamického programovania:
Vj (x) =
max
v(x)∈Wj (x)
Ej fj0 (x, v(x), zj ) + Vj+1 (fj (x, v(x), zj ))
= Ej fj0 (x, vˆ(x), zj ) + Vj+1 (fj (x, vˆ(x), zj )) ,
Vk (x) = ϕ(x),
(2.20)
pre každé x.
D ô k a z. Ukážeme platnosť implikácie v oboch smeroch.
„⇒ÿ Začneme prvou rovnosťou - priamo z definície V vyplýva
Vk−1 (x) =
max
Ek−1 Jk−1 (x, Vk−1 , Zk−1 )
=
max
0
Ek−1 fk−1
(x, vk−1 (x), zk−1 ) + ϕ(fk−1 (x, vk−1 (x), zk−1 )) ,
Vk−1
vk−1 (x)∈Wk−1 (x)
(2.21)
keďže Vk−1 = {vk−1 } a pre dané x možno hodnotu funkcie vk−1 (x) zvoliť spomedzi všetkých prípustných hodnôt riadenia pre dané x, teda v oboch prípadoch maximalizujeme
cez množinu Wk−1 (x).
Pre j = 0, . . . , k − 2 dostávame:
1
2
Vj (x) = max Ej, k−1 Jj (x, Vj , Zj ) = max Ij (x, Vj )
Vj
Vj
0
3
= max Ej fj (x, vj (x), zj ) + Ij+1 (fj (x, vj (x), zj ), Vj+1 )
Vj
4
=
max max Ej fj0 (x, vj (x), zj ) + Ij+1 (fj (x, vj (x), zj ), Vj+1 )
vj (x)∈Wj (x) Vj+1
5
=
max max Ej fj0 (x, vj (x), zj ) + Ej Ij+1 (fj (x, vj (x), zj ), Vj+1 )
vj (x)∈Wj (x) Vj+1
6
=
max
Ej fj0 (x, vj (x), zj ) + max Ej Ij+1 (fj (x, vj (x), zj ), Vj+1 )
Vj+1
vj (x)∈Wj (x)
7
0
=
max
Ej fj (x, vj (x), zj ) + Ej max Ij+1 (fj (x, vj (x), zj ), Vj+1 )
Vj+1
vj (x)∈Wj (x)
0
8
=
max Ej fj (x, vj (x), zj ) + max Ij+1 (fj (x, vj (x), zj ), Vj+1 )
Vj+1
vj (x)∈Wj (x)
0
9
=
max Ej fj (x, vj (x), zj ) + Vj+1 (fj (x, vj (x), zj ))
(2.22)
vj (x)∈Wj (x)
Zdôvodnime jednotlivé kroky: 1 - definícia 2.11 funkcie Vj , 2 a 3 - rozpísali sme
podľa lemmy 2.12, pričom Vj = {vj , . . . , vk−1 }, 4 - prepísali sme po zložkách maximum
17
2.4 ROVNICA DYNAMICKÉHO PROGRAMOVANIA
cez Vj = {vj , Vj+1 }, 5 - aditívna vlastnosť strednej hodnoty, 6 - prvý sčítanec nezávisí od
Vj+1 , 7 - platí podľa [15, str. 104], 8 - vybrali sme Ej pred zátvorku, 9 - opäť z definície
Vj a lemmy. Tým sme dokázali prvú rovnosť.
Druhá rovnosť v (2.20) je dôsledkom princípu optimality a tvrdenia 2.12:
Vj (x) = max Ej, k−1 Jj (x, Vj , Zj ) = max Ij (x, Vj ) = Ij (x, Vˆj )
Vj
Vj
0
= Ej fj (x, vˆj (x), zj ) + Ij+1 (fj (x, vˆj (x), zj ), Vˆj+1 )
= Ej fj0 (x, vˆj (x), zj ) + Vj+1 (fj (x, vˆj (x), zj )) .
(2.23)
Prvá časť tvrdenia (implikácia „⇒ÿ) je týmto dokázaná.
„⇐ÿ Opačný smer dokážeme pomocou indukcie. Začnime pre i = k − 1: ak Vk−1
a vˆk−1 spĺňajú (2.20), tak platí
Vk−1 (x) =
max
v(x)∈Wk−1 (x)
0
Ek−1 fk−1
(x, v(x), zk−1 ) + ϕ(fk−1 (x, v(x), zk−1 ))
0
= Ek−1 fk−1
(x, vˆk−1 (x), zk−1 ) + ϕ(fk−1 (x, vˆk−1 (x), zk−1 ))
= max Ek−1 Jk−1 (x, Vk−1 , Zk−1 ) = Ek−1 Jk−1 (x, Vˆk−1 , Zk−1 ),
Vk−1
pričom sme dosadili Vk (x) = ϕ(x). Výpočet dokazuje, že vˆk−1 (x) je optimálna spätná
väzba a Vk−1 jej hodnotová funkcia. Tým je prvý krok indukcie ukončený.
Teraz predpokladajme, že veta platí pre i = j +1, . . . , k −1. Chceme dokázať, že platí
aj pre i = j, . . . , k − 1. Majme funkcie Vj , Vj+1 , . . . , Vk , ktoré vyhovujú rovnici 2.20 a
x ∈ Xj . Podľa indukčného predpokladu sú Vj+1 , . . . , Vk hodnotové funkcie pre príslušné
úlohy. Dokážme sporom, že aj Vj je hodnotovou funkciou. Predpokladajme, že Vj nie je
maximálna hodnota účelovej funkcie pre Wj (x). Teda musí existovať taká stratégia V¯j ,
že platí
Ej, k−1 Jj (x, V¯j , Zj ) > Vj (x).
(2.24)
Potom však
Vj (x) < Ej, k−1 Jj (x, V¯j , Zj ) = Ij (x, V¯j )
= Ej fj0 (x, v¯j (x), zj ) + Ij+1 (fj (x, v¯j (x), zj ), V¯j+1 )
≤ Ej fj0 (x, v¯j (x), zj ) + Vj+1 (fj (x, v¯j (x), zj ))
≤
max Ej fj0 (x, vj (x), zj ) + Vj+1 (fj (x, vj (x), zj )) ,
(2.25)
vj (x)∈Wj (x)
pričom prvá neostrá nerovnosť vyplýva z indukčného predpokladu - keďže Vj+1 je hodnotová funkcia, Ij+1 ≤ Vj+1 pre akúkoľvek stratégiu. Posledná nerovnosť je v spore s tým,
že Vj , Vj+1 , . . . spĺňali RDP. Preto Vj je hodnotová funkcia.
18
2.4 ROVNICA DYNAMICKÉHO PROGRAMOVANIA
Nech teraz aj funkcie vˆj , vˆj+1 , . . . , vˆk−1 spĺňajú RDP. Podľa indukčného predpokladu je Vˆj+1 = {ˆ
vj+1 , . . . , vˆk−1 } je optimálnou stratégiou. Chceme dokázať, že aj
ˆ
ˆ
Vj = {ˆ
vj , Vj+1 } je optimálnou stratégiou. Platí
Ij (x, Vˆj ) = Ej fj0 (x, vˆj (x), zj ) + Ij+1 (fj (x, vˆj (x), zj ), Vˆj+1 )
= Ej fj0 (x, vˆj (x), zj ) + Vj+1 (fj (x, vˆj (x), zj ))
= Vj (x),
(2.26)
kde sme využili najprv tvrdenie 2.12, potom fakt, že Vˆj+1 je optimálna stratégia a Vj+1
je hodnotová funkcia a nakoniec, že vˆj spĺňa RDP. Pretože Vj je hodnotová funkcia, tak
(2.26) dokazuje optimalizu stratégie Vˆj . Dôkaz je hotový.
19
Kapitola 3
Numerické príklady
V tejto kapitole sa zameriame na numerické príklady, ktorými overíme možnosť použitia
RDP na stochastické úlohy s ohraničením v tvare strednej hodnoty. Riešenie získané
optimálnym riadením porovnáme s riešením metódou stochastického programovania.
Okrem popisu algoritmov uvádzame získané numerické výsledky oboch metód.
3.1 Úloha predavača reďkoviek
Numerické experimenty sme sa rozhodli realizovať na úlohe o predavačovi reďkoviek.
Námet sme získali z knihy [15], úlohu sme prispôsobili pre naše potreby. Jej výhodou je
diskrétna povaha stavu (nie je teda potrebná diskretizácia vo výpočte OR) a konečné
rozdelenie náhodnej premennej. Úlohu sme sformulovali nasledovne:
Predavač chce maximalizovať svoj zisk z predaja reďkoviek počas plánovacieho obdobia dlhého k dní. Každé ráno i-teho dňa nakúpi u dodávateľa ui reďkoviek za nákupnú
cenu n za zväzok, ktoré potom počas dňa predáva za cenu pi . Dopyt po reďkovkách zi je
náhodný, pričom zi nadobúda hodnoty z množiny Zi . Pre jednoduchosť predpokladajme
rovnomerné rozdelenie. Reďkovky, ktoré daný deň nepredá, môže predávať aj ďalší deň,
avšak vznikne mu tým strata s za každý zväzok (táto strata predstavuje napr. náklady
na skladovanie).
20
3.2 STOCHASTICKÉ OPTIMÁLNE RIADENIE
Predpokladajme, že predavač začína s prázdnym skladom (x0 = 0). Posledný deň
večer chce mať na sklade v priemere aspoň µ reďkoviek, keďže má kontrakt s veľkoodberateľom. Ten k-ty deň večer odkúpi všetky zostávajúce reďkovky za zostatkovú hodnotu
h, pričom požaduje, aby ich bolo priemerne aspoň µ.
Budeme riešiť rôzne verzie tejto úlohy. V autonómnej úlohe zvolíme predajnú cenu
pi ≡ p konštantnú, rovnako dopyt zi ∈ Zi ≡ Z bude rovnako rozdelený počas celého
plánovacieho obdobia. V neautonómnej verzii sa bude cena, resp. dopyt v priebehu
obdobia meniť.
3.2 Stochastické optimálne riadenie
V tejto časti úlohu predavača reďkoviek najskôr sformulujeme v tvare úlohy optimálneho
riadenia. Popíšeme tiež rekurzívny algoritmus riešenia za pomoci rovnice dynamického
programovania.
Zostavme teraz stochastickú úlohu optimálneho riadenia pre náš problém. Aktuálny
počet zväzkov reďkoviek ráno i-teho dňa označíme xi (stavová premenná), nákup pre
daný deň ui = vi (xi ) v tvare odozvovej funkcie, pričom možné hodnoty nákupu patria
do množiny Ui .
Teda obchodník bude ponúkať celkovo xi + ui reďkoviek. Dopyt počas daného dňa
označíme zi . Ak bude dopyt väčší ako ponuka, obchodník predá všetky reďkovky. V opačnom prípade mu nejaké reďkovky ostanú na sklade (tento počet označíme xi+1 ). Predpokladáme, že všetky náhodné premenné (dopyt v jednotlivých dňoch) sú združene
nezávislé a teda ani neuspokojený dopyt z jedného dňa sa neprenáša do ďalšieho.
Účelová funkcia - maximalizácia zisku predavača reďkoviek bude vyjadrená nasledovne:
fi0 (xi , ui , zi ) = pi min( xi + ui ; zi ) − n ui − s xi .
|
{z
} |{z} |{z}
predaj
nákup
(3.1)
straty
Navyše uvažujeme aj odpredaj reďkoviek zostávajúcich na konci (h za zväzok), teda
funkciu koncového stavu ϕ(x) = h x.
Počet reďkoviek na sklade počas dňa ovplyvňuje ich nákup a predaj (v závislosti od
náhodného dopytu), preto diferenčnú rovnicu zapíšeme ako:
xi+1 = fi (xi , ui , zi ) = max( xi + ui − zi ; 0 ).
(3.2)
Napokon pridáme požadované koncové ohraničenie - zostávajúci počet reďkoviek na
sklade musí spĺňať Ek−1 [xk ] ≥ µ pre zvolenú hodnotu µ.
21
3.2 STOCHASTICKÉ OPTIMÁLNE RIADENIE
Na základe predchádzajúcich úvah môžeme sformulovať úlohu predavača reďkoviek
v tvare stratégií nasledovne:
" k−1
#
X
max
E
pi min(xi + vi (xi ); zi ) − n vi (xi ) − s xi + h xk
V={v0 ,...,vk−1 }
i=0
xi+1 = max(xi + vi (xi ) − zi ; 0),
i = 0, ..., k−1,
x0 = 0,
vi (xi ) ∈ Ui ,
i = 0, ..., k−1,
zi ∈ Zi ,
h
i
Ek−1 max(xk−1 + vk−1 (xk−1 ) − zk−1 ; 0) ≥ µ.
i = 0, ..., k−1,
(3.3)
Riešenie pomocou rovnice dynamického programovania
Sformulovanú úlohu (3.3) môžeme efektívne riešiť pomocou rovnice dynamického programovania (RDP). Využijeme pri tom vetu 2.14, ktorá dáva návod na výpočet hodnotovej
funkcie „od koncaÿ. Postupne budeme pre jednotlivé časové etapy i = k −1, k −2, . . . , 0
hľadať hodnotovú funkciu tak, aby platilo
Vi (x) =
max Ei fi0 (x, v(x), zi ) + Vi+1 (fi (x, v(x), zi )) ,
v(x)∈Wi (x)
Vk (x) = ϕ(x) = h x,
pričom konkrétne v našej úlohe majú funkcie fi0 , fi tvar
fi0 (xi , v(xi ), zi ) = pi min(xi + vi (xi ); zi ) − n vi (xi ) − s xi ,
fi (xi , v(xi ), zi ) = min max(xi + vi (xi ) − zi ; 0); xMAX ,
i = 0, ..., k−1,
i = 0, ..., k−1.
Z technických dôvodov sme upravili diferenčnú rovnicu pre fi pridaním maximálnej hodnoty xMAX . Túto zvolíme dostatočne veľkú, aby neovplyvnila riešenie, avšak takú, aby
množina dosiahnuteľných stavov X = {0, 1, . . . , xMAX } nebola zbytočne veľká. Množiny
prípustných stratégií Wi (x) sú určené podmienkou na strednú hodnotu koncového stavu,
v nadväznosti na teóriu ich zvolíme v tvare rovnice (2.10).
Nájsť hodnotu Vi (x) pre dané i znamená pre každé x z množiny prípustných stavov
Xi ⊂ X nájsť optimálnu hodnotu stratégie vi (x). To urobíme postupným preskúmaním
všetkých prípustných hodnôt riadenia z množiny Wi (x), pričom priebežne ukladáme
najvyššiu hodnotu Vi (x), akú sa nám pre dané x podarilo dosiahnuť a tiež prislúchajúcu
hodnotu vi (x).
22
3.3 STOCHASTICKÉ PROGRAMOVANIE
Postupným výpočtom pre jednotlivé časy i nájdeme hodnotovú funkciu aj optimálnu stratégiu pre danú úlohu. Očakávanú hodnotu účelovej funkcie potom predstavuje
V0 (x0 ). Pri numerickom riešení využijeme program Matlab.
3.3 Stochastické programovanie
Zadaný problém - úlohu predavača reďkoviek vyriešime aj použitím stochastického programovania s cieľom porovnať získané výsledky. V podstate chceme zistiť, aký je prínos
riešenia získaného stochastickým optimálnym riadením, teda o koľko v priemere zvýši
predavačov zisk použitie optimálnej stratégie.
V stochastickom programovaní máme dve možnosti - buď zostaviť úlohu ako viacstupňovú (pre k dní plánovacieho obdobia potrebujeme (k + 1)-stupňovú úlohu) alebo
vygenerovať náhodné scenáre a previesť problém na úlohu lineárneho programovania.
Keďže úlohu budeme riešiť na dlhšom horizonte k = 20 dní, zvolili sme druhú možnosť.
Hlavná myšlienka postupu takéhoto postupu je jednoduchá: v prvom kroku vygenerujeme určitý počet (N ) náhodných scenárov, ktoré predstavujú konkrétne realizácie
náhodných premenných zi . V druhom kroku potom riešime špeciálnu úlohu lineárneho
programovania - maximalizácia priemerného zisku z týchto scenárov plynúcu pri programovom riadení U = {u0 , u1 , . . . , uk−1 }, spoločnom pre všetky náhodné scenáre.
Pri zostavovaní úlohy lineárneho programovania pritom musíme pamätať na rôzne
druhy ohraničení, podobne ako pri formulácii v tvare úlohy OR. Patria sem o ohraničenia
v tvare rovností (napr. podmienka kontinuity stavu na sklade) aj nerovností (najviac
možno predať toľko výrobkov, koľko sa nachádza na sklade a i.).
Generovanie náhodných scenárov
Prvým krokom riešenia za pomoci scenárov je vygenerovanie N náhodných scenárov.
Označme náhodný dopyt v i-tom dni j-teho scenára ako zij . Potom pri generovaní budeme náhodne vyberať zij z množiny možných hodnôt dopytu Zi . Pri generovaní rovnomerného rozdelenia dopytu použijeme základnú Matlabovskú funkciu rand().
Otázkou je, koľko scenárov je vhodné vygenerovať napr. pre k = 20 dňové obdobie.
Pri veľmi malom počte scenárov bude nájdené riešenie (programové riadenie) vhodné
len pre tieto konkrétne prípady. Pri vyššom počte scenárov sa viac prejaví náhodný charakter úlohy a nájdené riadenie bude lepšie reflektovať „priemernýÿ prípad. Na druhej
strane, čím vyšší počet scenárov, tým väčší je rozmer úlohy LP, ktorú budeme riešiť. Ok23
3.3 STOCHASTICKÉ PROGRAMOVANIE
rem počtu premenných, ktorých je rádovo 2 N k, výrazne rastie aj množstvo ohraničení
(pre každý scenár máme k rovníc a 7k nerovníc).
Napr. pri k = 20 dňoch a len N = 2 scenároch bude počet premenných 100, pri
N = 100 scenároch bude už 4020. Preto budeme vzhľadom na výpočtové a pamäťové
kapacity používať rádovo desiatky scenárov (cca 40-70). Aj pri tomto počte dávajú
získané riešenia celkom dobré výsledky, ako uvázdzame medzi konkrétnymi výsledkami
v podkapitole 3.5.
Formulácia úlohy lineárneho programovania
Sformulujme teraz úlohu lineárneho programovania, v ktorej budeme hľadať optimálne
hodnoty programového riadenia na N náhodných scenároch, ktoré predstavujú konkrétny (deterministický) dopyt. Použijeme tieto označenia:
i – index pre číslo dňa, i ∈ I := {0, . . . , k − 1},
j – index pre číslo scenára, j ∈ J := {1, . . . , N },
ui – objednávka v i-tom dni (programové riadenie), pre ∀i ∈ I,
xji – stav na sklade v i-tom dni j-teho scenára, pre ∀i ∈ I, ∀j ∈ J,
zij – náhodný dopyt v i-tom dni j-teho scenára, pre ∀i ∈ I, ∀j ∈ J,
yij – skutočne predané množstvo v i-tom dni j-teho scenára, pre ∀i ∈ I, ∀j ∈ J.
Rozmery jednotlivých premenných budú u ∈ Rk , x ∈ RN ×(k+1) , y ∈ RN ×k . Nasledujú
jednotlivé ohraničenia a účelová funkcia pre úlohu LP.
• Rovnice pre vývoj na sklade a počiatočný stav (kontinuita stavu)
xji+1 = xji + ui − yij ,
∀i ∈ I, ∀j ∈ J,
xj0 = 0,
∀j ∈ J.
(3.4)
• Obmedzenia pre aktuálny stav a riadenie
xji ∈ Xi ⇔ 0 ≤ xji ≤ xMAX ,
∀i ∈ I, ∀j ∈ J,
u i ∈ Ui
∀i ∈ I.
⇔ 0 ≤ ui ≤ max ui ,
ui ∈Ui
24
(3.5)
3.4 POROVNÁVANIE KVALITY RIEŠENÍ
• Obmedzenia predaného množstva (podľa dopytu a stavu na sklade)
0 ≤ yij ≤ zij ,
∀i ∈ I, ∀j ∈ J,
yij ≤ xji + ui ,
∀i ∈ I, ∀j ∈ J.
(3.6)
• Podmienka na strednú hodnotu koncového stavu Ek−1 [ xjk ] ≥ µ v tvare súčtu
X j
xk ≥ µ N .
(3.7)
j∈J
• Účelová funkcia zahŕňa príjem z predaja, náklady na nákup, skladovanie a výnos
z odpredaja ostávajúcich kusov; má tvar
#
"
X
X
X
X
1
1
1 XX
pi yij −
n ui −
s xji +
h xjk .
max
u, x, y
N j∈J i∈I
N
N
i∈I
j∈J i∈I
j∈J
(3.8)
Teda úloha lineárneho programovania, ktorou budeme hľadať optimálne riadenie pre
náhodné scenáre, pozostáva z účelovej funkcie (3.8) a ohraničení (3.4) – (3.7). Úlohu
budeme riešiť pomocou zabudovanej funkcie linprog() programu Matlab.
Poznamenajme ešte, že v prípade riešenia úlohy LP nemáme zaručené, že optimálne
riešenie bude celočíselné (hoci povaha úloha to predpokladá). Úloha obmedzuje iba
maximálnu a minimálnu hodnotu riadenia ohraničením (3.5). Pre zjednodušenie však
budeme ďalej pracovať s nájdeným riešením, keďže celočíselné by zrejme malo ešte nižšiu
hodnotu účelovej funkcie.
3.4 Porovnávanie kvality riešení
Riešenia získané dynamickým a stochastickým programovaním nemajú rovnaký tvar.
V prípade dynamického programovania je riešením odozvová funkcia vi (x), ktorá určuje,
aké má byť optimálne riadenie pre každú kombináciu i a x. Oproti tomu riešením úlohy
stochastického programovania je konkrétna postupnosť riadení U = {u0 , u1 , . . . , uk−1 },
optimálna na zvolenej množine náhodných scenárov. Takéto riešenia nie je možné priamo
porovnať.
V oboch prípadoch riešenie zahŕňa aj očakávanú (priemernú) hodnotu účelovej funkcie (hodnota V0 (x0 ) v OR, resp. dosiahnutá hodnota účelovej funkcie úlohy LP). Ani
tieto sa však nedajú priamo porovnávať, keďže v OR je to stredná hodnota cez všetky
náhodné premenné zi a v prípade SP iba cez vygenerované scenáre (nejakej podmnožine
všetkých scenárov, čo môže byť výhodnejšie).
25
3.5 KONKRÉTNE VÝSLEDKY
Preto sme sa rozhodli získané riešenia porovnávať priamo v reálnej situácii: vygenerujeme nový náhodný scenár dopytu a porovnáme výsledok oboch metód: celkový zisk
pri použití programového riadenia získaného stochastickým programovaním a stratégie získanej optimálnym riadením. Vypočítať výsledný zisk pri danom dopyte a riadení
(stratégii) je pritom jednoduchá deterministická úloha, tým pádom môžeme porovnanie
opakovať aj na veľkom počte rôznych náhodných scenárov (môže to byť rádovo 1000 pre
jedno nastavenie parametrov).
Obe metódy budeme porovnávať na širokej množine parametrov úlohy, napr. autonómna alebo neautonómna cena, resp. dopyt, ale aj rôzne hodnoty parametra µ (očakávaná koncová hodnota). Pri porovnávaní budeme sledovať nasledujúce ukazovatele:
• očakávaná hodnota zisku a xk každej z metód (vyplývajúca z výpočtu OR, LP),
• dosiahnutá priemerná, resp. aj minimálna a maximálna hodnota zisku oboch metód,
• v koľkých percentách prípadov má väčší zisk riešenie OR (je úspešnejšie),
• reálna hodnota riešenia získaného optimálnym riadením (rozdiel medzi priemernými hodnotami zisku oboch metód),
• skutočne dosiahnutá stredná hodnota xk (overíme splnenie koncovej podmienky).
3.5 Konkrétne výsledky
Začnime jednoduchými príkladmi. Pre pevné hodnoty parametrov vypočítame riešeníe
optimálnym riadením (OR) aj stochastickým programovaním (SP). Treba poznamenať,
že kým v OR je riešenie pre pevné hodnoty parametrov vždy rovnaké (vypočítame rovnaký tvar odozvových funkcií aj očakávanú hodnotu zisku), v prípade SP to tak byť
nemusí. Konkrétne výsledky - riadenie aj očakávaný zisk závisia od náhodne vygenerovanej sady scenárov. Potom už pri samotnom porovnávaní vygenerujeme ďalšie náhodné
scenáre, na ktoré reagujú vypočítané riešenia, takže aj dosiahnutý (priemerný) zisk OR
aj SP sa mení každým behom programu.
Tieto vlastnosti ukážeme na dvoch príkladoch v tabuľkách 3.1 a 3.2. Riešenie SP
sme počítali trikrát (výpočty 1, 2, 3), pričom každé vypočítané riešenie sme dvakrát
porovnávali s riešením OR na náhodnej sade 1000 scenárov (A, B). Popíšme stĺpce
oboch tabuliek. Očakávaný zisk obsahuje hodnotu zisku vypočítanú priamo SP, OR.
26
3.5 KONKRÉTNE VÝSLEDKY
Príklad 1
Očak. zisk
Priem. zisk
Min. zisk
Max. zisk
Rozdiel
Úspešnosť
Výpočet
SP
OR
SP
OR
SP
OR
SP
OR
abs.
rel.
OR
1A
56,1
63,6
53,4
64,2
-44,7
18,6
76,1
109,4
10,8
20,2%
87,8%
1B
56,1
63,6
52,4
63,5
-79,7
9,4
76,6
103,4
11,1
21,1%
87,1%
2A
59,4
63,6
49,0
62,9
-121,1
15,8
79,5
117,0
13,9
28,4%
91,8%
2B
59,4
63,6
49,0
63,1
-92,3
23,8
79,2
109,4
14,1
28,7%
90,4%
3A
54,6
63,6
52,6
63,5
-75,0
12,2
74,8
104,6
10,9
20,8%
88,1%
3B
54,6
63,6
52,8
63,8
-67,4
19,4
74,6
102,6
11,0
20,9%
89,4%
Priemer
56,7
63,6
51,5
63,5
-80,0
16,5
76,8
107,7
12,0
23,3%
89,1%
Tabuľka 3.1: Príklad 1, hodnoty parametrov sú k = 20, p = 0,7, n = 0,4, s = 0,1, h = 0,
µ = 10, N = 50 scenárov.
Príklad 2
Očak. zisk
Priem. zisk
Min. zisk
Max. zisk
Rozdiel
Úspešnosť
Výpočet
SP
OR
SP
OR
SP
OR
SP
OR
abs.
rel.
OR
1A
70,8
78,1
64,6
78,3
-69,3
23,6
92,5
126,8
13,7
21,2%
90,3%
1B
70,8
78,1
64,8
78,4
-136,8
3,1
92,4
127,4
13,6
21,0%
87,5%
2A
66,0
78,1
64,7
78,9
-67,3
18,5
85,4
125,3
14,2
21,9%
89,6%
2B
66,0
78,1
64,4
78,3
-41,6
16,1
86,6
132,5
13,9
21,6%
89,8%
3A
70,1
78,1
64,4
78,6
-153,3
20,6
90,2
134,6
14,3
22,2%
89,9%
3B
70,1
78,1
64,0
78,0
-129,9
14,3
90,4
128,6
14,0
21,9%
89,3%
Priemer
69,0
78,1
64,5
78,4
-99,7
16,0
89,6
129,2
14,0
21,6%
89,4%
Tabuľka 3.2: Príklad 2, hodnoty parametrov sú k = 20, p = 0,9, n = 0,5, s = 0,2,
h = 0,2, µ = 5, N = 50 scenárov.
Priemerný zisk zase predstavuje skutočne dosiahnutý priemerný zisk na náhodne vygenerovanej sade scenárov. Minimálny a maximálny zisk sú opäť skutočne dosiahnuté
hodnoty pre konkrétne scenáre, uvádzame ich na ukážku, v akom rozsahu sa skutočne
dosiahnutý zisk pohybuje. Stĺpec Rozdiel počítame medzi priemerným ziskom oboch metód, v podstate predstavuje hodnotu riešenia OR (o túto sumu má OR vyšší zisk oproti
SP). Posledný stĺpec Úspešnosť OR hovorí, v koľkých percentách testovacích prípadov
bol zisk dosiahnutý OR metódou vyšší.
V oboch príkladoch sa ukázalo ako výhodnejšie použiť OR riešenie, ktoré dosahovalo
vyšší zisk priemerne v 89% percentách všetkých náhodných scenárov. Priemerný zisk
v OR bol oproti SP vyšší oproti o 21–23%. Tento výsledok však nie je úplne prekvapujúci,
keďže v podstate porovnávame programové riadenie a optimálnu stratégiu. Výpočet
netrval dlho, metódou OR trval 10 sekúnd a v prípade použitia SP 7–20 sekúnd.
27
3.5 KONKRÉTNE VÝSLEDKY
Príklad 1
Očakávané xk
Priemerné xk
Očakávané xk
Priemerné xk
Výpočet
SP
SP
9,98
1A
6,47
5,52
6,14
6,61
10,11
10,48
1B
6,47
5,52
6,11
6,60
10,48
14,35
10,39
2A
5,50
5,52
4,30
6,55
10,00
10,48
14,10
10,25
2B
5,50
5,52
4,38
6,61
3A
10,00
10,48
9,89
10,75
3A
5,00
5,52
5,69
6,58
3B
10,00
10,48
9,89
10,60
3B
5,00
5,52
5,78
6,63
Výpočet
SP
OR
SP
1A
10,00
10,48
10,06
1B
10,00
10,48
2A
10,00
2B
Príklad 2
OR
OR
OR
Tabuľka 3.3: Príklady 1 a 2, očakávané a skutočne dosiahnuté stredné hodnoty xk .
Overme ešte splnenie podmienky na strednú hodnotu. V tabuľke 3.3 uvádzame vypočítané očakávané a skutočne dosiahnuté priemerné hodnoty koncového stavu xk . V prípade SP bola očakávaná hodnota väčšinou presne µ = 10 v prvom príklade, resp. µ = 5
v druhom (čo sa dosahovalo aj neceločíselným riadením v poslednej perióde). V optimálnom riadení sa využívalo len celočíselné (povolené) riadenie, preto aj predpokladaná
xk bola vyššia než požadovaná. V skutočnosti však na náhodnej sade scenárov SP riešenie nedosiahlo splnenie požadovaného ohraničenia v 4/12 prípadoch, OR iba v jednom
prípade. Opäť to zrejme súvisí s tým, že je riadenie v tvare spätnej väzby adresnejšie
reaguje na nízku hodnotu stavu.
Počet scenárov
Zaujímalo nás, ako závisí kvalita riešenia (úspešnosť stochastického programovania) od
počtu scenárov, ktoré sme použili v úlohe lineárneho programovania. Zvolili sme preto
pevné parametre úlohy a do tabuľky 3.4 vypočítali pre rôzne počty scenárov očakávaný
a dosiahnutý zisk, ako aj rozdiel ziskov a úspešnosť OR. Riešenie sme počítali pre 10
až 100 scenárov, keďže väčší počet sa nám nepodarilo vypočítať (kvôli pamäťovému
obmedzeniu počítača).
Z výsledkov môžeme vyvodiť záver, že vyšší počet scenárov má v priemere pozitívny
vplyv na úspešnosť SP riadenia, avšak často má väčší vplyv samotné náhodné generovanie scenárov. Pri počte scenárov 40 a viac má OR stále o 20–21% vyšší zisk ako SP,
úspešnosť OR sa pohybuje v priemere od 90% do 84 %, pri 20, resp. 100 scenároch. Pre
zaujímavosť v tabuľke uvádzame aj čas trvania jednotlivých výpočtov, čo je nemenej
podstatný ukazovateľ. Ako vidieť, s rastom počtu scenárov rýchlo rastie aj čas trvania
výpočtu. Na základe tohto porovnania sme ďalej uvažovali priemerne 50 scenárov.
28
3.5 KONKRÉTNE VÝSLEDKY
Očak. zisk
Priem. zisk
Úspešnosť
Čas výpočtu
scenárov
Počet
SP
OR
SP
OR
abs.
Rozdiel
rel.
OR
(min) : s
10
64,2
76,4
57,2
76,0
18,8
32,9%
94,5%
1,4
20
67,5
76,4
60,1
75,4
15,4
25,6%
88,6%
2,1
30
70,0
76,4
61,8
76,3
14,6
23,6%
89,7%
4,5
40
65,9
76,4
62,2
75,3
13,1
21,0%
88,9%
6,7
50
64,7
76,4
63,5
76,3
12,8
20,2%
86,4%
16,3
60
67,1
76,4
62,5
76,1
13,7
21,9%
89,2%
37,5
70
65,1
76,4
62,9
75,9
13,0
20,7%
84,5%
1:00,1
80
58,2
76,4
55,4
76,4
21,0
37,8%
91,2%
2:19,5
90
66,9
76,4
62,1
75,5
13,4
21,6%
84,8%
2:52,7
100
67,0
76,4
62,5
75,0
12,5
19,9%
84,2%
4:06,8
Priemer
65,7
76,4
61,0
75,8
14,8
24,5%
88,2%
Tabuľka 3.4: Príklad 3, zmena počtu scenárov N , hodnoty parametrov sú k = 20,
p = 0,8, n = 0,4, s = 0,2, h = 0, µ = 10.
Priemerná
Vývoj
Počet
Očak. zisk
Priem. zisk
cena p¯
ceny
scenárov
SP
OR
SP
OR
abs.
Rozdiel
rel.
OR
0,75
lomená f.
30
48,4
49,1
39,7
50,4
10,7
26,9%
85,7%
0,80
lomená f.
30
61,3
71,8
61,0
73,0
12,0
19,7%
89,6%
0,71
kvadratická f.
30
33,9
37,3
30,3
37,8
7,6
24,9%
87,2%
0,72
kvadratická f.
50
35,6
39,5
34,5
40,3
5,8
16,7%
84,1%
0,77
náhodné ceny
70
55,5
62,5
54,9
62,8
7,9
14,4%
83,4%
20,5%
86,0%
Priemer
Úspešnosť
Tabuľka 3.5: Príklad 4, neautonómna úloha so zmenou ceny, hodnoty parametrov sú
k = 20, n = 0,5, s = 0,15, h = 0,3, µ = 0.
Dopyt
Priemerný
Počet
Očak. zisk
Priem. zisk
dopyt z¯i
víkendový
scenárov
SP
OR
SP
OR
abs.
rel.
OR
7
40
38,6
40,4
36,6
41,0
4,4
12,1%
83,7%
víkendový
7
70
37,9
40,4
36,8
41,2
4,4
12,0%
85,6%
max v strede
10,5
40
67,0
68,4
64,6
69,3
4,7
7,2%
83,8%
max v strede
10,5
70
65,9
68,4
64,7
68,9
4,1
6,4%
83,0%
9,4%
84,0%
Priemer
Rozdiel
Úspešnosť
Tabuľka 3.6: Príklad 5, neautonómna úloha so zmenou dopytu, hodnoty parametrov sú
k = 20, n = 0,9, n = 0,5, s = 0,25, h = 0, µ = 3.
29
3.5 KONKRÉTNE VÝSLEDKY
Neautonómna cena
Porovnajme teraz obe metódy na neautonómnej úlohe. Pre jednoduchosť ponechajme
rovnice v pôvodnom tvare, meniť budeme cenu pi . Uvažujme rôzne postupnosti cien:
lomenú funkciu, v prvej polovici času lineárne cena rastie a potom klesá, kvadratickú
funkciu, cena je tvaru ax2 s najvyššou hodnotou v strede časového intervalu a náhodné
ceny, ktoré sme vygenerovali a potom použili ako pevné.
Pre lepšiu predstavu v tabuľke 3.5 okrem výsledkov uvádzame aj priemernú cenu p¯
počas celého obdobia. Opäť môžeme byť len spokojní s výsledkami, hodnota rozdielu
medzi riešeniami bola priemerne 20%, pričom OR malo lepší zisk v 86% všetkých testovacích prípadov.
Zmena dopytu
Neautonómnu úlohu dostaneme aj v prípade, že nastavíme rôzny dopyt v jednotlivých
dňoch. Predpokladajme teda, že sa bude meniť - zvoľme si dva druhy dopytu:
• víkendový dopyt, ktorý sa strieda - prvé štyri dni týždňa je dopyt 0 až 10 zväzkov
a ostatné tri dni (piatok-nedeľa) má hodnotu 5 až 15 zväzkov,
• najväčší v strede, ktorý dosahuje najväčšiu hodnotu dopytu 10–20 v strede časového intervalu, pričom prvú polovicu času dopyt rastie a potom klesá.
Pre každý dopyt sme vypočítali SP riešenie použitím 40 aj 70 scenárov, výsledky však
boli takmer rovnaké. Podrobnejšie v tabuľke 3.6 - úspešnosť OR vyšla priemerná okolo
84%, hodnota riešenia 6–12 percent.
Záverečné poznámky
V rámci tejto kapitoly sme uskutočnili veľký počet numerických experimentov, v ktorých
sme na náhodných scenároch porovnávali riešenia získané optimálnym riadením a scenármi v stochastickom programovaní. Výsledok je pomerne jednoznačný v prospech OR:
táto metóda dosiahla vyšší zisk v 80–90% náhodných scenárov, pričom priemerný prínos
OR riešenia predstavoval okolo 20%.
Potvrdilo sa, že optimálna stratégia má pred programovým riadením značný náskok.
Aj preto sme do ďalších cieľov dizertačnej práce zaradili porovnanie s riešením úlohy
lineárneho programovania, v ktorej nebudeme hľadať programové riadenie, ale (lineárnu)
spätnoväzobnú funkciu. Výsledok potom nemusí byť jednoznačný.
30
Kapitola 4
Prehľad literatúry
V nasledujúcej kapitole sa zameriame na dva hlavné body článkov o riešení stochastických úloh: tematické zaradenie úloh (aké problémy sa riešia) a metódy používané
pri riešení - či a akým spôsobom autori použili stochastické optimálne riadenie alebo
viacstupňové stochastické programovanie. Cieľom je spracovať stručný prehľad článkov
z týchto oblastí.
4.1 Témy stochastických úloh
Potreba modelovať realitu nás veľmi často vedie k úlohám, v ktorých nie sú niektoré
parametre vopred známe, nepoznáme ich hodnotu presne alebo majú náhodnú povahu.
Takými sú podľa [27] väčšinou vstupné parametre modelu - dopyt spotrebiteľov alebo
čas výroby. Deterministické modely takýchto problémov nedávajú postačujúce výsledky.
Preto musíme siahnuť po stochastickom aparáte, ktorý ponúka dobre rozpracovaný základ na vyjadrenie a riešenie reálnych problémov.
Nasledujúca časť ponúka stručný prehľad zaujímavých aplikácií a problémov formulovaných ako stochastické úlohy. Poznamenajme, že kým niektoré problémy sú reálne
problémy z praxe, ďalšie sú len akademické príklady, ktoré demonštrujú niektoré aspekty
modelovania v stochastických úlohách.
31
4.1 TÉMY STOCHASTICKÝCH ÚLOH
Kvetinárka
V článku [14] Dupačová a spol. píšu o probléme kvetinárky, čo je podobný problém ako
predavač novín v [7, str. 31]. Dievča predáva ruže za c, musí ich však pred začiatkom
predaja nakúpiť za cenu p. Kvety, ktoré nepredá, môže bez ďalších nákladov odložiť na
druhý deň, kedy ich už musí predať. Dopyt zákazníkov po ružiach je náhodný.
Cieľom kvetinárky je maximalizovať celkový očakávaný zisk. Plánovací horizont zodpovedá obdobiu, počas ktorého nepretržite predáva. Napríklad víkendu - prvú dávku
kvetov kúpi v piatok večer, predáva ich v sobotu, v sobotu večer kúpi druhú dávku,
ktorú môže predávať v nedeľu. Kvety, ktoré jej zostanú v nedeľu večer, musí vyhodiť.
Takto formulovaný problém sa dá jednoducho riešiť či už stochastickým alebo dynamickým programovaním. Ako autorka poznamenáva, podstatne zložitejšie to bude
v prípade, že chceme naplánovať dievčaťu predaj počas dvojmesačných letných prázdnin.
Dopĺňanie bankomatov
Jednou z úloh banky je zabezpečiť dostatok hotovosti v bankomatoch. Rozhodnutie,
kedy a koľko peňazí doplniť do bankomatu, pritom musí odrážať budúci dopyt zákazníkov. Ten však nie je vopred známy - je náhodný. Naplniť priveľa vedie k stratám na
úrokoch (v porovnaní s tým, že by sa peniaze uložili na termínovaný vklad), naplniť
primálo môže viesť k dodatočným nákladom (či už mimoriadne naplnenie alebo strata
dobrého mena banky).
Problému dopĺňania bankomatov sa venuje Castro vo svojom článku [11]. Keďže na
základe historických dát môžeme veľmi dobre odhadnúť rozdelenie dopytu pre konkrétny
bankomat, použitie metód riešenia stochastických úloh je ideálne.
Podobným spôsobom možno modelovať aj obeh hotovosti na jednotlivých pobočkách
banky (v takomto prípade uvažujeme aj vklady) alebo zúčtovanie kartových transakcií
zo špeciálneho účtu banky.
Riadenie aktív banky
Aj ďalšie záležitosti banky súvisia s náhodnými vplyvmi, takže ich môžeme modelovať pomocou stochastického programovania. Podľa článku [20] ide konkrétne ide o štyri
hlavné úlohy: zabezpečenie likvidity (schopnosť splácať záväzky a vyplácať peniaze klientom), riadenie záväzkov (primerané úrokové sadzby), asset manažment (diverzifikované
32
4.1 TÉMY STOCHASTICKÝCH ÚLOH
umiestnenie voľných zdrojov) a napokon kapitálová primeranosť (riadenie vlastného kapitálu banky).
Hlavná je pritom otázka: Aká je optimálna úroveň prílevu bankového kapitálu a návratnosti cenných papierov pri realizácii požadovanej úrovne pôžičiek? Týmito úlohami
sa v stochastickom modeli banky zaoberajú autori článku [20].
Údržba stroja
Autori článku [14] predstavujú aj nasledujúci problém: Majme zariadenie pozostávajúce
z n komponentov, pričom stav každého z nich môžeme popísať premennou sj ∈ R.
Zariadenie funguje správne v jednom z K módov, ak pre nejaké k platí
As = b(k),
sjmin ≤ sj ≤ sjmax
∀j.
Minimalizovať náklady na fungovanie zariadenia cT s v prípustnom móde je statická
úloha, bez problémov riešiteľná lineárnym programovaním.
Pokiaľ však predpokladáme, že zariadenie má pracovať dlhodobo a pritom dochádza
k očakávanej alebo aj náhodnej zmene stavu jednotlivých súčiastok, musíme ho pravidelne kontrolovať a nastavovať v diskrétnych časových intervaloch. To už bude o úlohu
optimálneho riadenia, resp. viacstupňového stochastického programovania: minimalizovať náklady na pravidelné nastavovanie stroja.
Výroba viacerých výrobkov
Firma môže vyrábať viacero výrobkov, na ktoré potrebuje rôzne suroviny v správnom pomere. Niektoré suroviny sa môžu použiť na výrobu viacerých výrobkov. V prvej perióde
firma na základe predpokladaného dopytu objedná určité množstvá surovín. V druhej
perióde, keď už pozná skutočný dopyt (napr. podľa prijatých objednávok), chce použitím
objednaných surovín maximalizovať svoj zisk výrobou dopytovaného množstva výrobkov. Rovnaký problém možno riešiť vo viacerých periódach, pričom nevyužité suroviny
ostávajú na sklade pre ďalšiu periódu. Problém možno nájsť v [22].
Reklamná kampaň
V knihe od Brocketta [6] sme našli ďalšiu zaujímavú aplikáciu stochastického dynamického programovania. Uvádza ju síce v tvare so spojitým časom, rovnako dobre však
možno sformulovať a používať diskrétny model. Predpokladajme, že obchod má na
33
4.1 TÉMY STOCHASTICKÝCH ÚLOH
sklade n výrobkov, ktoré sa stanú bezcennými, ak sa nepredajú počas nasledujúcich
k dní. Normálna predajná cena výrobkov je r. Obchodník môže predaj podporiť reklamou, pričom pozná pravdepodobnostné rozdelenie dopytu yt v závislosti od prostriedkov
investovaných do reklamy at v čase t:
P yk = k = pk (at ),
kde pk (at ) je daná funkcia, napr. Poissonove rozdelenie. Výsledok reklamy sa prejaví
ako zmena parametrov rozdelenia (napr. strednej hodnoty), nie je teda zaručený. Cieľom
obchodníka je samozrejme minimalizovať náklady - prostriedky investované do reklamy
a hodnotu výrobkov, ktoré sa nepredali.
Distribučná sieť
K stochastickým úlohám patria aj širšie modely distribučnej siete (podľa [21], [22],
[26]), ktorú predstavuje sieť dodávateľov surovín, tovární, skladov, distribučných kanálov
a predajní. Ich cieľom je zorganizovať všetky toky surovín a výrobkov tak, aby sa finálne
produkty dostávali k spotrebiteľom čo možno najefektívnejšie.
Konkrétnym príkladom z článku [26] je stochastický model na distribúciu mäsa a mäsových výrobkov v Nórsku. Hlavným problémom je dobre odhadnúť náhodný dopyt po
mäsových výrobkoch a prispôsobiť mu ponuku (napr. motivovať chovateľov odpredávať
zvieratá v čase najväčšieho dopytu, resp. vyrábať tie druhy výrobkov, po ktorých je
práve dopyt). Model zahŕňa fixnú ponuku, plánovanie spracovania zvierat a produkcie
výrobkov v jednotlivých prevádzkach, distribúciu a predaj. Cieľom je maximalizovať celkovú pridanú hodnotu. Podľa autorov už v prvom roku praktického používania modelu
dosiahli výrazné zlepšenie fungovania distribučnej siete.
Optimalizácia portfólia
Prostredníctvom stochastického programovania sa dá modelovať široké spektrum reálnych problémov z oblasti financií. Podľa článku [28] môžeme vymenovať najčastejšie
problémy vo financiách: umiestnenie aktív dôchodkových fondov a poisťovacích spoločnosti (riešia napr. [13], [18]), výber akcií a dlhopisov portfólio manažérmi, menové
zaisťovanie, hedžové fondy, manažment rizika medzinárodných korporácií.
Najdôležitejšou riešenou úlohou je zrejme správa a optimalizácia portfólia. Prvé modely uvažovali jednorázovú úlohu - dnes zostavíme optimálne portfólio a počkáme istý
čas, potom ho predáme. V súčasnosti sa preferujú modely, ktoré uvažujú rebalancovanie
34
4.2 METÓDY RIEŠENIA ÚLOH
portfólia v diskrétnych časových intervaloch na základe vývoja hodnoty aktív na trhu.
Základnú úlohu rebalancovania optimálneho portfólia popisuje [22].
V mnohých článkoch (napr. [5], [16]) možno nájsť rozšírenia modelu o transakčné
náklady alebo rôzne ohraničenia. Typické ohraničenia reálnych úloh správy portfólia
možno nájsť aj v [10]: minimálna cieľová hodnota výnosu, rozpočtové ohraničenie a
náklady na rebalancovanie portfólia, ohraničenie podielu alebo množstva jednotlivých
cenných papierov, podmienka diverzifikácie rizika.
Ďalšie témy
Tematická skála stochastických úloh týmto zďaleka nie je vyčerpaná. Mnohé ďalšie aplikácie sa ponúkajú aj v iných oblastiach. Napríklad v biológii - dokonca aj zvieratá
prirodzene objavili iteratívne riešenie problémov, ktoré zahŕňa reakciu na situáciu vo
svojom okolí (viď prednáška [25]). Alebo v teórii hier - pri hrách závisiacich od náhody,
napr. hry s kockami v [24].
4.2 Metódy riešenia úloh
Pokiaľ chceme dobre modelovať realitu, musíme zahrnúť aj možné riziká či inú formu
náhody, ktorá vstupuje do modelu. Vhodný matematický aparát na jej začlenenie ponúkajú stochastické programovanie a stochastické optimálne riadenie. Obe majú svoje
výhody i nevýhody, konkrétny problém môžeme zväčša sformulovať viacerými spôsobmi.
Niekedy je jeden z prístupov výhodnejší - či už presnejší, rýchlejší alebo praktickejší. V
tejto podkapitole podávame stručný prehľad metód, ktoré sa využili pri riešení rôznych
úloh opísaných v predchádzajúcej časti.
Stochastické programovanie
Pri stochastickom programovaní môžeme v najjednoduchšom prípade zostaviť dvojstupňovú úlohu. V druhom stupni nájdeme optimálne riešenie pre pevnú hodnotu náhodnej
a riadiacej premennej a potom v prvom stupni uvažujeme o strednej hodnote týchto
pevných riešení. Pre zložitejšie modely, najmä pokiaľ uvažujeme rozhodovanie počas viacerých periód, je potrebné riešiť viacstupňovú úlohu. Konkrétne pri n-rozhodovaniach
musíme vyriešiť (n + 1) stupňovú úlohu (podľa [11], [14]).
Výhodou stochastického programovania je, že nemusíme zadávať vývoj stavu v tvare
diferenčnej rovnice a tiež fakt, že riešenie možno v prípade spojitých stavových pre35
4.2 METÓDY RIEŠENIA ÚLOH
menných hľadať aj analyticky (netreba uvažovať diskretizáciu). Navyše vygenerovaním
náhodných scenárov možno viacstupňovú úlohu stochastického programovania previesť
na úlohu lineárneho programovania (napr. v [18]) - obvykle s veľkým rozmerom a riedkou maticou, avšak stále ide o výhodný spôsob riešenia takýchto úloh. Tento prístup
využívame aj v tejto práci - v časti 3.3.
Stochastické optimálne riadenie
Druhý prístup je stochastické optimálne riadenie, pričom v tejto práci sa zaoberáme
úlohami s diskrétnym časom. Povaha stavovej premennej môže byť buď prirodzene diskrétna (napr. počet výrobkov na sklade) alebo aj spojitá (zastúpenie aktív v portfóliu),
analogicky riadenie. Rovnako aj náhodná premenná môže mať diskrétne alebo spojité
rozdelenie, väčšinou kvôli zjednodušeniu uvažujeme diskrétne rozdelenie (viď tiež [15]).
Výhodou optimálneho riadenia je efektívne riešenie úlohy aj na dlhšom časovom
intervale, kedy postupne riešime úlohu pre jednotlivé časy pomocou rovnice dynamického programovania. Naopak nevýhodné je riešiť úlohy s veľkým rozmerom stavovej
a riadiacej premennej a úlohy so spojitým stavom. Tie treba diskretizovať, čím vzniká
diskretizačná chyba, resp. presnejšou diskretizáciou rýchlo rastú pamäťové nároky. Viacerí autori ([10], [17]) túto nevýhodu nazývajú aj preklatím dimenzionality (angl. curse
of dimensionality).
Zamerajme sa teraz na konkrétne metódy použité pri riešení reálnych problémov.
Kvetinárka
Dupačová a Sladký v [14] porovnávajú dynamické a stochastické programovanie na jednoduchom dvojperiódovom (víkendovom) modeli. Ukazujú riešenie dynamickým aj stochastickým programovaním, v tomto prípade sú oba prístupy rovnako efektívne.
Situácia sa však zmení, pokiaľ budeme chcieť uvažovať predaj počas obdobia letných
prázdnin, kedy by sme v stochastickom programovaní museli riešiť až 63-stupňovú úlohu.
Prípadne môžeme úlohu zjednodušiť iným spôsobom, napríklad vyriešiť ju pre týždňové
plánovacie obdobie s premenlivým začiatočným počtom kvetov a toto riešenie opakovať
počas 63 dní.
Vzhľadom na povahu úlohy (jednorozmerná diskrétna stavová premenná) bude riešenie pomocou dynamického programovania rovnako jednoduché aj na dlhšom časovom
horizonte, prakticky nezávisle od počtu dní plánovacieho obdobia. Ako však autori upo36
4.2 METÓDY RIEŠENIA ÚLOH
zorňujú, pri použití dynamického programovania, teda výpočtu od konca môže nastať
problém, ak dimenzia stavovej a riadiacej premennej vzrastie - napríklad ak kvetinárka
začne predávať všetky druhy kvetov, s rozličnými ohraničeniami, obmedzeným skladom
alebo substitučným efektom náhodného dopytu. Takáto úloha sa však bude komplikovane riešiť aj stochastickým programovaním.
Dopĺňanie bankomatov
Castro vo svojom článku [11] o dopĺňaní bankomatov používa stochastické programovanie, pričom uvažuje model na krátke časové obdobie, resp. len malý počet doplnení.
Ako uvádza, ak by sme chceli uvažovať o h doplneniach bankomatu, problém sa rozšíri
na (h + 1) stupňov.
Vlastnosti úlohy (najmä diskrétny stav) však umožnujú úlohu efektívne riešiť aj
použitím optimálneho riadenia. Tento spôsob použil Šimko vo svojej diplomovke [23],
výhodný je hlavne pri dlhšom plánovacom období, neobmedzenom počte dopĺňaní, meniacich sa parametroch dopytu (napr. väčší cez víkend) či iných komplikáciách.
Optimalizácia portfólia
Pri optimalizácii portfólia väčšinou hľadáme konkrétne váhy - zastúpenia jednotlivých
cenných papierov, čo vo všeobecnosti nie sú celé čísla. Z tohto dôvodu by mohlo byť
výhodnejšie použiť stochastické programovanie, ako napr. autori článkov [13], [28].
Komplikovanejšia situácia v prípade optimálneho riadenia (spojité riadiace a stavové
premenné) často vedie k potrebe úlohu zjednodušiť, okresať jej dimenziu, resp. hľadať
len približné riešenie. Ako uvádza Calafiore v [10], praktická numerická realizácia dynamického programovania je obvykle náročná, preto autori uvažujú len dve periódy a malý
počet aktív.
Zamerajme sa na približné riešenia úlohy optimálneho riadenia v jednotlivých článkoch. Autor [10] pri použití stochastického optimálneho riadenia zvolil odozvu v tvare
lineárnej funkcie. Tým pádom sa vyhol komplikovanej diskretizácii a rastúcej dimenzii,
mohol do riešenia zahrnúť rôzne ohraničenia a riešiť úlohu na väčšom počte časových
intervalov.
Heuristiku použili Brown a Smith v článku [9]. Porovnali dve metódy v dynamickom programovaní a použili duálny odhad presnosti. Do modelu zahrnuli transakčné
náklady, čo je však výmenný obchod - za časté rebalancovanie portfólia platíme vysoké
poplatky, takže v niektorých situáciách môže byť výhodnejšie ponechať portfólio bezo
37
4.2 METÓDY RIEŠENIA ÚLOH
zmeny (neoptimálne). Heuristika pravdepodobne neskladala portfólio úplne optimálne,
možno práve vďaka transakčným nákladom však dávala celkom dobré výsledky.
V [5] autori na viacperiódovú optimalizáciu portfólia tiež použili dynamické programovanie, v neohraničenom prípade našli pomocou DP dokonca presné riešenie. V druhej
časti článku uvažovali aj transakčné náklady a opísali dve sub-optimálne metódy spracovania ohraničení. Algoritmus približného riešenia dynamického programovania použili
aj autori [16], do ktorého tiež zahrnuli niektoré ohraničenia a ukázali vysokú presnosť
svojho algoritmu.
Ohraničenia na stav a riadenie
V prípade optimalizácií vo finančnej oblasti sa často môžeme stretnúť s rôznymi ohraničeniami na stav alebo riadenie. Konkrétne napr. pri voľbe dôchodkového fondu má
zmysel minimalizovať riziko za podmienky minimálnej (strednej hodnoty) nasporenej
koncovej sumy, podrobnejšie v prácach [8], [18] a tiež v teoretickej časti tejto práce.
Kým v stochastickom programovaní nepredstavuje takéto ohraničenie vážnu prekážku, v optimálnom riadení je to zložitejšie. Potrebujeme istým spôsobom obmedziť
množinu prípustných riadení - vynechať tie, ktoré by (aspoň pre nejakú realizáciu náhodnej premennej) viedli do neprípustného stavu, teda stavu, z ktorého nie je možné
pokračovať tak, aby bolo zaručené splnenie podmienky na minimálnu strednú hodnotu
koncového stavu.
Iný prístup k tomuto problému predstavuje článok [12] od autorov Doyen a Lara. Ten
sa nezameriava na konkrétnu aplikáciu, ale rieši prípustnosť stavov a riadení všeobecne
v stochastických úlohách trochu iným spôsobom - za prípustné považuje také riadenia,
ktoré vedú do prípustného stavu s určitou pravdepodobnosťou β (na hladine spoľahlivosti β), napr. 90% alebo 99%. To zväčšuje množinu prípustných riadení. V zmysle našej
notácie požaduje, aby
h
i
Pzi xi+1 = fi (xi , vi (xi ), zi ) ∈ Xi+1 ≥ β,
resp. induktívne definuje množiny prípustných hodnôt riadení pre i < k takto:
n
o
Wi (x) = ui ∈ Ui Pzi fi (x, ui , zi ) ∈ Xi+1 ≥ β .
Tento prístup je zaujímavý, keďže umožňuje o.i. riešiť úlohu predavača reďkoviek aj
v prípade, keď dopyt bude mať Poissonove rozdelenie (alebo iné nekonečne spočítateľné
rozdelenie). V tejto oblasti plánujeme pokračovať v ďalšom výskume.
38
4.2 METÓDY RIEŠENIA ÚLOH
Ďalšie aplikácie
Ďalšie aplikácie stochastického programovania možno nájsť v úlohách o riadení aktív
banky, výrobe viacerých výrobkov a distribučnej sieti. V týchto prípadoch ide o úlohy
s veľkým počtom stavových premenných, resp. komplikovanými vzťahmi medzi nimi,
preto si autori vybrali stochastické programovanie.
Druhým spôsobom, teda v tvare úlohy optimálneho riadenia sú sformulované modely o údržbe stroja a reklamnej kampani. V týchto prípadoch sa uvažuje dlhší časový
interval, teda treba voliť viac riadení a tak je prístup optimálneho riadenia výhodnejší.
Poznamenajme, že pri údržbe stroja autori v porovnacom článku [14] použili obe metódy
riešenia.
39
Kapitola 5
Projekt dizertačnej práce
V poslednej kapitole tejto práce sa zaoberáme cieľmi ďalšieho výskumu, teda formulujeme naše plány a úlohy v rámci pripravovanej dizertačnej práce. Pritom ide o otázky,
ktoré svojou náročnosťou alebo rozsahom prekračujú rámec tejto práce, avšak radi by
sme ich podrobnejšie preštudovali a následne zaradili do dizertačnej práce.
5.1 Teoretické otázky
V teoretickej časti pripravovanej práce chceme nadviazať na výsledky, ktoré sa nám
podarilo odvodiť v tejto práci. Plánujeme sa naďalej zaoberať stochastickými úlohami
optimálneho riadenia s diskrétnym časom.
Úloha so špeciálnymi ohraničeniami
Preskúmame úlohy s ďalšími ohraničeniami, ktoré vyplývajú z potreby konkrétnych reálnych aplikácií. Využijeme pri tom zovšeobecnenie pre prípustné hodnoty stratégie závislé
od aktuálneho stavu v tvare vi (x) ∈ Wi (x), pre ktoré sme odvodili a dokázali rovnicu
dynamického programovania. Našou úlohou bude teda formulovať špeciálne ohraničenia
v tvare množiny prípustných hodnôt riadenia Wi (x).
40
5.2 NUMERICKÉ EXPERIMENTY
β-prípustné riadenia
V teórii stochastického dynamického programovania sme prípustnosť riadenia (stratégie)
definovali tak, aby nemohlo dôjsť k neprípustnosti, teda aby sa systém nedostal do
stavu, v ktorom bude množina prípustných hodnôt riadenia prázdna. Tento spôsob úplne
vyhovuje pre diskrétne náhodné premenné s konečným rozdelením, nie však pre náhodné
premenné s nekonečne spočítateľným rozdelením.
Predstavme si napríklad úlohu o predavačovi reďkoviek, v ktorej by bol náhodný
dopyt popísaný Poissonovým rozdelením. Ak by sme požadovali mať na konci aspoň
µ zväzkov, pri veľmi veľkom dopyte (hoci s malou pravdepodobnosťou) by to nebolo
možné splniť, čo by viedlo k neprípustnosti celej úlohy. Využitím definície prípustnosti
na hladine spoľahlivosti β podľa článku [12] chceme teoreticky odvodiť riešenie aj pre
takéto úlohy.
Lineárne stratégie
V niektorých stochastických úlohách OR majú stratégie tvar lineárnej funkcie, čo súvisí
so špeciálnym tvarom úloh. Napríklad aj v úlohe o predavačovi reďkoviek majú stratégie
lineárny tvar, pričom sa menia iba koeficienty. Pokúsime sa odvodiť vlastnosti tohto
tvaru riešenia úlohy. Pri našich úvahách nadviažeme aj na článok [10], kde Calafiore
používa lineárne stratégie pri optimalizácii portfólia.
5.2 Numerické experimenty
Teoretické výsledky chceme v dizertačnej práci podporiť aj ďalšími numerickými príkladmi a experimentmi. Práve takto môžeme ukázať, že teoretické úvahy majú opodstatnenie a dajú sa použiť pri riešení praktických úloh. V rámci tejto práce sa zameriavame
na úlohy s diskrétnym časom, ktorých riešenie porovnávame s výsledkami úloh zadaných
v tvare stochastického programovania, resp. v tvare lineárneho programovania. Takéto
porovnanie chceme robiť aj v ďalších situáciách.
Lineárne stratégie v stochastickej úlohe
V stochastickej úlohe predavača reďkoviek hľadáme riešenie v tvare programového riadenia, ktoré má čo najlepšie výsledky na množine náhodných scenárov. V úlohách stochastického OR však hľadáme stratégie, teda hodnoty riadenia, ktoré závisia od mo-
41
5.2 NUMERICKÉ EXPERIMENTY
mentálneho stavu systému. To je zväčša výhodnejšie ako vopred určené programové
riadenie.
Preto chceme úlohu lineárneho programovania na náhodných scenároch preformulovať na hľadanie riešenia v tvare stratégie. Hľadali by sme teda cieľový stav na sklade
v jednotlivých časových periódach ci , stratégia bude mať tvar vi (x) = max(ci − x; 0).
Tým pádom pôjde o podobný prístup ako OR, preto aj výsledky budú lepšie - nie je
však jasné, či lepšie ako stochastické optimálne riadenie.
Reálne problémy
Našim zámerom je otestovať teóriu aj na ďalších úlohách, najmä komplikovanejších,
ktoré budú lepšie popisovať situácie z reálneho sveta. Napríklad sa môžeme zamerať na
niektoré modely z kapitoly 4.1.
Zaujíma nás najmä úloha o dopĺňaní bankomatov. V nej musíme vyriešiť, ako sformulovať stochastickú úlohu v tvare úlohy lineárneho programovania, keďže účelová funkcia
závisí od počtu dopĺňaní bankomatu, teda od znamienka riadenia (čo nie je v LP jednoducho riešiteľné), resp. previesť úlohu stochastického programovania pre dané scenáre
na úlohu nelineárneho programovania.
Úloha so spojitým stavom
Ako uvádzajú autori článku [14], stochastické optimálne riadenie prestáva byť výhodné
v prípade, že stavová premenná nie je diskrétna. To by sme mali overiť na konkrétnych
príkladoch. Okrem iného môžeme preveriť závislosť presnosti a dimenzie od zvolenej
diskretizácie. Druhou možnosťou je hľadanie stratégie a hodnotovej funkcie v špeciálnom
tvare, napr. lineárnej funkcie.
Medzi úlohy so spojitým stavom patria napríklad finančné aplikácie - najmä správa
portfólia, našim cieľom bude teda riešiť nejakú úlohu tohto typu, napr. aj s ohraničením
na strednú hodnotu koncového stavu. Ako účelovú funkciu si môžeme zvoliť nejakú mieru
rizika portfólia, teda vo všeobecnosti nelineárnu úlohu (teda aj v prípade stochastického
programovania budeme musieť previesť úlohu na nelineárne programovanie).
Viacrozmerná úloha
V tejto práci sme zatiaľ skúmali iba úlohy, ktoré mali stav a riadenie vyjadrené v jednom rozmere, čo je najjednoduchší a najvýhodnejší prípad pre stochastické dynamické
42
5.2 NUMERICKÉ EXPERIMENTY
programovanie. Pokúsime sa riešiť aj úlohy, kde je stav alebo riadenie viacrozmerné,
prípadne hľadať algoritmus na efektívne zvládnutie takéhoto typu úloh.
Nadviazanie na teóriu
Pokiaľ sa nám v teoretickej časti podarí prísť s novými výsledkami, hlavne v prípade
náhodnej premennej s nekonečným rozdelením, mali by sme v rámci experimentov vyskúšať riešiť aj takéto úlohy a samozrejme, porovnať výsledky s inými metódami (zrejme
stochastickým programovaním).
43
Literatúra
[1] Bellman, R.: Dynamic programming, Sixth Printing, Princeton University Press
(1972)
[2] Bertsekas, D. P.: Dynamic Programming and Optimal Control, Volume I, Third
Edition, Athena Scientific (2005)
[3] Bertsekas, D. P.: Dynamic Programming and Optimal Control, Volume II, Third
Edition, Athena Scientific (2007)
[4] Bertsekas, D. P., Shreve, S. E.: Stochastic Optimal Control: The DiscreteTime Case, Athena Scientific (1996)
[5] Boyd, S., Skaf, J.: Multi-Period Portfolio Optimization with Constraints and
Transaction Costs, Working manuscript, Stanford (2008), dostupné online
http://www.stanford.edu/~boyd/papers/pdf/dyn_port_opt.pdf
[6] Brockett, R.: Stochastic Control, elektronický text (2009), dostupné online
http://www.eeci-institute.eu/pdf/M015/RogersStochastic.pdf
[7] Brunovský, P.: Stochastické metódy operačnej analýzy, elektronický učebný text,
FMFI, Bratislava (2006), dostupné online
http://www.iam.fmph.uniba.sk/skripta/brunovsky-smoa/
[8] Brunovský, P., Halická, M., Kilianová, S.: Stochastic Dynamic Programming for Problems with Expected Value Constraint, Working paper, FMFI, Bratislava (2011)
44
LITERATÚRA
[9] Brown, D. B., Smith, J. E.: Dynamic Portfolio Optimization with Transaction
Costs: Heuristics and Dual Bounds, Duke University (2010), dostupné online
http://www.optimization-online.org/DB_FILE/2010/08/2703.pdf
[10] Calafiore, G. C.: Multi-period portfolio optimization with linear control
policies, Automatica 44 (2008), 2463–2473, dostupné online
http://staff.polito.it/giuseppe.calafiore/Documenti/Papers/
Automatica_Multi-period%20portfolio%20optimization%20with%20linear%
20control%20policies.pdf
[11] Castro, J.: A stochastic programming approach to cash management in banking,
European Journal of Operational Research, Vol. 192, Num. 3 (2009), 963–974.
[12] Doyen, L., Lara, M. D.: Stochastic viability and dynamic programming, Systems
& Control Letters (2010), 629–634, dostupné online
http://arxiv.org/PS_cache/arxiv/pdf/1002/1002.1140v1.pdf
[13] Dupačová, J., Polívka, J.: Asset-liability management for Czech pension funds
using stochastic programming, Annual Operational Research, Vol. 165 (2009), 5–28,
dostupné online
http://www.karlin.mff.cuni.cz/~dupacova/papers/ALM-finP.pdf
[14] Dupačová, J., Sladký, K.: Comparison of Multistage Stochastic Programs with
Recourse and Stochastic Dynamic Programs with Discrete Time, ZAMM 82 (2002),
753–765, dostupné online
http://www.karlin.mff.cuni.cz/~dupacova/papers/zammfin3.pdf
[15] Halická, M., Brunovský, P., Jurča, P.: Optimálne riadenie - Viacetapové
rozhodovacie procesy v ekonómii a financiách, Epos, Bratislava (2009)
[16] Haugh, M., Kogan, L., Wu, Z.: Portfolio Optimization with Position Constraints: an Approximate Dynamic Programming Approach, Working paper, Columbia University (2006), dostupné online
http://www.columbia.edu/~mh2078/ADP_Dual_Oct06.pdf
45
LITERATÚRA
[17] Chang, H. S., Fu, M. C., Hu J., Marcus, S. I.: A survey of some simulationbased algorithms for Markov decision processes, Communications in information
and system, Vol. 7, Num. 1 (2007), 59–92
[18] Kilianová, S.: Stochastic dynamic optimization models for pension planning, Dissertation Thesis, FMFI UK Bratislava (2008)
[19] Mukuddem-Petersen, J., Petersen, M. A.: Applied Optimal Control and Estimation, kapitola 1, Introduction to Modern Control Theory, Prentice-Hall (1992),
http://www.theorem.net/theorem/lewis1.html
[20] Mukuddem-Petersen, J., Petersen, M. A.: Bank management via stochastic
optimal control, Automatica 42 (2006), 1395–1406
[21] Santoso, T., Ahmed, S., Goetschalckx, M., Shapiro, A.: A stochastic
programming approach for supply chain network design under uncertainty, European Journal of Operational Research 167 (2005), 96–115, dostupné online
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.
4132&rep=rep1&type=pdf
[22] Shapiro, A., Dentcheva, D., Ruszczynsski, A.: Lectures on stochastic programming: modeling an theory, MPS-SIAM (2009), dostupné online
http://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf
[23] Šimko, M.: Stochastické úlohy optimálneho riadenia, Diplomová práca FMFI, Bratislava (2010)
[24] Tijms, H.: Dice games and stochastic dynamic programming, Morfismos, Vol. 11,
Num. 1 (2007), 1–14, dostupné online
http://chucha.math.cinvestav.mx/morfismos/v11n1/tij.pdf
[25] Todorov, E.: Stochastic Optimal Control in Biology and Engineering, Prednáška,
University of Washington (2009), dostupné online
http://www.youtube.com/watch?v=_R7XFfKBl6o
46
LITERATÚRA
[26] Tomasgard, A., Høeg, E.: A Supply Chain Optimization Model for the Norwegian Meat Cooperative, kapitola 14, Applications of Stochastic Programming, SIAM
(2005).
[27] Watson, J.-P., Woodruff, D., Hart, W.: PySP: Modeling and Solving
Stochastic Programs in Python, Technical Report, Sandia National Laboratories
(2010), dostupné online
http://www.optimization-online.org/DB_FILE/2010/09/2725.pdf
[28] Yu, L. Y., Ji X. D., Wang S. Y.: Stochastic Programming Models in Financial
Optimization: A Survey, AMO - Advanced Modeling and Optimization, Vol. 5,
Num. 1 (2003)
47
Download

Stochastické úlohy optimálneho riadenia