Řízené homogenní markovské řetězce
Příklad 1.: 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,
51
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(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 -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.: 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
−=−⋅+⋅=+==⋅+⋅=+=
( ) 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
−=−⋅+⋅=+==⋅+⋅=+=
1
q = 





− 3
6
(6, -3), 2
q = 





− 5
4
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žít funkci howard.m (vytvořil Pavel Mizera) – uložena v ISu v Učebních materiálech.
Příklad k samostatnému řešení:
Uvažujme provoz stroje, který může být buď v provozu (stav 0) nebo v poruše (stav 1). Ve
stavu 0 můžeme volit alternativu „bez preventivní údržby“ (strategie 1) nebo
„s preventivní údržbou“ (strategie 2). Ve stavu 1 můžeme volit buď alternativu „běžná
oprava“ (strategie 1) nebo „speciální oprava“ (strategie 2). Matice přechodu a matice výnosů
jsou následující:






−
=





=





−
=





=
92
17
R,
2,08,0
3,07,0
P,
24
49
R,
5,05,0
6,04,0
P 2211
.
Pro první tři kroky najděte maximální střední hodnotu celkového výnosu a optimální strategii.
S využitím funkce howard.m najděte takový vektor strategií, který maximalizuje střední
hodnotu celkového výnosu.
Výsledek: 





=
1
6
v1 , 





=
1
1
d 1
*
, 





=
8,4
7,9
v2 , 





=
2
2
d 2
*
, 





=
52,8
43,13
v3 , 





=
2
2
d 3
*
Funkce howard.m poskytne optimální vektor strategií 





2
2
.