Detail předmětu

Optimalizační metody II

FSI-VPP-AAk. rok: 2026/2027

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ů.

Jazyk výuky

angličtina

Počet kreditů

7

Příslušnost k typu studijního programu

magisterský navazující

Garant předmětu

doc. Ing. Jakub Kůdela, Ph.D.

Zajišťuje ústav

Ústav automatizace a informatiky (ÚAI)

Nabízen zahraničním studentům

Všech fakult

Vstupní znalosti

Znalosti základů programování, matematické analýzy, algebry, teorie množin, statistiky a pravděpodobnosti.

Způsob zakončení předmětu a pravidla hodnocení studentů

Požadavky pro zápočet: Aktivní účast na cvičeních, zpracování zadaného projektu. Zkouška: Písemná a ústní.
Účast na cvičeních je povinná. Zameškaná výuka může být nahrazena zpracováním zadaných úloh.

Učební cíle

Seznámit posluchače s přístupy k tvorbě a s aplikacemi matematických metod pro optimální řízení procesů technologických a ekonomických, uplatnitelných například v automatizaci strojírenství, v ekonomickém řízení strojírenské výroby, v projektovém řízení a v optimalizaci informačních systémů při využívání soudobých prostředků informatiky, a seznámit se s podílem informatiky na zdokonalování těchto metod a přístupů.
Znalosti: Znát základní principy a algoritmy metod, použitelných k optimalizaci deterministických a stochastických procesů diskrétních a spojitých. Znát základní principy a algoritmy metod, které jsou podstatou systémů na podporu rozhodování o projektech z hlediska jejich identifikace, výběru, průběhu a realizace. Dovednosti: Umět tyto metody používat k řešení praktických problémů z oblasti ekonomického rozhodování, ve zvyšování spolehlivosti technických zařízení, v automatizovaném řízení technologických procesů a v projektovém řízení s využitím soudobých prostředků informatiky.

Základní literatura

Bazaraa, M, S.; Sherali, H. D.; Shetty, C. M.: Nonlinear Programming. Wiley, 2013. (EN)
Bertsekas, D. P.: Dynamic Programming and Optimal Control: Vol. I. Athena Scientific, Nashua. 2017. (EN)
Brucker, P.: Scheduling Algorithms. Springer-Verlag, Berlin, 2010. (EN)
Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, 2014. (EN)
Martí, R. Pardalos, P.M., Resende, M.G.C.: Handbook of Heuristics. Springer Cham, 2025. (EN)
Luke, S.: Essentials of Metaheuristics: A Set of Undergraduate Lecture Notes. Lulu.com, 2016. (EN)
Puterman, M. L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience, New Jersey, 2005. (EN)

Doporučená literatura

Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B.: Network Flows. Prentice Hall, Upper Saddle River, New Jersey, 1993. (EN)
Bertsekas, D. P.: Dynamic Programming and Optimal Control: Vol. II: Approximate Dynamic Programming. Athena Scientific, Nashua. 2012. (EN)
Boyd, S; Vandenberghe, L.: Convex Optimization. Cambridge University Press, 2004. (EN)
Kerzner, H.: Project Management: A Systems Approach to Planning, Scheduling, and Controlling. Wiley, New Jersey, 2009. (EN)
Pinedo, M. L.: Scheduling: Theory, Algorithms, and Systems. Springer-Verlag, Cham, 2016. (EN)
Winston W.L.: Operations Research. Applications and Algorithms. Thomson - Brooks/Cole, Belmont 2004. (EN)

Zařazení předmětu ve studijních plánech

  • Program N-AIŘ-P magisterský navazující 2 ročník, zimní semestr, povinný

  • Program C-AKR-P celoživotní vzdělávání v akr. stud. programu

    specializace CZS , 1 ročník, zimní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

doc. Ing. Jakub Kůdela, Ph.D.

Osnova

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

Cvičení s počítačovou podporou

26 hod., povinná

Vyučující / Lektor

Mgr. Jakub Fišák, Ph.D.

Osnova

Implementace a analýza následujících problémů:
1. - 3. Základní úlohy dynamického programování.
4. Problémy se zpožděním.
5. Viterbiho algoritus pro dekódování konvolučních kódů.
6. Problémy hledání nejkratší cesty.
7. Vícekriteriální problémy.
8. LQR.
9. Problémy s nekonečným horizontem.
10. Problémy ve spojitém čase.
11. Evoluční strategie pro problém weighted MAX-SAT.
12. Genetické algoritmy a optimalizace mravenčí kolonií pro úlohu TSP.
13. Problémy rozvrhování výrobních procesů.