Generalized assignment problem
| Thesis title: | Zobecněná hromadná úloha batohu |
|---|---|
| Author: | Kocourková, Markéta |
| Thesis type: | Bakalářská práce |
| Supervisor: | Sekničková, Jana |
| Opponents: | Nečas, Dalibor |
| Thesis language: | Česky |
| Abstract: | Tématem této práce je zobecněná úloha batohu. Všeobecně problém batohu patří mezi základní úlohy lineárního programování a spadá do kategorie úloh celočíselných. Velice často je formulována jako úloha binární neboli 0-1. Problém batohu, který je v angličtině znám pod názvem The Knapsack Problem, uvažuje několik typů úloh, které budou v této bakalářské práci představeny. Některé úlohy batohu jsou tak rozsáhlé, že i přes existenci algoritmů vedoucích k optimálnímu řešení, jsou spíše využívány různé heuristiky, které sice k výsledku dojdou dříve, ale již nejsou tak přesné. Proto jsou některé úlohy řazeny do NP-těžkých úloh. Tato práce je zaměřena konkrétně na zobecněnou hromadnou úlohu batohu. Na praktickém příkladě bude ukázáno, kde je možné tuto úlohu využít. |
| Keywords: | zobecněná hromadná úloha batohu; celočíselné programování; úloha batohu |
| Thesis title: | Generalized assignment problem |
|---|---|
| Author: | Kocourková, Markéta |
| Thesis type: | Bachelor thesis |
| Supervisor: | Sekničková, Jana |
| Opponents: | Nečas, Dalibor |
| Thesis language: | Česky |
| Abstract: | The generalized assignment problem is a topic of this thesis. The knapsack problem in general belongs to among classical operation research problems and belongs to the category of integer linear programming. It is very often formulated as a binary problem or 0-1. There are several types of knapsack problems which are described in this thesis. Some of the knapsack problems are so large and although exist exact algorithms for finding optimal solution, heuristics are rather used. They are not so exact but they find solution much earlier. Therefore some of the knapsack problems belong to NP-hard problems. This thesis is focused on one type particularly, the generalized assignment problem, which is demonstrated on practical example how the problem can be used. |
| Keywords: | integer programming; the knapsack problem ; generalized assignment 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: | 3. 1. 2012 |
|---|---|
| Date of submission: | 9. 5. 2012 |
| Date of defense: | 20. 6. 2012 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/35343/podrobnosti |