Předmět Úvod do lin. programování a teorie her (KMA / ULPTH)

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 / ULPTH - Úvod do lin. programování a teorie her, 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. Úvod. Pojem hry. Základní dělení her (salónní aj.) Pojem strategie-rozhodnutí. Dělení her: hry hráčů dvou a více, nekooperativní a kooperativní, konečné a nekonečné, s informací úplnou a neúplnou; hry bez přítomnosti a s přítomností náhodného mechanismu (např. loterie), hry s neinteligentním protihráčem. Hra ve strategickém (nebo normálním) tvaru, její interpretace-příklady: ekonomické modely (trh, oligopol), biologické modely. Pojem Nashovy rovnováhy. Hra s nulovým součtem.8. Maticová hra. Sedlový bod. Příklady maticových her: Blotto hry a jejich interpretace (vojenská, aukce obálkovou metodou, presentace a získávání zakázek na trzích), Hide and Attack (napadení konvoje), prstová hra Morra, model protivzdušné obrany; operace zraněného. Otázka existence sedlového bodu matice a způsob jeho nalezení (max min a min max).9. Maticové hry. Sedlový bod a otázka jeho existence. Hodnota hry. Jednoznačnost hodnoty hry. Věta o sedlových bodech. Smíšené rozšíření maticové hry. Strategie čisté (nebo ryzí) a smíšené. Hlavní věta maticových her.10. Maticové hry. Symetrické maticové hry a jejich vlastnosti (nulová hodnota hry, symetričnost smíšeného rozšíření). Převod maticové hry na symetrickou maticovou hru.11. Souvislosti lineárního programování a maticových her. Princip duality, podmínky komplementarity a sedlový bod Lagrangeovy funkce. Řešení úlohy lineárního programování nalezením sedlového bodu smíšeného rozšíření maticové hry. Dominování v maticových hrách. Brownova metoda fiktivní hry.12. Obecné věty o sedlových bodech. Vztah mezi sup inf a inf sup (max min a min max). Charakteristika sedlového bodu.13. Opakování.

Získané způsobilosti

Orientuje se v úvodu do lineárního programování.Orientuje se v úvodu do teorie her.Rozumí základům teorie duality lineárního programování.Rozumí základům teorie maticových her.Zná Farkasovo lemma, podmínku optimality, princip duality.Zná základní větu maticových her.Zná obecné věty o existenci sedlových bodů.Dokáže ekonomicky interpretovat hodnoty duálních proměnných.Chápe souvislosti lineárního programování a maticových her.

Literatura

Guéret, C.; Prins, C.; Sevaux, M. Applications of optimization with Xpress-MP. Dash optimization, 2002. ISBN 0-9543503-0-8.Maňas, M. Optimalizační metody. Praha: SNTL, 1979. Maňas, M. Teorie her a její aplikace. Praha: SNTL, 1991. ISBN 80-03-00358-X.Brickman, L. Mathematical Introduction to Linear Programming and Game Theory. Springer, 1989. ISBN 0-387-96931-2.Franklin, J. N. Methods of Mathematical Economics: Linear and Nonlinear Programming, Fixed-Point Theorems. SIAM, 2002. ISBN 0-89871-509-1.

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 (zejm. princip duality a hlavní věta maticových her), 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.Mgr. Lenka Ploháková