Optimalizace I (FSI-SOP)

Akademický rok 1999/2000
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:
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.
Výstupy studia a kompetence:
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.
Prerekvizity:
 
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á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.
Metody vyučování:
 
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í.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky:
 
Typ (způsob) výuky:
    Přednáška  14 × 3 hod. nepovinná                  
    Cvičení na počítači  14 × 2 hod. povinná                  
Osnova:
    Přednáška 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 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ů.
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
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  
M2301-5 prezenční studium Matematické inženýrství -- zá,zk 6 Povinný 1 3 Z