|
|
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.