The Multi-Dimensional Knapsack Problem
| Thesis title: | Vícerozměrná úloha batohu |
|---|---|
| Author: | Ficová, Pavla |
| Thesis type: | Bakalářská práce |
| Supervisor: | Kalčevová, Jana |
| Opponents: | Černohous, Roman |
| Thesis language: | Česky |
| Abstract: | Tato práce se zabývá problémem vícerozměrné úlohy batohu. Úloha batohu spadá do kategorie celočíselných úloh lineárního programování. Díky nutnosti celočíselného výsledku bývá u úloh tohoto typu často obtížné nalézt řešení, při splnění všech omezení. Vymyšlením přesného algoritmu pro výpočet těchto úloh se zabývá mnoho matematiků a statistiků z celého světa. Už nyní existuje mnoho přístupů a heuristik, jak tyto úlohy řešit, nebo se alespoň optimálnímu řešení co nejvíce přiblížit. U úloh s více proměnnými nelze dojít k řešení pomocí ručních výpočtů, model je příliš složitý a počet iterací opravdu velký. Obsáhlé úlohy může řešit i velmi vyspělý software několik minut nebo déle. Následující text se snaží tuto problematiku objasnit, popsat a ukázat možnost praktické aplikace na reálný problém. |
| Keywords: | metoda včelího úlu; metoda hypercube; úloha batohu; celočíselné programování; Balasova metoda |
| Thesis title: | The Multi-Dimensional Knapsack Problem |
|---|---|
| Author: | Ficová, Pavla |
| Thesis type: | Bachelor thesis |
| Supervisor: | Kalčevová, Jana |
| Opponents: | Černohous, Roman |
| Thesis language: | Česky |
| Abstract: | This work deals with multi-dimensional knapsack problem. Knapsack problem coincides with the category of integer linear programming. Thanks to the necessity of integer result it used to be more difficult to find the solution, by meeting all limitations. A lot of statisticians and mathematicians from all over the world are engaged in inventing an exact algorithm for calculation of these problems. As at now, there have been various accesses and heuristics concerning how to solve these problems or at least how to get as close to the optimal solution as possible. Problems with many variables are impossible to solve by hand calculations, the model is too complex and number of iterations is really high. Extensive exercises can be solved by advanced software in several minutes or longer. This work is trying to describe the problems, clear up and show practical application of knapsack problem in a real situation. |
| Keywords: | Bee Colony Algorithm; Balas Method; integral programming; knapsack problem; Hypercube Algorithm |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| 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: | 15. 12. 2009 |
|---|---|
| Date of submission: | 17. 5. 2010 |
| Date of defense: | 8. 6. 2010 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/23709/podrobnosti |