12. Řízené markovské řetězce
12.1. Definice: Definice optimá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.
12.2. Věta: Věta o optimální strategii
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*
.
12.3. Příklad: 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
,
6,04,0
6,04,0
,
51
02
,
8,02,0
5,05,0 2211
RPRP .
Pro první tři kroky najděte maximální střední hodnotu celkového výnosu a optimální strategii.
Řešení: Připomeňme, že střední hodnota výnosu při jednom přechodu ze stavu i se vypočte podle vzorce ∑∈
=
Jj
ijiji
rpq .
A dále, maximální střední hodnota výnosu v n-tém kroku ve stavu i je






−+= ∑∈
≤≤
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 právě k*
.
Přitom






−
=





=





−
=





=
22
13
,
6,04,0
6,04,0
,
51
02
,
8,02,0
5,05,0 2211
RPRP , tedy
8,3)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
,
8,3
1 21
qq
{ } { } 2)1(d4,04,0;8,3max)1(v,2)1(d8,18,1;1max)1(v
*
11
*
00 =⇒−=−−==⇒==
{ }
( ) ( ){ } { } 2)2(d28,228,2;7,1max4,06,08,14.08,1;4,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(d08,008,0;76,3max4,06,08,14.04,0;4,08,08,12,08,3max
)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(d56,056,0;408,3max08,06,028,24.04,0;08,08,028,22,08,3max
)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, druhém i třetím kroku je vektor optimálních strategií 





2
2
.
{ }
{ } { } 2)3(d76,276,2;18,2max08,06,028,24.08,1;08,05,028,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
=⇒==⋅+⋅+⋅+⋅+=
=++++=
12.4. Poznámka: Uvedená metoda hledání optimálních strategií se
nazývá rekurentní metoda. Hodí se jen pro malý počet kroků. Pro větší
počet kroků je vhodnější použít iterační metodu.
12.5. Poznámka: Popis iterační metody hledání optimální strategie
Ve větě 11.5. bylo dokázáno, že vytvořující funkce posloupnosti vektorů { }∞
=0n)n(v má tvar: ( ) qPIv
1
z
z1
z
)z(G
−
−
−
= .
V teorii matic se dokazuje, že matice ( ) 1
z
−
− PI obsahuje stacionární složku (tj. limitní matici A










=
a
a
M , kde a je
stacionární vektor matice P , zde budeme matici A značit S) a tranzientní složku T. Lze tedy psát
( ) ( ) ( )
TqSqTqSqv












−
++
−
+
−
+
−
=






−⋅⋅





−−
+
−
=
k
k
1
1
2
k1
2
c
z
1
B
c
z
1
B
z1
A
z1
z
c
z
1
c
z
1z1
z
z1
z
)z(G K
K
, kde ci > 1, i = 1, ..., k.
( )2
z1
z
−
je vytvořující funkce posloupnosti an = n.
z1
1
A
−
je vytvořující funkce posloupnosti an = A (nezávisí tedy na n).
i
i
c
z
1
1
B
−
je vytvořující funkce posloupnosti an =
n
i
i
c
1
B 





. Protože ci > 1, budou výrazy obsahující
n
ic
1






pro
dostatečně velká n velmi malé. Pro dostatečně velká n tedy platí:
v(n) = nSq + ATq. Označíme-li Sq = g a ATq = v, lze psát pro dostatečně velká n:
v(n) = ng + v neboli vi(n) = ng + vi, i = 0, 1, ..., N. Dosadíme-li toto vyjádření do rekurentního vztahu
∑=
−+=
N
0j
jijii )1n(vpq)n(v , dostaneme
[ ]∑=
+−+=+
N
0j
jijii vg)1n(pqvng . Upravíme:
∑∑∑∑∑ =====
+=+⇒+−+=+−+=+
N
0j
jijii
N
0j
jiji
N
0j
jij
N
0j
ij
N
0j
ijii vpqvgvpgngqvppgpngqvng
Dostali jsme systém N + 1 rovnic pro N + 2 neznámých g, v0, v1, ..., vN. Protože neznámých je o jednu více
než rovnic, nelze určit skutečné hodnoty neznámých v0, v1, ..., vN, kterým se říká váhy. Howard navrhl
položit vN = 0. Tím se počet neznámých sníží a lze vypočítat relativní váhy v0, v1, ..., vN-1, které se od
skutečných vah budou lišit jenom o konstantu, tedy jejich rozdíly budou stejné jako u skutečných vah. Např.
rozdíl v0 – v1 lze interpretovat jako rozdíl mezi střední hodnotou výnosu procesu, který vyšel ze stavu 0 a
střední hodnotou výnosu procesu, který vyšel ze stavu 1. Kritériem pro volbu strategie je výraz ∑=
+
N
0j
jij
k
i
k
vpq .
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í.)
12.6. Příklad:
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)T
a 2
q = (2
q0, 2
q1)T
.
Přitom 





=
6,04,0
5,05,01
P , 





−
=
73
391
R , 





=
3,07,0
2,08,02
P , 





−
=
191
442
R
( ) 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)T
( ) 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)T
1. iterace: zvolíme d0(1) = 1, d1(1) = 1 a pro i = 0,1 vyřešíme systém rovnic ∑=
+=+
N
0j
jijii vpqvg (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)T
.
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)T
.
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.
12.7. Poznámka: Pro libovolný počet stavů a strategií lze použít funkce howardn.m (autor Jakub Buček,
2012):
function D = howardn(P,R)
% Algoritmus Howardova iteracniho postupu pro libovolny pocet stavu a strategii
% Vstupni parametry:
% P...matice prechodu vsech strategii naskladane do jedne matice
% R...matice vynosu vsech strategii naskladane do jedne matice
% Mame-li jednotlive matice P1,P2,...,Pk a R1,R2,...,Rk, doporucuje se
% uvadet funkci ve tvaru: howardn([P1,P2,...,Pk],[R1,R2,...,Rk])
% Vystup:
% D...matice obsahujici optimalni strategii pro jednotlive obdobi,
% jednotliva obdobi jsou oznacena cislem radku