|
|
Využití grafických procesorů v úlohách celočíselného programování
Hájek, Jan ; Fábry, Jan (vedoucí práce) ; Černý, Michal (oponent)
Široká podskupina okružních úloh z teorie grafů je častým problémem, který řeší přepravní firmy, letecké společnosti, hi-tech firmy pro plánování výroby plošných spojů nebo společnosti z úplně jiného hospodářského odvětví. Během dřívějších nejrůznějších výzkumů těchto úloh bylo provedeno mnoho analýz a představeno mnoho způsobů řešení, jejichž nástin je uveden v této práci. Některé z nich podávají lepší či horší výsledky v delším či kratším výpočetním čase. Přestože se výkon procesorů a současných technologií nadále zvyšuje, je s některými algoritmy obtížné se dopočítat výsledku v rozumném čase. Proto se práce zabývá otázkou, zda je možné nalézt vhodný algoritmus, který by bylo možné aplikovat na jiné a rychlejší struktury výpočetních jednotek tak, aby se zajistilo mnohonásobné zvýšení výpočetní rychlosti než doposud. Pro tento výzkum byl vytvořen a implementován testovací algoritmus metody větvení a mezí s maticovou redukcí sazeb, který byl podroben počítačovým experimentálním testům, jejichž důsledky jsou zde uvedeny.
|
|
|
Problém obchodního cestujícího a metoda GENIUS
Škopek, Michal ; Pelikán, Jan (vedoucí práce) ; Fábry, Jan (oponent)
Cílem diplomové práce je vysvětlit Problém obchodního cestujícího a vytvořit program, který bude počítat speciální metodu GENIUS. Problém obchodního cestujícího je popsán z několika hledisek. Nejprve z hlediska historického k objasnění souvislostí s určitými metodami a následně je popsán z hlediska výpočetních metod. Pro popis těchto metod byly vybrány zástupci jak exaktních metod tak i heuristických. Stěžejní částí diplomové práce je popis heuristiky GENIUS, ke které je vytvořen speciální počítačový program. Tento program pracuje nejprve s algoritmem GENI a následně s post-optimalizačním algoritmem US. Program je popsán z uživatelského pohledu a je k němu vytvořen manuál. Program je otestován na dvou základních příkladech. Výsledky, dané výpočtem pomocí programu pracujícím s heuristikou GENIUS, jsou srovnány s výsledky získanými pomocí exaktních algoritmů.
|
|
|
Heuristické a metaheuristické metody řešení úlohy obchodního cestujícího
Burdová, Jana ; Kalčevová, Jana (vedoucí práce) ; Zouhar, Jan (oponent)
Tato diplomová práce se zabývá otázkou nalezení minimální trasy pro úlohu obchodního cestujícího. Obchodní cestující musí projít každé místo právě jednou a vrátit se zpět do výchozího místa. Tento problém může být znázorněn jako úloha teorie grafů, kde místa odpovídají uzlům, cesty hranám a vzdálenosti mezi uzly ohodnocení hran. Optimální cesta úlohy obchodního cestujícího odpovídá nejkratšímu Hamiltonovu cyklu v grafu. Jedná se o klasickou NP-úplnou úlohu. Není znám žádný algoritmus, který řeší tuto úlohu v polynomiálním čase. Tento problém je možné řešit pomocí různých aproximačních algoritmů, které jsou rychlejší, ale méně kvalitní, než optimalizace. Mezi aproximační algoritmy, kterým se tato práce věnuje, patří například: metoda nejbližšího souseda, metoda minimální kostry grafu, Christofidova metoda, 2 opt., genetický algoritmus a další.
|
|
|
Optimalizace návštěv zákazníků - aplikace rozvozní úlohy
Dvořáčková, Tereza ; Šindelářová, Irena (vedoucí práce) ; Skočdopolová, Veronika (oponent)
Moje bakalářská práce se zabývá speciálními úlohami lineárního programování, jak z teoretické, tak i z praktické stránky. Jedná se o úlohy distribuční, zvláštní pozornost je věnována okružnímu a rozvoznímu problému. Práce obsahuje teoretické kapitoly vysvětlující matematické modely vybraných distribučních úloh, dále je zařazen popis některých heuristických metod pro řešení okružního problému. Modifikace těchto heuristik jsou pak aplikovány na konkrétní reálný rozvozní problém. V reálné úloze, uvedené v poslední části práce, se modeluje a řeší časový plán pro obchodního zástupce jedné nejmenované české firmy, který navštěvuje své zákazníky v přidělené oblasti. Optimalizace je zaměřena na úsporu času. Výsledky získané pomocí popsaných heuristik a pomocí softwaru LINGO jsou v závěru práce porovnány. V kapitole 3.5 je uvedena modifikace reálné úlohy, kde jsou zavedena nová omezení, tzv. časová okna. Výsledky práce budou firmě předloženy.
|
|
|
Problém ručního zalévání zahrady
Janovský, Martin ; Kalčevová, Jana (vedoucí práce) ; Mynařík, Petr (oponent)
Problém ručního zalévání zahrady se zaměřuje na aplikaci některých metod lineárního programování v praxi. Především se jedná o úlohu obchodního cestujícího a rozvozní úlohu. Postupy těchto metod jsou řešené na reálné zahradě. Problém nastává tehdy, kdy je třeba nalézt optimální cestu mezi zdrojem vody a rostlinami, které potřebují zalít. Obě úlohy (úloha obchodního cestujícího a rozvozní úloha) jsou počítané optimalizačním softwarem Lingo a třemi heuristickými metodami (metoda nejbližšího souseda, metoda výhodnostních čísel a metoda nejlevnějšího vkládání). Hlavním cílem je najít nejlepší řešení, které by se dalo využít v praxi.
|
|
|
Aplikace úlohy obchodního cestujícího na svoz reklamací
Havlová, Irena ; Skočdopolová, Veronika (vedoucí práce) ; Kuncová, Martina (oponent)
S různými obdobami nalezení optimální trasy či nejvhodnějšího nastavení je možné se setkat v mnohých oblastech lidské činnosti, ať již na poli vědy a techniky, tak i v obchodních sférách. Z matematického pohledu se jedná o řešení úlohy obchodního cestujícího a jejích modifikací. Tato práce je věnována řešení úlohy obchodního cestujícího pomocí lineárního modelu a některých jednodušších heuristik jako je metoda nebližšího souseda či metoda výhodnostních čísel. V rámci praktické části je pak demonstrováno využití této úlohy při svozech reklamací uvnitř části velkoobchodního řetězce s elektronikou, přičemž zahrnuto je i řešení při rozdělení cesty na více okruhů. V návaznosti na získané výsledky je pak nastíněno i finanční srovnání současného řešení situace ve společnosti s možnou vizí svozů vlastními silami po trasách určených řešením úlohy obchodního cestujícího.
|
|
|
Aplikace rozvozní úlohy na rozvržení zakázek v geodézii
Richtr, Vít ; Skočdopolová, Veronika (vedoucí práce) ; Šindelářová, Irena (oponent)
Rozvozní úloha, která spadá do kategorie distribučních úloh lineárního programování, má mnoho reálných podob a aplikací. Tato práce vychází ze skutečných dat poskytnutých geodetickou firmou a zaměřuje se na jejich optimalizaci s cílem sestavit efektivní týdenní rozvrh zakázek tak, aby byla účelně využita pracovní doba a byly minimalizovány dlouhé přejezdy mezi zakázkami. Nejdříve je úloha řešena bez omezení. V poslední části je přidána modifikace, která zavádí přesný čas, kdy může být zakázka realizována. Zadání je řešeno pomocí dvou heuristických metod -- metodou nejbližšího souseda a Clark-Wrightovou metodou výhodnostních koeficientů -- a pomocí optimalizačních systémů LINGO a Gurobi. Výsledky jednotlivých metod jsou vyhodnocovány a vzájemně srovnávány.
|
|
|
Řešení distribučních úloh v prostředí MS Excel / LINGO
Bisová, Sára ; Jablonský, Josef (vedoucí práce) ; Skočdopolová, Veronika (oponent)
Cílem této práce je přiblížit čtenáři tématiku distribučních úloh lineárního programování a možnosti jejich řešení v prostředí vybraných programových produktů. Pro usnadnění řešení několika typů distribučních úloh - dopravního problému, kontejnerového dopravního problému, přiřazovacího problému, alokačního problému a okružního dopravního problému - je zde popsána tvorba aplikace, která spočívá v propojení tabulkového kalkulátoru MS Excel s modelovacím systémem LINGO. Toto propojení je realizováno prostřednictvím aplikace VBA - Visual Basic for Applications. Jsou zde popsány základní procedury, příkazy a funkce systémů LINGO a VBA, včetně detailního popisu jejich propojení. Vytvořená aplikace je v závěrečné části práce demonstrována na několika ilustrativních příkladech.
|
|
|
Úloha obchodního cestujícího řešená Clark-Wrightovou metodou
Brož, Vojtěch ; Fábry, Jan (vedoucí práce) ; Ráčková, Adéla (oponent)
Práce řeší dvě reálné úlohy obchodního cestujícího s 18ti a 30ti uzly. Za použití Clark-Wrighotvy metody zvolené autorem jako nejvhodnější, především kvůli zohlednění reálných omezujících podmínek. Práce v úvodu obsahuje nutné teoretické základy úlohy obchodního cestujícího, její řešitelnost a praktické uplatnění. Následuje podrobný popis výpočetního algoritmu metody Clark-Wright. Výpočet reálných úloh zahrnuje i popis získání a úpravy použitých datových podkladů. Výsledky srovnává s optimálním řešením a řešením bez zahrnutí omezujících podmínek. V závěru zkoumá možnosti užití metody v praxi.
|
|
|
Optimalizace pomocí algoritmů mravenčích kolonií
Zahálka, Jaroslav ; Fábry, Jan (vedoucí práce) ; Zouhar, Jan (oponent)
Diplomová práce se zabývá algoritmy mravenčích kolonií a jejich využitím pro řešení okružních a rozvozních úloh. Tyto algoritmy se řadí mezi tzv. metaheuristiky a představují inovativní přístup k řešení NP - obtížných problémů vhodný především pro úlohy většího rozsahu. Práce začíná popisem okružních a rozvozních úloh včetně způsobů jejich řešení. V další kapitole analyzuje metaheuristiku Ant Colony a její možné aplikace na zmíněné problémy. Nejdůležitější součástí práce je praktická část, kterou představuje program Ant Colony Optimization Framework. Jde o rozšiřitelnou aplikaci napsanou v jazyce Java schopnou řešit úlohu obchodního cestujícího a základní rozvozní úlohu. V závěru práce je předvedena analýza řešení těchto problémů na testovacích datech.
|
host ::
RSS.