Lineární programování
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
01LIP | Z,ZK | 3 | 2+1 | česky |
- Garant předmětu:
- Jan Volec
- Přednášející:
- Jan Volec
- Cvičící:
- Adam Blažek, Jan Volec
- Předmět zajišťuje:
- katedra matematiky
- Anotace:
-
Předmět se zabývá speciálními úlohami na vázané extrémy funkcí více proměnných, kdy funkce je lineární a vazbové podmínky mají tvar lineárních rovnic a nerovnic.
- Požadavky:
-
Základní kurzy matematické analýzy a lineární algebry
dle přednášek na FJFI ČVUT v Praze 01MA1, 01MAA2-4, 01LAA1, 01LAA2.
- Osnova přednášek:
-
1. Úloha lineárního programování, převod na rovnicový tvar
2. Lineární relaxace kombinatorických úloh, totální unimodularita
3. Bazické přípustné řešení, neefektivní algoritmus řešení LP
4. Řešení úloh LP použitím volně dostupného software
5. Úvod do simplexové metody, pomocná úloha pro nalezení bazického přípustného řešení
6. Detailní popis simplexové metody
7. Blandtovo pravidlo, ukázka zacyklení
8. Dualita lineárního programovaní, Farkašova lemmata
9. Důkaz silné věty o dualitě LP, komplementarita bazí
10. Aplikace v teorii her - hry s nulovým součtem
11. Dopravní problém
12. Celočíselné programování, Gomoryho řezy
- Osnova cvičení:
-
1. Převody mezi variantami úloh LP, přiklady (např. papírenská úloha, separace bodů přímkou)
2. Kombinatorické úlohy a jejich lineární relaxace, totální unimodularita
3. Redukce úloh s absolutní hodnotou na LP, optimalizace podílu dvou lineárních funkcí
4. Řešení úloh simplexovou metodou
5. Aplikace duality LP, varianty Farkašova lemmatu
6. Úlohy celočísleného programovaní
- Cíle studia:
-
Znalosti:
Matematický základy řešení soustav lineárních nerovnic.
Schopnosti:
1) Rozumět simplexové metodě a dualitě lineárního programování.
2) Rozumět lineárním relaxacím úloh celočíselného programování, speciálně totální unimodularitě.
3) Umět vyřešit úlohy lineární optimalizace z praxe, zejména pomocí LP řešičů na počítači.
- Studijní materiály:
-
Povinná literatura:
[1] J. Matoušek : Lineárni programování, Úvod pro informatiky. ITI series MFF UK, 2006.
- Poznámka:
- Další informace:
- http://honza.ucw.cz/LIP
- Rozvrh na zimní semestr 2024/2025:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po Út St Čt Pá - Rozvrh na letní semestr 2024/2025:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Aplikovaná algebra a analýza (volitelný předmět)
- Aplikace informatiky v přírodních vědách (povinný předmět programu)
- Aplikované matematicko-stochastické metody (povinný předmět programu)
- Matematické inženýrství - Matematická informatika (PS)
- Matematické inženýrství - Matematické modelování (PS)