MASARYKOVA UNIVERZITA V BRNĚ
Přírodovědecká fakulta
DYNAMICKÉ PROGRAMOVÁNÍ V OPTIMALIZAČNÍCH ÚLOHÁCH
BRNO,květen 2005 Hana Pmdilová
Děkuji touto cestou Prof. RNDr. Ondřeji Došlému, DrSc. za cenné rady a pečlivé vedení diplomové práce, rovněž za trpělivost a pochopení.
Prohlašuji, že jsem pracovala samostatně, a že jsem použila pouze uvedené literatury.
$4mjkj ^IfylMtfl* l#~rO 25S. ZOOT
Obsah
Úvod 1
1 Konečněkrokový deterministický rozhodovací proces 2
1.1 Obecné schéma rozhodovacího procesu.................... 4
1.2 Dekompozice .................................. 5
1.3 Příklady..................................... 8
2 Nekonečněkrokový deterministický rozhodovací proces 16
2.1 Metody řešení funkcionální rovnice dynamického programování....... 19
2.1.1 Metoda postupných aproximací.................... 19
2.1.2 Metoda aproximace na množině optimálních rozhodnutí....... 19
2.2 Základní funkcionální rovnice dynamického programovaní.......... 22
2.3 Vlastnosti řešení funkcionální rovnice dynamického programovaní..... 24
2.4 Příklady..................................... 32
Závěr 34
Literatura
35
Úvod
Dynamické programování se používá k řešení komplexních optimalizačních problémů. Tato metoda byla rozpracována Richardem Bellmanem v 50. letech minulého století a základy této teorie jsou shrnuty v jeho monografii [1].
Cílem této diplomové práce je vysvětlit základní myšlenku této optimalizační metody a ukázat její použití na příkladech v případě konečně a nekonečněkrokového deterministického rozhodovacího procesu.
Práce je rozdělena do dvou kapitol. V první kapitole výkladu je specifikován obecný
konečněkrokový rozhodovací proces a popis řešení. Ve druhé kapitole je rozebrán ne-
konečněkrokový rozhodovací proces, metody jeho řešení s použitím funkcionálních rovnic
a na závěr obou kapitol je popsaná teorie aplikována na různé typy úloh.
Hlavním zdrojem při zpracování tématu byly práce R. Bellmana [1] a G.L. Nemhausera
[3].
Předpokládá se, že čtenář je seznámen se základy matematické analýzy a matematického programování v rosahu, v jakém jsou tyto probírány v kurzech na Přírodovědecké fakultě Masarykovy univerzity.
1
Kapitola 1
Konečněkrokový deterministický rozhodovací proces
Při řešení nějakého komplexního rozhodovacího problému se často používá dekompozice, kdy je původní rozhodovací problém rozložen na řadu z jistého pohledu jednodušších problémů a výsledek získán kombinací a složením řešení těchto subproblémů. Tuto metodu nazýváme rozklad vícerozměrného problému.
Rozhodovací situace nastává, pokud existuje více než jedno přípustné řešení. Cílem rozhodování nebo optimalizačního problému bude určení jednoho řešení (rozhodnutí), které dává optimální výsledek.
Začneme s výkladem vlastností typické situace obecného vícekrokového rozhodovacího procesu. Je dána rozhodovací situace, kterou můžeme schématicky znázornit následujícím obrázkem
X
Z
ve kterém je:
• Vstupní veličina Y, která se nazývá počáteční stav systému, představuje v něm popis počátečního stupně a obsahuje všechny relevantní vstupní informace.
• Výstupní stavová veličina Z, popisujcí systém v konečné úrovni, obsahuje všechny informace o výstupu.
• Rozhodovací proměnná X, která charakterizuje operace probíhající v průběhu jednotlivých kroků.
2
• Účelová funkce r představuje skalární proměnnou. Je to jednorozměrná funkce vstupu, rozhodování a výstupu, tzn.
r = r(Y,X, Z).
• Transformační funkce y, která vyjadřuje každou komponentu výstupní proměnné jako funkci vstupu a rozhodování,
Z = y(Y,X).
Pomocí transformační funkce y můžeme veličinu Z z účelové funkce vyeliminovat a dostáváme
r = r(Y,X, Z) = r{Y,X,y(Y,X)),
to znamená, že jednotlivé nezávislé proměnné, které ovlivňují výsledek, jsou Y a X. Jejich hodnoty jednoznačně určují hodnotu Z prostřednictvím transformační funkce y. Účelovou funkci můžeme tedy uvažovat pouze jako funkci1 vstupní a rozhodovací proměnné
r = r(Y,X).
Jednorozměrný optimalizační problém spočívá v nalezení maxima resp. minima účelové funkce jako funkce vstupní veličiny. Označme f(Y) jako optimální výnos aT = X{Y) jako optimální rozhodnutí. Potom obdržíme
f(Y) = r(Y,X*) = r(Y,X(Y)) = max r(Y,X) > r(Y,X).
V některých rozhodovacích situacích má být účelová funkce r, vyjadřující optimální výnos, určena jako funkce výstupu Z. Můžeme předpokládat Y jako jednoznačnou funkci Z a X, což dostaneme z inverze transformace
Z = y(Y,X).
Obdržíme tedy
Y = y(Z,X).
Vyjádříme výnos pouze jako funkci rozhodnutí a výstupu:
r = r{y{Z,X),X, Z) = r(Z,X).
Optimalizačním problémem je nalezení X jako funkci Z tak, aby r bylo maximální. Buď f (Z) optimální výnos a X* = X(Z) optimální rozhodnutí,
f (Z) = r(Z, X*) = max r(Z, X) = max r(Y, Z, X)
X YjX
za podmínky Z = y(Y,X) a je-li možné invertovat transformaci y, můžeme tedy provést maximalizaci přes ľal
Poznámka 1. Je lhostejné, zda uvažujeme optimalizační úlohu na maximum nebo na minimum, neboť maximalizovat funkci / je totéž, jako minimalizovat funkci -/.
označme ji opět r
3
1.1   Obecné schéma rozhodovacího procesu
Obecný rozhodovací proces, popsaný v předchozím odstavci se ve většině případů sestává z řady rekurzivně provázaných rozhodnutí tak, že výstup jednoho kroku je zároveň vstupem dalšího kroku, což můžeme znázornit následujícím schématem
Xl
Xí
	•		
	n		
			
Yk
Y1
Y0
1
ľ ý v
rn rk n
Z důvodu, který bude patrný z konkrétních příkladů, prvnímu rozhodovacímu kroku přiřadíme index n a poslednímu index 1, tj. rozhodovací kroky jsou očíslovány v sestupném pořadí.
Pro k-tý krok n-rozměrného systému je výstupní veličina Yk_ľ zároveň vstupem (jfc -1)-kroku, tedy transformační rovnice Y = y (Y, X) je tvaru
Yk-i = yk(Yk, Xk),      pro každé k = 1,2,n, (1.1)
a výnos tohoto kroku je
rk = rk(Yk,Xk).
Z transformace (1.1) plyne, že Yk závisí na rozhodnutích, které předcházejí jfe-tému kroku, tedy naXfc+i,...,Xn, anaľn:
Yk  = yk+i{Yk+uXk+1)^yk+1(yk+2(Yk+2,Xk+2),Xk+^
= ífc+iWfe+2, Xk+2, Xk+1) = yk+1(yk+s(Yk+3, Xk+3), Xk+í,Xk+2) =  •■• = yk+1(Yn,Xn,Xn_1...,Xk).
Poznámka 2. Poslední zápis není zcela korektní, protože yk+1 je funkce dvou proměnných. Nebudeme však funkční závislost Yk na Yn,Xn,Xn_i ...,Xk označovat novým symbolem. Podobné nepřesnosti se dopustíme i ve zbývající části tohoto odstavce.
Dosazením do účelové funkce
rk  =  rk(Yk,Xk) = rk(yk+1{Yn,Xn,Xn.u...,Xk+1),Xk) = = rk(Y„,Xn,Xn-1,...,Xk),
jinými slovy, Xk ovlivňuje jenom výnos prvního až fc-tého kroku. Celkový výnos z prvního až n-tého kroku je funkce
RniYn, yn_i,..., Yu Xn, Xn_i,..., Xi) = ^[rn(y„,Xn),rn_1(yn_1,X„_1),...,ri(y1,X1)],
4
kde g je zatím nespecifikovaná funkce n proměnných vyjadřující, jak jednotlivé výnosy rk, pro každé k = 1,..., n, přispívají k celkovému výnosu Ä„.
Nyní z výrazu pro celkový výnos eliminujeme (Yn_l5...,Yi). Z rovnice (1.1), dále pomocí výrazu pro rk, tedy rk = rk(Yk, Xk) a z rovnice rk = rk(Yn, Xn, X„_i,..., Xk) dostaneme rovnici
Rn = g(rn, ...,n) = g [r„(y„, Xn), rv.^, Xn, X^),..., n(Yni Xn, Xn_u ..., Xj)].
Máme tedy optimalizační problém: maximalizovat celkový zisk iž„ při dílčích rozhodnutích Xu X2,..., Xn, jako funkci vkladu Yn.
Položme funkci fn(Yn) jako maximální výnos v n-tém kroku a Xk* = Xfc(y„) jako optimální rozhodnutí v fc-tém kroku
fn(Yn) = y[r„(ľB,^)>rB.1(ľB.1,x;_1),...,r1(y1,x;)]
=    max g[rn(y^,Xn),r„_i(yí,_i,Xn_i),... ,ri(Ví,Xi)],
Xl,...,Xn
za podmínky Yk^ = yk{Yk, Xk), pro každé k = 1,..., n. Tedy
/n(y„)= max ^[^(y^xj^^fy^x^x^!),...^^^,^,^^!,...,^!)].
Xi,.,X„
1.2 Dekompozice
Cílem bude rozložit problém
fn(Yn)=  max £ [rn(y„, Xn), r„_i(y„_i, X^j),..., n(YÍ, X"i)],
za podmínky Yk_x = yfc(yfc,Xfc) na n jednodušších subproblémů. Předpokládejme, že celková účelová funkce je aditivní funkcí účelových funkcí v jednotlivých krocích, tj.
Rn = rn{Yn,Xn) + rn^Yn.uX^) + • • • +r1(y1,X1),
potom
/„(y„)=  max {rn(yn,Xn)+rn_1(yn_i,Xn_1)-r--- + r1(y1,Xi)},
Xi,...,Xn
za podmínky yfc_! = yfc(yfc, A; = 1,..., n.
Výnos n-tého kroku nezávisí na Xn-lt ... ,X1? můžeme tedy předchozí rovnost přepsat ve tvaru
fn(Yn) = max{rn(Yn,Xn)+   max   [r„_i(y„_i, Xn_i) + • • • + n(Yu XJ]}. (1.2)
Xn Xl,...,Xn_l
Z definice fn{Yn) získáme
/„_i(y„_i) =   max   {rn_i(yn_i,X„_i) + • • • + n(yi,Xi)}.
5
Použijeme-li tento vztah v rovnici (1.2), dostaneme
a tedy
Položme nyní
fn(Yn) = max{rn(Yn,Xn) + /„^(y^)},
Xn
fn(Yn) = max{rn(Yn,Xn) + /n_i(y„(y„, *„))}.
Qn{Yn,Xn) = rn{Yn,Xn) + fn-i{yn(Yn,Xn)).
Potom je určení fn(Yn) při dané funkci /n_i(y„_i) jednoduchý jednorozměrný optimalizační problém se vstupní proměnnou Yn, rozhodovací proměnnou Xn a výnosem Q„. Tedy
/n(K) = maxQn(yn,Xn) = max{rn(yn, Xn) + /n_i(y„(yn,Xn))}.
Xn Xn \*s \
Původní n-rozměrný problém máme tedy rozložený na dva subproblémy:
1. (n - 1) - rozměrný optimalizační problém
/»-i(yn-i)=    max   K_1(yn_1,Xn_1) + --- + r1(y1,X1)},
Xn-1,--;X\
za podmínky Yk_x = yk{Yk, Xk),   k = 1,..., n - 1;
2. jednorozměrný optimalizační problém
/n(yn)  = maxQn(Yn,Xn)
=  max {rn(yn, X„) + /„_i(í„(y„, Xn))}.
Podobným postupem při určování /n_l5..., fx dostaneme následující rekurzivní schéma
fk(Yk) = max Qk{Yk, Xk), pro k = 1,..., n
Xk
\rfc(yfc)Xfc) + A-i(y„(y*,Xfc)),   pro fc = 2,..., n Poznámka 3. Optimalizace v koncovém kroku
Speciálním případem rozhodovacího procesu, který lze zkoumat v rámci výše popsaného obecného schématu je maximalizace jisté funkce v koncové proměnné. Tento případ se nazývá optimalizace v koncovém produktu. Uvažujme optimalizační problém
/„(y„)=  max g(Y0)
6
za podmínky   Yk^ = yk(Yk,Xk),   k = Předpokládejme, že pro výnosy ve
2.,3.,...,n-tém kroku platí
rn{Yn,Xn) = r^Y^X^) = ■•■ = r2(Y2,X2) = 0 a pro výnos v 1. kroku
r1(Y1,X1) = g[y1(YuX1)] = g(Y0).
Pak platí
rn(Yn,Xn) + --' + r1(Y1,X1)=g(Y0).
Odtud můžeme psát
fn(Yn)=  max [r„(y„,Xn) + ..-+ri(yi,X1)].
Xn,—,Xi
Nechť platí
n
zn = 0      a      zk =       n{YuXt\ pro k = 0,... ,n - 1.
Položme pevně
71
£o =     í"fc(Yjfc, -^fc)      a      ^fc-i = Zk + ^fc), pro   = 1,..., n\
k— 1
potom platí
fn(Yn) =   max {zo}
X\ ,...,Xn—i
za podmínky    Yjfc_i = ^(1*;, Xk)    a    2^_i = zk + rk(Yk, Xk),   kde A; = 1,..., n.
7
1.3 Příklady
Příklad 1.3.1. Řešte extrémální úlohu
^]r(xfc)       min, Xl + ...+xn>a, xu    xn > 0,
k=i
kde r je konvexní a rostoucí funkce aaGi Řešení:
Označme yn = x\ + ... + xn, yk_i = yk - xk, pro každé k = 2,..., n a y0 = y1 - x\ =0. Z poslední rovnice máme 3/1 = a?i. Použijeme rekurzívní schéma
A(yfc)=   min   {rfe) + /fc-i(?/fc-i)}
0<xfc<yfc
S využitím vztahu yx - xi dostaneme pro k = 1:
/i(yi)= min r(si)=rfoi).
xi=yi
Nyní počítejme pro fc = 2, použijeme vazebné podmínky yk_x = yk- xk, tedy yi^y2- x2 a odtud
Íi{y2) —   min   {^fe) + —   min   {t(x2) + r(y2 — x2)},
0<X2<]/2 0<X2<2/2
hledáme tedy takové x2, pro které bude výraz ve složených závorkách minimální. Derivaci podle x2 položíme rovnu nule
r'(x2) — r'{y2 — x2) = 0, z podmínky pro funkci r (monotonie) obdržíme
X2     2 j2m)    rV2/V2/ rV2/'
Stejným způsobem spočítáme výraz pro k = 3 :
/3(y3)=  min   {r(x3) + f2(y2)} =   min   (rfe) + 2r f ,
0<x3<y3 0<x3<y3   t \      2      / J
opět derivujeme (podle a*)
//    \        / / y3     %3 \ monotonie ?/3     ^3 , y3
r(*s)-r (—j—J=0      =>      *3 = =►   *3 = p
dosadíme do /3(?/3) a dostáváme
J3\y3) — Tyiz) +    v) = ^rív)-
ó ó ó
8
Z předchozích výsledků odvodíme výraz pro fc-tý člen:
A(yO = r(^) + (fe-l)r(|) = My),   prokaždéfc=l,...ln,   xk = |,
tento vzorec ověříme pro n-tý krok:
fn(yn)=   min   {r(zn) + /n_i(2,n_i)}=   min    (r(zn) + (n - 1) r f ^L^lA 1 =
0<x„<y„ 0<xn<yn    [ \  U — 1   J )
u     x        / (yn-Xn\       .      monotonie ?/„ ~ Ž/„
Z transformačního vzorce   yn-i = yn-xn   a extrému v bodě   xn = y— dostaneme
n
ž/„-i = yn - xn = yn - I = (^) yn.
Vypočítáme-li zpětně extrémy xk, pro k = n — 1,..., 1, dostaneme
1    / n - 1 \ yn yn
- I - I    Ol - - 'T*- - -
Xn-1 = -7 - ) yn = — ,        3?1 = —
n — 1 \  n   / n n
Nyní máme minimalizovat funkci /n(y„) = r (^) + (n - 1) r (^) = nr (^), za podmínky yn > a . Protože r je rostoucí funkce, pak výraz r (^) bude nabývat nejmenší hodnoty při yn — a.
Dosazením do výrazů pro x získáme optimální hodnoty
*    ^      * * Xn = n =       = *"' = ^ a tedy xk    ^, &    1,..., ti. Výsledek tedy je
fn{yn)    min{r(xi) + • • • 4- r(xn) \xi + ...#„}    nr i J.
\ TI /
I^ríklcid X*3«2« R^este extremalni úlohu
£>(**) - min,   f[xk>a, xk>0,
kde r je konvexní a rostoucí funkce, a a G M Řešeni:
Označme yn = ÍILi^ yk-i = ^, pro každé fc = 2,...,n a je zřejmé, že Vl = n. Použijeme rekurzívní schéma
A(y*)=   min   {r(*0 + A-i(lfc-i)}.
9
S využitím vztahu Vl = xx dostaneme pro k = 1:
fi(yi)= min r(xl) = r(yl).
Nyní počítejme pro k = 2, použijeme       = ^, tedy Vl = ^ a odtud
/2(ífc)=   min   {r(x2) + /1(yi)}=   min   {r(z2) + r(^) }
0<x2<y2 0<x2<V2 x2
derivujeme podle x2
x22 x2
z podmínky pro funkci r (monotonie) dostaneme
—z = 1 — = ^2 £2 = yjy2,
x2z x2
a tedy f2(y2) = r (^) + r (J=) = 2r (^) . Stejným způsobem spočítáme výraz pro ife = 3:
/3(2/3)=   min   {r{x3) + /2(y2)} =   min   (rfo) + 2r f ) ,
0<x3<y3 0<x3<y3   [ VV^S/J
opět derivujeme (podle x3)
r'(x3)-2r'( [Ž?) m    ^P = l x3 = (y3)i
\\ x3J 2 a;3§ a; f
dosadíme do /3(y3) a dostáváme
/3(lfe) = r((y3)*) + 2r J = 3^ ((ife)*) •
Z předchozích výsledků odvodíme výraz pro jfc-tý člen:
A(y*) = r(^) + My) = Mf)i   * = l,...,n,   zfc = |
a tento vzorec ověříme pro n-tý krok:
2/n
0<xn<yn  " " "       0<xn<yn    I \ V £n
f„{yn)=   min   {r(o;n) + /„_i(y„_i)} =   min    \ r(xn) + (n - 1) r 11
10
derivujeme:
1                                         1 1 //     \        f   I Un \ n_1       1       ( Vn\ n~1       mon.       f Vn\ "_1       i _v / \i
dosazením do výrazu pro fn(yn) získáme
/n(?/n) = r{{yn)») + (n - l)r I [ I      I =n(Vn)
Tento výraz chceme minimalizovat za podmínky yn > a. Nejmenší hodnoty bude nabývat při 2/n = a, a optimálni hodnoty jsou:
Výsledek je tedy
/„(y„) = min{r(zi) + • • • + r(zn)||xi •■ - íc„ = ?/„} = n (a)i. Příklad 1.3.3. Řešte extrémální úlohu
n
—>
k=l fc=l
—>• max,
Řešení:
Označme yn = ELi < <*, yk-i = Vk - xkl pro každé k = 2,..., n a y0 = j/i - xx = 0. Z poslední rovnice máme y1 = x1. Použijeme rekurzívní schéma
fk(yk)=  max {a;fc./fc_i(^_i)}.
S využitím vztahu ^ = Xl dostaneme pro k = 1:
/i(yi) = max x1 = yi.
Nyní počítejme pro k = 2, použijeme vazebné podmínky ^ = yfc - xk, tedy ^ = y2 - x2l odtud
72(1/2) =
max  {^2/"i (l/i)} —
max {  £2(2/2 — ^2)   }    =^    £2 = ir,
derivujeme podle X2
„, 2
a tedy 72(2/2) — —:-•
11
Počítáme výraz pro k = 3 :
/3(ífe)=  max   {Z3/2MH  max {x3hy3 - x3)2},
0<x3<y3 0<x3<y3 4
položením derivace podle x2 rovno nule máme £3 = y, dosadíme do f3(y3) :
/ /   \_    1/3 1 /       ?/3\2 _ 1 3
/312/3,1 —       ^2/3 ~ ~§ )  ~ 27 ^3 '
Z předchozích výsledků odvodíme pro k-tý člen:
fk(yk) = ^L_    =^    xk = —, kk k '
vzorec ověříme pro n-tý krok:
fn(yn) = Q<max   {xnfn-i(yn_i)} = 0<max |^n^—^n ~ Xn^ *}
Položíme-li parciální derivaci podle :rra rovnu nule, obdržíme: xn =     dosazením do výrazu pro fn(yn) '•
f (V) = ^_í_(y -1b)n-=K
Jn\yn) ( 1 \„_i  l í/n I •
n (n — l)n 1 \       n / nn
Má-li být fn(yn) maximální za podmínky yn < a, potom yn = a, a pro výrazy pro k — 1,..., n potom platí:
*     Vn oč n n
* _ Vn-1 _ * _ y n _       U — 1
7i      Vn-1 — Vn ~ %n — ÍJn — y n
n — 1 n n
* 1      ti — 1        yn oi
Xn-1 = 7 ' Vn ~        ~ —
n — 1     n n n
*^n—1        ^ ^
Obdrželi jsme výsledek
fn(yn) = max^ • • • x„| a* + • • • + xn = yn} = —.
12
Příklad 1.3.4. Řešte extrémální úlohu Ch. Huygense2
Xix2 ...xn (a + Xi)(xi +x2)... (av-i + xn)(xn + 6)
max,
za podmínky a < xl < x2 < ■ ■ • < xn < b.
Interpretace: do intervalu (a, b) se mají rozmístit čísla xY... xn tak, aby uvedená veličina byla maximální. Řešeni: Označme
_ , X\X2 ...xn
Fn(a,b) = ^ max
a<*i<-<*»<i (a + Xjfa + X2) . . . (Xn + b)
Nyní rozepíšeme Fn{a, b) jako
Fn(a,b)= max.-^-r- max.
a<*n<6 £n + 6    o<xi<-<i„ (a + Xl) . . . (X„_i + Xn) '
Počítejme
F!(a,x2)=  max Xl
Hledáme takové a*, pro které bude výraz maximální. Budeme derivovat podle Xi
d
dxi
Xi
(a + xl)(xl+x2)
(a + xi){xi + x2) - xi(a + xl + xx + s2) (a + rci)2(a;i+a;2)2
(a + a^fa+za)2' derivaci položíme rovnu nule a vyjádříme Xl
xi = y/Ex^.
Dosadíme zpět do funkce Fi(a,x2)
Fi(a,x2)- v _ v
_ yfaňj 1
Pro ^ - a nebo a* = x2 (krajní body intervalu maximalizace) dostáváme hodnotu š^y, která je menší než ^^2, tedy maxima je opravdu nabyto ve stacionárním bodě xi = yjax2.
Dále využijeme rekurzivního schématu
Fk(a,xk+1)=    max -^--max ^•••^-1
a<xk<xk+i Xk + Xk-\-i    a<xk<xk+i {d -f- a^i) . . . (xk—l ~\~ Xk)
max ——-Fk_i(a,xk)
^Christian Huygens (1629-1695), nizozemský matematik a fyzik.
13
Tohoto schématu vužijeme pro výpočet F2{a,x3)
F2(a,x3) = max
x2
Fi(a,x2) = max
x2
1
a<x2<x3 X2 + X3    ^   ' a<x2<x3 [x2 + X3     (y/Čb + ^2~)2 J '
Výraz ve složených závorkách opět budeme derivovat podle x2l derivaci položíme rovnu nule, abychom získali takové x2l pro které bude výraz maximální (podobně jako v předchozím kroku lze ukázat, že maxima je vskutku nabyto ve stacionárním bodě a nikoliv v jednom z krajních bodů x2 = a, x2 = x3):
d
dx2
x2
1
x2JrX3 — x2
x2
X2 + X3    (^+V^)2J {*2 + X3y   (v^+V^)2 ^2+^3(xA+V/^)3
£3
^2 + X3       y/ä + v^2".
= 0.
Vypočítáme a získáme a;2
Máme tedy x2, pro které je funkce F2{a,x3) maximální, dosadíme a máme
F2(a,x3)
ax\
^l+*3 [V5+(^3)*i2 4(^+^3-)M(^+4)i2
{ah+x\Y
Z výsledků výpočtů funkcí Fx(a,x2), F2(a,x3) můžeme předpokládat fc-tý člen ve tvaru
Fk{a,xk+1) =
yaj;k
fc+i-
Toto ověříme pro n-tý člen:
Fn(a,b) = max (-^-r ' K-i{a,xn)X = max i
a<i„<6 [Xn + 0 J       a<i„<b + 0
O" + In
opět vypočteme in:
dxn \xn + b (ai+ÍCiy
^ i „ň
xn + b-xn _ 1
(;r„ -f &)2(a" + x£ )n+1
1
1
14
Derivaci položíme rovnu nule a vypočteme xn. dosadíme do Fn(a,b):
Fn{a,b)
1    , n
/       1    ,    n ,x        /    l 1 1 \
1
1
což je v souladu s předchozím výpočtem pro fc-tý krok. Veličina
X\X2...Xn
(a + x1)(x1 + x2) ■ ■ ■ (z„-i + xn)(xn + 6) bude maximální při hodnotách
a tato veličina bude nabývat hodnoty
F„(a,6) =-1-^-.
1
71
15
Kapitola 2
Nekonečněkrokový deterministický rozhodovací proces
Předpokládejme nyní rozhodovací proces s velkým počtem rozhodovacích stupňů n. Jako model uvažujeme následující úlohu:
[M + B(yk - xkf] - min,
(2.1)
kde
Vk-i = b(yk - xk), 0 < b < 1, 0 < xk < yk, A,B>0. Použijeme postup, jaký známe z první kapitoly a příklad znázorníme schématicky:
Xr
Vn-1
Vk
rn(xn,yn)
Vk-i
rk(xk,yk)
	X\		yo
			
kde r„(x„,y„) v našem konkrétním príklade je Axl + B(yn - xnf a yk_x = b(yk - xk). V prvním kroku minimalizujeme Ax\ + B(Vl - Xl)2. Tedy
/,(»,) =  min   [Ax\ + B(yi-Xlf}.
Hledáme takové xu aby frfa) bylo nejmenší. Derivaci minimalizované funkce podle Xl položíme rovnu nule a vyjádříme Xl:
2Ax1-2B{y1-x1) = 0 xx
B
ÄTBVl
_
16
a dosadíme do frfa) (všimněme si, že minimalizovaná funkce / je konvexní, proto stacionární bod je bodem absolutního minima):
fÁVi)
AB A + B
Ví
Stejným postupem získáme f2(y2):
h{V2)
Ax\ + B(y2 - x2f + 4^(V2 - x2)2
AB(A + B) + 2 (^ + 5)2 + ^62
i4 + B
kde jsme využili skutečnosti, že
_ B(A + B) + ^^62
je stacionárním bodem minimalizované funkce.
Pokračováním ve schématu dostáváme stále komplikovanější výrazy, zejména pro n jdoucí k nekonečnu. Všimněme si však, že fkl resp. xk, k = 1,2, závisí na yk kvadraticky, resp. lineárně. Předpokládejme tedy, že
A-i(ífc-i) =       yŽ_i = afc-i &2 (y* - xfc)2. Vyjádříme-li tedy /fc(yfc), dostáváme:
/fc(yfc)=   min   [^ + %-ířfc)a + at.1%-ífc)2].
Derivováním zjistíme     a dosazením také /fc(yfc):
AB + Aak^b2
fk{yk)
xk
A + B + afc_i 62 5 + afc_! 62
A + B + afc_i 62
tedy i /fc závisí na yk kvadraticky a xk lineárně. Máme obecnou rovnici schématu:
fk(yk) =   min   [Ax2k + Sfe* - xkf + - zfc))l ,    = 1,... ,n. (2.2)
Formálním limitním přechodem pro k -+ oo (předpokládáme, že existují limity posloupností xk, yk a funkcí fk - vysvětlení viz konec tohoto odstavce), můžeme uvažovat následující rovnici:
}{y) = min [Ax2 + B(y - xf + f{b{y - x))] .
0<x<y
17
_
Na úvodním příkladě (2.1) si ukážeme, jak dobře řešení této jedné rovnice aproximuje n-stupňový proces pro n -> oo. Na základě výsledku pro n = 1,2 hledáme řešení ve tvaru f(y) = ay2,s neznámou konstantou a. Dostáváme tedy rovnici:
ay2 = min \Ax2 + B(y - x)2 + ab2(y - x)2} .
0<x<y V* J
Již známým způsobem najdeme takové x, pro které je výraz v hranatých závorkách minimální, tedy
B + ab2
2Ax - 2B(y - x) - 2a b2 (y - x) = 0
x
A + B + ab2 A po dosazení řešíme rovnici pro a:
ay2= ^+B + aPy2    ^   b2 a2   (A-\- B - Ab2) a - AB = 0
a tedy
a = — [Ab2 ~ A - 5 ±        + B - ^62)2 + 462 .
Jako příklad vezměme hodnoty A = 3, B = 1, b = ^, dosazením do výrazu pro a vyjde a = l1. Nalezli jsme řešení funkcionální rovnice f(y) = ay2, s výsledkem
f (v) = v2,* = |-
Poznámka 4. Srovnáme-li tyto hodnoty se skutečnými optimálními hodnotami z jednotlivých kroků pro n = 1,2, kde
B 1
X2 = (i4 + £)2 + ABb2 V2 = 2/2 A tyto hodnoty poměrně rychle konvergují k |, tedy xn      f.
Když budeme mít rozhodovací proces s n-kroky (n > 1), ukazuje se jako výhodné n-krokový proces (tedy konečně krokový rozhodovací proces) nahradit nekonečně stupňovým, který popisuje jistá funkcionální rovnice.
Nyní uvažujme rekurzivní formuli rz-krokového procesu:
fn(yn)=   min   [rn(a?B,yn) + /n_1(^_1(xn,yn))]2
0<xn<yn
V tomto vztahu proveďme (formálně) limitní přechod pro n oo. Slovo "formálně" znamená, že předpokládáme, že všechny veličiny s indexem n mají limity pro n -+ oo. Tímto postupem dostaneme základní funkcionální rovnici dynamického programování:
f(y)= min [r{x,y) + f(g{x,y))]. (2.4)
0<x<y
Jv předchozím vzorci pro a bereme znaménko plus, neboť hledáme a > 0.
2v předchozím motivačním příkladu bylo rn(a;n,yn) rovno Ax2n + B(yn - xn)2 a #(a;n,yn) bylo rovno b{yn-xn)
18
2.1   Metody řešení funkcionální rovnice dynamického programování
Uvažujme rovnici
/(»)= min lr(x,y) + f(g(x,y))], (2.5)
tedy funkcionální rovnici, kde předpokládáme, že celkový zisk je součtem zisků z jednotlivých stupňů rozhodovacího procesu a / je neznámá funkce, kterou chceme spočítat. Nyní uvedeme dvě základní metody, jak lze tuto rovnici řešit.
2.1.1 Metoda postupných aproximací
Zvolíme počáteční aproximaci neznámé funkce f(y) a tu označíme f0(y). Většinou bereme fo(y) = 0. Definujeme posloupnost funkcí fn(y) rekurentním předpisem
fk(y)= min [r(x,y) + fk-i(g{x,y))], k = 1,2,... ,n,
0<x<y
což je vlastně zpětné nahrazení nekonečně-stupňového procesu konečně-stupňovou analogií. Chceme, aby fn(y) konvergovalo k f {y), pro n oo.
2.1.2 Metoda aproximace na množině optimálních rozhodnutí
V rovnici (2.5) je extrému nabyto v bodě x = x(y)3, tj. závisí na hodnotě y. Učiníme počáteční aproximaci této neznámé funkce x = x(y), a to x = x0{y), což je počáteční aproximace závislosti bodu extrému na y. Po dosazení do (2.5) máme
f(y) = r(x0(y),y) + f(g(x0(y),y)). (2.6)
Tato rovnice má tu výhodu, že neobsahuje operaci maxima, je to tedy funkcionální rovnice v obvyklém smyslu. Formální definice pojmu funkcionální rovnice je značně komplikovaná, lze ji najít např. v [4], [5].
Nechť f0(y) je řešení této funkcionální rovnice. Následující aproximaci x = Xi(y) optimálního rozhodnutí x(y) najdeme jako řešení extrémální úlohy :
lr{x,y) + fo(g(x,y))] - min, se[0,y]. Pak pro h{y) dostáváme obyčejnou funkcionální rovnici (tj. rovnici bez operace minima)
fi(y) = rfaiy^y) + fMx^y)^)). Nyní známe řešení f^y) a pomocí tohoto řešení najdeme x2(y) jako optimální řešení úlohy
lr{x,y) + fi(g(x,y))] - min, x G [0,y],
3funkci x = x(y) neznáme
19
a f2(y) jako řešení funkcionální rovnice
f2(y) = r(x2(y)iy) + f2(g(x2(y),y)),
takto postupujeme dále.
Příklad 2.1.1. Nyní ilustrujeme tyto dvě metody na úvodním příkladě
r(x, y) = Ax2 + B(y - xf ,   g(x, y) = b{y - x), 0 < b < 1.
Metodou postupných aproximací /0, /i, ... jsme řešení již naznačili, ukážeme tedy postup metodou aproximace na množině optimálních rozhodnutí. Jako počáteční aproximaci vezměme x0(y) = -jf^y, což odpovídá počáteční aproximaci f0{y) = 0. Funkci x0{y) jsme
našli jako řešení úlohy
min \Ax2 + B(y-x)2]
0<x<y 1
Nyní pomocí x0{y) hledáme f0(y) (využijeme vztahu (2.6)):
fo(y) = Ax2 + B(y - xf + /0 (b(y - y)) = y2 + /0 y) . (2.7)
Při řešení této rovnice využijeme skutečnosti, že řešení by mělo záviset na y kvadraticky, tedy fQ(y) = a0y2. Dosazením do rovnice (2.7) obdržíme:
AB(A + B) AB(A + B) 2
a° ~~ (4 + 5)2 - 6M2 ^ ío{y) ~ (A + £)2 - 6M2 y "
Funkci Xl(y) určíme jako řešení extrémální úlohy
min \Ax2 + £(y - x)2 + /0(6(y - x)) 1 .
0<x<y V
Na základě toho, že /0(y) = a0y2, předchozí extrémální úlohu můžeme psát ve tvaru
min \Ax2 + B(y-x)2 + a0b2(y-x)2}.
0<x<y 1 ^ J
Minimalizací dostáváme
, ,       B + apb2 Xliy)= A + B + a0Vy>
dosadíme do f(y) a obdržíme:
A(B + a0b2)2    2       /        B + aob2     V ,
. /        B + a062
,46y
^ + g062)2 + ^ 2 (,4 + £ + ao&2)2   V +/l
yt + £-fa062_
20
a v této rovnici opět využijeme toho, že fx(y) závisí na y kvadraticky, tedy h{y) = ax y2 a vyjádříme ax a zpětným dosazením f^y):
A(B + a0b2)2 + A2B A(B + a0b2)2 + A2 B 2
ai~ (A + B + a0b2)2-AH2 a fl(y)- (A + B + a0b2)2-A2b2V-
Pro x2 řešíme tuto úlohu:
min \Ax2 + B(y-x)2 + f1{b{y-x))]
0<x<y 1 v- / v  v* //j
což je
min lAx' + Biy-xf + atfiy-x)2]
0<x<y 1 v /
Minimalizací získáme x2:
X2[y)- A + B + ouP1*'
Dosazením do f(y) obdržíme výraz pro f2(y): r, ,    A{B + a^b2)2 + A2B
y2 + í2
Aby
A + B + axb2
(A + B + a,b2)2
Opět s využitím poznatku, že f2(y) = a2y2 vypočteme z předchozí rovnice a2 dosazením:
A(B + aib2)2 + A2B
Oí2
Funkce f2(y) bude po dosazení
í2{y)
Vezmeme-li opět hodnoty A
(A   i    D   i   „   W?\9        A 9 W>
\A + B + OL\(ry — AÁ 0Z
+ aiO )       A tí 2
(j4 + 5 + a\b2)2 — A2b2 '
3, 5 = 1, b = ^, z následující tabulky je vidět, že výsledky metody aproximace optimálních rozhodnutí (v tabulce jako MAOR) konvergují rychleji, než s použitím metody postupných aproximací (MPA) funkce /.
	MPA		MAOR	
k = 0 k=l fc = 2 k = 3 k = 4	/o = 0 íi = 0.75y2 f2 = 0.945y2 f3 = 0.987y2 U = 0.995y2	Xo = 0 id = 0.25y x2 = 0.314y ^3 - 0.37y z4 - 0.332y	/o = 1.043y2 /i = 1-OOy2 h = 1.00y2	x0 = 0.25y a;i = 0.32y x2 = 0.333?y
21
2.2   Základní funkcionální rovnice dynamického programování
Jako speciální případ funkcionální rovnice (2.5) uvažujme tento případ: y vstupních prostředků máme rozdělit do nákupu dvou zařízení (strojů). Do prvního stroje investujeme x {0<x< y), do druhého y-z, přičemž zisky z používání těchto strojů jsou g{x) a h{y-x). To vede k řešení úlohy:
g(x) + h(y - x) -> max,   0 < x < y.
Nyní předpokládejme dvoukrokový proces: po určité době obě výrobní zařízení prodáme a obdržíme za ně částku ax resp. b(y - x), a, b € [0,1) (předpokládáme amortizaci, tj. sníží se hodnota, proto uvažujeme a, b < 1). Ve druhém kroku máme k dispozici na rozdělení už jen ax + b(y - x) prostředků, které označíme yY. To vede na úlohu
max [g(x) + h(y - x) + gfa) + h(Vl - Xl)],
0<x<yL
při vazebné podmínce yx = ax + b(y - x).
Stejnou úvahou jako v obecném schématu se dostáváme k rekurentní formuli
fn{y) = max [g{x) + h(y - x) + fn-i{ax + b(y - x))]
0<x<y
a pro formální limitní proces n -+ oo obdržíme funkcionální rovnici
f(y) = max [g(x) + h(y - x) + f{ax + b(y - x))]. (2.8)
0<x<y
Nyní se budeme zabývat problematikou řešení této rovnice, tedy existencí, jednoznačností a způsoby řešení ve speciálních případech.
Věta 2.1. (O existenci a jednoznačnosti řešení). Nechť funkce g(y), h(y) jsou spojité na intervalu [0, oo), g{0) = 0 - h(0). Dále nechť
m(y) = oMx{max{ 1^)1,1^)1}},
c = max{a, 6}, kde a, b G [0,1). Jestliže YZi m(c^) < oo pro y > 0, pak existuje jediné řešení rovnice (2.8), splňující podmínky spojitosti funkce / v bodě y = 0 a /(O) = 0 . Toto řešení je spojité pro všechna y G [0, oo], pro něž jsou splněny podmínky věty.
Důkaz. Větu dokážeme na dílčím případě, kdy obě funkce g i h nabývají pouze nezáporných hodnot. Tehdy je při libovolném y posloupnost funkcí {fn(y)}, získaná ze vztahu
fk(y) = max \g{x) + h{y - x) + h-^ax + b{y - x))], k = 1,... ,n,
0<x<y
monotónně rostoucí, a jak bude ukázáno dále, také ohraničená v důsledku podmínky EÍLi m(cky) < oo. Proto pro všechny y>0 posloupnost funkcí fn{y) konverguje k funkci f(y) pro n —► co.
22
Ukážeme, že tato funkce vyhovuje rovnici
f (y) = sup [g{x) + h(y - x) + f(ax + b(y - x))}. (2.9)
0<x<y
Pro zjednodušení zápisu definujeme zobrazení T : C[0, oo)xR^ C[0, oo) předpisem
T(/, x) =       + % - x) + /(az + 6(y - a;)). Pak základní rekurentní vztah zapíšeme ve formě
fk+i(y)= max T{fk,x). (2.10)
0<x<y '
Odtud a z monotónnosti pro všechna k G N dostaneme, že
f (y) > max T(fk,x),
0<x<y
ale toto značí, že pro libovolné x G [0,y] platí nerovnice
f (y) > T(fk,x),
a tato nerovnice zůstává zachována i pro k -> co, tj.
/(y) > T(/,a;) pro všechna x G [0,y], odkud ve skutečnosti vyplývá, že
f (y) >  sup T(f,x). (2.11)
0<x<y
Poznamenejme, že zde nemůžeme použít operace maxima, protože (zatím) není zaručena spojitost limitní funkce f(y). Na druhé straně z (2.10) dostaneme vztah
fk+i(v) <  sup T(f,x)
0<x<y
pro každé k = 0,..., oo a odtud také
f(y) <  sup T(/,x). (2.12)
0<x<y
Spojení (2.11) a (2.12) nám dá vztah (2.9), tedy
f(y) = sup {g{x) + h(y - x) + f{ax + b(y - x))}.
0<x<y
K dokončení důkazu je nyní třeba ukázat, že funkce / je spojitá, a tedy operaci suprema v (2.9) lze nahradit operací maxima. Tato část důkazu je technicky poměrně náročná, proto ji neuvádíme. Poznamenejme, že tento důkaz je založen na konstrukci posloupnosti postupných aproximací. Podrobnosti je možno nalézt v [1]. □
23
Nyní se budeme zabývat konvergencí druhé základní metody vyšetřování funkcionální rovnice dynamického programování, metody aproximace na množině optimálních řešení. Zde ukážeme, že v případě, kdy počáteční aproximaci f0(y) bereme jako výsledek (řešení) funkcionální rovnice, kde je dosazena počáteční aproximace x0 = x0{y) v prostoru optimálních rozhodnutí, pak je konvergence posloupnosti postupných aproximací monotónní.
Věta 2.2. Nechť x0 = x0{y) je libovolná spojitá funkce splňující nerovnost 0 < x0(y) < y a nechť /0 je řešením funkcionální rovnice
fo(y) = g(x0(y)) + h(y - x0(y)) + f(ax0(y) + b(y - x0(y))).
Pak posloupnost definovaná rekurentně
fk(y) = max {g(x) + h(y - x) + /fc_i(as + b(y - x))}
0<x<y
je monotónní a její konvergence je stejnoměrná.
Důkaz. Neprovádíme, je podobný důkazu předchozí věty. □
2.3   Vlastnosti řešení funkcionální rovnice dynamického programování
Věta 2.3. Předpokládejme, že jsou splněny předpoklady Věty 2.1 o existenci a jednoznačnosti řešení a nechť navíc funkce g & h jsou konvexní na intervalu [0,oo). Pak funkce /, která je řešením rovnice (2.8), tedy rovnice
f (y) = max [g(x) + h(y - x) + f(ax + b(y - x))\,
0<x<y
je také konvexní a pro libovolné y je optimální rozhodnutí x{y) = 0 nebo x(y) = y, tj. maxima je dosaženo v jednom z krajních bodů intervalu [0, y] a rovnice (2.8) se zjednodušší na tvar
f(y) = max{%) + f (by), g(y) + f(ay)}. Zejména, je-li a = 6, předchozí rovnice se dále zjednodušují na
f(y) = max{h(y),g(y)} + f(ay)
a označíme-li F(y) = max{%), g{y)}, lze řešení funkcionální rovnice vyjádřit ve tvaru
oo
/(») = E F^ky)-
k=0
24
Důkaz. Pro / = 0 je
h{y)= m^{g{x) + h{y-x)}
0<x<y
a g(x) + h(y - x) je konvexní v proměnné x. Konvexní funkce nabývá na daném intervalu maxima v krajním bodě tohoto intervalu, tj.
/i(y) = max{(?(0) + h(y),g(y) + h(0)} = max{ %),<?(?/)}
je konvexní, neboť je maximem konvexních funkcí. Dále funkce
f2(y) = max {g(x) + h(y - x) + fi(ax + b{y - x))}
= max{p(0) + h(y) + h(by),g(y) + fc(0) + h(ay)} = max{h(y) + f1(by),g(y) + fl(ay)}
je ze stejného důvodu také konvexní. Indukcí bychom dostali, že každá z funkcí fk je konvexní. Konvexnost funkce / pak plyne z faktu, že stejnoměrná limita konvexních funkcí je konvexní funkce. Protože tedy i / je konvexní,
f(y) = max {g(x) + h(y - x) + f(ax + b(y - x))}
0<x<y
= max{<?(0) + h{y) + f(by),g{y) + fc(0) + /(ay)} - max{%) + f(by),g(y) + /(ay)}.
Nyní dokážeme druhou část věty pro speciální případ a = b. Zapíšeme funkci /(y) pomocí uvedeného značení:
/(*) - ^(y) + nay).
Nyní rozepíšeme výraz pro f(ay) :
/(ay) = F(oy) + /(a2y). Pro /(y) potom dostáváme výraz
f(y) = F{y) + ^(ai/) + f (o2 y) = F(y) + F(ay) + F(a2 y) + /(a3 y) = = ... = £F(A)+/(a"+1y).
k=0
Pro a G [0,1] posloupnost f{an y) konverguje k nule. Získali jsme tedy dokazovanou formuli
oo
f(y) = F(aky)-
k=0
Věta 2.4. Nechť opět platí předpoklady Věty 2.1 o existenci a jednoznačnosti a předpokládejme navíc, že h a g jsou rostoucí a konkávni. Pak i řešení / je ostře konkávni funkce a optimální řešení rovnice (2.8) je jediné.
Důkaz. Je v podstatě stejný jako důkaz předchozí věty, proto jej neuvádíme. □
Věta 2.5. Nechť jsou splněny předpoklady Věty 2.1 a funkce f,g jsou ostře konkávni, rostoucí a spojitě diferencovatelné. Dále předpokládejme, že
l>6>a>0,   ^<J-Í°1,   h'(0)>g'(oc). (2.13) 1 — a    l — o
Pak existuje číslo y G (0, oo), které je určeno jako řešení rovnice
oo
h'W = 9'(y) -     ~~ a)aV(a/c+1y)
fc=0
s následující vlastností
a) Pro y < y je maxima v rovnici (2.8) nabyto v pravém krajním bodě x(y) = y a v tomto
případě je řešením úlohy 2.8 funkce
OO
í(y) = g{y)Jr^J9{^y) ■
k=i
b) Pro y > y je maxima v rovnici (2.8) nabyto ve stacionárním bodě, který je řešením
rovnice
g'(x) - h'(y -x) + (a- b)f'(ax + b(y - x)) = 0. Důkaz. Nechť /0 = 0, potom
/i= max{g(x)-{-h{y-x)}.
Protože g'{0) > h'{0) (to plyne z (2.13), neboť b > a > 0) a g', h' jsou spojité, existuje y > 0 takové, že
inf g'(x) > max h'(t), xe[o,»] íg[o)2/]
pak pro x G [0,y] je g'{x) > h'{y - x), což znamená že [g(x) + h(y - x)]' > 0 a tedy
max\g{x) + h(y-x)]=g(y).
0<x<y
Dále z konkávnosti funkcí ^hz toho, že g'(oo) < tí(0) plyne existence jediného řešení rovnice g'(y) = h'(0). Označíme-li ý toto řešení, pak pro y > y leží řešení rovnice
g'(x) - tí{y - x) = 0
26
uvnitř intervalu [O, y], což plyne z toho, že pro y = y je řešením rovnice g'(x) -h'(y-x) = 0 právě x = y. Označme toto řešení xx = Xl(y) (tj. Xl(ý) = y). Funkce fľ(y) je tvaru
h[y)    \ g{Xl) + h(y-Xl), y>y,
a po derivaci
JÚV) ~ \   UK o.
Ji\y>-\ h'(y-xx), y>ý, kde h'(y - xi) máme z výpočtu
4-[g{xi) + h(y - a*)] = y(Xl) - h'(y - Xl)] ^ + h'(y - Xl) =      - zi) ay >-v-' ay
=o
Všimněme si, že f[ je spojitá funkce, neboť
fi(v-) = 9'(v),   ti(H) = ti(0) = g'(y).
Z konkávnosti funkcí g, h plyne konkávnost funkce h(y) - viz důkaz předchozí věty. Pro další iteraci označme:
D(x) = g\x)-h\y-x)+f[{ax+b{y-x))(b-a) = ^[g{x)+h{y-x)+h{ax+b{y-x)){b-a% přičemž pro x = y = 0 platí
g'{0) - h'(0) + f[(0)(b - a) = </(0) - fc'(0) + g'(Q)(b - a) =
(l + 6-a)(l-a)
= ^(0)(l + 6-a)-/i,(0)>/i,(0) Odtud plyne, že existuje y > 0 takové, že
> 0
min [g'(x) + f[{ax + 6(y - x))] > max fc(í),
a tedy D(a;) > 0 pro re e 0,y. To znamená, že pro malá y > 0 je maxima v definici /2(y): /2(y) = max {g(x) + % - x) + /^az + % - z))}
0<x<y
dosaženo v pravém krajním bodě x = y. S rostoucím y bude existovat nejmenší hodnota, označme ji y, pro níž D(x) = 0, toto y je řešením
g\x) = tí(0) + (b-a)fl(ax).
Vezmeme-li v úvahu, že ý je řešením rovnice g'{x) = fc'(0), dostáváme 0<y<y.
Proy > y leží řešení rovnice D(a;) - 0 uvnitř intervalu [0,y], označme toto řešení x2 =
x2(y). S využitím těchto informací dostáváme
\ pfefe)) + % - x2(y)) + fi(ax2(y) + 6(y - x2(y))), y>y,
27
to je
S, ,    í 9'(y) + ag'(ay), 0<y<y h[y) ~ \ h'(y - x2(y)) + bf[{ax2(y) + b(y - x2(y))), y>y.
Všimněme si opět spojitosti funkce f2(y) :
ň(y-) - sf(y) + ^(ay) = g'(y) + a/í(ay), f2(y+) = ^ (0) + bf1(ay).
Nyní pomocí rozdílu
/í(y-) - /í(y+) = </(y) - fr'(o) + (a - 6)/í(ay) = o,
neboť na pravé straně je právě rovnice definujcí y.
Nyní přeznačme proměnné yuy2 následujícím způsobem: yx := ý,y2 := £ a pokračujme dále
/n+1(2/) = max {g(x) + % - x) + /„(os + 6fo - x))}.
0<x<y
Chceme ukázat existenci yn+1 s vlastností 0 < yn+1 < yn < ■ ■ • < y2 < Vl takové, že pro y < yn+l je maximum realizováno v pravém krajním bodě x = yn+1 a pro y > yn+1 ve stacionárním bodě uvnitř intervalu. Existenci yn+1 dokážeme obdobně jako v předchozí části, je to řešení rovnice
g'(x)-tí{0) + (a-b)&(ax)=0
K důkazu nerovnosti yn+1 < yn musíme ukázat, že f'n{y) > f^(y), neboť yn je řešením g'(x) - h'(0) + (a - 6)/;_!(aa;) = 0. Ukážeme, že f'2{y) > f[(y), pro další n se postupuje indukcí. Pro y > yY je
ň(y) = fc'(y - *2(y)) + bfí(ax2(y) + % - x2(y))), f1(y) = tí(y-x1(y)),
kde a?i(i/),a?2(y) jsou stacionární body v definicích funkcí f^y), f2{y), tedy xx(y) získáme z rovnice <?'(;r)-/i'(y-a;) = 0ai2(y) z rovnice ^(s) -/*'(y-zH(a-&)/í(az + 6(y-aO) - 0. Dosazením do vztahů pro f[(y)JÍ(y) dostáváme
/í(y) = Ä'(y - *i(y)) = g'My)) - ah'(y - ^(y))]
'-"-' /X^T^
/í i y  ii i y))
>-v-'      O —
g'{xi(y)) h'(y—xi(y))
bg(x1(y))-ah'(y-x1(y))
b — a
Z rovnice pro x2{y) :
VMy)) - a^'(y - *2(y)) - M'(y - x2(y)) - ah'{y - x2(y)) - b(a - b)f[{ax2{y) + + b{y - x2(y))) = (b - aMtffo - z2(y)) + bf[{ax2(y) + 6fo - x2(y)))] = (6 - a)/^?/),
28
a tedy
h\y)
bg(x2(y)) - ah'(y - x2(y)) b — a
Funkce (6-a) [bg(x(V))-ah (y-x(y)} je: klesající na m^u [O »]. Mttri, azfektu, ze My) < (viz rovnice, které je určuji) dostávame f2(y) > /,(„). Podobne dostaneme
tyto nerovnosti i pro y e Ijte, WiJ a y £ |0,iftj.
Jeste naznačíme, jaK oy se urciio y3:
fz{y) = Qmax {p(a;) + h(y - x) + f2(ax + b(y-x))}, potom y3 bude nejmenší kořen rovnice
0 = g'(x) - h'{0) + (a - b)f2{ax) = </(:r) - fc'(0) + (a - 6) (</(a*) + a</(a2*)) a obecně yn bude řešením rovnice
g'(x) - h'(0) + (a - ô)b'(ax) + a</(a2z) + ■ • • + ^"V (a""1*)] = 0.
Výsledkem celé konstrukce je posloupnost yi > y2 > ■ ■ ■ > yn > ..., posloupnost derivací funkcí fí{y) > fi(y) > ..., a posloupnost optimálních řešení Xl{y) > x2(y) > .... Protože posloupnosti jsou monotónní, existují jejich limity a tím dostáváme tvrzení věty.
□
Na závěr uveďme ještě dvě tvrzení týkající se řešitelnosti rovnice (2.8) v případě, kdy funkce g, h jsou mocninné, resp. kvadratické funkce.
Věta 2.6. Spojité řešení rovnice
f(y) = max[q/d + f(ay), ey9 + f(by)],   /(O) - 0, pro jejíž parametry platí
o) a, 6 G (0,1); c,d,e,g>0, 6) 0 < d < g
je tvaru
kde
y
c(l - a*)-1
e(l — ¥) 1
Zejména, funkci f(y) lze vyjádřit v explicitním tvaru na každém intervalu
(2.14)
(2.15)
(2.16)
(2 17)
(2.18)
n
0,1,2,....
_
z
29
Důkaz. Označme A, resp. B skutečnost, že v rovnici (2.14) nastane maximum pro funkce cyd + f{ay), resp. ey9 + f (by) (dále budeme mluvit o strategiích A a B). Pak řešení 5, odpovídající optimálnímu výběru maxima v rovnici (2.14) (při řešení této rovnice metodou postupných aproximací) je možno symbolicky zapsat jako
kde <n a b{ jsou celá čísla, přičemž A* označuje, že maximum v rovnici (2.14) bylo nabyto prvním výrazem arkrát v řadě, Bb* má stejný význam. Předpokládejme, že řešení má uvedený tvar (2.17) a ukážeme, jak je možné získat hodnotu y. V bodě y je A i B současně maximem v rovnici (2.14), přičemž pro y < y je maximum nabyto pro první výraz A (to plyne z předpokladu (2.15)). Tedy, pro (y = y) můžeme situaci popsat formálně rovností
BA°° = A°°.
Pro situaci formálně popsanou výrazem A°° platí
f (V) = ?yd + fW = cyd + c{ay)d + c(a2y)d + • • • = (2.19)
1 — ar
Analogicky, pro situaci popsanou výrazem BA°° platí
í(y) = ty9 + f^-d- (2-20)
1 — ar
Porovnáním výrazů (2.19) a (2.20) dostáváme rovnici (2.18) pro y.
Zbývá dokázat, že řešení dané rovnice má tvar (2.17). Nejprve ukážeme, že pro malé hodnoty y maximum nastane vždy pro výraz A. K tomu stačí ukázat, že f(y) = cyd/{l - ad) je pro tato y řešením. Toto nastane, pokud pro malá y platí
°^    = max
l-ad
dn4
cyd , cbdy' -:,ey9
ad l — ar
což však plyne z nerovností y>d>0a0<6<l.
Dále postupujeme indukcí. Nechť z označuje nejmenší hodnotu y, pro kterou maximum nastane pro výraz B. Pak pro toto y platí BA°° = A°°. To znamená, že z = y. Uvažujme nyní interval pfa definujme bod p jako bod, v němž AB = BA. Nechť platí (při již zavedeném značení)
fAB(y) = cyd + ea9y9 + f (aby), fBA(y) = ey9 + cbdyd-hf{aby).
Odtud pro hledaný bod p dostáváme rovnost
P
c(l - bd) _e(l-ad).
30
a protože g > d, platí p < y.
Z toho, že fAB{y) < fBA(y) pro y > p plyne, že pro y > y optimální strategie AB následovaná optimálními rozhodnutími v dalších krocích je horší, než strategie BA následovaná optimálními rozhodnutími. Odtud je vidět, že strategie A nemůže být vybrána pro y > y, s výjimkou případu, kdy je následována strategií A°°, což však také není možné, jak jsme ukázali v předchozí části důkazu. Tím je důkaz věty dokončen. □
V následující větě se budeme zabývat situací, kdy funkce g, h jsou kvadratické.
Věta 2.7. Nechť c, d > 0, 0 < 6 < a < 1 a
f(y) = max [cx - x2 + d(y - x) - (y - x)2 + f(ax + b(y - x))],   /(O) = 0. (2.21)
Pak v intervalu 0 < y < min(c/2, d/2) 4 je řešení f{y) následujícího tvaru, který závisí na znaménku rozdílu c/(l - a) - d/(l - b). Řešení rozdělíme na několik případů:
(i) Případc/(l-a) = d/(l-6).
f(y)
(c-d)a + d l-b+{b-a)aV
a2 + (1 - a)2 2
1- [(a-b)a + b]2V '
kde
(ii) Případ c/(l - a) <d/(l-b).
pro 0 < y < min{A, c/2, d/2}, kde
(l + 6)[d(l-a)-c(l-6)] 2(1 - ob)
(iii) Případ c/(l - a) >       - 6).
pro0<y <min{/*,c/2,d/2}, kde
(l + o)[c(o-6)-d(l-o)] 2(1 - ob)
4To je nejdelší interval, na kterém jsou obě funkce /, g rostoucí.
31
2.4 Příklady
Příklad 2.4.1. Určete řešení základní rovnice dynamického programování f(y) = max {g(x) + h(y - x) + f(ax + b(y ~ x))},
je-li g(x) = x2, h(x) = 2x2-x,a = b=l Řešení:
Funkce g, h jsou konvexní, maxima je tedy nabyto v bodě x = 0 nebo v bodě z = y, tedy
f(y) = max{p(0) + h(y) + f(by),g(y) + fc(0) + /(ay)} - /(ay) + max{%),p(y)},
s použitím označení z Věty 2.3 a toho, že a = \ dostáváme
k=0 k=0
Do výrazu pro F{y) dosadíme funkce g(y) a h{y) a máme
y2,        2/e [0,1]
F(y) = max{y2,2y2-y}
1 ty -y, y>i
Je-li y G [0,1], pak
Nyní nechť y G [2", 2n+1] pro n = 0, l„pak
»<i => /(ž/) = E(í)2=2/2t1t = ^2-
> 1   a   -\- < 1.
2n — 2n~*~
V tomto případě funkci f(y) získáme takto:
/<*> = £^) = E'(£)+=
fc=0 fc=0 fc=n+l
-£{»(&■-(*)}♦£(*)-
fc=0 fc=rz+l
Příklad 2.4.2. Určete mezní hodnotu y a pro y < y určete řešení rovnice f(y) = 3^ {g{x) + h{y - x) + /(az + ft(y - a?))},
0<x<y
32
je-li g{x) = 2x- x2, h(x) = x - x2, a = §, b = f. Řešení:
Funkce g, h jsou konvexní, maxima pro funkci / je nabyto pro x(y) = y, je-li y < y. Určíme y z definice jako řešení rovnice:
oo
ft'(0) = j'(j)-(i-«)^'-V(«'})
k=l
Víme, že fc'fe) = 1 - 2y, h'(0) = 1, = 2 - 2y, ^(o*y) = 2 - 2(a*y). Dosadíme do
rovnice a spočítáme y:
^   oo / /]\*
V rovnici vyřešíme první sumu a druhou upravíme:
1 = 2 - 2y
1 = 2 - 2y - -y 3
OO /
2fc
2-*
3
a odtud dostáváme
y
Tě'
Nyní dosadíme do vztahu
tedy
/(») = 2y
"^Ž2^)   ^"Ž^^7) ~2^
2ý
2y   y ~\~ 2y Ay '
Proy<± je řešením funkce
/(l/) = 4y-^.
1
3
33
Závěr
V současné době existuje celá řada monografií zabývajících se teorií a praxí dynamického programování. Vedle již zmíněných knih R. Bellmana a G. L. Nemhausera zmiňme alespoň monografie M. Sniedoviche [6] a A. Kaufmanna a R. Cruona [2]. Stručným nahlédnutím do posledně jmenovaných dvou knih se snadno přesvědčíme, že přístup v knihách [1],[3] je jenom jedním z možných přístupů ke studiu a prezentaci dané problematiky. Nakonec poznamenejme, že zcela stranou zůstala problematika stochastických rozhodovacích procesů. Ale i stručná prezentace metod a výsledků této teorie přesahuje rámec této diplomové práce.
34
Literatura
[1] BELLMAN, R. Dynamic Programming. Princeton University Press,Princeton, 1957
[2] KAUFMANN, A., CRUON, R. Dynamické programovanie. Alfa, Bratislava, 1969
[3] NEMHAUSER, G. L. Einführung in die Praxis der Dynamischen Programmierung. R.Oldenbourg Verlag München-Wien, 1969
[4] NEUMAN, F. Funkcionální rovnice. SNTL, Praha, 1986
[5] SMÍTAL, J. O funkciách a funkcionálních rovniciach. Alfa, Bratislava, 1984
[6] SNIEDOVICH, M. Dynamic Programming. Marcel Dekker, New York, 1992
35
Knihovna PřF MU 3145326888
MASARYKOVA UNIVER2,TA v RDWé
5ft9    ÍJ^NA SEKCE MATEM/miv
W. 549493 87? m2a
3145326888