Alternative Method of Solution for LP Problem
| Thesis title: | Alternativní způsob řešení úloh LP |
|---|---|
| Author: | Hanzlík, Tomáš |
| Thesis type: | Diplomová práce |
| Supervisor: | Kalčevová, Jana |
| Opponents: | Rada, Miroslav |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | central path; základní řešení; Self-duální úloha; Lemkeho algoritmus |
| Thesis title: | Alternative Method of Solution for LP Problem |
|---|---|
| Author: | Hanzlík, Tomáš |
| Thesis type: | Diploma thesis |
| Supervisor: | Kalčevová, Jana |
| Opponents: | Rada, Miroslav |
| Thesis language: | Česky |
| Abstract: | 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: | Lemke's algorithm; basic feasible solution; Self-Dual problem; central path |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Type of study programme: | Magisterský studijní program |
| Assigned degree: | Ing. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 20. 10. 2009 |
|---|---|
| Date of submission: | 5. 1. 2011 |
| Date of defense: | 3. 2. 2011 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/22292/podrobnosti |