Metody na výpočet optimálních hodnot intervalového lineárního programování

Abstract

Tato práce pojednává o problému hledání intervalu, ve kterém se m·žou nacházet optimální hodnoty účelové funkce intervalového lineárního programu, takzvaný rozsah optimální hodnoty (optimal value range). ešení toho pro- blému m·že být v určitých případech redukováno na řešení několika lineárních program·, obecně se ale jedná o těžký problém. Po seznámení s intervalovou aritmetikou a rozšířením lineárního programování na intervalové si zavedeme d·ležité množiny a jejich vlastnosti, B-stabilitu a další podproblémy s tím souvi- sející. Rozšíříme pojem B-stability na generalizované intervalové lineární progra- mování a budeme se věnovat metodám na výpočet rozsahu optimálních hodnot a jejich numerickému porovnání na náhodných soustavách. Cílem bude dané me- tody naimplementovat pomocí MATLAB/INTLAB a na základě provedených test· vytvořit jedinou funkci, která bude problém řešit, pokud možno efektivně. 1

This thesis is about the problem of searching an interval that enclose all op- timal values of the objective function in interval linear programming, so called the optimal value range. The solution to this problem is sometimes reduced to solving just a few linear programs but in general it is a hard problem. Af- ter we get familiar with interval arithmetics and when we extend it to linear programming, we define important sets and their properties, B-stability and other connected subproblems. We will extend B-stability to generalized interval linear programming and we will examine methods for computing the optimal value range and we will compare them numerically on random systems. The goal is to implement all mentioned methods in MATLAB/INTLAB and based on numerical results provide one function that will solve this problem, possible efficiently. 1