IA102 Linear and Integer Optimization Tasks and their Solutions

Fakulta informatiky
jaro 2009
Rozsah
2/1. 3 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
St 9:00–11: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
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://www.fi.muni.cz/~hlineny/Teaching/OU/OU-text07.pdf.
  • 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
  • JANÁČEK, Jaroslav. Matematické Programování. Žilina, SK: EDIS Žilinská Univerzita, 2003. info
Metody hodnocení
This is an advanced course, taught mostly in English (with Czech materials), and conducted quite informally - with seminar-type lectures. Evaluation is by a written individual homework assignment (one), and a subsequent oral exam.
Vyučovací jazyk
Angličtina
Informace učitele
http://www.fi.muni.cz/~hlineny/Teaching/OU.html
Online course materials - main: P. Hliněný, Optimalizační úlohy, "http://www.fi.muni.cz/~hlineny/Teaching/OU/OU-text07.pdf" (in czech). Supplementary: R.J. Vanderbei, Linear Programming: Foundations and Extensions, "http://www.princeton.edu/~rvdb/LPbook/". A. Schrijver, A Course in Combinatorial Optimization. "http://homepages.cwi.nl/~lex/files/dict.pdf", CWI, Amsterdam. Sven O. Krumke, Course Materials, "http://optimierung.mathematik.uni-kl.de/~krumke/lecturenotes.html".
Students must read the course web page "http://www.fi.muni.cz/~hlineny/Teaching/OU.html" for information.
Další komentáře
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích podzim 2005, jaro 2007, jaro 2011.