Algoritmická teorie her: cvičení

bude oznámeno, když cviko odpadne

• 4 sady domácích úkolů, v každé 3–4 příklady
• celkem 36 bodů, z nich potřebujeme 18 na zápočet
• zápočtový test byl zrušen
• všichni musejí na zkoušku, ale zkoušející bude přihlížet k vyššímu počtu bodů z příkladů
• odevzdávání přes Sovu
• deadline vždycky za 2 týdny
• čím dřív odevzdáme, tím je větší šance, že dostaneme zpětnou vazbu včas a budeme si moct řešení opravit

• podmínka $p_i:a_{i1}x_1+a_{i2}x_2+\dots+a_{im}x_m\leq b_i$
• řešení … $x=(x_1,\dots,x_m)\in\mathbb R^m$
• maximalizujeme účelovou funkci $c_1x_1+c_2x_2+\dots+c_mx_m$

• účelová funkce roste ve směru vektoru $c$
• nadrovina kolmá na $c$ určuje řešení se stejnou hodnotou účelové funkce
• „zametáme“ nadrovinou, najdeme optimální řešení $x^*$
• pozorování: aspoň jedno optimální řešení se nachází ve vrcholu mnohostěnu

• lineární program nemá řešení – průnik (mnohostěn) je prázdný
• má řešení, ale není omezené
• má maximální řešení

• začne v nějakém vrcholu, pak cestuje po hraně dokud nedojde do dalšího vrcholu
• podle pivotovacího pravidla si vybírá další směr
• simplexová metoda může běžet až exponenciálně
  • ale průměrně je velmi rychlá
  • jsou i polynomiální způsoby řešení

• řešení se nacházejí na celočíselné mřížce uvnitř mnohostěnu
• tento problém je NP těžký