Předmět Algoritmy optimalizace (KMA / ALGOP)

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 / ALGOP - Algoritmy optimalizace, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).

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

Obsah

1. Úloha lineárního programování. Simplexová metoda. Bazická řešení, jejich přípustnost a degenerace. Základní věta LP.2. 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).3. 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).4. Úloha kvadratického programování. Wolfeho metoda.5. Problém lineární komplementarity. Souvislost úlohy kvadratického programování a problému lin. komplementarity.6. Problém lineární komplementarity. P-matice. Věta Fiedlerova-Ptákova. Murtyho algoritmus.7. Problém lineární komplementarity. Matice kopositivní plus. Lemkeho algoritmus.

Získané způsobilosti

Osvojuje si různé klasické algoritmy optimalizace: simplexová metoda, maďarská metoda, Dinicův algoritmus, Wolfeho metoda, Murtyho algoritmus, Lemkeho algoritmus.

Literatura

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.Franklin, J. N. Methods of Mathematical Economics: Linear and Nonlinear Programming, Fixed-Point Theorems. SIAM, 2002. ISBN 0-89871-509-1.Kučera, L. Kombinatorické algoritmy. Praha: SNTL, 1989. Unčovský, L.; Kovaľ, L; Fiala, P.; Vejmola, S. Modely sieťovej analýzy. Bratislava: Alfa, 1991. ISBN 80-05-00812-0.

Požadavky

Hodnocení předmětu včetně klasifikace v případě zkoušky probíhá v souladu s čl. 32 a čl. 33 Studijního a zkušebního řádu OU.OBECNÉ ZÁSADYPodmínkou pro úspěšné složení zkoušky je průběžné studium, aktivní účast na cvičeních a průběžné plnění zadaných domácích úkolů.Na známku "E" nebo "D" (odpovídající dříve používaná známka: "dobře", "3") 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.Na známku "C" nebo "B" (odpovídající dříve používaná známka: "velmi dobře", "2") 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 krátké resp. jednoduché důkazy, s tím, že použití resp. řešení je potřeba rozumět.Na známku "A" (odpovídající dříve používaná známka: "výborně", "1") je potřeba znát probranou látku v plném rozsahu, rozumět také hlubším výsledkům, jejich významu a souvislostem, jakož i způsobu jejich odvození, tzn., je třeba znát rovněž složitější důkazy a rozumět jejich struktuře.KONKRÉTNÍ PRŮBĚH ZKOUŠKY A ZPŮSOB BODOVÉHO HODNOCENÍZkouška je ústní. Zkouška probíhá ve třech fázích.V první fázi dostane student tři otázky spočívající ve vyslovení a krátkém okomentování probraných definic, popř. tvrzení, vět apod. nebo uvedení základních souvislostí. Za každou správnou odpověď lze získat 20 bodů. (Tedy maximálně 60 bodů celkem.)Ve druhé fázi dostane student za úkol předvést důkaz jednoduchého tvrzení (popřípadě vyřešit příklad). Za správně provedený jednoduchý důkaz (vyřešený příklad) lze získat dalších 20 bodů. (Předpokladem správného předvedení důkazu, tj. dovednosti použít zavedené pojmy k odvození vztahů mezi nimi, je samotná znalost zavedených pojmů. Student nemůže být v této fázi hodnocen, jestliže v první fázi neuspěl, tj., nemá dostatek bodů pro získání známky "E".)Ve třetí fázi dostane student za úkol předvést důkaz některého z hlubších výsledků. Za správně provedený těžší důkaz lze získat posledních 20 bodů. (Správné předvedení náročného důkazu předpokládá znalost základních pojmů i schopnost odvozovat jednoduché vztahy mezi nimi. Student nemůže být v této fázi hodnocen, jestliže ve druhé fázi neuspěl / nebyl hodnocen, tj., nemá dostatek bodů pro získání známky "C").

Garant

doc. RNDr. David Bartl, Ph.D.

Vyučující

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