Cvičení z Optimalizačních metod v LS 16/17 (pátek 10:40, S6)
K přednášce Optimalizační metody prof. Martin Loebla vedu cvičení, které se koná v pátek od 10:40 v S6.
Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po cvičení. Také budu rád, když se v průběhu cvičení budete ptát, jakmile vám nebude něco jasné.
Chcete-li konzultaci, ozvěte se mi emailem. Budu dostupný od 21.8. do 1.9., poté 14.-15.9. a poslední týden v září, jinak jsem pryč.
23.5. přibyly testovací vstupy k 2. praktickému úkolu (viz níže).
Co jsme dělali
| 24. 2. | Úvod k LPčkům a příklady na formulace lineárních programů. |
| 3. 3. | Příklady na formulace lineárních a celočíselných programů (poslední doděláme příště). Důkaz, že lineární relaxace CLP na minimální vážené perfektní párování v bipartitním grafu má celočíselné optimum. |
| 10. 3. | První opáčko a dokončení příkladu s obchodním cestujících z minula. Geometrie: opakování lineárních / afinních / konvexních pojmů, příklady na afinní prostory (poslední si můžete rozmyslet přes týden :-). |
| 17. 3. | Příklady na geometrickou intuici okolo afinních prostorů a mnohostěny a jejich stěny (skončili jsme u 4.a), zbytek příště). |
| 24. 3. | Zmínka o minimálním popisu mnohostěnu (viz skripta prof. Sgalla). Příklady na mnohostěny z minula i pár dalších. 5. domácí úkol, zadání upřesněno 3.4. |
| 31. 3. | Rovnicový tvar LP a úvod do simplexové metody. Příklady, včetně DÚ. |
| 7. 4. | Simplexová metoda: pokračování, hledání počátečního přípustného bázického řešení, speciální případy (neomezenost, nepřípustnost, degenerovanost, zacyklení), pivotovací pravidla. Příklady (nestihli jsme poslední dva). |
| 14. 4. | Státní svátek Velký pátek |
| 21. 4. | Malá písemka na simplexovou metodu, příklady na dualitu, poslední doděláme příště. Domácí úkol (deadline 5.5. do začátku cvičení). |
| 28. 4. | Dva duální programy na nejkratší cestu a příklady na totální unimodularitu. Domácí úkol (deadline 19.5. do začátku cvičení). |
| 5. 5. | Cvičení na dualitu a Farkasovo lemma v různých verzích. Příklady (poslední si můžete zkusit doma, není těžký). |
| 12. 5. | Malá písemka na dualizaci hledání maximálního toku, příklady na totální unimodularitu. Aplikace: jsou-li kapacity celočíselné, existuje celočíselný maximální tok. |
| 19. 5. | Velká písemka na celé cvičení. |
| 26. 5. | Řešení dvou příkladů z písemky (cesta délky k, geometrie) a komplementarita. Příklady, včetně posledního domácího úkolu (do 27. června). |
Praktické domácí úkoly
Než začnete, projděte si obecné informace k praktickým úkolům a návod k jazyku MathProg od Martina Böhma.- 1. úkol: šéfova kancelář – deadline 24. dubna, vzorové vstupy a vzorové vstupy.
- 2. úkol: rozvrhování úkolů – deadline 26. června 10:00, vzorové vstupy.
Studijní materiály
V češtině:- Lineární programování pro informatiky (Jiří Matoušek, 2006) – dostupné v knihovně MFF UK (jako Lineární programování a lineární algebra pro informatiky) a také na webu. Dobře popsán úvod (včetně příkladů LP), simplexová metodaa dualita
- Poznámky z přednášky prof. Sgalla. Doporučuji jako zdroj pro geometrii (konvexní množiny a mnohostěny), dualitu a perfektní bipartitní párování minimální ceny, ostatní části jsou v rozpracovaném stavu. Navíc se obsah letošní přednášky může trochu lišit, obzvláště na konci semestru.
- Další zdroje na stránkách loňské přednášky
- Slidy z prvních pár přednášek
- Skriptíčka na stránkách letošní přednášky
- Slidy z anglické přednášky
- Understanding and Using Linear Programming (Jiří Matoušek, Bernd Gärtner). An introductory book to Linear Programming for computer scientists which covers a large part of the lecture. Very accessible and readable. Contains applications, but no exercises.
- Linear programming, A Concise Introduction (Thomas S. Ferguson). A writeup of a lecture with a similar linear programming content, but missing other combinatorial optimization topics.
- Combinatorial Optimization: Polyhedra and Efficiency (Alexander Schrijver). A series of three textbooks containing almost everything one needs to know from combinatorial optimization. A bit dense in some places, but it is readable.
- Introduction to Discrete Geometry and Lectures on Discrete Geometry (Jiří Matoušek). The first link are lecture notes from a discrete geometry class, available for borrowing at the Faculty of Math and Physics library. The second book is a normal book on the same subject. You do not need to read the whole book; the essential parts are the lectures on convexity and on convex polytopes.
Související předmět: Pokročilý seminář z optimalizačních metod od Jirky Finka. Pro ty, kdo se chtějí dozvědět více o řešeních optimalizačních úloh, ať už pomocí teoretických nástrojů (lineární a celočíselné programování) nebo praktických nástrojů. Lze zapsat spolu s Optimalizačními metodami.
Cvičení z let minulých:- LS 2016: Pavel Veselý, Tomáš Masařík, Radek Hušek
- LS 2015: Martin Böhm, Tomáš Masařík, Radek Hušek
- LS 2014: Martin Böhm, Marek Eliáš,
- LS 2012: Dušan Knop, Marek Eliáš, Vojta Tůma
- LS 2011: Dušan Knop, Marek Krčál
- LS 2010: Marek Krčál
Zápočet
Všechna česká cvičení mají velmi podobné podmínky na zápočet. Zápočet dostanete, když získáte celkem alespoň 40 bodů, z čehož alespoň 4 musí být za praktické domácí úkoly. Body můžete získat těmito způsoby:- aktivita na cvičení: 1 až 2 body za kompletně předvedený příklad (za část řešení také něco bude),
- 3-krát za semestr: 15-minutové opáčko (malá písemka), celkově všechna za 15 bodů,
- jedna velká písemka za 25 bodů,
- dva praktické domácí úkoly dohromady za 20 bodů,
- teoretické domácí úkoly celkem alespoň za 20 bodů.
Aktivita: pokud by vám přišlo, že jste měli během cvičení dostat nějaké body a já to přehlédl nebo zapomněl, ozvěte se emailem či po cvičení.
Opáčko je opakování látky z posledních dvou až třech cvičení a přednášek formou minipísemky s jedním či dvěma příklady. Bude probíhat 3-krát za semestr, vždycky prvních 15 minut cvičení. Opáčka jsou dobrovolná a nejsou přepadová; tj. týden dopředu vyvěsím na web, jestli se příští cvičení bude konat.
Písemka je 90-minutový klasický test. Bude se konat 19. května. Písemka také není povinná, silně však doporučujeme na ni přijít. Pokud se nebudete moci na písemku dostavit a chtěli byste si ji napsat, kontaktujte mne co nejdříve předem emailem či po cvičení.
Praktické domácí úkoly budou programovací. Za úkol bude vyřešit daný problém pomocí lineárního programování – tedy napsat program/skript, který zadanou úlohu vyřeší a vypíše výsledek. Na domácí úkoly bude vždy alespoň měsíc času a odevzdávají se emailem.
Teoretické domácí úkoly budou zadávány průběžně, většinou formou drobnějších příkladů po cca 2 bodech. Na jejich řešení můžete spolupracovat, důležité ale je, abyste řešení důkladně rozuměli a sami ho sepsali. Na teoretické úkoly bude 14 dní času, přesněji do začátku cvičení 14 dní od zadání. Naleznete je v PDF se zadáním. Odevzdávejte je nejlépe elektronicky (ve formátu PDF, ODT, ... nebo i jen jako text emailu) nebo na papíře na začátku cvičení. Nafocené či naskenované papíry mi posílejte jen v případě nouze (nemoc, během zkouškového apod.).
Obecně: Všechny kroky se snažte pečlivě zdůvodňovat, je to důležitější než mít správný výsledek. Naopak můžete používat cokoli z přednášek či cvičení bez důkazu, jen vždy uveďte, co právě využíváte. Bodové hodnocení jednotlivých příkladů nemusí vždy nutně odpovídat jejich obtížnosti.
Všimněte si, že je mnoho způsobů, jak získat 40 bodů; vyberte si tu cestu, která vám vyhovuje nejvíce.
Tabulka výsledků
V tabulce jsou zobrazeny inicály (v obráceném pořadí, tj. PM pro studenta Příjmení Jméno), ale můžete si zvolit přezdívku. Vysvětlivky: pduX = X. praktický domácí úkol, tduX = X. teoretický domácí úkol, oX = body z X. opáčka (malé písemky). Počet teoretických úkolů se ještě může změnit a počty bodů z DÚ pana Dantziga jsou předběžné (Dantzig slouží jen jako příklad). Otazník znamená, že řešení je potřeba dovysvětlit.