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

• Pá 8:00 - 9:40 T-209
• Pá 14:00 - 14:50 T-209

• Lineární programování, Úvod pro informatiky – skripta J. Matouška (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)
• Řešení LP pomocí Pythonu – materiály Dr. Kubery z FJFI Děčín (zde a zde)

• 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

• W1: 29.9. - přednáška není (děkanské volno)
• W2: 6.10. - Úvod, formulace úlohy LP, příklady úloh s LP, certifikat pro Ax=b nemá řešení
• W3: 13.10. - LP relaxace celočíselných/kombinatorických problémů (párování, max-tok / min-řez, nezávislá množina), totální unimodularita
• W4: 20.10. - Konvexní kombinace, bazické přípustné řešení úlohy LP, celocislne úlohy s TU matici, tipy a triky na absolutní hodnotu v účelové funkci, cesta v grafu minimální délky pomocí LP
• W5: 27.10. - přednáška není, samostudium řešení LP s pomocí počítače (např. online LP solvery), formát souboru LP
• W6: 3.11. - Úvod do simplexové metody, degenerovaný příklad zacyklení
• W7: 10.11. - Simplexová metoda - detailní popis obecného algoritmu, Blandtovo pravidlo
• W8 17.11. - přednáška není (státní svátek)
• W9: 24.11. - Dokončení důkazu o Blandtově pravidle, dualita lineárního programování
• W10: 1.12. - Důkaz silné věty o dualitě LP, Farkášova lemmata, komplementarita bazí, optimalizace podílu dvou lineárních funkcí, racionální řešení LP s racionálními koeficienty
• W11: 8.12. - Aplikace LP – von Neumannova věta o hrách s nulovým součtem, dopravní problém
• W12: 15.12. - Celočíselné programovaní a Gomoryho řezy, LP a prokládání přímky danou množinou bodů
• W13: 22.12. - přednáška není (děkanské volno)
• W14: 5.1. - Zápočtová písemka – řešení LP simplexovou metodou