Multidimensional Knapsack Problem
| Thesis title: | Vícerozměrná úloha batohu |
|---|---|
| Author: | Cibulka, Adam |
| Thesis type: | Bakalářská práce |
| Supervisor: | Sekničková, Jana |
| Opponents: | Čížků, Andrea |
| Thesis language: | Česky |
| Abstract: | Práce se zaměřuje na často používanou aplikaci kombinatorické optimalizace, na úlohu batohu. Cílem úlohy batohu je rozhodnout, jaké položky, případně v jakém počtu a na jaké místo, umístit do omezeného prostoru tak, aby výsledné umístění přineslo co nejvyšší užitek. Z hlediska charakteru spadá tato úloha mezi úlohy celočíselné, a proto může být nalezení výsledku složité, hlavně při aplikaci úlohy na větší rozměry. U úloh jednorozměrných, dvourozměrných i vícerozměrných je matematický model závislý též na maximálním počtu daných předmětů, což úlohy dále rozlišuje a komplikuje. Existuje mnoho způsobů, jak tento typ úloh klasifikovat a následně řešit. Navíc se stále vyvíjejí nové postupy optimalizace. Cílem této práce bude úlohy batohu obecně kategorizovat, popsat včetně jejich reálného použití a formulovat jejich ekonomické a matematické modely. Hlavním cílem je vytvoření aplikace umožňující uživateli snadné zadání problému a nalezení optimálního řešení vícerozměrné úlohy batohu, jedné z typů úloh batohu, která je oproti té klasické rozšířená o další dimenzi. |
| Keywords: | Kombinatorická optimalizace; Dvourozměrná úloha batohu; Lineární programování; Vícerozměrná úloha batohu; Python |
| Thesis title: | Multidimensional Knapsack Problem |
|---|---|
| Author: | Cibulka, Adam |
| Thesis type: | Bachelor thesis |
| Supervisor: | Sekničková, Jana |
| Opponents: | Čížků, Andrea |
| Thesis language: | Česky |
| Abstract: | This paper focuses on a frequently used application of combinatorial optimization, the knapsack problem. The goal of the knapsack problem is to decide which items, potentially in what number and location, to place in a bounded space so that the resulting placement yields the highest utility. Due to the nature of this problem, it is an integer problem and therefore finding the result can be difficult, especially when applying the problem to larger dimensions. For one-dimensional, two-dimensional and multi-dimensional problems, the mathematical model is also dependent on the maximum number of objects given, which further differentiates and complicates the problem. There are many ways to classify and subsequently solve this type of problems. In addition, new optimization techniques are constantly being developed. The goal of this paper will be to categorize knaspacking problems in general, describe them including their real-world applications, and formulate their economic and mathematical models. The main objective is to create an application that allows the user to easily define the problem and find the optimal solution to a multidimensional knapsack problem, one of the types of knapsack problems that is extended by an additional dimension compared to the traditional one. |
| Keywords: | Combinatorial optimization; Two-dimensional knapsack problem; Multidimensional knapsack problem; Python; Linear programming |
Information about study
| Study programme: | Aplikovaná informatika/Aplikovaná informatika |
|---|---|
| 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: | 17. 3. 2022 |
|---|---|
| Date of submission: | 8. 5. 2022 |
| Date of defense: | 24. 6. 2022 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/80301/podrobnosti |