456-0340/01 – Optimalizační úlohy (OU)
| Garantující katedra | Katedra informatiky | Kredity | 4 |
| Garant předmětu | doc. RNDr. Petr Hliněný, Ph.D. | Garant verze předmětu | doc. RNDr. Petr Hliněný, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | povinně volitelný |
| Ročník | 2 | Semestr | letní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2003/2004 | Rok zrušení | 2005/2006 |
| Určeno pro fakulty | FEI | Určeno pro typy studia | magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Cílem předmětu je poskytnout studentům základní přehled kombinatorických, lineárních a celočíselných optimalizačních úloh, včetně běžných metod jejich řešení a vysvětlení.
Na přednáškách budou vysvětleny matematické principy využívané při řešení těchto optimalizačních úloh a na cvičeních bude látka doplněna ukázkami prakticky motivovaných úloh a použití optimalizačního softwaru.
Vyučovací metody
Anotace
Studenti se seznámí s běžnými typy optimalizačních úloh (kombinatorické, lineární a celočíselné optimalizace) a naučí se některé základní metody jejich řešení. Důraz bude kladen především na vysvětlení a pochopení simplexové metody pro lineární optimalizaci a metody větvení a mezí pro celočíselnou optimalizaci. Zmíněny budou také některé jiné specifické problémy jako třeba toky v sítích nebo problémy rozvrhování a obchodního cestujícího.
Jedná se o přehledový předmět. Na přednáškách budou vysvětleny matematické principy využívané při řešení těchto optimalizačních úloh a na cvičeních bude látka doplněna ukázkami prakticky motivovaných úloh a použití optimalizačního softwaru.
Povinná literatura:
Jaroslav Janáček: Matematické Programování.
EDIS Žilinská Univerzita, 2003.
Petr Hliněný, Optimalizační úlohy, http://www.cs/hlineny/vyuka/OU-slides/, 2005.
Doporučená literatura:
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Podmínky udělení zápočtu:
Podmínkou zápočtu je aktivní účast na alespoň polovině cvičení
a úspěšné vyřešení tam zadaných praktických optimalizačních úloh.
E-learning
Další požadavky na studenta
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
Hladový algoritmus a jeho použití v příkladech.
Toky v sítích: formulace a použití. Dualita toků a řezů.
Úloha lineární optimalizace: formulace a aplikace.
Konvexita a dualita v lineární optimalizaci.
Vysvětlení simplexové metody pro řešení lineární optimalizace.
Implementace simplexové metody, umělé proměnné.
Degenerované úlohy, prevence zacyklení a délka výpočtu.
Další aplikace: toky, dopravní úloha a maticové hry.
Úloha celočíselné nebo diskrétní optimalizace.
Obecné vysvětlení metody větvení a mezí, relaxace úlohy.
Implementace metody větvení a mezí.
Specifické varianty úlohy: rozvrhování a obchodní cestující.
Cvičení:
Na cvičeních se prakticky řeší zadané optimalizační úlohy, většinou za pomoci výpočetní techniky.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.