Dynamické programování
Dynamické programování (DP) je metodika pro řešení vícestupňových rozhodovacích úloh, které lze rozdělit na dílčí podúlohy. Každá podúloha je řešena jednou a její výsledek je uložen pro další využití. Využívá principu optimality a rekurzivní struktury problému.
- Vhodné pro TSP, VRP s malým počtem zákazníků, batohové problémy, řízení zásob.
- Poskytuje přesné řešení pomocí postupného budování tabulek (bottom-up).
- Redukuje počet výpočtů díky uchovávání mezivýsledků.
- Jednoduché pro pochopení a implementaci u menších úloh.
Zajímavosti a praktická využití
- Používá se při výuce jako příklad optimalizačního přístupu.
- Využívá se v teorii zásob, plánování výroby nebo bioinformatice.
- V moderních řešeních je často integrováno jako dílčí procedura.
Omezení a limity
Hlavním omezením DP je extrémně vysoká paměťová náročnost a výpočetní čas při větších instancích. Komplexita často roste exponenciálně s počtem stavů, což omezuje praktické použití na velmi malé nebo speciálně strukturované problémy.
Shrnutí
Dynamické programování je silný exaktní nástroj, který umožňuje efektivní řešení rekurzivních úloh. I když není vhodný pro velké VRP, tvoří důležitý základ mnoha algoritmů a je ideální pro pochopení principu dekompozice problémů.
Zdroje:
[1] Winston, W. L. (2004). Operations Research: Applications and Algorithms (4th ed.). Belmont, CA: Thomson/Brooks/Cole.
[2] Doležal, J., Fiala, P. (2012). Operační výzkum: Příklady a úlohy. Praha: Oeconomica – Nakladatelství VŠE.
[3] Závodný, K. (2016). Operační výzkum. Praha: ČZU.
Důležité odkazy
Kontakt
List Title
- kvetapapouskova@gmail.com
- Univerzitní 22, 306 14 Plzeň