|
|
Interval linear programming
Garajová, Elif ; Hladík, Milan (vedoucí práce) ; Kearfott, Ralph Baker (oponent) ; Bartl, David (oponent)
Intervalové lineární programování představuje moderní přístup k řešení optimalizač- ních úloh s daty zatíženými intervalovou neurčitostí. Úloha intervalového lineárního pro- gramování reprezentuje množinu klasických úloh lineárního programování takových, že koeficienty jednotlivých úloh mohou být nezávisle perturbovány mezi zadanými dolními a horními mezemi. Práce předkládá ucelený přehled vlastností týkajících se optimality v úlohách intervalového lineárního programování a jejich řešeních. Práce kompiluje exis- tující výzkum s důrazem na výsledky publikované autorkou, které přispěly k rozšíření a doplnění stavu poznání problematiky intervalového programování. Nejprve jsou uva- žovány standardní transformace mezi obvyklými formulacemi klasických úloh lineárního programování, pro které je zkoumán jejich vliv na optimální řešení a optimální hodnoty v intervalových úlohách. Dále jsou charakterizovány vlastnosti přípustnosti, optimality a (ne)omezenosti ve slabém resp. silném smyslu (t.j. zda je vlastnost pozorována pro ale- spoň jeden scénář resp. pro všechny scénáře), spolu s charakterizacemi je také zkoumána výpočetní složitost rozhodovacích problémů souvisejících s testováním těchto vlastností. Speciálně, práce ukazuje, že některé z těchto problémů jsou (co)NP-těžké dokonce i pro úlohy intervalového...
|
|
|
Interval solver for nonlinear constraints
Garajová, Elif ; Hladík, Milan (vedoucí práce) ; Pergel, Martin (oponent)
Práce se zabývá algoritmem Sivia (Set Inverter via Interval Analysis) pro řešení spojitého problému splňování omezujících podmínek pomocí intervalo- vých metod a propagačních technik. Prezentovány jsou základní vlastnosti al- goritmu, a také oprava uváděného odhadu jeho složitosti. Dále jsou navrhnuta vylepšení týkající se testování splnění omezujících podmínek a optimalizace poč- tu intervalových boxů popisujících získané řešení problému. Představeny jsou též tzv. kontraktory používané pro zvýšení efektivity algoritmu Sivia prostřednic- tvím redukce zpracovávaných intervalových boxů. Uvedené algoritmy byly im- plementované jako knihovna funkcí jazyka Matlab tvořící solver nelineárních podmínek s možností jednoduché vizualizace získaného řešení. Součástí práce je také porovnání základních kontraktorů na konkrétních příkladech.
|
|
|
Hledání v polygonální mapě
Navrátil, Šimon ; Pangrác, Ondřej (vedoucí práce) ; Garajová, Elif (oponent)
Vyhledávání nejkratší cesty je dobře probádaná oblast pro dikrétní problémy. Ne všechny problémy lze ale přímo popsat grafem a v orientačním běhu může běžec zvo- lit cestu kudykoliv. I tak ale musí z mapy vybrat tu nejrychlejší. To komplikuje i fakt, že v jednotlivých oblastech mezi kontrolami se pohybuje různě rychle. Pro nalezení opti- mální cesty je tedy potřeba najít nějaké spojité řešení. V této práci je popsáno, jak dostat z mapového souboru polygonální reprezentaci mapy a jak v ní pak následně vyhledávat nejrychlejší cestu, pomocí dvou různých přístupů. 1
|
|
|
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)
|
|
|
Interval solver for nonlinear constraints
Garajová, Elif ; Hladík, Milan (vedoucí práce) ; Pergel, Martin (oponent)
Práce se zabývá algoritmem Sivia (Set Inverter via Interval Analysis) pro řešení spojitého problému splňování omezujících podmínek pomocí intervalo- vých metod a propagačních technik. Prezentovány jsou základní vlastnosti al- goritmu, a také oprava uváděného odhadu jeho složitosti. Dále jsou navrhnuta vylepšení týkající se testování splnění omezujících podmínek a optimalizace poč- tu intervalových boxů popisujících získané řešení problému. Představeny jsou též tzv. kontraktory používané pro zvýšení efektivity algoritmu Sivia prostřednic- tvím redukce zpracovávaných intervalových boxů. Uvedené algoritmy byly im- plementované jako knihovna funkcí jazyka Matlab tvořící solver nelineárních podmínek s možností jednoduché vizualizace získaného řešení. Součástí práce je také porovnání základních kontraktorů na konkrétních příkladech.
|
host ::
RSS.