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

Přednášející – Jan Volec

Kontakt:	jan [AT] ucw [DOT] cz
Kancelář:	T-108a

Základní časo-prostorové informace

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í)

Studijní materiály (CZ)

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

Dodatečné studijní materiály (CZ)

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)

LP řešiče

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

Podmínky pro úspěšné splnění předmětu

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Č

Obsah přednášek

W1: 27.9. – Úvod a formality, formulace úlohy LP, příklady úloh LP, certifikat pro Ax=b nemá řešení
W2: 4.10. - LP relaxace celočíselných/kombinatorických problémů (párování, vrcholové pokrytí, nezávislá množina), totální unimodularita
W3: 11.10. - Plán: 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í
W5: 25.10. – přednáška nebude

Obsah cvičení

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í)
29.10. (3. cvičení)
12.11. (4. cvičení)
26.11. (5. cvičení)
10.12. (6. cvičení)
17.12. 10:30-11:30 – Zápočtový test