Lineární programování

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ů:

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