Optimalizace I (FSI-SOP)

Akademický rok 2023/2024
Garant: RNDr. Pavel Popela, Ph.D.  
Garantující pracoviště: ÚM všechny předměty garantované tímto pracovištěm
Jazyk výuky: čeština
Cíle předmětu:

Předmět se zaměřuje na seznámení studentů se základními poznatky z oblasti optimalizace - matematického programování. Důraz je kladen na uvedení podstatných informací o modelech a metodách řešení optimalizačních problémů. Jedná se zejména o uvedení do analýzy rozhodovacích problémů, tvorby základních (lineárních  a nelineárních) matematických modelů, jejich formálních zápisů a rozborů jeho vlastností, vhodných transformací modelů z pohledu jejich řešitelnosti, volby a modifikací algoritmů. Teoretický výklad uvedených poznatků je podložen ilustrujícími náázornými geometrickými a číselnými příklady s cíllem vést studenty k hlubokému a aplikačně užitečnému pochopení přednášené látky.  

Výstupy studia a kompetence:

Předmět je určen pro studenty matematického inženýrství a je užitečný pro studenty aplikovaných věd a vybraných inženýrských oborů. Účastnící se studenti získají znalosti teoretických základů optimalizace (zejména lineárního a nelineárního programování), osvojí si obecné principy modelování a vybrané algoritmy řešení optimalizačních úloh a utvoří si základní představu o uplatnění optimalizačních modelů v typických aplikacích. 

 

Prerekvizity:

Předpokládají se znalosti základních poznatků matematické analýzy a lineární algebry v rozsahu látky předmětů vyučovaných v matematickém inženýrství.

Obsah předmětu (anotace):

Předmět je zaměřen na základní optimalizační modely a metody pro řešení technických problémů. Výklad se opírá o základní zásady matematického programování prezentované v následujících krocích: 1) formulace a analýza problémů, 2) sestavování matematických modelu, 3) jejich klasifikace, případná transformace a posouzení jejich teoretických vlastností,  4) výběr a úpravy řešících algoritmů, 5) jejich softwarová implementace 6)  nalezení, analýza a interpretace optimálních řešení. Předmět zejména zahrnuje témata lineárního programování (konvexní a polyedrické množiny, simplexová metoda, dualita) a nelineárního programování (konvexní funkce, podmínky optimality, typické algoritmy). Součástí výkladu jsou rovněž úvodní informace o principech modifkací a zobecňování základních optimalizačních modelů (o celočíselných úlohách, modelování toků v sítích, času a náhodnosti, aj.). které se dále rozšiřují a prohlubují v navazujících předmětech. Náplň předmětu byla  autorem sestavena na základě jeho zkušeností s obdobnými kursy na zahraničních školách, kde působil.

Metody vyučování:

Předmět je vyučován formou přednášek, které mají charakter výkladu základních principů a teorie dané disciplíny ilustrované na geometrických a výpočtových příkladech. Cvičení je zaměřeno na praktické zvládnutí látky probrané na přednáškách.

Způsob a kritéria hodnocení:

Zápočet je udělen na základě aktivní účasti studenta na výuce předmětu a  jeho významného podílu na zpracování skupinových domácích projjektů během semestru. Zkouška je založena na vypracování písemné práce zahrnujcí formulační, výpočtové a teoretické otázky. K písemné práci pak probíhá ústní rozprava se studentem.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky:

Účast je kontrolována pomocí aktivní účasti studentů na řešených problémech, zameškaná výuka je nahrazována samostatným řešením zadaných úloh.

Typ (způsob) výuky:
    Přednáška  13 × 2 hod. nepovinná                  
    Cvičení s počítačovou podporou  13 × 1 hod. povinná                  
Osnova:
    Přednáška

1. Úvodní modely (ÚM): formulace a analýza problému, návrh modelu, klasifikace modelů a jejich základní teoretické vlastnosti.


2. ÚM: vizualizace, algoritmy, software, postoptimalizace. Poznámky o speciálních a obecných ooptimalizačních modelech. 


3. Lineární programování (LP): Konvexní a polyedrické množiny.


4. LP: Množina přípustných řešení, krajní body, krajní směry, věta o reprezentaci, základní věta LP.


5. LP: Simplexová metoda - úvod, odvození, tabulkové výpočty.


6. LP: Simplexová metoda - rozšiřující témata. 


7. LP: Dualita, citlivost a parametrická analýza.


8. Nelineární programování (NLP): Konvexní funkce a jejich vlastnosti.


9. NLP: Volné extrémy - teoretické výsledky a aplikace. 


10. NLP: Vázané extrémy a podmínky optimality (geometrické, FJ, KKT). 


11. NLP: Volné extrémy  a související numerické metody jednorozměrné a vícerozměrné optimalizace.


12. NLP:  Vázané extrémy a související numerické metody. 


13. Vybraná doplňující témata. 

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

Uvodni ulohy (1-3)
Linearni ulohy (4-8)
Nelinearni ulohy (9-13)

Účast na cvičení je povinná.

Literatura - základní:
1. Dupačová et al.: Lineárne programovanie, Alfa 1990
2. Bazaraa et al.: Linear Programming and Network Flows, , Wiley 2011
3. Bazaraa et al.: Nonlinear Programming, , Wiley 2012
4. Klapka a kol.: Metody operačního výzkumu, VUT 2001
Literatura - doporučená:
1. Klapka a kol.: Metody operačního výzkumu, VUT, 2001
2. Dvořák a kol.: Operační analýza, VUT FSI, 2001
3. Charamza a kol.: Modelovací systém GAMS, MFF UK Praha, 1994
Zařazení předmětu ve studijních programech:
Program Forma Obor Spec. Typ ukončení   Kredity     Povinnost     St.     Roč.     Semestr  
B-MAI-P prezenční studium --- bez specializace -- zá,zk 4 Povinný 1 3 L