Lineární optimalizace a metody

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Studenti získají přehled o aplikacích optimalizačních metod v informatické, ekonomické a průmyslové praxi. Budou seznámeni s praktickým významem lineárního a celočíselného programování. Budou umět pracovat s optimalizačním softwarem a ovládat jazyky užívané při jeho programování. Dokáží formalizovat optimalizační problémy z oblasti informatické (např. přidělování úloh procesorům, analýza síťových toků), distribuce a alokace zdrojů (dopravní problémy, problém obchodního cestujícího, apod.), z ekonomické praxe a modelování konfliktních situací pomocí teorie her. Získají přehled o problematice výpočetní složitosti v optimalizaci. Získají dobrou orientaci v algoritmech lineárního programování.

Požadavky:

Osnova přednášek:

1. Klasifikace optimalizačních technik: lineární a celočíselné programování, nelineární optimalizace, spojitá optimalizace, speciální typy lineárních problémů, úlohy obecné konvexní optimalizace, vícekriteriální optimalizace.

2. Matematické modely optimalizačních úloh (optimalizace a kombinatorika, úlohy distribuční, alokační, síťové, statistické, apod.).

3. Modelování konfliktních situací, úvod do teorie her.

4. Lineární algebra: matice a lineární zobrazení, vlastní čísla a vlastní vektory, základní odhady, positivní (semi)definitnost, $L_k$-normy, maticové normy.

5. Základy teorie lineárního a celočíselného programování a jeho geometrie, tvary lineárních programů.

6. Simplexový algoritmus.

7. Dualita lineárního programování.

8. Užití duality v kombinatorice a v návrhu algoritmů.

9. Klasifikace optimalizačních úloh z hlediska výpočetní složitosti.

10. Elipsoidový algoritmus.

11. Algoritmy vnitřního bodu.

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

13. Implementační otázky (numerická stabilita, řídné matice, přibližná a přesná řešení, datové struktury).

Osnova cvičení:

1. Formulace optimalizačních úloh.

2. Formulace optimalizačních úloh -- pokračování.

3. Syntax optimalizačních jazyků: LINGO.

4. Řešení konkrétních úloh v LINGO.

5. Syntax optimalizačních jazyků: CPLEX.

6. Řešení konkrétních úloh v CPLEX.

7. Syntax optimalizačních jazyků: MatLab.

8. Řešení konkrétních úloh v MatLabu.

9. Citlivost; užití duality.

10. Simplexový algoritmus.

11. Složitost simplexového algoritmu, průměrný a exponenciální případ.

12. Vícekriteriální úlohy redukovatelné na lineární programování I.

13. Vícekriteriální úlohy redukovatelné na lineární programování II.

Cíle studia:

Cílem předmětu je seznámit studenty s užitím metod a algoritmů optimalizace a matematického programování. Pozornost bude věnována lineární a celočíselné optimalizaci a jejímu užití v distribučních a alokačních úlohách, analýze dat, návrhu sítí či třeba při modelování konfliktních situací pomocí teorie her. Na cvičení se studenti seznámí s profesionálním optimalizační softwarem a jazyky k jeho programování.

Studijní materiály:

Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., Schrijver, A. ''Combinatorial Optimization''. Wiley-Interscience, 1997. ISBN 047155894X.

Chvatal, V. ''Linear Programming''. W. H. Freeman, 1983. ISBN 0716715872.

Matousek, J., Gärtner, B. ''Understanding and Using Linear Programming''. Springer, 2006. ISBN 3540306978.

Roos, C., Terlaky, T., Vial, J. P. ''Interior Point Methods for Linear Optimization''. Springer, 2005. ISBN 0387263780.

Schrijver, A. ''Theory of Linear and Integer Programming''. Wiley, 1998. ISBN 0471982326.

Thie, P. R., Keough, G. E. ''An Introduction to Linear Programming and Game Theory''. Wiley-Interscience, 2008. ISBN 0470232862.

Venkataraman, P. ''Applied Optimization with MATLAB Programming''. Wiley, 2009. ISBN 047008488X.

Poznámka:

Informace o předmětu a výukové materiály naleznete na http://mi-lom.polyedr.cz/

Další informace:

http://mi-lom.polyedr.cz/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Mgr. obor Znalostní inženýrství, 2016-2017 (volitelný předmět)
• Mgr. obor Počítačová bezpečnost, 2016-2019 (volitelný předmět)
• Mgr. obor Počítačové systémy a sítě, 2016-2019 (volitelný předmět)
• Mgr. obor Návrh a programování vestavných systémů, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Informační systémy a management, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2016-2019 (volitelný předmět)
• Mgr. program Informatika, pro fázi studia bez oboru, 2016-2019 (volitelný předmět)
• Mgr. obor Systémové programování, zaměření Systémové programování, 2016-2019 (volitelný předmět)
• Mgr. obor Systémové programování, zaměření Teoretická informatika, 2016-2017 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2018-2019 (volitelný předmět)
• Mgr. obor Znalostní inženýrství, 2018-2019 (volitelný předmět)