Modifikace algoritmu metody větvení a mezí pro řešení úloh celočíselného programování
| Název práce: | Modifikace algoritmu metody větvení a mezí pro řešení úloh celočíselného programování |
|---|---|
| Autor(ka) práce: | Vítek, Lukáš |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Pelikán, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | Hlavním cílem práce je srovnat výpočetní náročnost vybraných úloh celočíselného programování devíti modifikacemi metody větvení a mezí. Jednotlivé modifikace spočívají v kombinaci volby větvící proměnné a způsobu prohledávání vygenerovaného prohledávacího stromu. V první části práce je představena teorie lineárního programování, celočíselného programování a také typy metod řešení celočíselných úloh, přičemž důraz je kladen zejména na metodu větvení a mezí. Ve druhé části jsou naprogramovány modifikace algoritmů metody větvení a mezí v jazyce Visual Basic for Applications, kdy tento kód je propojen s matematickými modely v MPL for Windows. Prostřednictvím tohoto programu jsou nakonec vyřešeny tři úlohy celočíselného lineárního programování pro více variant vstupních údajů, přičemž je porovnána výpočetní náročnost jednotlivých modifikací a také její robustnost vůči změnám v zadání. Zcela nakonec je na příkladu řezné úlohy demonstrována optimalizace metodou generování sloupců, kdy rychlost této optimalizace je opět srovnána se všemi uvedenými modifikacemi metody větvení a mezí. |
| Klíčová slova: | celočíselné lineární programování; Visual Basic for Applications; MPL for Windows; metoda větvení a mezí |
| Název práce: | Modifications of Branch and Bound algorithm for solving integer linear programming problems |
|---|---|
| Autor(ka) práce: | Vítek, Lukáš |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Pelikán, Jan |
| Jazyk práce: | Česky |
| Abstrakt: | The main aim of this diploma thesis is to compare computational difficulty of selected integer linear programming problems by nine alterations of Branch and Bound method. The alterations are based on combination of branching variable selection and generated search tree vertices searching. There are introduced the linear programming theory, the integer linear programming theory and the ways of solving integer linear programming problems in the first part. Especially the Branch and Bound method is described. Secondly, the alterations of Branch and Bound algorithm are programmed in Visual Basic for Applications and they are connected with mathematical models written in MPL for Windows. Three integer linear programming problems with various input data order are solved by this program and their computational difficulty and robustness to input data variations are compared to each other. Finally, by solving the cutting stock problem, the column generation method is demonstrated and compared with other alterations again. |
| Klíčová slova: | Branch and Bound; Integer Linear Programming; Visual Basic for Applications; MPL for Windows |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| 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: | 7. 11. 2018 |
|---|---|
| Datum podání práce: | 28. 4. 2019 |
| Datum obhajoby: | 5. 6. 2019 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/67678/podrobnosti |