Alternativní způsob řešení úloh LP
| Název práce: | Alternativní způsob řešení úloh LP |
|---|---|
| Autor(ka) práce: | Hanzlík, Tomáš |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Kalčevová, Jana |
| Oponenti práce: | Rada, Miroslav |
| Jazyk práce: | Česky |
| Abstrakt: | 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. |
| Klíčová slova: | central path; základní řešení; Self-duální úloha; Lemkeho algoritmus |
| Název práce: | Alternative Method of Solution for LP Problem |
|---|---|
| Autor(ka) práce: | Hanzlík, Tomáš |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Kalčevová, Jana |
| Oponenti práce: | Rada, Miroslav |
| Jazyk práce: | Česky |
| Abstrakt: | 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. |
| Klíčová slova: | Lemke's algorithm; basic feasible solution; Self-Dual problem; central path |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Typ studijního programu: | Magisterský studijní program |
| Přidělovaná hodnost: | Ing. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 20. 10. 2009 |
|---|---|
| Datum podání práce: | 5. 1. 2011 |
| Datum obhajoby: | 3. 2. 2011 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/22292/podrobnosti |