Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Lineární programování

Zobrazit rozvrh
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
místnost TR:208
Blažek J.
10:00–11:50
SUDÝ TÝDEN

(paralelka 101)
Trojanova 13
učebna 208
St
Čt

místnost TR:209
Volec J.
10:00–11:50
(přednášková par. 1)
Trojanova 13
učebna 209
Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 19. 3. 2025
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet11339905.html