Practical application of change-making problem
| Thesis title: | Praktická aplikace change-making problemu |
|---|---|
| Author: | Jindrová, Karolína |
| Thesis type: | Bakalářská práce |
| Supervisor: | Sekničková, Jana |
| Opponents: | Hanousek, Jakub |
| Thesis language: | Česky |
| Abstract: | Change-making problém je jednou z nejjednodušších úloh celočíselného lineárního programování a spadá do kategorie úloh batohu. Cílem této bakalářské práce je využít change-making problém k vyřešení tří různých úloh, na kterých je ukázáno, jak lze tento problém řešit. První úloha se zabývá nalezením optimálního řešení ve hře šipek. Toto optimální řešení je spočteno pomocí softwaru MPL for Windows a následně je porovnáváno s řešením získaným pomocí greedy algoritmu, které ale již nemusí být optimální. Druhá úloha ilustruje, jakým způsobem mohou fungovat bankomaty, a optimalizace je opět provedena v softwaru MPL for Windows. Třetí úloha se zaměřuje na to, jak lze change-making problém využít pro optimalizaci časového rozvržení práce servisního technika plynových spotřebičů. Pro optimalizaci je sestavena jednoduchá aplikace v prostředí MS Excel, která k optimalizaci využívá vestavěného řešitele. Na základě výsledků optimalizace je sestaven týdenní rozvrh práce servisního technika, který je aplikován v praxi. Reálný průběh práce technika je zaznamenán a následně jsou oba pracovní rozvrhy mezi sebou porovnány. |
| Keywords: | celočíselné lineární programování; úloha batohu; change-making problém; greedy algoritmus |
| Thesis title: | Practical application of change-making problem |
|---|---|
| Author: | Jindrová, Karolína |
| Thesis type: | Bachelor thesis |
| Supervisor: | Sekničková, Jana |
| Opponents: | Hanousek, Jakub |
| Thesis language: | Česky |
| Abstract: | The change-making problem is one of the simplest linear integer programming problems and falls into the category of the so-called "knapsack problems". The aim of this bachelor thesis is to use the change-making problem to solve three different tasks, which demonstrates how to solve the change-making problem. The first task aims to find an optimal solution in~a~game of darts. The optimal solution is calculated with the help of the MPL for Windows software and is subsequently being compared with the solution found with the help of the greedy algorithm which, on the other hand, is not necessarily optimal. The second task demonstrates the way ATMs can potentially work and the optimization is once again being carried out with the assistance of the MPL for Windows software. The third task focuses on how the change-making problem can be used to optimize the work schedule of a gas appliance service technician. For the purpose of optimization, a simple application that uses a built-in solver is created in MS Excel. Based on the results, a weekly work schedule of~a~service technician is put together and then used in practice. The actual work schedule of the technician is being monitored and both of the schedules are subsequently compared. |
| Keywords: | knapsack problems; linear integer programming; change-making problem; greedy algorithm |
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: | 16. 3. 2022 |
|---|---|
| Date of submission: | 29. 6. 2022 |
| Date of defense: | 25. 8. 2022 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/80287/podrobnosti |