|
|
Řešení optimalizačních úloh s neklesajícími max-separabilními omezeními
Pavlíček, Ondřej ; Zimmermann, Karel (vedoucí práce) ; Palata, Jan (oponent)
Obsahem této diplomové práce jsou navržené algoritmy řešící optimalizační úlohy s max-separabilní účelovou funkcí ve tvaru f(x) = maxjJ fj (xj), kde fj jsou spojité unimodální funkce. Omezení úlohy mají tvar soustavy max-separabilních rovnic a nerovností s proměnnými na obou stranách rovnic a nerovností, přičemž max-separabilní funkce vystupující v omezení úloh jsou spojité a neklesající. V kapitole 6 je rozšíření těchto algoritmů na úlohy s různými proměnnými na obou stranách. V kapitole 7 je rozšíření úlohy na úlohy s koeficienty a -. Práce vychází z dříve publikovaných prací, v nichž bylo dokázáno, že množina přípustných řešení úlohy má v případě, že je neprázdná, vždy maximální prvek. Navrhované algoritmy vychází z tohoto maximálního prvku a postupně snižují hodnotu účelové funkce postupem, který je analogií metody přístupných směrů. Součástí diplomové práce je důkaz správnosti zde navrhnutých algoritmů, odhad jejich časové náročnosti. Dále také vytvořený program pro počítání úloh s použitím zde navrhnutých algoritmů.
|
|
|
Cooperative games with partial information
Černý, Martin ; Bok, Jan (vedoucí práce) ; Zimmermann, Karel (oponent)
(česky) 21. května 2021 Částečně definované kooperativní hry jsou zobecněným modelem klasických kooperativních her, ve kterém je známa hodnota pouze některých koalic. Proto se dá na tento model nahlížet jako na jeden z možných přístupů k modelování neurčitosti. Hlavním cílem této práce je shrnout a rozšířit existující výsledky této teorie. Práce obsahuje výsledky týkající se superaditivity, konvexity, pozitivity a 1- konvexity neúplných her. Pro všechny tyto vlastnosti studujeme popis množiny všech extenzí (úplných her rozšiřujících danou neúplnou hru). V rámci toho se soustředíme na několik tříd neúplných her. Mezi dalšími se jedná o neúplné hry s minimální informací, neúplné hry s definovaným horním vektorem nebo symetrické neúplné hry. Uvádíme i několik výsledků k obecným neúplným hrám. V rámci studia superaditivity a 1-konvexity definujeme a studujeme koncepty řešení (definované pouze na částečné informaci). Konkrétně pro 1-konvexitu na- bízíme rozsáhlou analýzu zadefinovaných konceptů, zahrnující několik ekviva- lentních charakterizací. 1
|
|
|
Monge property for interval matrices
Černý, Martin ; Hladík, Milan (vedoucí práce) ; Zimmermann, Karel (oponent)
Tato práce je prvním průzkumem oblasti intervalových matic s Mongeovou vlastností. Zabývá se charakterizacemi a vlastnostmi dvojice tříd matic - třídy intervalových silně Mongeových matic a třídy intervalových slabě Mongeových matic. V práci je představeno několik metod na rozpoznávání a rekonstrukci těchto matic a následně prozkoumána jejich aplikace v problémech kombina- torické optimalizace a v problému související s výpočetní geometrií.
|
|
|
The optimal solution set of interval linear programming problems
Garajová, Elif ; Hladík, Milan (vedoucí práce) ; Zimmermann, Karel (oponent)
Určení množiny všech optimálních řešení lineárního programu s intervalovými daty je jedním z hlavních problémů intervalové optimalizace. Prezentujeme dvě metody založené na dualitě v lineárním programovaní, které jsou využívány k aproximaci optimální množiny. Dále je také navržena dekompoziční metoda založená na komplementaritě omezujících podmínek. Tato metoda poskytuje přesný popis optimální množiny pro problémy s pevnou maticí koeficientů. Druhá část práce se zabývá topologickými a geometrickými vlastnostmi optimální množiny. V této části zkoumáme postačující podmínky pro uzavřenost, omezenost, souvislost a konvexitu. Navíc je dokázáno, že testování omezenosti je co-NP-těžké pro problémy s omezeními ve formě nerovností a volnými proměnnými. Silnější výsledky jsou odvozeny pro některé speciální třídy intervalových lineárních programů, například programy s pevnou maticí koeficientů. Dále studujeme efekt transformací běžně používaných v lineárním programování na intervalové problémy, což umožňuje přímé zobecnění některých výsledků na různé typy intervalových lineárních programů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Optimization Problems under (max; min) - Linear Constraint and Some Related Topics
Gad, Mahmoud Attya Mohamed ; Zimmermann, Karel (vedoucí práce) ; Gavalec, Martin (oponent) ; Grygarová, Libuše (oponent)
Název práce: Optimalizační problémy při (max,min)-lineárních omezeních a některé související úlohy. Author: Mahmoud Gad Katedra/Ústav: Katedra Pravděpodobnosti a matematické statistiky Vedoucí dizertační práce: 1. Prof. RNDr. Karel Zimmermann, DrSc 2. Prof. Dr. Assem Tharwat, Cairo University Egypt . Abstrakt: Úlohy na algebraických strukturách, v nichž dvojice operací (max, +) nebo (max, min) nahrazují operace sčítání a násobení v klasické lineární algebře se objevují v literatuře přibližně od šedesátých let minulého století. První výsledky s využitím těchto struktur publikovali A. Shimbel v práci [37] s aplikacemi v komunikačních sítích, a dále R. A. Cunnighame-Green [12,13], N. Vorobjov [40] a B. Giffler [18] s aplikacemi na rozvrhování práce strojů a v teorii spolehlivosti. Ucelená systematická teorie takových algebraických struktur byla publikována pravděpodobně poprvé v práci [14]. V nedávno publikované knize [4] lze nalézt nejnovější stav výzkumu teorie a algoritmů ve struktuře s operacemi (max,+). Protože operace maxima, která v uvedených strukturách nahrazuje operaci sčítání, není grupovou, ale pouze pologrupovou operací, je podstatný rozdíl mezi řešením soustav s proměnnými pouze na jedné straně rovnic resp. nerovností a soustav, v nichž se proměnné nacházejí na obou stranách těchto vztahů....
|
|
|
Evaluating public state space abstractions in extensive form games with an application in poker
Moravčík, Matej ; Hladík, Milan (vedoucí práce) ; Zimmermann, Karel (oponent)
Poznáme efektívne techniky na výpočet optimálnej stratégie pre hry v rozšírenej forme. Niektoré problémy, napríklad poker, sú stále omnoho väčšie, ako sú tieto techniky schopné zvládnuť. Riešením je vytvoriť abstrakciu hry, ktorá je menšia ako pôvodná hra. V tejto abstrakcii už dokážeme nájsť optimálnu stratégiu. Túto stratégiu môžeme potom využiť v originálnej hre. V tejto práci opisujeme techniky, ktoré sa na tvorbu abstrakcií aktuálne používajú. Väčšina z nich neberie osobite v úvahu informácie, ktoré sú viditeľné pre všetkých hráčov v hre. My sme na tento účel vyvinuli vlastnú techniku a otestovali sme ju v pokeri. Naše experimentálne výsledky ukázali, že nová technika priniesla značné zlepšenie oproti doteraz používaným technikám. Powered by TCPDF (www.tcpdf.org)
|
|
|
Metody řešení vybraných dopravních problémů a jejich implementace.
Drobný, Michal ; Grygarová, Libuše (vedoucí práce) ; Zimmermann, Karel (oponent)
S různými typy dopravních problémů se v praxi setkáváme velmi často. Tento problém lze chápat především jako rozvoz zboží od dodavatelů k odběratelům s cílem minimalizace distribučních nákladů. Reálné dopravní problémy se od těch obecných liší především uvažovanými restrikcemi, což mohou být například kapacity vozidel a objednávek, časová okna a různá další speciální distribuční omezení. Problematiku dopravního problému formuloval již F. L. Hitchcock v roce 1941 a od té doby bylo popsáno mnoho stochastických a nedeterministických metod pro řešení dopravního problému, nicméně při zavedení distribučních restrikcí pro řešení reálných problémů jsou tyto metody obtížně aplikovatelné. Tato práce poskytuje kompilaci nejznámějších deterministických metod vhodných pro řešení dopravních problémů, přičemž metody vhodné pro řešení reálných dopravních problémů jsou popsány podrobněji. Postup řešení pro vybrané metody je demonstrován na jednoduchých příkladech a výsledky porovnány s výsledky řešení ostatních metod. Na základě analýzy těchto metod jsou navrženy nové metody pro řešení reálných dopravních problémů, které jsou implementovány a jejich výsledky porovnány s metodami, které poskytuje komerční softwarový produkt.
|
|
|
Ekonomické aplikace geometrického programování
Štěpánek, Ladislav ; Dupačová, Jitka (vedoucí práce) ; Zimmermann, Karel (oponent)
Úlohy geometrického programování jsou speciální úlohy nelineárního programování, v nichž účelová funkce a omezení jsou ve tvaru posynomů. V této práci představíme úlohu geometrického programování a uvedeme možné způsoby řešení. V poslední kapitole budeme geometrické programování aplikovat na Cobb-Douglasovu produkční funkci, vytvoříme model s náhodnou poptávkou a uvedeme možná rozšíření této úlohy. Powered by TCPDF (www.tcpdf.org)
|
|
|
Game theory and poker
Schmid, Martin ; Hladík, Milan (vedoucí práce) ; Zimmermann, Karel (oponent)
Tato práce představí základní koncepty teorie her. Jsou představeny nezbytné modely a koncepty, následovány výpočetní složitostí odpovídajích algoritmů. Pok- er je formalizován v rámci modelů teorie her. Nejnovější algoritmy pro tento mod- el her jsou vysvětleny pomocí aplikace na poker. Práce také podává přehled o tom jak mezi sebou mohou jednotlivé programy soutěžit, konkrétně na příkladu Annu- al Computer Poker Competition a příhlášených programů. Nakonec je představen nový výsledek týkající se extensive form her s mnoha akcemi. Klíčová slova: Teorie her, poker, Nash equilibrium, hry s neúplnou informací
|
|
| |
host ::
RSS.