velikost textu

The optimal solution set of interval linear programming problems

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
The optimal solution set of interval linear programming problems
Název v češtině:
Množina optimálních řešení úlohy intervalového lineárního programování
Typ:
Diplomová práce
Autor:
Bc. Elif Garajová
Vedoucí:
Mgr. Milan Hladík, Ph.D.
Oponent:
prof. RNDr. Karel Zimmermann, DrSc.
Id práce:
168259
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (N1801)
Obor studia:
Diskrétní modely a algoritmy (IDMA)
Přidělovaný titul:
Mgr.
Datum obhajoby:
13. 9. 2016
Výsledek obhajoby:
Výborně
Jazyk práce:
Angličtina
Klíčová slova:
intervalové lineární programování, optimální množina, topologické vlastnosti
Klíčová slova v angličtině:
interval linear programming, optimal set, topological properties
Abstrakt:
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)
Abstract v angličtině:
Determining the set of all optimal solutions of a linear program with interval data is one of the main problems discussed in interval optimization. We review two methods based on duality in linear programming, which are used to approximate the optimal set. Additionally, another decomposition method based on complementary slackness is proposed. This method provides the exact description of the optimal set for problems with a fixed coefficient matrix. The second part of the thesis is focused on studying the topological and geometric properties of the optimal set. We examine sufficient conditions for closedness, boundedness, connectedness and convexity. We also prove that testing boundedness is co- NP-hard for inequality-constrained problems with free variables. Stronger results are derived for some special classes of interval linear programs, such as problems with a fixed coefficient matrix. Furthermore, we study the effect of transformations commonly used in linear programming on interval problems, which allows for a direct generalization of some results to different types of interval linear programs. Powered by TCPDF (www.tcpdf.org)
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Elif Garajová 824 kB
Stáhnout Abstrakt v českém jazyce Bc. Elif Garajová 84 kB
Stáhnout Abstrakt anglicky Bc. Elif Garajová 83 kB
Stáhnout Posudek vedoucího Mgr. Milan Hladík, Ph.D. 119 kB
Stáhnout Posudek oponenta prof. RNDr. Karel Zimmermann, DrSc. 1.23 MB
Stáhnout Záznam o průběhu obhajoby 67 kB