LS 2023, Jiří Sgall, úterý 9:00, S4
Kontakt a konzultace
Konzultace nejlépe po předběžné domluvě mailem.
E-mail: last name at iuuk.mff.cuni.cz
Telefon: 951 554 293, 608 035 102
https://iuuk.mff.cuni.cz/~sgall/
Pracovna: 3. patro, místnost 307, Malostranské nám. 25
Cvičení mají vlastní stránky,
vede je Martin Balko.
Zkoušky
V září je vypsaný termín na 18.9. V létě se můžeme případně
domluvit individuálně koncem července nebo v druhé půlce srpna.
Literatura a další pomůcky
Poznámky k přednášce v tuto chvíli bohužel nejsou dopsané ale
poslouží k přehledu první části přednášky, která je dobře pokryta
dvojími skripty J. Matouška Lineární programování a lineární
algebra pro informatiky a Introduction to Discrete
Geometry. Pro druhou část použijte nejlépe poznámky z r.
2010; algoritmy pro párování jsou dobře pokryty v knize Cook
et al: Combinatorial Optimization, která je v informatické
knihovně.
Probraná témata
- 1. (14. 2.)
- optimalizační problémy
- příklad: maticové hry
- úloha lineárního programování
- převedení rovnic na nerovnice atd.
- úloha celočíselného programování
- příklad: hledání nejkratší cesty, dvě formulace (primární a
duální)
- příklad: dopravní problém
- 2. (21. 2.)
- opakování: afinní prostory, obal, kombinace, nezávislost
- definice: dimenze
- definice: konvexní množina, konvexní obal, konvexní
kombinace
- konvexní obal X je množina všech konvexních kombinací bodů z
X
- věta (Caratheodory): bod konvexního obalu X je konvexní
kombinací kombinací nejvýše d+1 bodů z X, kde d je dimenze X
- 3. (28. 2.)
- definice: nadrovina, poloprostor
- definice: konvexní mnohostěn jako průnik poloprostorů
- terminologie: omezený konvexní mnohostěn
- věta o oddělování konvexních množin nadrovinou
- věta Minkowski-Weyl: X je omezený konvexní mnohostěn
právě když X je konvexní obal konečné množiny bodů
- 4. (7. 3.)
- definice: stěna mnohostěnu, vrchol, faseta
- věta: omezený mnohostěn je konvexní obal vrcholů, vrcholy
jsou právě extremální body
- věta: stěna stěny je stěna
- 5. (14. 3.)
- minimální popis mnohostěnu
- věta: dimenze polytopu je dána hodností systému rovnic v
minimálním popisu
- věta: v minimálním popisu polytopu nerovnosti vzájemně
jednoznačně odpovídají fasetám
- stěna jako průnik faset
- svaz stěn mnohostěnu - neprobráno
- 6. (21. 3.)
- simplexová metoda
- příklad
- bázické řešení
- pivotovací krok
- ukončení (optimum, neomezenost)
- degenerovanost
- pivotovací pravidla
- efektivnost, zacyklení
- 7. (28. 3.)
- simplexová metoda
- nalezení počátečního řešení dvoufázovou metodou
- výpočetní složitost
- elipsoidová metoda, stručný popis, separační
orákulum, výpočetní složitost
- metody vnitřního bodu
- dualita: příklad
- 8. (4. 4.)
- Farkasovo lemma pro nerovnice pomocí Fourier-Motzkinovy eliminace
- Farkasovo lemma pro rovnice
- věta o odvozování libovolné platné nerovnosti, která je
důsledkem soustavy nerovností
- dualita: důkaz z Farkasova lemmatu
- 9. (11. 4.)
- dualita: obecný případ, speciální LP, kuchařka
- dualita: podmínky komplementarity
- perfektní párování minimální ceny v bipartitním grafu
pomocí primárně duálního algoritmu
algoritmus
- 10. (18. 4.)
- párování v obecných grafech
- párování maximální velikosti
- perfektní párování minimální ceny (Edmonsův
kvítkový/blossom algoritmus)
- 11. (25. 4.)
- polytop perfektních párování, definice a souvislost s
řezy, celočíselnost
- polytop zlomkových párování, jeho poloceločíselnost
- stěny polytopu párování
- 11. (2. 5.)
- totálně unimodulární matice
- definice, důsledky pro LP
- totálně unimodulární matice se dvěma nenulovými prvky ve
sloupci
- toky a řezy: unimodularita, dualita a její důsledky
- Königova věta: dualita maximálního párování a
minimálního vrcholové pokrytí v bipartitním grafu
- aproximační algoritmy
- 2-aproximační algoritmus pro vrcholové pokrytí
- 12. (9. 5.)
- matroidy
- definice, charakterizace množiny bází
- příklady: vektorové prostory, lesy
- řádová funkce (rank) - definice a vlastnosti
- hladový algoritmus
- polytop matroidu a průniku dvou matroidů, jejich
celočíselnost
- 13. (16. 5.)
- kužely: formulace Minkowski-Weylovy věty pro
neomezené mnohostěny, geometrický důkaz duality
- metoda řezů (sečných nadrovin, cutting plane
methods)
- platný řez, příklady
- věta o univerzalitě: lze odvodit každou nerovnost
platnou pro všechna celočíselná řešení
- přehled metod celočíselného programování
- neprobraná témata
- příklad: perfektní párování minimální ceny, důkaz existence
celočíselného řešení
Probraná témata z předchozího běhu v r. 2018 (s nahrávkou)
- 1. (19. 2.)
- historie optimalizace, optimalizační problémy
- příklad: maticové hry
- úloha lineárního programování
- převedení rovnic na nerovnice atd.
- úloha celočíselného programování
- příklad: hledání nejkratší cesty, dvě formulace (primární a
duální)
- 2. (26. 2.)
- příklad: perfektní párování minimální ceny, důkaz existence
celočíselného řešení
- opakování: afinní prostory, obal, kombinace, nezávislost
- definice: dimenze
- definice: konvexní množina, konvexní obal, konvexní
kombinace
- konvexní obal X je množina všech konvexních kombinací bodů z
X
- 3. (12. 3.)
- věta (Caratheodory): bod konvexního obalu X je konvexní
kombinací kombinací nejvýše d+1 bodů z X, kde d je dimenze X
- definice: nadrovina, poloprostor
- definice: konvexní mnohostěn jako průnik poloprostorů
- terminologie: omezený konvexní mnohostěn
- věta o oddělování konvexních množin nadrovinou
- věta Minkowski-Weyl: X je omezený konvexní mnohostěn
právě když X je konvexní obal konečné množiny bodů
- 4. (19. 3.)
- definice: stěna mnohostěnu, vrchol, faseta
- věta: omezený mnohostěn je konvexní obal vrcholů, vrcholy
jsou právě extremální body
- věta: stěna stěny je stěna
- 5. (26. 3.)
- minimální popis mnohostěnu
- věta: dimenze polytopu je dána hodností systému rovnic v
minimálním popisu
- věta: v minimálním popisu polytopu nerovnosti vzájemně
jednoznačně odpovídají fasetám
- stěna jako průnik faset
- svaz stěn mnohostěnu
- 6. (9. 4.)
- simplexová metoda
- příklad
- bázické řešení
- pivotovací krok
- ukončení (optimum, neomezenost)
- degenerovanost
- pivotovací pravidla
- efektivnost, zacyklení
- 7. (16. 4.)
- simplexová metoda
- nalezení počátečního řešení dvoufázovou metodou
- výpočetní složitost
- elipsoidová metoda, stručný popis, separační
orákulum, výpočetní složitost
- metody vnitřního bodu
- dualita: příklad
- Farkasovo lemma pro nerovnice pomocí Fourier-Motzkinovy eliminace
- 8. (23. 4.)
- Farkasovo lemma pro rovnice
- věta o odvozování libovolné platné nerovnosti, která je
důsledkem soustavy nerovností
- dualita: znění pro různé tvary LP, rovnicový tvar
apod.
- dualita: důkaz z Farkasova lemmatu
- 9. (30. 4.)
- dualita: podmínky komplementarity
- perfektní párování minimální ceny v bipartitním grafu
pomocí primárně duálního algoritmu
algoritmus
- 10. (7. 5.)
- párování v obecných grafech
- párování maximální velikosti
- perfektní párování minimální ceny (Edmonsův
kvítkový/blossom algoritmus)
- 11. (14. 5.)
- totálně unimodulární matice
- definice, důsledky pro LP
- totálně unimodulární matice se dvěma nenulovými prvky ve
sloupci
- toky a řezy: unimodularita, dualita a její důsledky
- Königova věta: dualita maximálního párování a
minimálního vrcholové pokrytí v bipartitním grafu
- 12. (21. 5.)
- matroidy
- definice, charakterizace množiny bází
- příklady: vektorové prostory, lesy
- řádová funkce (rank) - definice a vlastnosti
- hladový algoritmus
- polytop matroidu a průniku dvou matroidů, jejich
celočíselnost
- 13. (28. 5.)
- kužely: formulace Minkowski-Weylovy věty pro
neomezené mnohostěny, geometrický důkaz duality
- metoda řezů (sečných nadrovin, cutting plane
methods)
- platný řez, příklady
- věta o univerzalitě: lze odvodit každou nerovnost
platnou pro všechna celočíselná řešení
- přehled metod celočíselného programování
- neprobraná témata
- polytop párování, definice a souvislost s algoritmem,
celočíselnost
- aproximační algoritmy
- 2-aproximační algoritmus pro vrcholové pokrytí