Řešení celočíselných úloh pomocí dynamického programování
| Název práce: | Řešení celočíselných úloh pomocí dynamického programování |
|---|---|
| Autor(ka) práce: | Polonyankina, Tatiana |
| Typ práce: | Bakalářská práce |
| Vedoucí práce: | Kalčevová, Jana |
| Oponenti práce: | Lagová, Milada |
| Jazyk práce: | Česky |
| Abstrakt: | 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. |
| Klíčová slova: | Lagrangeovy multiplikátory; dynamické programování; princip optimality |
| Název práce: | Solving of integer problems by dynamic programming |
|---|---|
| Autor(ka) práce: | Polonyankina, Tatiana |
| Typ práce: | Bachelor thesis |
| Vedoucí práce: | Kalčevová, Jana |
| Oponenti práce: | Lagová, Milada |
| Jazyk práce: | Česky |
| Abstrakt: | 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. |
| Klíčová slova: | principle of optimality; dynamic programming; Lagrange multipliers |
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: | 25. 2. 2010 |
|---|---|
| Datum podání práce: | 17. 5. 2010 |
| Datum obhajoby: | 8. 6. 2010 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/25195/podrobnosti |