Lineární programování 01LIP (ZS 2023/2024)
Kontakt: | jan [AT] ucw [DOT] cz
|
Kancelář: | T-108a
|
Základní informace
- Pá 8:00 - 9:40 T-209
- Pá 14:00 - 14:50 T-209
Studijní materiály (CZ)
- 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)
LP řešiče
Obsah přednášek
- W1: 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: 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. - Plán: důkaz silné věty o dualitě LP, Farkášova lemmata, komplementarita bazí
- W11: 8.12. - Plán: aplikace LP – dopravní problém, von Neumannova věta o hrách s nulovým součtem