Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2018/2019

Lineární optimalizace a metody

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
MI-LOM Z,ZK 4 2P+1C česky
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:

Rozsah=prednasky+proseminare+cviceni2p+1c

Další informace:
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 22. 7. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1434406.html