Original title: Praktická aplikace hromadné úlohy batohu
Translated title: The multiple knapsack problem in use
Authors: Procházková, Lucie ; Sekničková, Jana (advisor) ; Suchánková, Tereza (referee)
Document type: Bachelor's theses
Year: 2011
Language: cze
Publisher: Vysoká škola ekonomická v Praze
Abstract: [cze] [eng]
V oblasti celočíselných úloh lineárního programování se nachází úloha batohu včetně jejích modifikací. Mezi ně patří i hromadná úloha batohu, jež je předmětem této práce. V souvislosti s interpretací výsledků je nutné úlohu batohu rozšířit o celočíselné podmínky, které jsou nejčastěji transformovány na podmínky bivalentní. Tato skutečnost značně zvyšuje výpočetní náročnost těchto úloh. I přes to, že pro řešení existují exaktní algoritmy, často je při výpočtu některých rozsáhlých úloh není možné použít. Přibližného a dostatečně přesného výsledku lze dosáhnout pomocí heuristik a dalších metod, které byly k tomuto účelu vytvořené. Jednotlivé podkapitoly v první části práce blíže popisují variace úlohy batohu, přičemž druhá část na ně navazuje a představuje některé možné využití v praxi. In the area of integer linear programming problems is placed the knapsack problem, including its modifications. Among them is the multiple knapsack problem which is the subject of this thesis. In connection with the interpretation of results is necessary to extend the knapsack problem to integer conditions that are most often transformed into a bivalent conditions. This greatly increases the computational complexity of these tasks. Despite the fact that solutions exist for the exact algorithms, often in the calculation of some large problems can not be used. Approximate and sufficiently accurate results can be achieved by using heuristics and other techniques that have been created for this purpose. Subchapters in the first part further describe the variation of the knapsack problem, in the second part subchapters followed, and present some possible use in practice.
Keywords: integer programing; knapsack problem; multiple knapsack problem; celočíselné programování; hromadná úloha batohu; ú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/32587

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


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