|
| |
|
|
Řešení úloh rekreační matematiky jako diskrétních optimalizačních úloh
Künzelová, Barbora ; Jablonský, Josef (vedoucí práce) ; Rada, Miroslav (oponent)
Bakalářská práce se zabývá řešením tří vybraných úloh rekreační matematiky pomocí diskrétní optimalizace. Jedná se o hry Gridspeed Puzzle, Shifty Witnesses a Alien Tiles. Čtenář se nejdříve seznámí s těmito úlohami a jejich pravidly, ze kterých jsou pak formulovány matematické modely, které jsou ve všech případech celočíselné. První dvě hry mají jeden model a řeší se jedním způsobem, u hry Alien Tiles se aplikují různé přístupy, a to jak ve velikosti modelu, tak i ve formě požadovaného výsledku hry. Všechny modely jsou přepsány modelovacím jazykem MPL, ve kterém jsou vyřešeny řešitelem CPLEX. U všech vybraných úloh je nalezeno optimální celočíselné řešení, které je následně čtenáři popsáno a vysvětleno. U úlohy Alien Tiles jsou nakonec porovnány výsledky řešení různých přístupů, ze kterých můžeme usoudit, že jedna forma požadovaného výsledku hry je na výpočet náročnější.
|
|
|
Problém plnění palet a využití jedné z jeho heuristik při rozmístění zboží ve skladu
Rybka, Ondřej ; Pelikán, Jan (vedoucí práce) ; Rada, Miroslav (oponent)
Tato práce se zabývá novými mezemi, heuristikami, přesnými algoritmy a matematickým modelem problému optimálního plnění palet (PLP), přičemž se snažíme zjistit možnost jeho využití na praktickém případě. Snažíme se maximalizovat počet boxů umístěných na obdélníkové palety jednoho skladu pomocí vybrané heuristiky. Všechny boxy mají obdélníkové tvary stejných rozměrů a jsou na paletě umístěné zcela. Můžeme otáčet s boxy o 90 % tak dlouho, dokud jejich okraje neleží souběžně s okraji palety. Jednotlivé případy jsou zadány ve formě (X, Y, a, b), kde X je délka, Y šířka palety, a délka boxu, b šířka boxu.
|
|
|
Alternativní způsob řešení úloh LP
Hanzlík, Tomáš ; Kalčevová, Jana (vedoucí práce) ; Rada, Miroslav (oponent)
Lineární programování (LP) se zabývá optimalizací lineárních funkcí při respektování soustavy lineárních omezujících podmínek a podmínek nezápornosti. Za tímto účelem vznikla řada metod, z nichž nejznámější je simplexová metoda. Velkou skupinu metod pro LP tvoří metody vnitřního bodu (IPM), které vycházejí z vnitřního řešení úlohy a tím se stávají alternativou k simplexové metodě, která pracuje se základním řešením úlohy. Tato práce se zabývá teoretickými východisky metod vnitřního bodu a jejich významem pro obecné algoritmy metod vnitřního bodu. Uveden je také význam KKT podmínek a způsob řešení lineární komplementární úlohy. V práci jsou formulovány dva algoritmy založené na metodách vnitřního bodu a tyto algoritmy jsou ve své základní podobě aplikovány na vzorovou úlohu LP.
|
|
|
Využití teorie her a metody reálných opcí v investičním rozhodování
Kuchina, Elena ; Dlouhý, Martin (vedoucí práce) ; Rada, Miroslav (oponent)
Tato práce ukazuje nový přístup ohodnocování investičních projektů za podmínek nejistoty, který spočívá ve sjednocení metody reálných opcí a základních principů teorie her. Aplikace teoretických východisek "opční hry" je ukázána na ilustračním příkladu představujícím dvouúrovňovou hru. Řešení příkladu porovnává hodnotu investičního projektu pro variantu, kdy investice do výzkumu a vývoje není uskutečněna oproti variantě, kdy je investice provedena, přičemž ve druhém případě se zároveň rozlišují dvě možnosti, a to zdali výsledky výzkumu a vývoje budou proprietární nebo sdílené. Předkládaná práce poukazuje na to, že při hodnocení investičních projektů by kromě standardní NPV hodnoty měla být vzata v úvahu také hodnota flexibility a hodnota strategického efektu, přičemž tyto dvě složky disponují antagonistickým charakterem. V rámci řešení ilustračního příkladu je pro různé případy ukázán rozklad hodnoty investičního projektu na jednotlivé složky.
|
|
|
Aplikace teorie her na oligopolní trhy
Nekola, Jan ; Dlouhý, Martin (vedoucí práce) ; Rada, Miroslav (oponent)
Tato práce ukazuje na použití modelů teorie her na oligopolní trh. Vychází z modelů Bertranda, Cournota a Stackelbergera, jejichž příklady řeší, jak mají firmy optimálně rozhodovat, aby maximalizovaly svůj užitek. Je zde uveden ilustrační příklad, který je rozšířením těchto modelů. Rozhodování probíhá v několika etapách, kde právě podle určitých pravidel teorie her, je firmám navržena strategie, jak mají postupovat. Druhý příklad se zabývá signální hrou. Cílem této práce je přiblížit teorii her na ilustrační příklad a ukázat, jak jsou hry citlivé na změnu informací nebo jak určité faktory ovlivní hru.
|
|
|
Traveling Tournament Problem
Šimpach, Ondřej ; Jablonský, Josef (vedoucí práce) ; Rada, Miroslav (oponent)
Traveling Tournament Problem je optimalizační úloha sportovního kalendáře, ve které se vyžaduje nalezení minimální možné úhrnné vzdálenosti při cestování týmů mezi jednotlivými zápasy turnaje. Turnaj je nejčastěji typu "dvakrát každý s každým", kde vzdálenosti jsou pro jednotlivé týmy klíčové. Paralelně se v problematice hledá optimální řešení vhodného uspořádání týmů do sportovní tabulky při respektování nejvyššího možného počtu všech kritérií, které jsou na pořadatele apelovány zainteresovanými subjekty, jako například manažery týmů či televizními a radiovými společnostmi. Práce poskytuje náhled do složitosti řešení úloh takovýchto rozsahů, doporučení při jejich řešení a možná východiska. V závěru je uvedena alternativní varianta pro výpočty turnajových rozpisů v českém prostředí, pro které vzdálenosti nejsou až tak důležité.
|
|
|
Optimalizace v prostředí internetu
Šálek, Pavel ; Jablonský, Josef (vedoucí práce) ; Rada, Miroslav (oponent)
Cílem této práce je analyzovat a zhodnotit efektivnost systémů pro řešení úloh matematického programování, které jsou k dispozici v rámci projektu NEOS (Network Enabled Optimization Server). V úvodní části práce jsou popsány nejpoužívanější algoritmy pro řešení úloh lineárního a smíšeně celočíselného programování -- simplexové algoritmy, metody vnitřního bodu, metody sečných nadrovin a metody větvení a mezí. Tyto algoritmy jsou používány v řešitelích, které server NEOS podporuje. Efektivnost algoritmů a jednotlivých řešitelů byla testována na souboru vybraných úloh obsažených v knihovnách NETLIB a MIPLIB.
|
|
|
Model tahové hry s finančními odměnami
Erbsová, Markéta ; Dlouhý, Martin (vedoucí práce) ; Rada, Miroslav (oponent)
Cílem práce je analýza a představení původní tahové hry s finančními odměnami, kterou nazveme Výměna. V teoretické části popíšeme základní pojmy teorie her, zvláště pak hru v explicitním tvaru.V praktické části se budeme zabývat samotnou hrou Výměna. Určíme pravidla hry, grafickou podobu hry a formulujeme matematický model hry. Samotné části hry podrobněji popíšeme. Neméně významnou částí bude charakteristika hry, ve které nastíníme možné využití hry v praxi.
|
|
|
Výpočetní aspekty metody maximálního polyedru pro rozhodování při neurčitosti
Rada, Miroslav ; Ivánek, Jiří (vedoucí práce) ; Dlouhý, Martin (oponent)
Metoda maximálního polyedru je metoda výběru nejlepší varianty pro rozhodování při neurčitosti. Její hlavní myšlenkou je vybrat tu variantu, která bude nejčastěji mít nejvyšší střední hodnotu, pokud zvolíme náhodně vektor pravděpodobností, s nimiž nastanou jednotlivé stavy světa. Stručně je tedy v práci popsána rozhodovací situace za neurčitosti, s důrazem na zmíněnou metodu. Cílem práce je popsat a implementovat algoritmus, jakým metoda maximálního polyedru vybírá nejlepší variantu, a posoudit jeho výpočetní aspekty. Každé rozhodovací variantě přísluší mnohostěn n-tic (vektorů) pravděpodobností, ve kterých je daná varianta nejlepší. Součástí práce je proto popis několika známých algoritmů pro exaktní výpočet objemu mnohostěnu. Protože některé algoritmy vyžadují na vstupu mnohostěn zadaný více způsoby, jsou zahrnuty též některé algoritmy pro přepočet reprezentace mnohostěnu. Jako nejvhodnější metoda výpočtu objemu pro mnohostěny vznikající v metodě maximálního polyedru je zvolena metoda HOT, doplněná pro případy jednoduchých mnohostěnů Lawrenceovou metodou. Jako nejvhodnější metoda přepočtu reprezentace je zvolena metoda LRS. V práci je dále sestaven rozhodovací program, který využívá dostupných implementací zvolených metod. Program je testován na náhodně vygenerovaných rozhodovacích úlohách. Na základě testování jsou odhadnuty meze jeho praktické použitelnosti ? velikost úlohy bez potíží výpočetně zvládnutelné (doba výpočtu cca 30 min) danou implementací je cca 15 variant x 14 stavů světa, přičemž výpočetní náročnost se zvyšuje rychleji s počtem stavů světa než s počtem variant. Konkrétní hodnoty mezní velikosti úlohy samozřejmě závisejí na požadované době odezvy a použitém hardware. V práci je dále provedeno srovnání výsledků rozhodování podle různých kritérií a jsou navrženy některé směry zdokonalení implementace metody maximálního polyedru.
|
host ::
RSS.