Alternative Method of Solution for LP Problem

Lineární programování (LP) se zabývá optimalizací lineárních funkcí při respektování soustavy lineárních omezujících podmínek a podmínek nezápornosti. Za tímto účelem vznikla řada metod, z nichž nejznámější je simplexová metoda. Velkou skupinu metod pro LP tvoří metody vnitřního bodu (IPM), které vycházejí z vnitřního řešení úlohy a tím se stávají alternativou k simplexové metodě, která pracuje se základním řešením úlohy. Tato práce se zabývá teoretickými východisky metod vnitřního bodu a jejich významem pro obecné algoritmy metod vnitřního bodu. Uveden je také význam KKT podmínek a způsob řešení lineární komplementární úlohy. V práci jsou formulovány dva algoritmy založené na metodách vnitřního bodu a tyto algoritmy jsou ve své základní podobě aplikovány na vzorovou úlohu LP.Linear programming (LP) stands for an optimization of a linear objective function, subject to linear and non-negativity constraints. For this purpose many methods for LP emerged. The best known is Simplex Method. Another group of methods for LP is represented by Interior Point Methods (IPM). These methods are based on interior points of feasible region of a problem, while Simplex Method uses basic feasible solution of a problem. This thesis focuses on theoretical background of IPM and brings it into relation with algorithms based on IPM. KKT system and its significance are included and the algorithm solving Linear Complementarity Problem is discussed as well. In this thesis, two algorithms based on IPM are introduced and used for solving a sample LP problem