Original title: Vícerozměrná úloha batohu
Translated title: The Multi-Dimensional Knapsack Problem
Authors: Ficová, Pavla ; Kalčevová, Jana (advisor) ; Černohous, Roman (referee)
Document type: Bachelor's theses
Year: 2009
Language: cze
Publisher: Vysoká škola ekonomická v Praze
Abstract: [cze] [eng]
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. 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: Balas Method; Bee Colony Algorithm; Hypercube Algorithm; integral programming; knapsack problem; Balasova metoda; celočíselné programování; metoda hypercube; metoda včelího úlu; ú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/21453

Permalink: http://www.nusl.cz/ntk/nusl-17423


The record appears in these collections:
Universities and colleges > Public universities > University of Economics, Prague
Academic theses (ETDs) > Bachelor's theses