Příklady na páté cvičení v počítačové učebně, SMI, PS 2010
Definice otimální strategie:
Nechť v každém kroku je možno ergodický homogenní markovský řetězec s konečnou
množinou stavů J = {0, 1, .., N} definovat h různými maticemi přechodu 1
P = (1
pij), ..., h
P =
(h
pij) a h různými maticemi výnosů 1
R = (1
rij), ..., h
P = (h
rij). V každém kroku můžeme vybrat
jednu matici přechodu a odpovídající matici výnosů. Možnosti 1, 2, ..., h se nazývají strategie.
Označme di(n) strategii vybranou v n-tém kroku ve stavu i. Ta strategie di
*
(n), pro kterou
dosahuje střední hodnota celkového výnosu svého maxima, se nazývá optimální strategie.
Rekurentní metoda hledání optimální startegie:
Předpokládejme, že v krocích n-1, n-2, ..., 1 byla nalezena optimální strategie. Označme vi(n)
maximální střední hodnotu celkového výnosu v n-tém kroku ve stavu i, tj.






 

Jj
jij
k
i
k
hk1
i )1n(vpqmax)n(v . Je-li maxima dosaženo pro k = k*
, pak optimální
strategie v n-tém kroku ve stavu i je di
*
(n) = k*
.
Iterační metoda hledání optimální strategie
Algoritmus Howardova iteračního postupu:
1. krok: Pomocí veličin pij, qi určíme veličiny g,vi z rovnic 

N
0j
jijii vpqvg , přičemž
vN = 0.
2. krok: Pro každý stav Ji  najdeme strategii k*
, která maximalizuje výraz 

N
0j
jij
k
i
k
vpq .
3. krok: Nalezená strategie k*
poskytne hodnoty ij
k
i
k
p,q **
pro opakování kroků 1 a 2.
Algoritmus končí, jakmile vektor strategií je stejný ve dvou po sobě následujících iteracích.
(Zpravidla stačí provést jen několik málo iterací.)
Příklad 1. (na použití rekurentní metody): Je sledována výrobní linka, která se může
nacházet buď v provozu (stav 0) nebo v opravě (stav 1). Ve stavu 0 je možný provoz „bez
kontroly agregátů“ (strategie 1) nebo
„s kontrolou agregátů“ (strategie 2). Ve stavu 1 je možno rozlišit opravu „bez výměny
agregátů“ (strategie 1) nebo „s výměnou agregátů“ (strategie 2). Matice přechodu a matice
výnosů jsou následující:



























22
13
R,
6,04,0
6,04,0
P,
5,01
02
R,
8,02,0
5,05,0
P 2211
.
Pro první tři kroky najděte maximální střední hodnotu celkového výnosu a optimální strategii.
Řešení:
2,0)5,0(8,012,0rprpq,105,025,0rprpq 11
1
11
1
10
1
10
1
1
1
01
1
01
1
00
1
00
1
0
1

4,0)2(6,024,0rprpq,8,116,034,0rprpq 11
2
11
2
10
2
10
2
1
2
01
2
01
2
00
2
00
2
0
2
















4,0
8,1
,
2,0
1 21
qq
    1)1(d2,04,0;2,0max)1(v,2)1(d8,18,1;1max)1(v
*
11
*
00 
 
       2)2(d4,24,2;8,1max2,06,08,14.08,1;2,05,08,15,01max
)1(vp)1(vpq);1(vp)1(vpqmax)2(v
*
0
101
2
000
2
0
2
101
1
000
1
0
1
0


 
       2)2(d2,02,0;0max2,06,08,14.04,0;2,08,08,12,02,0max
)1(vp)1(vpq);1(vp)1(vpqmax)2(v
*
1
111
2
010
2
1
2
111
1
010
1
1
1
1


 
    2)3(d88,288,2;3,2max2,06,04,24.08,1;2,05,04,25,01max
)2(vp)2(vpq);2(vp)2(vpqmax)3(v
*
0
101
2
000
2
0
2
101
1
000
1
0
1
0


 
    2)3(d68,068,0;44,0max2,06,04,24.04,0;2,08,04,22,02,0max
)2(vp)2(vpq);2(vp)2(vpqmax)3(v
*
1
111
2
010
2
1
2
111
1
010
1
1
1
1


Závěr: V prvním kroku je vektor optimálních strategií 





1
2
, ve druhém a třetím kroku 





2
2
.
Návod na řešení v MATLABu:
Zadáme matice 1
P, 1
R, 2
P, 2
R:
P1=[0.5 0.5;0.2 0.8]; R1=[2 0;1 -0.5]; P2=[0.4 0.6;0.4 0.6]; R2=[3 1;2 -2];
Vypočteme pomocné matice Q1=P1*R1’; Q2=P2*R2’;
Diagonála matice Q1 je vektor q1=diag(Q1)
Diagonála matice Q2 je vektor q2=diag(Q2)
Vypočteme vektor v1=max(q1,q2)
(Protože první složka vektoru v1 odpovídá první složce vektoru q2, znamená to, že když je
linka v provozu, je optimální strategie v 1. kroku strategie 2.
Protože druhá složka vektoru v1 odpovídá druhé složce vektoru q1, znamená to, že když je
linka v opravě, je optimální strategie v 1. kroku strategie 1.)
Spočítáme střední hodnotu celkového výnosu ve 2. kroku pro strategii 1, je-li linka v provozu:
v2_provoz_s1= q1(1)+P1(1,1)*v1(1)+P1(1,2)*v1(2)
a totéž pro strategii 2:
v2_provoz_s2= q2(1)+P2(1,1)*v1(1)+P2(1,2)*v1(2)
Dále spočítáme střední hodnotu celkového výnosu ve 2. kroku pro strategii 1, je-li linka
v opravě:
v2_oprava_s1= q1(2)+P1(2,1)*v1(1)+P1(2,2)*v1(2)
a totéž pro strategii 2:
v2_oprava_s2= q2(2)+P2(2,1)*v1(1)+P2(2,2)*v1(2)
Vypočítáme vektor v2:
v2=[max(v2_provoz_s1, v2_provoz_s2); max(v2_oprava_s1, v2_oprava_s2)]
(Vidíme, že první složka vektoru v2 odpovídá strategii 2 a druhá složka rovněž.)
Spočítáme střední hodnotu celkového výnosu ve 3. kroku pro strategii 1, je-li linka v provozu:
v3_provoz_s1= q1(1)+P1(1,1)*v2(1)+P1(1,2)*v2(2)
a totéž pro strategii 2:
v3_provoz_s2= q2(1)+P2(1,1)*v2(1)+P2(1,2)*v2(2)
Dále spočítáme střední hodnotu celkového výnosu ve 3. kroku pro strategii 1, je-li linka
v opravě:
v3_oprava_s1= q1(2)+P1(2,1)*v2(1)+P1(2,2)*v2(2)
a totéž pro strategii 2:
v3_oprava_s2= q2(2)+P2(2,1)*v2(1)+P2(2,2)*v2(2)
Vypočítáme vektor v3:
v3=[max(v3_provoz_s1, v3_provoz_s2); max(v3_oprava_s1, v3_oprava_s2)]
(Vidíme, že první složka vektoru v3 odpovídá strategii 2 a druhá složka rovněž.)
Upozornění: Uvedené řešení je pouze jedním z možných, zajisté lze vytvořit lepší.
Příklad 2. (na použití Howardova algoritmu): Závod produkuje nějaký spotřební výrobek,
u něhož lze rozeznat dva stavy: stav 0 – výrobek je úspěšný s dobrým odbytem a cenou, stav 1
– výrobek je neúspěšný, odbyt vázne a cena je nízká. Při 1. strategii vedení závodu
neinvestuje ani do technického rozvoje ani do reklamy. Při této strategii je matice přechodu







6,04,0
5,05,01
P a matice výnosů 







73
391
R . Při 2. strategii vedení závodu zajistí
technický rozvoj a investuje do reklamy. Matice přechodu: 






3,07,0
2,08,02
P , matice výnosů:








191
442
R . (Při 2. strategii se vyšší náklady promítnou do zisku, proto výnos 2
r00 musí
být nižší než 1
r00, stejně tak 2
r11 musí být nižší než 1
r11.) Pomocí iterační metody je třeba
zjistit, jakou strategii doporučit vedení závodu, aby střední hodnota celkového výnosu byla
maximální.
Řešení: Nejprve vypočítáme vektory 1
q = (1
q0, 1
q1) a 2
q = (2
q0, 2
q1).
  376,034,0rprpq,635,095,0rprpq 11
1
11
1
10
1
10
1
1
1
01
1
01
1
00
1
00
1
0
1

1
q = (6, -3)
  5193,017,0rprpq,442,048,0rprpq 11
2
11
2
10
2
10
2
1
2
01
2
01
2
00
2
00
2
0
2

2
q = (4, -5)
1. iterace: zvolíme d0(1) = 1, d1(1) = 1 a vyřešíme systém rovnic (přitom položíme v1 = 0)
00101
1
000
1
0
1
0 v5,06vg:vpvpqvg 
0111
1
010
1
1
1
1 v4,03g:vpvpqvg 
Řešením tohoto systému obdržíme v0 = 10, g = 1.
2. iterace:
i = 0, k = 1: 11105,06vpvpq 101
1
000
1
0
1

k = 2: 12108,04vpvpq 101
2
000
2
0
2

max{11, 12} = 12, tedy d0(2) = 2
i = 1, k = 1: 1104,03vpvpq 111
1
010
1
1
1

k = 2: 2107,05vpvpq 111
2
010
2
1
2

max{1, 2} = 2, tedy d1(2) = 2
Výsledek 2. iterace dává vektor strategií (2, 2).
S tímto vektorem vyřešíme systém rovnic (přitom položíme v1 = 0)
00101
2
000
2
0
2
0 v8,04vg:vpvpqvg 
0111
2
010
2
1
2
1 v7,05g:vpvpqvg 
Řešením tohoto systému obdržíme v0 = 10, g = 2.
3. iterace:
i = 0, k = 1: 11105,06vpvpq 101
1
000
1
0
1

k = 2: 12108,04vpvpq 101
2
000
2
0
2

max{11, 12} = 12, tedy d0(3) = 2
i = 1, k = 1: 1104,03vpvpq 111
1
010
1
1
1

k = 2: 2107,05vpvpq 111
2
010
2
1
2

max{1, 2} = 2, tedy d1(3) = 2
Výsledek 3. iterace dává vektor strategií (2, 2).
Protože ve dvou po sobě jdoucích iteracích jsme dostali stejný vektor strategií, výpočet končí.
Interpretace: Kromě počátečního kroku přinese větší zisk ta strategie, která zahrnuje náklady
na technický rozvoj a reklamu výrobku.
Návod na řešení v MATLABu:
Použití funkcí uložených v ISu v Učebních materiálech
howard.m (vytvořil Pavel Mizera),
howard1.m (vytvořil Ondřej Petřík)
howard2.m (vytvořil Pavel Hellebrand)