The multiple knapsack problem
| Thesis title: | Praktická aplikace hromadné bivalentní úlohy batohu |
|---|---|
| Author: | Černý, Vít |
| Thesis type: | Bakalářská práce |
| Supervisor: | Kalčevová, Jana |
| Opponents: | Suchánková, Tereza |
| Thesis language: | Česky |
| Abstract: | Úloha batohu je jednou z klasických úloh operačního výzkumu. Patří do kategorie celočíselných úloh lineárního programování, nejčastěji je formulována jako binární úloha. V této bakalářské práci jsou popsány jednotlivé kategorie úlohy a také některé metody vedoucí k nalezení řešení takových úloh. Ačkoli existují přesné algoritmy pro spolehlivé nalezení optimálního řešení, některé úlohy batohu jsou tak rozsáhlé, že výpočet pomocí exaktních algoritmů by nebylo možné realizovat. Z toho důvodu jsou složitější úlohy batohu řazeny do kategorie NP-úplné. Proto bylo vytvořeno několik heuristik a metod, které mohou vést k dostatečně dobrému řešení v relativně krátkém čase a poměrně jednoduchým způsobem. Tato práce se zaměřuje zejména na jednu z popisovaných úloh, na hromadnou bivalentní úlohu batohu. Na praktickém příkladě ukazuje, jak je možné tento problém řešit. |
| Keywords: | bivalentní programování; úloha batohu; heuristika |
| Thesis title: | The multiple knapsack problem |
|---|---|
| Author: | Černý, Vít |
| Thesis type: | Bachelor thesis |
| Supervisor: | Kalčevová, Jana |
| Opponents: | Suchánková, Tereza |
| Thesis language: | Česky |
| Abstract: | The knapsack problem is one of the classical operations research problems. It belongs to the category of integer linear programming problems and is most often formulated as a binary problem. This thesis describes different categories of the problem and also some methods for finding their solution. Although there are precise algorithms for finding reliable optimal solution, some of the knapsack problems are so large that it would be impossible to follow the exact algorithms. Therefore, more complex knapsack problems belong to the complexity class of NP-complete. Yet there are a variety of heuristics and methods developed, which can lead to a sufficiently good solution in a relatively short time and relatively simple way. This paper focuses particularly on one of the problems described, the multiple knapsack problem. It is showed on a practical example how the problem can be solved. |
| Keywords: | heuristic; knapsack problem; binary programming |
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: | 5. 10. 2010 |
|---|---|
| Date of submission: | 10. 8. 2011 |
| Date of defense: | 25. 8. 2011 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/27804/podrobnosti |