Detail předmětu

Optimalizace I

FSI-SOPAk. rok: 1999/2000

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ásady matematického
programování: porozumění problému, sestavení modelu, nalezení,
analýza a interpretace optimálního řešení. Předmět zahrnuje zejména
lineární programování (polyedrické množiny,simplexová metoda,
dualita)a nelineární programování (konvexní analýza, Karushovy -
Kuhnovy - Tuckerovy podmínky, typické algoritmy). Součástí výkladu
je rovněž krátké seznámení s problematikou celočíselného programování
a toků v síti, kterou dále prohlubují navazující kurzy.
Výklad je v závěru semestru rozšířen o úvodní informaci o
principech zobecňování základních optimalizačních modelů (modelování
času, náhodnosti, aj.). Kurs byl sestaven na základě zkušeností autora
s obdobnými kursy na zahraničních školách.

Jazyk výuky

čeština

Počet kreditů

6

Garant předmětu

RNDr. Pavel Popela, Ph.D.

Zajišťuje ústav

Ústav matematiky (ÚM)

Výsledky učení předmětu

Předmět je určen pro studenty matematického inženýrství, je užitečný
pro studenty aplikovaných věd. Studenti získají znalosti teoretických
základů optimalizace (zejména lineárního a nelineárního programování)
osvojí si 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.

Způsob a kritéria hodnocení

K zápočtu je vyhodnocena účast a aktivita na cvičeních. Udělení
zápočtu je samozřejmým předpokladem vykonání zkoušky. Přihlíží
se ke zpracování samostatných písemných prací zadaných k vybraným
tématům během semestru.
Ke zkoušce obdrží studenti podrobné písemné pokyny včetně okruhu
otázek (ukázka cca 50ti otázek) a bodového systému do 4.týdne výuky.
Proto jen stručně:
Hlavní část zkoušky je písemná a zahrnuje řešení 4 praktických
příkladů (např. formulace matematického modelu, řešení zadané
úlohy LP numericky, řešení zadané úlohy NLP analyticky),
zodpovězení 4 teoretických otázek z probrané látky a je doplněna
ústní diskuzí.

Učební cíle

Důraz je kladen na získání hlubokých znalostí modelů a metod řešení
optimalizačních problémů, počínaje analýzou problému, přes tvorbu
matematického modelu, včetně zápisu modelu, nalezení ekvivalentních
modelů, volbu a modifikaci algoritmů. Uvedené metody jsou podloženy
výkladem teoretických poznatků, navazujícím na geometrický názor.

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)

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 M2301-5 magisterský

    obor , 3. ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

42 hod., nepovinná

Vyučující / Lektor

RNDr. Pavel Popela, Ph.D.

Osnova

1. Úvodní úlohy: Motivace. Historie. Teoretické základy. Klasifikace.
2. Lineární úlohy: Konvexní a polyedrické množiny. Farkasova věta.
3. Formulace ULP. Standardní tvar. Množina příp.řešení. Řešitelnost ULP.
4. Geom.idea algoritmu řešení ULP. Maticový rozbor simplexové metody.
5. Dvoufázová metoda. Konečnost, zacyklení, degenerace. Paměťové nároky.
6. Duální úloha LP. Věty o dualitě a komplementaritě. Analýza citlivosti.
7. Speciální úlohy: Poznámky o síťové struktuře a celočíselnosti (B-B).
8. Nelineární úlohy: Konvexní funkce.Lokální a globální extrémy.
9. Metody jednorozměrné optimalizace. Algoritmy nevyužívající derivace.
10. Algoritmy vícerozměrné optimalizace využívající derivace.
11. Vázaný extrém. Karush - Kuhn - Tuckerovy podmínky. Regularita.
12. Penalizační metody. Metody redukce gradientu, aproximační metody.
13. Transformace úloh a speciální úlohy. Hledání globálního minima.
14. Obecné úlohy: Úvod do problematiky. Ukázkové příklady.

Cvičení na počítači

28 hod., povinná

Vyučující / Lektor

RNDr. Pavel Popela, Ph.D.

Osnova

1. Formulace a řešení elementárních optimalizačních úloh (grafické).
2. Stručné opakování SLR. Aplikace teoretických poznatků (konvexnost).
3. Formulace, geometrický význam a grafické řešení ULP. Standardní tvar.
4. Řešení ULP simplexovou metodou v maticovém i tabulkovém tvaru.
5. Řešení názorných příkladů ULP ilustrujících poznatky přednášky.
6. Určení a řešení duální úlohy a analýza citlivosti řešení.
7. Formulace síťových úloh jako úloh LP. Ukázky metody větví a mezí.
8. Formulace a řešení některých typických úloh na volný extrém.
9. Výpočty na kalkulačce podle vybraných algoritmů z přednášky I.
10. Výpočty na kalkulačce podle vybraných algoritmů z přednášky II.
11. Použití KKT podmínek k řešení optimalizačních úloh.
12. Výpočty na kalkulačce podle algoritmů z přednášky III.
13. Řešení příkladů na transformaci úloh.
14. Vyhodnocení samostatné práce a udělení zápočtů.