12. Řízené markovské řetězce

   

   12.1. Definice: Definice strategie a optimální strategie.

   

   12.2. Věta: Věta o hledání optimální strategie.

   

   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í:

   .

   Pro první tři kroky najděte maximální střední hodnotu celkového výnosu a optimální strategii.

   

   Řešení:

   

   

   Závěr: V prvním kroku je vektor optimálních strategií , ve druhém a třetím kroku .

   

   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

   Vytvořující funkce posloupnosti vektorů  má tvar: . V teorii matic se dokazuje, že matice
    obsahuje stacionární složku , kde a je stacionární vektor matice P a tranzientní složku T.
   Lze tedy psát

   kde c[i] > 1, i = 1, ..., k.

    je vytvořující funkce posloupnosti a[n] = n.

    je vytvořující funkce posloupnosti a[n] = A (nezávisí tedy na n).

    je vytvořující funkce posloupnosti a[n] = . Protože c[i] > 1, budou výrazy obsahující  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 v[i](n) = ng + v[i], i = 0, 1, ..., N. Dosadíme-li toto vyjádření do
   rekurentního vztahu , dostaneme

   . Upravíme:

   Dostali jsme systém N + 1 rovnic pro N + 2 neznámých g, v[0], v[1], ..., v[N]. Protože
   neznámých je o jednu více než rovnic, nelze určit skutečné hodnoty neznámých v[0], v[1], ...,
   v[N], kterým se říká váhy. Howard navrhl položit v[N] = 0. Tím se počet neznámých sníží a lze
   vypočítat relativní váhy v[0], v[1], ..., v[N-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 v[0] – v[1]
   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 .

   Algoritmus Howardova iteračního postupu:

    1. krok: Pomocí veličin p[ij], q[i] určíme veličiny g,v[i] z rovnic , přičemž v[N] = 0.
    2. krok: Pro každý stav najdeme strategii k^*, která maximalizuje výraz .
    3. krok: Nalezená strategie k^* poskytne hodnoty  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  a matice výnosů . Při 2. strategii vedení
   závodu zajistí technický rozvoj a investuje do reklamy. Matice přechodu: , matice výnosů: .
   (Při 2. strategii se vyšší náklady promítnou do zisku, proto výnos ^2r[00] musí být nižší než
   ^1r[00], stejně tak ^2r[11] musí být nižší než ^1r[11].) 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 ^1q = (^1q[0], ^1q[1]) a ^2q = (^2q[0], ^2q[1]).

   ^1q = (6, -3)

   ^2q = (4, -5)

   

   1. iterace: zvolíme d[0](1) = 1, d[1](1) = 1 a vyřešíme systém rovnic (přitom položíme v[1] =
   0)

   Řešením tohoto systému obdržíme v[0] = 10, g = 1.

   2. iterace:

   i = 0, k = 1:

            k = 2:

   max{11, 12} = 12, tedy d[0](2) = 2

   i = 1, k = 1:

            k = 2:

   max{1, 2} = 2, tedy d[1](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 v[1] = 0)

   Řešením tohoto systému obdržíme v[0] = 10, g = 2.

   

   3. iterace:

   i = 0, k = 1:

            k = 2:

   max{11, 12} = 12, tedy d[0](3) = 2

   i = 1, k = 1:

            k = 2:

   max{1, 2} = 2, tedy d[1](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.