Detail předmětu

Optimalizační metody

FSI-VOMAk. rok: 1999/2000

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

Jazyk výuky

čeština

Počet kreditů

5

Garant předmětu

doc. RNDr. Jindřich Klapka, CSc.

Zajišťuje ústav

Ústav automatizace a informatiky (ÚAI)

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

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

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.

Učební cíle

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

Základní literatura

RARDIN, R .L.: Optimization in Operations Research, Prentice-Hall, pp. 919, 1997. ISBN 0-13-281925-2.
DANTZIG, G. B.: Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963. ISBN: 0-691-05913-6
GRITZMANN, P.; HORST, R.; SACHS, E.; TICHATSCHKE, R. (eds): Recent Advances in Optimization. Springer, Berlin, pp. 379, 1997. ISBN 3-540-63022-8.

Doporučená literatura

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 plánech

  • Program M2301-5 magisterský

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

Typ (způsob) výuky

 

Přednáška

42 hod., nepovinná

Vyučující / Lektor

doc. RNDr. Jindřich Klapka, CSc.

Osnova

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

14 hod., povinná

Vyučující / Lektor

doc. RNDr. Jindřich Klapka, CSc.

Osnova

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

14 hod., povinná

Vyučující / Lektor

doc. RNDr. Jindřich Klapka, CSc.

Osnova

Viz. osnovu cvičení odborného základu. Jeho část bude prováděna u
počítače.