Detail předmětu

Optimalizace I

FSI-SOPAk. rok: 2023/2024

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.

Jazyk výuky

čeština

Počet kreditů

4

Garant předmětu

RNDr. Pavel Popela, Ph.D.

Zajišťuje ústav

Ústav matematiky (ÚM)

Vstupní znalosti

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

Pravidla hodnocení a ukončení předmětu

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.


Úč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.

Učební cíle

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.  


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. 

 

Základní literatura

Dupačová et al.: Lineárne programovanie, Alfa 1990 (CS)
Bazaraa et al.: Linear Programming and Network Flows, , Wiley 2011 (EN)
Bazaraa et al.: Nonlinear Programming, , Wiley 2012 (EN)
Klapka a kol.: Metody operačního výzkumu, VUT 2001 (CS)

Doporučená literatura

Klapka a kol.: Metody operačního výzkumu, VUT, 2001 (CS)
Dvořák a kol.: Operační analýza, VUT FSI, 2001 (CS)
Charamza a kol.: Modelovací systém GAMS, MFF UK Praha, 1994 (EN)

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

  • Program B-MAI-P bakalářský, 3. ročník, letní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

RNDr. Pavel Popela, Ph.D.

Osnova

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

13 hod., povinná

Vyučující / Lektor

RNDr. Pavel Popela, Ph.D.

Osnova

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

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