Požadavky ke zkoušce z EMM I a průběh zkoušky Písemná zkouška: Ke zkoušce je třeba si přinést vlastní papíry a 2 kancelářské sponky. Pro výpočty je možno použít pouze jednoduchou kalkulačku. I. část: 3 příklady s pomocí literatury (včetně zápisů přednášek a cvičení); doba trvání 105 minut. II. část: 4 otázky a 1 jednoduchý příklad bez pomoci literatury; doba trvání 35 minut (při počtu účastníků větším než 45 proběhne tato část postupně ve dvou skupinách). Typy úloh pro I. část 1. Tvorba modelu: Na základě slovního zadání zformulujte optimalizační model. Mohou se vyskytnout i nelineární funkce, podmínky celočíselnosti a bivalentní proměnné. Zadané veličiny mohou být vyjádřeny číselně nebo symbolicky. 2. Úloha LP: Danou úlohu převeďte ji do simplexové tabulky a řešte pomocí simplexové metody, přičemž u každé tabulky uveďte odpovídající bázické řešení. Na závěr charakterizujte, o jaký případ zakončení simplexové metody se jedná. 3. Úloha NLP: Pro danou úlohu zformulujte Kuhn-Tuckerovy podmínky a s jejich pomocí najděte řešení. Prověřte, zda jsou splněny dostatečné podmínky optimality a charakterizujte získané řešení. Okruhy otázek a příkladů pro II. část 1. Úvod do operačního výzkumu. Formulace a vlastnosti úloh LP. 2. Simplexová metoda. Dualita a analýza citlivosti. 3. Nelineární a celočíselné programování. 4. Úlohy síťové optimalizace. Složité rozhodovací úlohy. 5. Příklad z kterékoli z předchozích oblastí. Hodnocení písemné zkoušky Za každý příklad I. části maximálně 15 bodů Za každou otázku či příklad II. části maximálně 5 bodů Celkem maximálně 70 bodů Celkové hodnocení Do celkového hodnocení se dále započítávají body získané za semestrální projekt a průběžné testy (celkem maximálně 30 bodů). Body 100 ­ 91 90 ­ 81 80 ­ 71 70 ­ 61 60 ­ 50 49 ­ 0 Klasifikace A B C D E F Tato tabulka má pomocný charakter a klasifikace může být upřesněna na základě ústní zkoušky. Ústní zkouška K ústní zkoušce nedojde, když počet bodů za písemku bude menší než 35, nebo když tento počet bude sice větší nebo roven 35, ale počet bodů za druhou část bude menší než 10. V takových případech bude celkový výsledek zkoušky F. Ústní zkouška bude moci být prominuta, když výsledek písemky bude jednoznačně příznivě klasifikovatelný, tj. když počet bodů za každou část písemky bude větší než poloviční, nebudou se vyskytovat výpadky odpovědí ve II. části písemky, nebude podezření z opisování a celkové hodnocení se nebude nacházet na hranici mezi dvěma klasifikačními stupni. O výsledku hodnocení písemky budou studenti informováni v poznámkovém bloku nebo mailem. Tato informace bude k dispozici nejpozději do týdne po konání písemky (při počtu účastníků menším než 90 to bude přiměřeně dříve). V případě nutnosti ústní zkoušky bude možno se dostavit na některý z vypsaných zkušebních termínů. Bude možná i domluva na jiný termín. Otázky ke II. části písemné zkoušky Úvod do operačního výzkumu 1. Popište proces operačního výzkumu a uveďte typy rozhodovacích situací. 2. Na zvoleném příkladě popište strukturu optimalizačního modelu. Formulace a vlastnosti úloh lineárního programování 3. Napište definici báze. Ilustrujte na příkladě. Jaký je maximální počet různých bází? 4. Jak se zjistí bázické řešení odpovídající dané bázi B? Ilustrujte na příkladě. Jaký je geometrický význam bázického řešení? 5. Jak zní základní věta LP a co je jejím důsledkem? Simplexová metoda 6. Stručně popište dvoufázovou simplexovou metodu. 7. Jaké jsou možné případy zakončení simplexové metody? Ilustrujte graficky. Jak se tyto případy poznají v simplexové tabulce? Dualita a analýza citlivosti 8. Napište definici dvojice symetricky duálně sdružených úloh a uveďte konkrétní příklad takové dvojice. 9. Napište slabou a silnou větu o dualitě. Jaké jsou důsledky těchto vět? 10. Napište větu o komplementaritě. Na jejím základě odpovězte na otázku, jaká bude v úloze optimalizace výrobního programu optimální hodnota duální proměnné, když odpovídající zdroj nebude plně využit? 11. Co je cílem analýzy citlivosti a jaké úlohy se zde řeší? Jaký je význam duálních proměnných z hlediska analýzy citlivosti? Nelineární programování 12. Napište definice konvexní funkce a konvexní množiny a nakreslete příklady. Jaký je význam konvexnosti pro řešení úloh NLP? 13. Zvolte si nějakou nelineární funkci více proměnných a určete její gradient. Jaké jsou vlastnosti gradientu? 14. Zvolte si nějakou nelineární funkci více proměnných a určete Hessovu matici této funkce. K čemu používáme Hessovu matici? Ilustrujte to na zvolené funkci. 15. Charakterizujte obecný princip vícerozměrných metod hledání volných extrémů funkce více proměnných. Dále stručně charakterizujte možné způsoby určení směru přechodu k dalšímu řešení? 16. Charakterizujte typy metod pro hledání vázaných extrémů funkce více proměnných. Celočíselné programování 17. Charakterizujte princip metody sečných nadrovin. 18. Charakterizujte princip metody větví a mezí a uveďte příklady způsobů větvení a omezování. Úlohy síťové optimalizace 19. Napište definici orientovaného grafu a nakreslete příklad. Jaké znáte typy grafů? Uveďte příklady aplikací. 20. Jak je definován tok od zdroje ke spotřebiči? Ilustrujte na příkladě. Charakterizujte možné způsoby nalezení maximálního toku (stačí slovně). 21. Vysvětlete pojmy cesta a vzdálenost v orientovaném hranově ohodnoceném grafu. Ilustrujte na příkladě. Charakterizujte možné způsoby nalezení nejkratší cesty (stačí slovně). Složité rozhodovací úlohy 22. Charakterizujte úlohu stochastického programování a uveďte příklady aplikací. Jaké jsou možnosti vytvoření deterministického ekvivalentu této úlohy?. 23. Charakterizujte úlohy vícekriteriálního rozhodování a uveďte příklady aplikací. Popište možnosti řešení těchto úloh. 24. Napište definici hry v normálním tvaru a definici maticové hry. Uveďte příklady aplikací teorie her. Na příkladě ilustrujte možnost řešení maticové hry. Příklady ke II. části písemné zkoušky Formulace a vlastnosti úloh lineárního programování 1. Je dána matice A typu (2, n). Určete všechny báze. 2. Je dána soustava dvou lineárních rovnic a báze B. Zjistěte odpovídající bázické řešení. 3. Je dána úloha LP se 2 proměnnými. Graficky určete optimální řešení. Simplexová metoda a dualita 4. Je dána simplexová tabulka odpovídající optimálnímu řešení s příznakem existence dalších optimálních řešení. Určete všechna optimální bázická řešení. 5. Je dána jedna z dvojice symetricky duálně sdružených úloh. Zkonstruujte k ní úlohu duální. Nelineární programování 6. Je dána nelineární funkce f(x) více proměnných a bod x0. Určete směry, v nichž funkce f(x) v bodě x0 nejrychleji roste a klesá. 7. Je dána nelineární funkce dvou proměnných ve tvaru polynomu 3. stupně. Určete obor, ve kterém je daná funkce konvexní. 8. Je dána úloha NLP. Zjistěte, zda se jedná o úlohu konvexního programování. Síťové a složité rozhodovací úlohy 9. Jsou zadány veličiny dopravní úlohy (vektory a, b a matice C). Sestavte matematický model. 10. Je dána úloha stochastického LP, kde koeficienty v účelové funkci jsou navzájem nezávislé náhodné veličiny se zadanými středními hodnotami a rozptyly. Sestavte možné deterministické ekvivalenty dané úlohy. 11. Je dána úloha dvoukriteriálního LP. Dále jsou dány minimální a maximální hodnoty obou účelových funkcí a případně také jejich váhy. Sestavte možné jednokriteriální úlohy. 12. Úloha vícekriteriálního hodnocení variant je zadána kriteriální maticí a případně také vahami jednotlivých kritérií. Určete bazální variantu, ideální variantu, nedominované varianty a pomocí nějaké jednoduché metody vyberte kompromisní variantu.