Original title:
Praktické řešení úlohy batohu
Translated title:
Knapsack problem
Authors:
Šemnická, Eliška ; Kalčevová, Jana (advisor) ; Šmídová, Milada (referee) Document type: Bachelor's theses
Year:
2008
Language:
cze Publisher:
Vysoká škola ekonomická v Praze Abstract:
[cze][eng] Práce seznamuje čtenáře s problematikou celočíselných úloh a metodou řešení těchto úloh. Ze speciálních celočíselných úloh je popsán přiřazovací problém, úloha o pokrytí a okružní dopravní problém. Jako metoda výpočtu je popsána metoda autorek Lang a Doig. Následuje podrobnější popis úlohy batohu a jejích typů. Dále se čtenář dočte o metodě pro řešení ryze bivalentních úloh, konkrétně o Balasově metodě, pro kterou je uveden algoritmus pro minimalizační účelovou funkci. V práci je uveden vlastní příklad z oblasti optimálního složení finančního portfolia, který je formulován jako úloha batohu a řešen Balasovou metodou.In the study are described integer programming, particular problems, as assignment problem, cover problem and city transportation problem, and method of solving these kinds of problems. It is depictured Lang and Doig method. Then is described knapsack problem and its types. A reader can find a method for solving zero-to-one problems, especially Balas method for minimisation of a target function. There is introduced a financial problem of optimisation portfolio in the study which is formulated as a zero-to-one problem and solved by Balas method.
Keywords:
Balas method; integer programming; zero-to-one programming; Balasova metoda; bivalentní programování; celočíselné programování
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/10090