Original title:
Praktická aplikace hromadné bivalentní úlohy batohu
Translated title:
The multiple knapsack problem
Authors:
Černý, Vít ; Kalčevová, Jana (advisor) ; Suchánková, Tereza (referee) Document type: Bachelor's theses
Year:
2010
Language:
cze Publisher:
Vysoká škola ekonomická v Praze Abstract:
[cze][eng] Ú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.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:
binary programming; heuristic; knapsack problem; bivalentní programování; heuristika; úloha batohu
Institution: University of Economics, Prague
(web)
Document availability information: Available in the digital repository of the University of Economics, Prague. Original record: http://www.vse.cz/vskp/eid/28395