Solving of integer problems by dynamic programming
| Thesis title: | Řešení celočíselných úloh pomocí dynamického programování |
|---|---|
| Author: | Polonyankina, Tatiana |
| Thesis type: | Bakalářská práce |
| Supervisor: | Kalčevová, Jana |
| Opponents: | Lagová, Milada |
| Thesis language: | Česky |
| Abstract: | Název práce: Řešení celočíselných úloh pomocí dynamického programování Autor: Tatiana Polonyankina Katedra: Katedra ekonometrie Vedoucí práce: Mgr. Jana Kalčevová, Ph. D. Optimalizační úlohy s celočíselnými požadavky na proměnné se v praktickém životě vyskytují často. Bohužel hledání optimálního řešení takových problémů je mnohokrát početně velice náročné. V práci je popsáno několik možných algoritmů řešení lineárních celočíselných úloh. Déle je čtenář seznámen s metodou dynamického programování a principem optimality. Ten je demonstrován na praktickém příkladu úlohy batohu, kde je výpočet proveden tabulkovou metodou. Cílem práce je aplikovat poznatky z použití dynamického programování na typickou lineární celočíselnou úlohu, konkrétně na úlohu o dělení materiálu, a tím ukázat další z algoritmů výpočtu celočíselných úloh. Hledání optimálního celočíselného řešení je provedeno dvěma způsoby a to: klasickou tabulkovou metodou a zjednodušenou tabulkovou metodou s použitím Lagrangeových multiplikátorů. V závěru jsou shrnuté výhody a nevýhody této výpočetní techniky. |
| Keywords: | Lagrangeovy multiplikátory; dynamické programování; princip optimality |
| Thesis title: | Solving of integer problems by dynamic programming |
|---|---|
| Author: | Polonyankina, Tatiana |
| Thesis type: | Bachelor thesis |
| Supervisor: | Kalčevová, Jana |
| Opponents: | Lagová, Milada |
| Thesis language: | Česky |
| Abstract: | Optimalization problems with integer requirements on the variables occurs in real life very often. Unfortunately, finding optimal solutions to such problems are often numerically very difficukt. The work describes several possible algorithms for solving linear integer problems. The reader is also familiarized with the method of dynamic programming and the principle of optimality. This is demonstrated in a practical example of a knapsack model where the calculation is done using tables. The goal of this work is to apply the knowledge from the application of dynamic programming on a typical linear integer problems, namely on the problem of material separation, and thus show the algorithm of calculating integer problems. Finding the optimal integer solution is accomplished in two ways: by the classical method of spreadsheet tables and by the simplified method of using Lagrange multipliers. In the conclusion there are summarized the advantages and disadvantages of solving technic. |
| Keywords: | principle of optimality; dynamic programming; Lagrange multipliers |
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: | 25. 2. 2010 |
|---|---|
| Date of submission: | 17. 5. 2010 |
| Date of defense: | 8. 6. 2010 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/25195/podrobnosti |