text size

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.
Title:
The optimal solution set of interval linear programming problems
Title (in czech):
Množina optimálních řešení úlohy intervalového lineárního programování
Type:
Diploma thesis
Author:
Bc. Elif Garajová
Supervisor:
Mgr. Milan Hladík, Ph.D.
Opponent:
prof. RNDr. Karel Zimmermann, DrSc.
Thesis Id:
168259
Faculty:
Faculty of Mathematics and Physics (MFF)
Department:
Department of Applied Mathematics (32-KAM)
Study programm:
Informatics (N1801)
Study branch:
Discrete Models and Algorithms (IDMA)
Degree granted:
Mgr.
Defence date:
13/09/2016
Defence result:
Excellent
Language:
English
Keywords (in czech):
intervalové lineární programování, optimální množina, topologické vlastnosti
Keywords:
interval linear programming, optimal set, topological properties
Abstract (in czech):
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:
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)
Documents
Download Document Author Type File size
Download Text of the thesis Bc. Elif Garajová 824 kB
Download Abstract in czech Bc. Elif Garajová 84 kB
Download Abstract in english Bc. Elif Garajová 83 kB
Download Supervisor's review Mgr. Milan Hladík, Ph.D. 119 kB
Download Opponent's review prof. RNDr. Karel Zimmermann, DrSc. 1.23 MB
Download Defence's report 67 kB