Cvičení z optimalizačních metod (letní sem. 17/18)

Podmínky zápočtu

K získání zápočtu je třeba získat alespoň 60 bodů a odevezdat alespoň jedno funkční řešení praktického úkolu (viz níže). Pokud získáte dokonce 85 bodů prof. Sgall vám u zkoušky odpustí úvodní písemku. Body lze získat za písemky (malá opáčka a velké písemky), domácí úkoly (malé teoretické a velké praktické) a aktivitu. Docházka není povinná, ale doporučená -- veškeré důležité informace se pokusím včas dávat na web (sem), může se ale stát, že mi občas něco uteče a jen to řeknu na cvičení. Nebojte se ptát (v nejhoším případě se prostě nic nedozvíte :-)).

V průběhu semestru se budou psát dvě velké písemky, každá za 25 bodů. Písemky budou cca na celé cvičení a budou ohlášeny alespoň dva týdny předem. Též budou zadány dva praktické domácí úkoly, každý za 25 bodů. Vesměs budou spočívat v praktickém vyřešení nějakého problému -- vaším cílem typicky bude problém namodelovat pomocí (celočíselného) lineárního programu daný problém a napsat program, který ze vstupu vytvoří LP a poté ho předhodí solveru LP. Detaily a zadání zde. Podmínkou pro získání zápočtu je odevzdat funkční řešení alespoň jedné úlohy.

Dále se v průběhu semestru bude psát blíže neurčený počet opáček a bude zadán blíže neurčený počet teoretických domácích úkolů, celkem za 20 bodů, cca 2-3 body za kus. Opáčko je desetiminutová písemka na začátku cvičení na látku probranou na posledních cvičení. Opáčka budou hlášena minimálně cvičení předem. Teoretické úkoly budou podobného rozsahu jako opáčka.

Navíc je možno získat bonusové body za aktivitu na cvičení (typicky předvedení příkladu u tabule), či za jinou podobně bohulibou aktivitu.

Získané body budou k vidění níže na stránce, pokud mi pošlete svou přezdívku, nebo k dispozici na požádání

Odevzdávání teoretických domácích úkolů

Domácí úkoly mají termín do začátku blíže definovaného cvičení. Odevzdávat je můžete elektronicky e-mailem (nezapomeňte do předmětu e-mailu uvést kód předmětu) nebo fyzicky mé osobě (typicky na začátku cvičení), případně je můžete hodit do mé schránky na koleji (ale to jen spíš v případě nouze).

Pokud odevzdáváte úkoly elektronicky, posílejte je ve formátu pdf a čitelné. Speciálně, fotky nekvalitním fotoaparátem při mizerných světelných podmínkých a strašlivém škrabopisu vám hodím na hlavu!

Středeční paralelka

1. cvičení: Úvodní informace, formulace problémů pomocí LP, ukázka grafického řešení LP. Zadán 1. teoretický DÚ.

2. cvičení: Převody mezi tvary LP (rovnicový tvar, jak simulovat záporné proměnné pomocí nezáporných), trik, jak se dá občas zbavit absolutní hodnoty. Celočíselné programování a jeho NP-úplnost (aneb, jde s ním namodelovat batoh) a základní trik s 0-1 proměnnými.

3. cvičení: Psalo se 1. opáčko. Lineární programy a ostré nerovnosti. V rychlosti ukázka LP s exponenciálním počtem podmínek.

4. cvičení: Zadán první praktiký DÚ Více informací zde. Afinní prostory, afinní (ne)závislost.

6. cvičení: Psalo 2. opáčko. Mnohostěny a jejich stěny. Počty vrcholů a faset krychle a křížového mnohostěnu, jak poznat vrcholy a jak zjistit, v jaké poloze je mnohostěn vůči nadrovině.

8. cvičení: Řešení písemky a časté chyby. Simplexová metoda, když nám problém nehází klacky pod nohy. Co to je bázické (přípustné) řešení, co dělá pivotovací krok, jak najít počáteční bázi okometricky (metoda Kouknu a vidím).

9. cvičení: Simplexová metoda, jak najít počáteční bázi, pivotovací pravidla.

10. cvičení: Psalo se 3. opáčko. Zaskakoval Pavel Hubáček. Dualita.

12. cvičení: Psalo se 4. opáčko. Něco málo o prvním praktickém úkolu. Totální unimodularita.

Bonusový teoretický úkol pro ty, komu chybí nejvýše 4 body do zápočtu. Zadání zde.

Body

Pokud se zde nevidíte, pak je to nejspíše tím, že jste mi neposlali svou přezdívku.

Čtvrteční paralelka

1. cvičení: Úvodní informace, formulace problémů pomocí LP, ukázka grafického řešení LP. Zadán 1. teoretický DÚ.

3. cvičení: Psalo se 1. opáčko. Tentokráte cvičil Pavel Hubáček.

4. cvičení: Zadán první praktiký DÚ Více informací zde. Afinní prostory, afinní (ne)závislost.

6. cvičení: Psalo se 2. opáčko. Mnohostěny a jejich stěny. Počty vrcholů a faset krychle a křížového mnohostěnu, jak poznat vrcholy a jak zjistit, v jaké poloze je mnohostěn vůči nadrovině.

9. cvičení: Simplexová metoda, jak najít počáteční bázi, pivotovací pravidla.

10. cvičení: Psalo se 3. opáčko. Zaskakoval Pavel Hubáček. Dualita.

12. cvičení: Psalo se 4. opáčko. Něco málo o první praktickém úkolu. Totální unimodularita.

Body

Pokud se zde nevidíte, pak je to nejspíše tím, že jste mi neposlali svou přezdívku.

Cvičení z optimalizačních metod (NOPT048)

Středa od 14:00 a čtvrtek od 17:20

Podmínky zápočtu

Odevzdávání teoretických domácích úkolů

Středeční paralelka

Body

Čtvrteční paralelka

Body