Matematické programování a polyedrální kombinatorika, zimni semestr 2009/2010 (P. Kolman, M. Loebl)

Prednasky

1. přednáška  (8. 10. 2009)
Lineární programování v průniku P a NP. Úvod k elipsoidové metodě, hrubé porovnání se simplexovým algoritmem a metodou vnitřího bodu.
2. přednáška  (15. 10. 2009)
Pokracovani elip. met. - jak začít a jak udělat iterační krok v ideálním (snadném) případě.
3. přednáška  (22. 10. 2009)
pokracovani elip. met.
29. 10. 2009 - přednáška není 
4. přednáška  (5.11. 2009)
dokončení elip. metody. Úvod k metodě vnitřního bodu.
5.-8. přednáška  (12.11., 19.11., 26.11., 3.12. 2009)
Martin Loebl - optimalizace submodulární funkce, ...
9-10. přednáška  (10.12, 17.12. 2009)
metoda vnitrniho bodu, pokracovani (primarni, dualni krok, pokles potencialu)
11. přednáška  (7. 12. 2010)
Martin Loebl
12. přednáška  (14. 1. 2010)
metoda vnitrniho bodu - nalezeni vychoziho reseni; pouziti "nejkratsiho vektoru mrizky" pro zaokrouhlovani na konci metody vnitrniho bodu.

Zapocty

Vyreste aspon tri z prikladu v nasledujicim zadani. Reseni prosim piste na pocitaci.

Literatura


Přednáška v roce 2008/2009
Leden 2010