O PŘEDMĚTU

Úvod do optimalizace je základní přednáška z optimalizace, na které se studenti dozvědí základní postupy a metody používané při hledání optimálního řešení zadané úlohy. Přednáška je věnována teorii, numerické příklady a jejich analytické či softwarové řešení jsou vyučovány na cvičeních.

Čas a místo konání přednášky a cvičení:

Přednáška	Pondělí 9:00 - 10:30 - K1
Cvičení	Pondělí 10:40 - 12:10 - K2 - (doc. Branda)
	Středa 15:40 - 17:10 - K5

Cvičení 16.3. proběhne samostudiem. Prosím, podívejte se na příklady 3.6 - 4.4. ve skriptech, stále se jedná o procvičování konvexity množin/funkcí, což je něco, s čím jste se již setkali. Všechny příklady tam jsou řešené, případné otázky k nim si prosím připravte na cvičení 23.3., kde se jim v úvodu budeme věnovat.

Doporučená literatura:

Dupačová, J., Lachout, P. (2011). Úvod do optimalizace, Matfyzpress, Praha.

Stránka předmětu v SISu je zde. Informace o přednášce a zkoušce pak hledejte na stránkách doc. Brandy

O CVIČENÍ

Nutné podmínky pro udělení zápočtu:

• Zápis na jednu paralelku v SIS.
• Odevzdání správně vypracovaného domácího úkolu na simplexový algoritmus (s možností jedné opravy).
• Úspěšné napsání zápočtové písemky.

Cvičení budou probíhat prezenčním způsobem. Materiály ke cvičení budou zveřejňovány zde na webu.

Na jednom ze cvičení (cca půlka dubna) bude zadána domácí úloha na simplexový algoritmus. Každý student obdrží své vlastní zadání, úlohu vyřeší ručně na papír a také pomocí softwaru (GAMS, R, Python, Matlab, Mathematica, apod.) a kód programu přiloží k vypracovanému řešení. Datum pro odevzdání úlohy je neděle 15.5.2022. Špatně vyřešenou úlohu bude možné opravit.

Simplexová úloha se skládá z jedné úlohy a tří otázek. Ty jsou:

1. Formulujte úlohu jako úlohu LP, pomocí libovolného softwaru úlohu vyřešte. V emailu pak přiložte kód úlohy a výstup solveru včetně komentáře co a jak děláte.
2. Úlohu vyřeště ručně na papír pomocí dvojfázového simplexu. Zkontrolujte si, že Vám vyšel stejný výsledek jako v 1.
3. Sestavte duální úlohu k původní úloze, pomocí podmínek komplemetarity nalezněte její řešení (znáte již řešení primární úlohy, není nutné řešit znovu např. simplexem).

Na předposledním cvičení, (4.5./9.5), se bude psát zápočtový test.

Test se bude skládat ze 4 příkladů:

1. Formulace úloh LP [3b]
2. Konvexita [4b]
3. Lineární programování (dualita + grafické řešení + komplementarita / simplex) [8b]
4. Farkasova věta / nelineární programování (LPO + GPO) [5b]

Příklady budou velmi podobné těm ze cvičení, na jejich řešení bude 90 minut. Povolené pomůcky jsou psací potřeby a papír. Celkem bude možné získat 20 bodů, k úspěšnému napsání bude potřeba 13 bodů. Ve výjimečných a odůvodněných případech bude možné test napsat i distančně.

Vzorové zadání písemky: písemka z roku 2021. Vzorové řešení (děkuji autorce za příkladné vypracování).

Krom projití řešených příkladů se doporučuji k lepšímu pochopení látky podívat na nějaká videa, kde je problematika lineárního programování názorně vysvětlena. Na youtube jich je velké množství. Můžu doporučit například tyto z kurzu o lineárním programování na jedné americké univerzitě.

MATERIÁLY

Řešené příklady ze cvičení jsou k dispozici zde (poslední aktualizace 2022-02-01).