Detail předmětu

Optimalizační metody II

FSI-VPP-A Ak. rok: 2027/2028 Zimní semestr

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

Garant předmětu

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

Zajišťuje ústav

Ústav automatizace a informatiky

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

Použití předmětu ve studijních plánech

Program N-AIŘ-P: Aplikovaná informatika a řízení, magisterský navazující, povinný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

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á

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