Lineární programování

Garant předmětu:

Radek Fučík, Jan Volec

Přednášející:

Jan Bureš, Radek Fučík, Jan Volec

Cvičící:

Jan Bureš, Radek Fučík, 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ápočet: Udělen za splněnou docházku a úspěšné vyřešení zápočtového testu.

Zkouška: Teoretická a praktická část vybraná z obsahu probraného na přednáškách.

Osnova přednášek:

1. Formulace úlohy lineárního programování, převody omezení, příklady úloh

2. Vlastnosti úloh lineárního programování, množina přípustných a optimálních řešení a jejich vlastnosti, geometrie úloh LP

3. Základní věta LP, grafické řešení úloh LP

4. Simplexový algoritmus jednofázová metoda, neomezenost úlohy, více optimálních řešení

5. Simplexový algoritmus dvoufázová metoda (technika pomocné báze), M-úloha

6. Vlastnosti simplexové metody degenerace, cyklení, časová náročnost algoritmu

7. Dualita úloh lineárního programování-formulace duální úlohy, věty o dualitě

8. Algoritmus duálně simplexové metody

9. Dopravní problém metoda MODI

10. Aplikace v teorii her maticové hry s nulovým součtem, smíšené strategie, minmax teorém

11. Algoritmy celočíselného programování typické úlohy LIP, metoda větví a mezí

12. Algoritmy celočíselného programování Gomoryho řezy

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áklad o soustavách lineárních rovnic a nerovnic.

Schopnosti:

Umět používat probrané algoritmy na řešení konkrétních úloh z praxe.

Studijní materiály:

Povinná literatura:

[1] J. Rohn: Lineární programování. Skripta 2004

[2] J. Rohn: Lineární a nelineární programování. Skripta 1997

Doporučená literatura:

[3] J. Matoušek: Lineární programování, Úvod pro informatiky. Skripta 2006

[4] B. Gärtner, J. Matoušek: Understanding and Using Linear Programming. Springer, 2007.

Poznámka:

Rozvrh na zimní semestr 2025/2026:

Rozvrh není připraven

Rozvrh na letní semestr 2025/2026:

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)
• Matematické inženýrství - Matematické modelování (PS)
• Matematické inženýrství - Matematická informatika-5248 (PS)