Lineární programování

Garant předmětu:

Jan Volec

Přednášející:

Jan Volec

Cvičící:

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(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í.

2. Kritérium optimality.

3. Simplexový algoritmus.

4. Dvoufázová simplexová metoda.

5. Ukázka vypočtu a zacyklení.

6. Primární a duální úloha.

7. Věta o dualitě.

8. Farkašova věta.

9. Aplikace v teorii her.

10. Dopravní problém.

11. Celočíselné programování.

12. Gomoryho algoritmus.

13. Parametrické programování.

Osnova cvičení:

1. Úloha lineárního programování, podmínka optimality a neomezenost.

2. Simplexová metoda.

3. Dvojfázová simplexová metoda.

4. Duální simplexová metoda.

5. Příklad z teorie her.

6. Gomoryho algoritmus.

7. Kvadratické programování.

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

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