Original title:
Optimální složení potravin pro výlet do hor
Translated title:
Optimal composition of groceries for mountain trip
Authors:
Fesenko, Anastasiya ; Kalčevová, Jana (advisor) ; Flusserová, Lenka (referee) Document type: Bachelor's theses
Year:
2010
Language:
cze Publisher:
Vysoká škola ekonomická v Praze Abstract:
[cze][eng] Tato práce je zaměřená na aplikaci úlohy batohu - na praktický příklad balení potravin pro výlet do hor. Úloha batohu je jedním z problémů celočíselného programování. Toto programování je založené na modelech, ve kterých proměnné mohou nabývat pouze celočíselných hodnot. Řešení celočíselných úloh je většinou výpočetně velmi náročné. Proto byly vymyšlené speciální algoritmy, které jsou schopné nalézt celočíselné řešení takové úlohy, například: metoda větvení a mezí, Balasova metoda atd. Takové algoritmy jsou popsány v první části této práce. Při psaní je kladen velký důraz na použitelnost výsledků v praxi. Proto pro dosažení větší aplikovatelnosti je praktická úloha řešena z několika různých pohledů, a v každé variantě řešení jsou stanovené různé cíle. Výsledky každé varianty jsou interpretovány, veškeré odlišnosti jsou vysvětleny.This work is aimed towards the application of knapsack problem in practical example of packing of groceries for mountain trip. The knapsack problem is one of the tasks of integral programming; those are the models that can only variably accept the integral value. The solutions of integral tasks are usually very meticulous. That is why for their solution special algorithms were created, which are capable of discovering an integral solution of such tasks, for example, branch and bound method, Balas method etc. These types of algorithms are defined in the first part of this work. While writing this thesis a considerable emphasis was put into application of its result in practice. Hence, for achieving applicability practical tasks are solved from various angles and therefore various aims have been set forth in each solution option. The results of each option are interpreted and then the differences are explained.
Keywords:
Balas method; Branch and Bound method; integral programming; knapsack problem; Balasova metoda; celočíselné programování; metoda větvení a mezí; ú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/23671