Příklad se zpětnou indukcí
Příklad Během devíti týdnů prázdnin se na konci každého týdne může naskytnout možnost být zaměstnán od následujícího týdne během zbývajících týdnů (před prvním týdnem se také rozhodujeme). V úvahu připadají dvě brigády, jedna za tři tisíce za týden, druhá za dva tisíce za týden. Šance, že na konci týdne nastane příležitost na první brigádu je 0,3, na druhou 0,4. Jakým způsobem je výhodné se rozhodovat, chceme-li maximalizovat peněžní zisk během prázdnin? Danou brigádu je možné vzít vždy pouze na celou dobu do konce prázdnin.
Řešení. Je jasné, že je výhodné vzít první brigádu, pokud je více nabídek. Je však výhodnější čekat na nabídku první brigády, než vzít nabídku brigády druhé? Budeme postupovat „zpětnou indukcí'. Před posledním týdnem je jasné, že pokud dostaneme nabídku pouze druhé brigády, je dobré ji vzít (nic jiného dostat později už z časových důvodů nemůžeme). Hodnota přijetí 1. brigády v i-tém týdnu je 3 • (9 — i), přijetí druhé brigády má hodnotu 2 • (9 — i). Pravděpodobnost obdržení l.brigády v následujícím týdnu je 0,3, obdržení druhé, ale ne první brigády je 0,4 • 0,7 a pravděpodobnost neobdržení žádné nabídky je 0,6-0,7. Označíme-li hodnotu nepřijetí žádné brigády jako q dostáváme tak rekurentní vztah (pro 1 < / < 7)
d = 3 • (9 - i) • 0,3 + 2 • (9 - i) ■ 0,7 • 0,4 + 0,6 • 0,7 • ci+i.
Navíc víme, že cg — 0. Postupně tak dopočítáme c% — 1,46, cj — 3,5332, ..., C2 = 15,802, c\ = 18,317. Zjišťujeme tedy, že hodnota odmítnutí druhé brigády v prvním týdnu (tj. střední hodnota budoucích zisků) má větší hodnotu než přijetí nabídky druhé brigády (to má hodnotu 9 • 2 — 18). Dostaneme-li tedy před prázdninami pouze nabídku druhé brigády, je výhodnější tuto odmítnout a týden počkat. Pak již je výhodnější přijmout i nabídku druhé brigády, nebof přijetí nabídky druhé brigády má počínaje druhým týdnem větší hodnotu (c;- < 2 • (9 — /) < 3 • (9 — /), pro 2 < i < 9).
□
1