Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Lineární optimalizace a metody

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
NI-LOM Z,ZK 5 2P+1C česky
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 2023/2024:
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-1242
Knop D.
12:45–14:15
SUDÝ TÝDEN

(přednášková par. 1
paralelka 101)

Thákurova 7 (budova FSv)
místnost TH:A-1242
Knop D.
14:30–16:00
(přednášková par. 1)
Thákurova 7 (budova FSv)
St
Čt

Rozvrh na letní semestr 2023/2024:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 27. 3. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6167306.html