Lineární optimalizace a metody

Garant předmětu:

Dušan Knop

Přednášející:

Dušan Knop

Cvičící:

Dušan Knop

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/

Rozvrh na zimní semestr 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út	místnost TH:A-1247 Knop D. 11:00–12:30 (přednášková par. 1) Thákurova 7 (budova FSv) seminární místnost
St
Čt
Pá

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

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

• Mgr. specializace Počítačová bezpečnost, 2020 (volitelný předmět)
• Mgr. specializace Návrh a programování vestavných systémů, 2020 (volitelný předmět)
• Mgr. specializace Počítačové systémy a sítě, 2020 (volitelný předmět)
• Mgr. specializace Manažerská informatika, 2020 (volitelný předmět)
• Mgr. specializace Softwarové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2020 (volitelný předmět)
• Mgr. specializace Webové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Znalostní inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2020 (volitelný předmět)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2020 a vyšší (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2023 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2023 (PS, volitelný předmět)