Lineární programování 01LIP (ZS 2024/2025)

• Přednáška: Pá 10:00 - 11:40, místnost T-209
• Cvičení: Út 10:00 - 11:40, místnost T-208 (jednou za 14 dní)

• Lineární programování, Úvod pro informatiky – skripta J. Matouška zde
• Simplexová metoda (obecný popis algoritmu; varianta z přednášky) – PDF zde
• Řešení LP pomocí Pythonu – materiály Dr. Kubery z FJFI Děčín zde a zde

• Lineární programování (stručný učební text) – skripta J. Rohna zde
• Lineární a nelineární programování (Učební text) – skripta J. Rohna zde
• Understanding and Using Linear Programming – kniha B. Gärtner, J. Matoušek, vydal Springer

• Online solver pro formát LP – Neos CPLEX v LP formátu
• Popis souborového formátu LP – dokumentace Gurobi, dokumetance lp_solve, dokumentace QSopt

• Zápočet: úspěšné vyrešení zápočtového testu – 60minut, vyřešit zadanou úlohu LP
• Zkouška: úspěšně vyřešená domácí úloha – deadline: 16. květen 2025 23:59:59 SELČ

• W1: 27.9. – Úvod a formality, formulace úlohy LP, příklady úloh LP, certifikat pro Ax=b nemá řešení (Matoušek, Kapitola 1 a 2)
• W2: 4.10. – LP relaxace celočíselných/kombinatorických problémů (párování, vrcholové pokrytí, nezávislá množina), totální unimodularita (Matoušek, Kapitola 3)
• W3: 11.10. – Konvexní kombinace, bazické přípustné řešení úlohy LP, racionální řešení pro LP s racionálními koeficienty, celočíselné úlohy s TU maticí (Matousek, Kapitola 4)
• W4: 18.10. – Tipy a triky na absolutní hodnotu v účelové funkci, těžkosti s absolutní hodnotou v obecném případě, řešení úloh LP pomocí počítače
• W5: 25.10. – přednáška nebyla; samostudium řešení LP s pomocí počítače
• W6: 1.11. – Úvod do simplexové metody, pomocná úloha pro počáteční řešení původní úlohy, simplexová metoda vs. degenerovaná resp. neomezená úloha
• W7: 8.11. – Simplexová metoda - detailní popis obecného algoritmu
• W8: 15.11. – přednáška nebyla; přeloženo na úterý 26.11.
• W9: 22.11. – Dokončení Simplexové metody, Blandtovo pravidlo, příklad zacyklení simplexové metody
• W10a: 26.11. – Celočíselné programovaní a Gomoryho řezy
• W10b: 29.11. – Dualita lineárního programování, Farkášova lemmata, vztah přípustnosti vs. optimality pro obecné úlohy LP
• W11: 6.12. – Důkaz silné věty o dualitě LP, komplementarita bazí
• W12: 13.12. – Aplikace LP: Dopravní problém – severozápadní hledání bazického přípustného řešení, von Neumannova věta o hrách s nulovým součtem
• W13: 20.12. 10:30-11:30 – Zápočtový test (2. pokus)

• 1.10. (1. cvičení) – převody mezi rovnicovým a nerovnicovým tvarem LP, certifikát neřešitelnosti systému lineárních rovnic, maximální tok jako úloha LP (Matoušek, příklad 2.2)
• 15.10. (2. cvičení) – Maximální tok a TU, nejkratší cesta a TU, zachování TU během převodu mezi LP v rovnicovém a nerovnicovém tvaru, oddělování bodů přímkou (Matoušek, příklad 2.4), papírenská úloha (Matoušek, příklad 2.7)
• 29.10. (3. cvičení) – 10 náhodných bodů v rovině vs. různé variace na aproximaci polynomem pevného stupně, optimalizace podílu dvou lineárních funkcí, konvexní cvičení (Matoušek, Lemma 4.3.1)
• 12.11. (4. cvičení) – 1-ku-1 vztah mezi simplexovými tabulkami a bázemi (Matoušek, Lemma 5.5.1), řešení úloh simplexovou metodou
• 3.12. (5. cvičení) – použítí duality lineárního programování na úlohy z minulých cvičení, varianty Farkašova lemmatu
• 10.12. (6. cvičení) – další varianta Farkašova lemmatu, dopravní problem – LP formulace a totální unimodularita příslušňé matice, Q&A / další příklad na simplex
• 17.12. 10:30-11:30 – Zápočtový test (1. pokus)