Lineární programování

Garant předmětu:

Radek Fučík

Přednášející:

Jan Bureš, Radek Fučík

Cvičící:

Jan Bureš, Radek Fučík

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. Řešení úloh LP na počítači - softwarové nástroje a jejich použití

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

3. Simplexová metoda - základní kroky algoritmu, různé situace při řešení..

4. Dvoufázová simplexová metoda - algoritmus techniky pomocné báze, varianta řešení pomocí M-úlohy.

5. Duální simplexová metoda.

6. Příklad z teorie her - hledání smíšených strategií.

7. Gomoryho algoritmus a další algoritmy LIP (metoda větví a mezí).

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