Diskrétní a spojitá optimalizace

Sylabus

Základy diskrétní optimalizace:

- Úvod, příklady optimalizačních problémů a optimalizačních technik. Analýza algoritmů, implementace, složitost.

- Eulerovská procházka, hladový algoritmus, nejkratsi cesta a jejich souvislosti.

- Párování a aplikace, souvislost s toky v sítích. Heuristiky a algoritmy, i pravděpodobnostní, na párování. Problém pošťáka.

- Problém obchodního cestujícího (TSP): heuristiky, aplikace a souvislosti

- Porovnání těžkých a polynomiálních problémů: TSP, problém pošťáka, Euler tours, minimální kostra, minimální Steiner tree.

Základy spojité optimalizace:

- Konvexní funkce a množiny

- Konvexní optimalizace

- Kvadratické programování

- Kuželové programování a dualita

- Karush-Kuhn-Tuckerovy podmí­nky optimality

- Základní metody

- Programování s nepřesnými daty, robustní optimalizace

Anotace

Přehledová přednáška pokrývající základní oblasti optimalizace, včetně výpočetních metod. Na úlohy spadající pod tuto problematiku vede nesčetné množství problémů z téměř všech oborů lidské činnosti. Má velmi široké možnosti použití. Úvod k dalším přednáškám specializovaným na řešení jednotlivých tříd optimalizačních úloh.

Pro absolvování předmětu jsou vhodné (nikoli však nutné) předběžné znalosti lineárního programování, např. z přednášky NOPT048 Lineární programování a kombinatorická optimalizace (dříve Opt. Metody).