Optimalizační metody (FSI-VOM)

Akademický rok 1999/2000
Garant: doc. RNDr. Jindřich Klapka, CSc.  
Garantující pracoviště: ÚAI všechny předměty garantované tímto pracovištěm
Jazyk výuky: čeština
Cíle předmětu:
Rozšířit znalosti aplikované matematiky o problematiku optimalisačních
metod, zvláště takových,při jejichž aplikaci nevystačíme se znalostí
klasických metod matematické analýsy. Tyto znalosti jsou dále použitelné
i při řešení datově rozsáhlých problémů v informatice, automatisaci,
strojírenství a ekonomice, s využitím moderních prostředků výpočetní
techniky
Výstupy studia a kompetence:
<B>Znalosti:</B> Znát základní principy a algoritmy optimalisačních
metod, které jsou hlavnímy nástroji operačního výzkumu, kybernetiky a
systémových věd.
<B>Dovednosti:</B> Umět formulovat jednoduché optimalisační problémy,
např. ze strojírenské a ekonomické praxe a z oblasti automatizace.
Vytvořit pro ně matematické modely, zvolit metodu jejich řešení a
realisovat ji pomocí soudobých nástrojů informatiky.
Prerekvizity:
 
Obsah předmětu (anotace):
Úloha optimalisačních metod v operačním výzkumu, kybernetice a systémových vědách. Formulace lineárních optimalisačních problémů.Lineární programování, simplexová metoda. Duální problémy, citlivostníanalýza. Parametrické programování.Formulace nelineárních optimalisačníchproblémů, nelineární programování. Kuhn-Tuckerovy podmínky. Konvexní a kvazikonvexní programování. Kvadratické programování. Metody větví a mezí. Gradientní metody. Některé další deterministické a stochastickéoptimalisační metody. Heuristické metody. Podstata optimalisačních metod,odvozených na základě studia biologických systémů (genetické algoritmy,umělé neuronové sítě) a na základě studia fysikálních procesů (simulovanéžíhání). Aplikace optimalisačních metod k řešení problémů z oblastistrojírenství, ekonomiky, informatiky a automatisace. Procvičování řešeníúloh na počítačích.
Metody vyučování:
 
Způsob a kritéria hodnocení:
<B>Požadavky pro zápočet: </B>
Aktivní účast na cvičeních, zpracování zápočtového příkladu.
<B>Zkouška: </B>
Ústní, zahrnující dvě otázky.
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í odborného základu  7 × 2 hod. povinná                  
    Cvičení na počítači  7 × 2 hod. povinná                  
Osnova:
    Přednáška Týden 1
Úloha optimalisačních metod v operačním výzkumu, kybernetice a
systémových vědách. Klasifikace optimalisačních metod a problémů.
Týden 2
Strukturální a funkcionální popis systému. Systém a automat.
Popis struktury ve formě algebraické a ve formě orientovaného grafu.
Optimalisace systému přesná a heuristická.
Týden 3
Formulace lineárních optimalisačních problémů. Lineární programování.
Týden 4
Simplexová metoda a její odvození.
Týden 5
Převádění lineárních optimalisačních problémů na kanonický tvar.
Umělá báze.
Týden 6
Duální problémy, citlivostní analýsa.
Týden 7
Metody větví a mezí. Jejich presentace ve formě stromového grafu.
Týden 8
Parametrické programování.
Týden 9
Nelineární programování. Konvexní programování.
Týden 10
Kuhn-Tuckerovy podmínky. Gradientní metody přímé a nepřímé.
Týden 11
Základní pojmy teorie her. Metody simulační.
Týden 12
Kvazikonvexní programování.
Týden 13
Kvadratické programování. Wolfeho metoda
Týden 14
Podstata optimalisačních metod, odvozených na základě studia biologických
systémů (genetické algoritmy, neuronové sítě) a na základě studia
fyzikálních procesů (simulované žíhání aj.)
    Cvičení odborného základu 1.týden. Příklady problémů operačního výzkumu.
2.týden. Ukázky heuristik (nap5. FIFO, MINSLK, SASP, ...). Jejich
vlastnosti a uplatnění při tvorbě časových rozvrhů výroby.
3.týden. Grafické řešení lineárních optimalizačních problémů.
4.týden. Aplikace částí simplexové metody k řešení číselných příkladů.
5.týden. Číselné příklady řešené simplexovou metodou.
6.týden. Aplikace duality při řešení problémů operačního výzkumu. Číselné
příklady.
7.týden. Číselné řešení lineárních optimalizačních problémů metodou větví
a mezí.
8.týden. Formulace nelineárních optimalizačních problémů z praxe (program
rozvoje firmy, kvadratický přiřazovací - rozmisťovací problém,
...)
9.týden. Rozbor konvexnosti a konkávnosti konkrétních funkcí.
10.týden. Grafický výklad Kuhn-Tuckerových podmínek.
11.týden. Simulace letištního provozu.
12.týden. Maximalizace haléřového ukazatele. Číselný příklad.
13.týden. Číselný příklad na aplikaci Wolfeho metody.
14.týden. Zhodnocení kvality řešení problému optimálního rozdělování
zdrojů pomocí různých klasických i moderních metod.
Poznámka: Část těchto cvičení bude probíhat u počítače.
    Cvičení na počítači Viz. osnovu cvičení odborného základu. Jeho část bude prováděna u
počítače.
Literatura - základní:
1. RARDIN, R .L.: Optimization in Operations Research, Prentice-Hall, pp. 919, 1997. ISBN 0-13-281925-2.
2. DANTZIG, G. B.: Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963. ISBN: 0-691-05913-6
3. GRITZMANN, P.; HORST, R.; SACHS, E.; TICHATSCHKE, R. (eds): Recent Advances in Optimization. Springer, Berlin, pp. 379, 1997. ISBN 3-540-63022-8.
Literatura - doporučená:
1. KLAPKA, J.; DVOŘÁK, J.; POPELA, P.: Metody operačního výzkumu. VUTIUM, Brno, 2001. ISBN 80-214-1839-7.
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 Inženýrská informatika a automatizace 01 Inženýrská informatika a automatizace informatika zá,zk 5 Povinný 2 1 Z