IA102 Úlohy lineární a celočíselné optimalizace a jejich řešení

Fakulta informatiky
podzim 2005
Rozsah
2/2. 4 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
Vyučující
prof. RNDr. Petr Hliněný, Ph.D. (přednášející)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Petr Hliněný, Ph.D.
Rozvrh
Čt 10:00–11:50 B411 a každý lichý čtvrtek 14:00–15:50 B116 a každý sudý čtvrtek 14:00–15:50 B411
Předpoklady
Matematické znalosti na úrovni základních kurzů lineární algebry (vektory, matice, lineární rovnice) a diskrétní matematiky (relace, grafy). Vítány jsou i úvodní znalosti topologie.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 50 stud.
Momentální stav registrace a zápisu: zapsáno: 0/50, pouze zareg.: 0/50, pouze zareg. s předností (mateřské obory): 0/50
Mateřské obory/plány
předmět má 7 mateřských oborů, zobrazit
Cíle předmětu
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.
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. (V žádném případě nebude náplní bezduché memorování různých postupů simplexové metody.)
Osnova
  • Kombinatorická optimalizace: 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 mnohostěny v lineární optimalizaci.
  • Dualita úloh v lineární optimalizaci.
  • Vysvětlení principů 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.
  • Úlohy celočíselné optimalizace: formulace a příklady.
  • Obecné vysvětlení metody větvení a mezí, relaxace úlohy.
  • Kombinatorické optimalizační problémy.
  • Umění formulace úloh celočíselné optimalizace.
  • Pokročilá diskrétní optimalizace.
Literatura
  • P. Hliněný, Optimalizační úlohy, http://is.muni.cz/el/1433/podzim2005/IA102/um/OU-text05.pdf, 2005.
  • JANÁČEK, Jaroslav. Matematické Programování. Žilina, SK: EDIS Žilinská Univerzita, 2003. info
  • NEMHAUSER, George L. a Laurence A. WOLSEY. Integer and combinatorial oprimization. New York: John Wiley & Sons, 1988, 763 s. ISBN 0-471-82819-X. info
  • A. Schrijver, A Course in Combinatorial Optimization. http://homepages.cwi.nl/~lex/files/dict.pdf, CWI, Amsterdam.
Metody hodnocení
Samostatné domácí písemné projekty v průběhu semestru. Závěrečná písemná a navazující ústní zkouška.
Vyučovací jazyk
Angličtina
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2007, jaro 2009, jaro 2011.