\[
\def\_#1{\mathbf{#1}}
\def\R{\mathbb{R}}
\]
===== Jistá výhra =====
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:
^ událost | 1 | 10 | 0 | 02 | 2 |
^ kurz | 1.27 | 1.02 | 4.70 | 3.09 | 9.00 |
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.
==== Formalizace slovního zadání úlohy ====
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:
^ událost | 1 | 10 | 0 | 02 | 2 |
^ vložené peníze [Kč] | $x_1$ | $x_{10}$ | $x_0$ | $x_{02}$ | $x_2$ |
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í:
^ výsledek | výhra domácích |remíza | výhra hostů |
^ hodnota výhry [Kč] | $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$ |
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}
\]
==== Úkoly k vypracování ====
- Převeďte zformulovanou úlohu na lineární program.
- 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č.
- 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.
=== Příklady I/O ===
Pro python:
import numpy as np
c = np.array([1.27, 1.02, 4.70, 3.09, 9.00])
k = 3000
x = vyhra(c,k)
# x = array([3.40905816e-06, 2.69461077e+03, 9.28004584e-07, 1.68174891e-08, 3.05389222e+02]) or
# x = [3.40905816e-06, 2.69461077e+03, 9.28004584e-07, 1.68174891e-08, 3.05389222e+02] etc.
c = np.array([1.27, 4.70, 9.00])
k = 3000
m = 400
x = vyhra2(c,k,m)
# x = array([2046.90108498, 553.09881711, 400.00004477]) or
# x = [2046.90108498, 553.09881711, 400.00004477] etc.
Pro matlab:
c = [1.27, 1.02, 4.70, 3.09, 9.00];
k = 3000;
x = vyhra(c,k)
% x = [0.0000e+00 2.6946e+03 0.0000e+00 1.1772e-13 3.0539e+02]' or
% x = [0.0000e+00 2.6946e+03 0.0000e+00 1.1772e-13 3.0539e+02]
c = [1.27, 4.70, 9.00];
k = 3000;
m = 400;
x = vyhra2(c,k,m)
% x = [2046.90 553.10 400.00]' or
% x = [2046.90 553.10 400.00]