Hlavní stránka | Seznam oborů/specializací | Seznam všech skupin předmětů | Seznam všech předmětů | Seznam rolí                Návod

Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2  značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS
MI-LOM.16 Lineární optimalizace a metody Rozsah kontaktní výuky: 2P+1C
Vyučující: Způsob zakončení: Z,ZK
Zodpovědná katedra: 18101 ECTS Kredity: 5 Semestr: Z

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í.

Osnovy 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).

Osnovy 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.

Literatura:
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.

Požadavky:

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

Předmět je zahrnut do těchto studijních plánů:
Plán Obor Role Dop. semestr
MI-ZI.2016 Znalostní inženýrství V Není
MI-ZI.2018 Znalostní inženýrství V Není
MI-SP-TI.2016 Systémové programování V Není
MI-SP-SP.2016 Systémové programování V Není
MI-SPOL.2016 Nespecifikovaný/á obor/specializace studia - Unspecified Branch/Specialisation of Study V Není
MI-WSI-WI.2016 Webové a softwarové inženýrství V Není
MI-WSI-SI.2016 Webové a softwarové inženýrství V Není
MI-WSI-ISM.2016 Webové a softwarové inženýrství V Není
MI-NPVS.2016 Návrh a programování vestavných systémů V Není
MI-PSS.2016 Počítačové systémy a sítě V Není
MI-PB.2016 Počítačová bezpečnost V Není
NI-TI.2018 Teoretická informatika V 1,3


Stránka vytvořena 28. 3. 2024, semestry: Z/2022-3, L/2020-1, L/2019-20, L/2023-4, L/2022-3, Z/2023-4, Z/2019-20, Z/2021-2, Z/2020-1, L/2021-2, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: J. Novák, I. Halaška