Original title: Alternativní způsob řešení úloh LP
Translated title: Alternative Method of Solution for LP Problem
Authors: Hanzlík, Tomáš ; Kalčevová, Jana (advisor) ; Rada, Miroslav (referee)
Document type: Master’s theses
Year: 2009
Language: cze
Publisher: Vysoká škola ekonomická v Praze
Abstract: [cze] [eng]
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.
Keywords: basic feasible solution; central path; Lemke's algorithm; Self-Dual problem; central path; Lemkeho algoritmus; Self-duální úloha; základní řešení

Institution: University of Economics, Prague (web)
Document availability information: Available in the digital repository of the University of Economics, Prague.
Original record: http://www.vse.cz/vskp/eid/23577

Permalink: http://www.nusl.cz/ntk/nusl-76656


The record appears in these collections:
Universities and colleges > Public universities > University of Economics, Prague
Academic theses (ETDs) > Master’s theses