|
Vyučující
|
-
Ženčák Pavel, RNDr. Ph.D.
-
Vodák Rostislav, doc. 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
|
|
Výstupy z učení
|
Cílem 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.
KMA/DM a zároveň KAG/LA1A a zároveň KMI/ALGO1
|
|
Hodnoticí metody a kritéria
|
Známkou, Ústní zkouška, Analýza výkonů studenta, Seminární práce
Ústní zkouška. K získání zápočtu je nutná aktivní účast na cvičení, vypracovat seminární práci a úspěšné zvládnout zápočtové písemky.
|
|
Doporučená literatura
|
-
Applegate, D. L., Bixby, R. E., Chvátal, V., Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study.
-
Du, D. Z., Pardalos, P. M., Hu, X., Wu. (2022). Introduction to combinatorial optimization. Springer Optimization and Its Applications. Cham, Switzerland.
-
Korte, B., Vygen, J. (2018). Combinatorial Optimization. Theory and Algorithms. 6th edition. Springer.
-
Papadimitriou, Ch. H.,? Steiglitz K. (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications.
-
Pinar, M. Ç., Akkaya, D. (2023). Problems and Solutions for Integer and Combinatorial Optimization: Building Skills in Discrete Optimization. SIAM.
|