The multiple knapsack problem in use
| Thesis title: | Praktická aplikace hromadné úlohy batohu |
|---|---|
| Author: | Procházková, Lucie |
| Thesis type: | Bakalářská práce |
| Supervisor: | Sekničková, Jana |
| Opponents: | Suchánková, Tereza |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | hromadná úloha batohu; celočíselné programování; úloha batohu |
| Thesis title: | The multiple knapsack problem in use |
|---|---|
| Author: | Procházková, Lucie |
| Thesis type: | Bachelor thesis |
| Supervisor: | Sekničková, Jana |
| Opponents: | Suchánková, Tereza |
| Thesis language: | Česky |
| Abstract: | 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; multiple knapsack problem; knapsack problem |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Type of study programme: | Bakalářský studijní program |
| Assigned degree: | Bc. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 20. 10. 2011 |
|---|---|
| Date of submission: | 9. 5. 2012 |
| Date of defense: | 20. 6. 2012 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/33794/podrobnosti |