Praktická aplikace hromadné bivalentní úlohy batohu
| Název práce: | Praktická aplikace hromadné bivalentní úlohy batohu |
|---|---|
| Autor(ka) práce: | Černý, Vít |
| Typ práce: | Bakalářská práce |
| Vedoucí práce: | Kalčevová, Jana |
| Oponenti práce: | Suchánková, Tereza |
| Jazyk práce: | Česky |
| Abstrakt: | Úloha batohu je jednou z klasických úloh operačního výzkumu. Patří do kategorie celočíselných úloh lineárního programování, nejčastěji je formulována jako binární úloha. V této bakalářské práci jsou popsány jednotlivé kategorie úlohy a také některé metody vedoucí k nalezení řešení takových úloh. Ačkoli existují přesné algoritmy pro spolehlivé nalezení optimálního řešení, některé úlohy batohu jsou tak rozsáhlé, že výpočet pomocí exaktních algoritmů by nebylo možné realizovat. Z toho důvodu jsou složitější úlohy batohu řazeny do kategorie NP-úplné. Proto bylo vytvořeno několik heuristik a metod, které mohou vést k dostatečně dobrému řešení v relativně krátkém čase a poměrně jednoduchým způsobem. Tato práce se zaměřuje zejména na jednu z popisovaných úloh, na hromadnou bivalentní úlohu batohu. Na praktickém příkladě ukazuje, jak je možné tento problém řešit. |
| Klíčová slova: | bivalentní programování; úloha batohu; heuristika |
| Název práce: | The multiple knapsack problem |
|---|---|
| Autor(ka) práce: | Černý, Vít |
| Typ práce: | Bachelor thesis |
| Vedoucí práce: | Kalčevová, Jana |
| Oponenti práce: | Suchánková, Tereza |
| Jazyk práce: | Česky |
| Abstrakt: | The knapsack problem is one of the classical operations research problems. It belongs to the category of integer linear programming problems and is most often formulated as a binary problem. This thesis describes different categories of the problem and also some methods for finding their solution. Although there are precise algorithms for finding reliable optimal solution, some of the knapsack problems are so large that it would be impossible to follow the exact algorithms. Therefore, more complex knapsack problems belong to the complexity class of NP-complete. Yet there are a variety of heuristics and methods developed, which can lead to a sufficiently good solution in a relatively short time and relatively simple way. This paper focuses particularly on one of the problems described, the multiple knapsack problem. It is showed on a practical example how the problem can be solved. |
| Klíčová slova: | heuristic; knapsack problem; binary programming |
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: | 5. 10. 2010 |
|---|---|
| Datum podání práce: | 10. 8. 2011 |
| Datum obhajoby: | 25. 8. 2011 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/27804/podrobnosti |