|
Vyučující
|
-
Novotný Lukáš, doc. Ing. Ph.D.
|
|
Obsah předmětu
|
1. Lineární programování. Geometrie lineárních nerovností. Polyedry. 2. Polyedrální kombinatorika. Farkasovo lemma. Dualita. Maticové hry. 3. Simplexová metoda. Duální simplexová metoda. Citlivostní analýza. 4. Homotopie. Parametrické programování. Revidovaná simplexová metoda. 5. Metoda generování sloupců. Dantzigova-Wolfeova dekompozice. 6. Celočíselné a smíšené lineární programování. Metody řezů. LP a Lagrangeova relaxace. Metody větví a mezí, větví a cen, větví a řezů. 7. Nelineární optimalizace. Konvexní optimalizace. KKT podmínky. Dualita. 8. Metody vnitřního bodu pro lineární programování. Centrální cesta. Kvadratické programování. 9. Semidefinitní programování. Spektraedry. Dualita. Vektorové programování. Metody vnitřního bodu. 10. Kuželové programování. Nelineární celočíselné programování. 11. Vícekriteriální optimalizace. Fuzzy optimalizace. Stochastická optimalizace. 12. Robustní optimalizace. Víceúrovňová optimalizace. Stackelbergovy hry. 13. Aproximační algoritmy. Moderní heuristické algoritmy. Prostor řešení úloh diskrétní optimalizace a jeho analýza. Programování s omezenými podmínkami. 14. Paralelní algoritmy pro lineární a semidefinitní programování.
|
|
Studijní aktivity a metody výuky
|
Přednáška s aktivizací, Přednáška, Cvičení
- Příprava na zkoušku [10-60]
- 56 hodin za semestr
- Příprava na souhrnný test [6-30]
- 35 hodin za semestr
- Kontaktní výuka
- 52 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| vysvětlit základní pojmy lineární algebry |
| vysvětlit základní pojmy matematické analýzy |
| vysvětlit základní pojmy teorie pravděpodobnosti |
| Odborné dovednosti |
|---|
| vyřešit základní úlohy lineární algebry |
| analyzovat jednoduché úlohy optimalizace funkcí |
| zhodnotit výpočetní složitost jednoduchých algoritmů |
| Obecné způsobilosti |
|---|
| bc. studium: kriticky přistupuje ke zdrojům informací, informace tvořivě zpracovává a využívá při svém studiu a praxi, |
| bc. studium: vytváří hypotézy, navrhuje postupné kroky, zvažuje využití různých postupů při řešení problému nebo ověřování hypotézy, |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| formulovat standardní úlohy diskrétní optimalizace |
| vysvětlit základní optimalizační metody |
| vysvětlit použití relaxačních metod |
| klasifikovat optimalizační úlohy podle jejich aproximovatelnosti |
| Odborné dovednosti |
|---|
| řešit standardní úlohy diskrétní optimalizace |
| aplikovat aproximační algoritmy na standardní optimalizační úlohy |
| analyzovat složitější úlohy diskrétní optimalizace |
| posoudit vhodnost aproximačních a heuristických algoritmů pro danou úlohu |
| Obecné způsobilosti |
|---|
| mgr. studium: používají své odborné znalosti, odborné dovednosti a obecné způsobilosti alespoň v jednom cizím jazyce, |
| bc. studium: samostatně získávají další odborné znalosti, dovednosti a způsobilosti na základě především praktické zkušenosti a jejího vyhodnocení, ale také samostatným studiem teoretických poznatků oboru, |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Přednáška založená na výkladu, |
| Přednáška s aktivizací studentů, |
| Cvičení (praktické činnosti), |
| Odborné dovednosti |
|---|
| Cvičení (praktické činnosti), |
| Přednáška s aktivizací studentů, |
| Obecné způsobilosti |
|---|
| Cvičení (praktické činnosti), |
| Přednáška s aktivizací studentů, |
| Hodnotící metody |
|---|
| Odborné znalosti |
|---|
| Ústní zkouška, |
| Odborné dovednosti |
|---|
| Demonstrace dovedností (praktická činnost), |
| Test, |
| Ústní zkouška, |
| Obecné způsobilosti |
|---|
| Ústní zkouška, |
| Test, |
|
Doporučená literatura
|
-
Ehrgott, Matthias. Multicriteria optimization. Second edition. 2010. ISBN 978-3-642-05975-9.
-
Korte, Bernhard; Vygen, Jens. Combinatorial optimization : theory and algorithms. 2nd ed. Berlin : Springer, 2002. ISBN 3-540-43154-3.
-
Schrijver, A. Combinatorial optimization polyhedra and efficiency. Berlin : Springer-Verlag, 2004. ISBN 3-540-20456-3.
-
Vanderbei, Robert J. Linear programming : foundations and extensions. Fifth edition. 2020.
|