Vícerozměrná úloha batohu
Název práce: | Vícerozměrná úloha batohu |
---|---|
Autor(ka) práce: | Ficová, Pavla |
Typ práce: | Bakalářská práce |
Vedoucí práce: | Kalčevová, Jana |
Oponenti práce: | Černohous, Roman |
Jazyk práce: | Česky |
Abstrakt: | 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. |
Klíčová slova: | metoda včelího úlu; metoda hypercube; úloha batohu; celočíselné programování; Balasova metoda |
Název práce: | The Multi-Dimensional Knapsack Problem |
---|---|
Autor(ka) práce: | Ficová, Pavla |
Typ práce: | Bachelor thesis |
Vedoucí práce: | Kalčevová, Jana |
Oponenti práce: | Černohous, Roman |
Jazyk práce: | Česky |
Abstrakt: | 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. |
Klíčová slova: | Bee Colony Algorithm; Balas Method; integral programming; knapsack problem; Hypercube Algorithm |
Informace o studiu
Studijní program / obor: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
---|---|
Typ studijního programu: | Bakalářský studijní program |
Přidělovaná hodnost: | Bc. |
Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
Fakulta: | Fakulta informatiky a statistiky |
Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
Datum zadání práce: | 15. 12. 2009 |
---|---|
Datum podání práce: | 17. 5. 2010 |
Datum obhajoby: | 8. 6. 2010 |
Identifikátor v systému InSIS: | https://insis.vse.cz/zp/23709/podrobnosti |