Optimalizační metody II (FSI-VPP-A)

Akademický rok 2025/2026
Garant: doc. Ing. Jakub Kůdela, Ph.D.  
Garantující pracoviště: ÚAI všechny předměty garantované tímto pracovištěm
Jazyk výuky: angličtina
Typ předmětu: oborový předmět
Cíle předmětu:
 
Výstupy studia a kompetence:
 
Prerekvizity:
 
Obsah předmětu (anotace):

Dynamické programování a optimální řízení stochastických procesů. Bellmanův princip optimality jako nástroj optimalizace víceetapových procesů s obecně nelineární kriteriální funkcí. Strategie optimálního rozhodování. Výpočetní aspekty dynamického programování v diskrétním čase. Skryté Markovovy modely a Viterbi algoritmus. Algoritmy pro hledání nejkratších cest v grafu. Vícekriteriální úlohy optimálního řízení a úlohy s omezeními. Deterministické optimální řízení ve spojitém čase, Hamilton-Jacobi-Bellman rovnice, Pontrjaginův princip maxima. LQR a Kalmanův filtr. Plánování a rozvrhování procesů. Problémy s nekonečným počtem etap. Příbližné dynamické programování. Heuristické metody pro složité úlohy.  Aplikace metod v řešení praktických problémů z oblasti ekonomického rozhodování a v řízení technologických procesů.
Metody vyučování:
 
Způsob a kritéria hodnocení:
 
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky:
 
Typ (způsob) výuky:
    Přednáška  13 × 3 hod. nepovinná                  
    Cvičení s počítačovou podporou  13 × 2 hod. povinná                  
Osnova:
    Přednáška

1. Základy matematické teorie procesů. Bellmanův princip optimality a dynamické programování.
2. Minimax (robustní) formulace. Reformulace a rozšiřování stavového prostoru.
3. Deterministické konečněstavové úlohy. Dopředný algoritmus dynamického programování.
4. Skryté Markovovy modely a Viterbi algoritmus.
5. Algoritmy pro hledání nejkratších cest v grafu.
6. Vícekriteriální úlohy optimálního řízení a úlohy s omezeními.
7. LQR a Kalmanův filtr.
8. Problémy s nekonečným počtem etap.
9. Deterministické optimální řízení ve spojitém čase, Hamilton-Jacobi-Bellman rovnice, Pontrjaginův princip maxima.
10. Rozvrhování výrobních procesů.
11. Příbližné dynamické programování.
12. Prediktivní řízení.
13. Heuristiky pro složité úlohy - genetické algoritmus a optimalizace mravenčí kolonií.
    Cvičení s počítačovou podporou

Cvičení navazuje na látku probranou na přednášce. Hlavní důraz je kladen na softwarovou implementaci probíraných metod.
Literatura - základní:
1. Bertsekas, D. P.: Dynamic Programming and Optimal Control: Vol. I. Athena Scientific, Nashua. 2017.
2. Puterman, M. L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience, New Jersey, 2005.
3. Brucker, P.: Scheduling Algorithms. Springer-Verlag, Berlin, 2010.
4. Bazaraa, M, S.; Sherali, H. D.; Shetty, C. M.: Nonlinear Programming. Wiley, 2013.
5. Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, 2014.
6. Martí, R. Pardalos, P.M., Resende, M.G.C.: Handbook of Heuristics. Springer Cham, 2018.
Literatura - doporučená:
1. Bertsekas, D. P.: Dynamic Programming and Optimal Control: Vol. II: Approximate Dynamic Programming. Athena Scientific, Nashua. 2012.
2. Pinedo, M. L.: Scheduling: Theory, Algorithms, and Systems. Springer-Verlag, Cham, 2016.
3. Kerzner, H.: Project Management: A Systems Approach to Planning, Scheduling, and Controlling. Wiley, New Jersey, 2009.
4. Winston W.L.: Operations Research. Applications and Algorithms. Thomson - Brooks/Cole, Belmont 2004.
5. Boyd, S; Vandenberghe, L.: Convex Optimization. Cambridge University Press, 2004.
6. Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B.: Network Flows. Prentice Hall, Upper Saddle River, New Jersey, 1993.
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
C-AKR-P prezenční studium CZS Předměty zimního semestru -- zá,zk 5 Volitelný 1 1 Z
N-AIŘ-P prezenční studium --- bez specializace -- zá,zk 5 Povinný 2 2 Z