Název:
Řešení celočíselných úloh pomocí dynamického programování
Překlad názvu:
Solving of integer problems by dynamic programming
Autoři:
Polonyankina, Tatiana ; Kalčevová, Jana (vedoucí práce) ; Lagová, Milada (oponent) Typ dokumentu: Bakalářské práce
Rok:
2010
Jazyk:
cze
Nakladatel: Vysoká škola ekonomická v Praze
Abstrakt: [cze][eng] 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.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:
dynamické programování; Lagrangeovy multiplikátory; princip optimality; dynamic programming; Lagrange multipliers; principle of optimality
Instituce: Vysoká škola ekonomická v Praze
(web)
Informace o dostupnosti dokumentu:
Dostupné v digitálním repozitáři VŠE. Původní záznam: http://www.vse.cz/vskp/eid/21423