Detail předmětu

Optimalizační metody II

FSI-VPP-AAk. rok: 2027/2028

Předmět se zabývá matematickými a výpočetními metodami pro optimalizaci vícestupňových rozhodovacích procesů, optimální řízení a řešení složitých inženýrských optimalizačních úloh. Základ tvoří Bellmanův princip optimality a dynamické programování v diskrétním čase, včetně deterministických a stochastických úloh s konečným i nekonečným horizontem. Probírány jsou algoritmy nejkratších cest, skryté Markovovy modely a Viterbiho algoritmus, vícekriteriální optimalizace a optimalizace s omezeními.

Další část předmětu je věnována optimálnímu řízení ve spojitém čase, Hamiltonově–Jacobiho–Bellmanově rovnici, Pontrjaginovu principu maxima, lineárně kvadratickému řízení (LQR), Kalmanovu filtru a prediktivnímu řízení. Pozornost je věnována také přibližnému dynamickému programování a heuristickým optimalizačním metodám, zejména evolučním strategiím, genetickým algoritmům a optimalizaci mravenčími koloniemi.

Počítačová cvičení se zaměřují na formulaci matematických modelů, implementaci vybraných algoritmů, jejich experimentální vyhodnocování a interpretaci výsledků. Praktické úlohy zahrnují rozhodovací procesy, optimalizaci cest v grafech, řízení dynamických systémů a kombinatorické optimalizační problémy včetně rozvrhování výrobních procesů.

Jazyk výuky

angličtina

Počet kreditů

7

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

magisterský navazující

Nabízen zahraničním studentům

Všech fakult

Vstupní znalosti

Předpokládá se znalost základů programování, zejména práce s proměnnými, datovými strukturami, funkcemi a řídicími příkazy, a schopnost samostatně implementovat a testovat jednoduché algoritmy.

Z matematických disciplín jsou požadovány základy lineární algebry (vektory, matice, soustavy lineárních rovnic), matematické analýzy (diferenciální a integrální počet, funkce více proměnných), teorie množin, pravděpodobnosti a statistiky. Student by měl být schopen formulovat jednoduchou matematickou optimalizační úlohu a interpretovat její řešení.

Znalost základních principů matematické optimalizace a modelování dynamických systémů je výhodou.

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

Po úspěšném absolvování předmětu student:

  1. Formuluje deterministické a stochastické vícestupňové rozhodovací úlohy, identifikuje jejich stavy, rozhodnutí, přechody, účelové funkce a omezení a navrhne vhodný matematický model.

  2. Odvodí a použije Bellmanovy rekurzivní vztahy a implementuje vybrané algoritmy dynamického programování, včetně algoritmů pro hledání nejkratších cest a Viterbiho algoritmu.

  3. Analyzuje rozhodovací problémy s konečným a nekonečným horizontem, porovná přesné a přibližné postupy dynamického programování a posoudí jejich výpočetní náročnost a omezení.

  4. Vysvětlí a aplikuje vybrané principy optimálního řízení v diskrétním a spojitém čase, včetně základních úloh LQR, stavové estimace Kalmanovým filtrem a prediktivního řízení, a interpretuje podmínky optimality založené na Hamiltonově–Jacobiho–Bellmanově rovnici a Pontrjaginově principu maxima.

  5. Formuluje a řeší vybrané optimalizační úlohy s omezeními a více kritérii, porovná přípustná řešení a vyhodnotí kompromisy mezi jednotlivými kritérii.

  6. Implementuje a experimentálně vyhodnotí vybrané heuristické a metaheuristické algoritmy pro kombinatorické a rozvrhovací problémy, porovná kvalitu získaných řešení, výpočetní náročnost a vhodnost použitých metod.

Studijní opory

Pro podporu studia jsou studentům poskytovány materiály k přednáškám a počítačovým cvičením. Materiály jsou zpřístupňovány prostřednictvím univerzitního e-learningového prostředí. 

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ý

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

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

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