Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2025/2026

Lineární programování

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
01LIP Z,ZK 3 2+1 česky
Garant předmětu:
Přednášející:
Cvičící:
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
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 18. 3. 2025
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet11339905.html