Selected methods for solving integer programming problems
| Thesis title: | Vybrané metody řešení úloh smíšeného celočíselného programování |
|---|---|
| Author: | Picková, Veronika |
| Thesis type: | Bakalářská práce |
| Supervisor: | Sekničková, Jana |
| Opponents: | Charvát, Karel |
| Thesis language: | Česky |
| Abstract: | Tato práce se zabývá úlohami smíšeného celočíselného programování a metodami jejich řešení. Čtenář je v první části nejprve uveden do problematiky celočíselného programování a poté, v druhé části, seznámen s různými metodami řešení. V této práci se jedná konkrétně o možnost výpočtu bez podmínek celočíselnosti a následnému zaokrouhlení, metodu větvení a mezí a Gomoryho metodu. Cílem této práce je seznámit čtenáře i s další metodou, konkrétně s Bendersovou dekompoziční metodou. Dekompoziční metody v podstatě úlohu rozkládají na dvě části, a to na část, která řeší úlohu s podmínkami celočíselnosti, a na část bez podmínek celočíselnosti. Veškeré použité metody jsou doplněny ilustrativním příkladem pro názornější pochopení. Třetí část práce je následná aplikace vysvětlených metod na konkrétním příkladu. |
| Keywords: | metoda zaokrouhlování; Bendersova dekompozice; Gomoryho metoda; metoda větvení a mezí; smíšené celočíselné programování |
| Thesis title: | Selected methods for solving integer programming problems |
|---|---|
| Author: | Picková, Veronika |
| Thesis type: | Bachelor thesis |
| Supervisor: | Sekničková, Jana |
| Opponents: | Charvát, Karel |
| Thesis language: | Česky |
| Abstract: | This final thesis work is dealing with the problems of mixed integer linear programming and their possible methods of solving. The reader will be introduced to the issues of integer programming in the first part of the work. There follow the different methods of solving in the second part, concretely the possibility of solving without the integer constraints and rounding the solution, the branch and bound method and the Gomory's method. The purpose of this work is to inform the reader about the Benders decomposing algorithm. Decomposing methods divide the original problem into two parts: a part with the constraints of integrity and a part without them. All of the explained methods are supported by illustrative examples. The third part of this thesis is the application of used methods to a concrete problem. |
| Keywords: | rounding method; Benders decomposition; Gomory's method; branch and bound method; mixed integer linear programming |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Statistika a ekonometrie |
|---|---|
| Type of study programme: | Bakalářský studijní program |
| Assigned degree: | Bc. |
| 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: | 3. 11. 2011 |
|---|---|
| Date of submission: | 9. 5. 2012 |
| Date of defense: | 20. 6. 2012 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/34358/podrobnosti |