|
Vyučující
|
-
Ženčák Pavel, RNDr. Ph.D.
|
|
Obsah předmětu
|
1. Úloha lineárního programování a simplexová metoda. 2. Princip duality v lineárním programování. 3. Duální simplexová metoda, metody celočíselného programování. 4. Dopravní úloha: formulace problému a metody řešení. 5. Přiřazovací problém: formulace problému a metody řešení. 6. Toky v sítích: hledání minimálního a maximálního toku. 7. Problém obchodního cestujícího (jako ukázková úloha): exaktní metody řešení. 8. Heuristiky a meta-heuristiky: genetické algoritmy, simulované žíhání, tabu search, mravenčí kolonie. 9. Další aplikace kombinatorické optimalizace.
|
|
Studijní aktivity a metody výuky
|
Monologická (výklad, přednáška, instruktáž), Demonstrace
- Účast na výuce
- 52 hodin za semestr
- Semestrální práce
- 50 hodin za semestr
- Domácí příprava na výuku
- 40 hodin za semestr
|
|
Výstupy z učení
|
Smyslem předmětu je doplnit porozumění klasické (spojité) optimalizaci znalostmi z optimalizace diskrétní a seznámit studenty s moderními metodami řešení takových úloh. Hlubší porozumění daným metodám bude následovat v navazujícím studiu.
Porozumění Porozumět základním problémům diskrétní optimalizace a různým přístupům k jejich řešení.
|
|
Předpoklady
|
Základní znalosti numerických metod a klasických optimalizačních metod.
|
|
Hodnoticí metody a kritéria
|
Analýza výkonů studenta, Seminární práce
Kolokvium: zpracování vybraného problému jednou z metod kombinatorické optimalizace, obhajoba formou prezentace.
|
|
Doporučená literatura
|
-
Online přednáška.
-
Online přednáška.
-
Alexander Schrijver. A Course in Combinatorial Optimization.
-
Bernhard Korte, Jens Vygen. (2018). Combinatorial Optimization Theory and Algorithms (6th ed.). Springer.
-
David L. Applegate, Robert E. Bixby, Vašek Chvátal, William J. Cook. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.
-
Christos H. Papadimitriou,? Kenneth Steiglitz. (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications.
|