15. srpna roku 2009 se v rámci čtvrtého kola fotbalové Gambrinus ligy konalo utkání mezi Spartou Praha (domácí) a Kladnem (hosté). Jistá sázková kancelář vypsala na výsledek utkání následující kurzy:

První řádek tabulky označuje tyto události: 1 je výhra domácích, 10 je výhra domácích nebo remíza, 0 je remíza, 02 je remíza nebo výhra hostů, 2 je výhra hostů. Druhý řádek je kurz vypsaný na danou událost. Sázková kancelář umožňuje každému sázejícímu uzavírat sázky na libovolnou kombinaci událostí (např. lze současně vsadit na vítězství Sparty i Kladna).

V rámci své marketingové strategie nabízí sázková kancelář sázejícím jednorázový bonus ve výši $50\%$ z vložené částky a to až do výše $1000$ korun. Bonus nelze vybrat přímo, ale lze ho použít k sázení. To znamená, že pokud například sázející vloží svých $2000$ korun, přidá mu sázková kancelář bonus $1000$ korun. Sázející pak může prosázet celkem $2000+1000=3000$ korun.

Je spousta strategií, jak sázet. Jednou z nich je sázet tak, abychom maximalizovali jistou výhru. Jistá výhra je taková, kterou dostaneme bez ohledu na výsledek utkání, který je (nebo by alespoň měl být) neznámý. Jinými slovy jistá výhra je minimální možná výhra. Uveďme jednoduchý příklad. Předpokládejme, že vsadíme celých $3000$ korun (našich $2000$ plus $1000$ bonus) na výhru Kladna. V tomto případě je jistá výhra $0$ korun, které dostaneme pokud vyhraje Sparta nebo pokud bude remíza. Je očividné, že k tomu abychom zajistili nenulovou jistou výhru, musíme pokrýt nějakou částkou každý z možných výsledků daného utkání. První co nás napadne je vsadit $3000$ korun rovnoměrně na všechny události, tj. $3000/5=600$ korun na každou událost vypsanou sázkovou kanceláří. V tomto případě bude hodnota jisté výhry $600 \times (1.27+1.02) = 1374$ korun, které dostaneme pokud vyhraje Sparta (ověřte si, že ve všech ostatních případech bude výhra vyšší). Jak vidno ani tato sázka nevypadá optimálně, protože ve výsledku můžeme přijít o $2000-1374=626$ korun.

Naším cílem je nalézt optimální sázku, tj. optimální rozložení vložených $2000$ korun plus $1000$ korunový bonus na jednotlivé události, tak aby jistá výhra byla maximální. Pokud úlohu správně vyřešíte, uvidíte, že optimální sázka dokonce zaručí vyšší výhru než vložených $2000$ korun.

Zavedeme proměnné $x_1,\ldots,x_5$, které budou odpovídat množství peněz vsazených na danou událost. Jejich význam je v tabulce:

Musí být $x_1+x_{10}+x_0+x_{02}+x_2=3000$ (chceme prosázet přesně 3000 korun) a $x_1,\ldots,x_2\ge0$ (sázky nemohou být záporné). Z tabulek odvodíme, jaká bude hodnota výhry v závislosti na výsledku utkání:

Hodnota jisté (tj. minimální) výhry je tudíž rovna \[ f(x_1,x_{10},x_0,x_{02},x_2) = \min\{ 1.27 x_1 + 1.02 x_{10}, 1.02 x_{10} + 4.70 x_0 + 3.09 x_{02}, 3.09 x_{02} + 9 x_2 \}. \] Hledání optimální sázky pak můžeme vyjádřit jako maximalizaci hodnoty jisté výhry za daných omezení: \[ \begin{array}{rl} \max & f(x_1,x_{10},x_0,x_{02},x_2) \\ \text{za podmínek} & \begin{aligned}[t] x_1+x_{10}+x_0+x_{02}+x_2 &= 3000 \\ x_1,x_{10},x_0,x_{02},x_2 &\ge 0 \end{aligned} \end{array} \]

1. Převeďte zformulovanou úlohu na lineární program.
2. Napište funkci x=vyhra(c,k), kde složky vektoru $\_c=(c_1,c_{10},c_0,c_{02},c_2)\in\R_+^5$ jsou kursy na události podle tabulky výše (např. $c_1=1.27$), $k$ je množství peněz na prosázení (zde tedy $k=3000$), a $\_x=(x_1,x_{10},x_0,x_{02},x_2)\in\R_+^5$ je optimální rozdělení sázek. Pro kontrolu: hodnota jisté výhry má vyjít $2748.5\,$Kč.
3. Uvažujte modifikovanou úlohu, kdy sázková kancelář vypisuje kurzy jen na výhru domácích, remízu a výhru hostí, tj. jen a události 1, 0 a 2. Navíc kancelář stanovuje výši minimální sázky na každou událost na $400$ korun. Pro takto modifikovanou slovní úlohu formulujte úlohu LP, která opět nalezne strategii sázení maximalizující minimální výhru. Napište funkci x=vyhra2(c,k,m), kde $\_c=(c_1,c_0,c_2)$, $k$ je jako minule, $m$ je výše minimální sázky (zde $m=400$) a $\_x=(x_1,x_0,x_2)$.

Poznámka: Funkce budeme testovat nejen pro hodnoty $\_c,k$ příp. $m$ ze zadání, ale i pro jiné hodnoty.