Předmět Metody optimalizace (KMA / METOP)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMA / METOP - Metody optimalizace, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).

Materiál	Typ	Datum	Počet stažení

Obsah

1. Úvod. Obecná úloha optimalizace. Základní dělení úloh optimalizace (úlohy lineární, kvadratické, konvexní, nelineární, nekonvexní, matematické programování). Příklady úloh lineárního programování (úloha o dietě, stanovení výrobního programu (směšovací úloha), klasický dopravní problém).2. Obecná úloha lineárního programování. Množina přípustných řešení. Konvexní kombinace, konvexní množina. Konvexní polyedr, jeho stěna, vrchol. Základní věta lineárního programování.3. Standardní a kanonický tvar úlohy LP. Primární a duální úloha. Převod obecné úlohy LP na standardní, normální a kanonický tvar. Věta o slabé dualitě a její důsledky.4. Základy teorie duality. Farkasovo lemma. Galeova věta. Podmínka optimality pro primární úlohu.5. Základy teorie duality. Podmínka optimality pro duální úlohu. Princip duality. Věta o existenci optimálních řešení pro úlohy LP. Důsledky principu duality a věty o existenci opt. řešeni.6. Základy teorie duality. Ekonomická interpretace duálních proměnných.7. Simplexová metoda. Bazická řešení, jejich přípustnost a degenerace. Základní věta LP.8. Primární simplexová metoda. Běžný krok (fáze II), výchozí krok (fáze I) a konečnost. Grafické znázornění výpočtu. Degenerace a cyklus. Volba klíčového sloupce. Odstranění cyklu (lexikografická a kombinatorická pravidla).9. Duální simplexová metoda. Běžný krok, výchozí krok a konečnost. Degenerace a cyklus. Grafické znázornění výpočtu. Odstranění cyklu (epsilon-modifikace a kombinatorická pravidla).10. Krátký úvod do celočíselného lineárního programování. (Klasický dopravní problém, úlohy dopravního typu, přiřazovací úlohy apod.) Totálně unimodulární matice. Hoffmanova-Kruskalova věta.11. Rozšiřující témata. Aproximace (Čebyševova aproximace, l1-aproximace). Teorie konvexních polyedrů (charakteristiky stěny konvexního polyedru, konečnost počtu stěn konvexního polyedru, stejná kodimenze minimálních a maximálních vlastních stěn).12. Rozšiřující témata. Další věty o alternativě (základní lemma lineární algebry, Fredholmova věta).

Získané způsobilosti

zná obecné úlohy optimalizace a dělení úloh optimalizacezná základní geometricke pojmy: vrchol, hrana, stěna a faseta konvexního polyedruzná základní věty lineárního programovánízná standardní a kanonické tvary úlohy lineárního programovánízískává schopnost převádět úlohy lineárního programování mezi různými tvaryzná některe věty o alternativě (Farkasovo lemma)zná principy duality a jeho důsledkyzískává schopnost ekonomicky interpretovat duální proměnnézná algoritmy primární a duální metodyzískává schopnost vyřešit úlohy lineárního programování simplexovou metodou

Literatura

Guéret, C.; Prins, C.; Sevaux, M. Applications of optimization with Xpress-MP. Dash optimization, 2002. ISBN 0-9543503-0-8.Dantzig, G. B. -- Thapa, M. N. Linear Programming. 1. Introduction. Springer, 1997. ISBN 0-387-94833-1.Dantzig, G. B. -- Thapa, M. N. Linear Programming. 2. Theory and Extensions. Springer, 2003. ISBN 0-387-98613-5.Dantzig, G. B. -- Thapa, M. N. Linear Programming. 3. Implementation. Springer, 2007. ISBN 0-387-98609-X.nullKasana, H. S. -- Kumar, K. D. Introductory Operations Research: Theory and Applications. Springer, 2004. ISBN 3-540-40138-5.Padberg, M. Linear Optimization and Extensions. Berlin: Springer, 1999. ISBN 3-540-65833-5.Brickman, L. Mathematical Introduction to Linear Programming and Game Theory. Springer, 1989. ISBN 0-387-96931-2.http://www.ifors.org/tutorial/Franklin, J. N. Methods of Mathematical Economics: Linear and Nonlinear Programming, Fixed-Point Theorems. SIAM, 2002. ISBN 0-89871-509-1.Maňas, M. Optimalizační metody. Praha: SNTL, 1979.

Požadavky

Průběžné studium a průběžné plnění zadaných domácích úkolů.Je třeba znát probranou látku v rozsahu zavedených pojmů spolu s jejich vlastnostmi a vztahy mezi nimi, tzn., je třeba znát definice, tvrzení, věty atd., s tím, že těmto pojmům, jejich vlastnostem a vztahům mezi nimi je potřeba rozumět.Je potřeba umět zavedené pojmy, jejich vlastnosti a vztahy mezi nimi samostatně použít k odvození nových vlastností nebo vztahů nebo při řešení příkladů, tzn., je třeba umět také důkazy, s tím, že použití resp. řešení je potřeba rozumět.Hodnocení předmětu včetně klasifikace v případě zkoušky probíhá v souladu s čl. 10 a čl. 11 Studijního a zkušebního řádu OU.

Garant

doc. RNDr. David Bartl, Ph.D.

Vyučující

doc. RNDr. David Bartl, Ph.D.doc. RNDr. David Bartl, Ph.D.