Lineární programování a kombinatorická optimalizace

Cvičení k přednášce prof. Sgalla, které se koná ve středu od 14:00 v učebně S8. Případné dotazy a připomínky můžete směřovat na adresu elif@kam.mff.cuni.cz.


Tipy na další optimalizační předměty:

  • NOPT046 Diskrétní a spojitá optimalizace
  • NOPT053 Optimalizační seminář

Požadavky na zápočet

K získání zápočtu je nutné dosáhnout celkem alespoň 60 bodů a odevzdat alespoň jedno funkční řešení praktického domácího úkolu. Při zisku 85 bodů nemusíte psát na zkoušce úvodní písemku.


Body lze získat za:

  • dvě velké písemky (každá za 25 bodů),
  • dva praktické domácí úkoly (každý za 25 bodů),
  • opáčka a teoretické domácí úkoly (celkem za 20 bodů),
  • aktivitu na cvičení (1–2 body za příklad).

Stav získaných bodů

Aktuální počty získaných bodů za velké písemky (Pís), teoretické a praktické domácí úkoly (TDÚ/PDÚ), opáčka (Op) a aktivitu na cvičení (Akt).


Přezdívka Pís 1 Pís 2 PDÚ 1 PDÚ 2 TDÚ 1 TDÚ 2 TDÚ 3 Op 1Op 2Op 3AktΣ
Maximalistický student 25 25 25 25 4 2 4 3 3 4 120
_Ríša 16 23 24 4 3 3 4 2 79
Akolyta 16 13 21 4 1,5 3 1 1 60,5
Anče 12 14 17 10 4 0,5 3 3 63,5
AWK 12 18 25 4 2 2,5 2 65,5
Barnabáš 23 25 20 3 3 3 4 81
C-žloutek 22 24 25 4 3 3 4 1 86
Dave 23 17 23 10 4 3 3 4 87
Freddy 20 20 23 10 4 2,5 3 3 85,5
Georgeus 22 19 24 10 4 3 2 3 87
Gooner 9 16 23 4 2 1,5 2 3 60,5
jame 25 25 23 4 3 3 4 87
Jirka 21 23 24 4 2,5 3 4 4 85,5
Jurkis 9 15 24 4 3 3 4 62
kubík 15 11 25 4 3 3 2 63
kukulam 13 13 21 9 0 1,5 3 1 61,5
Lístek 15 14 23 4 2 2,5 2 62,5
Lukáš 25 23 24 0 3 3 3 2 2 85
Maty 13 16 21 4 2 3 3 2 64
Michal 25 21 24 10 4 3 3 0 90
Náhodné číslo 21 24 24 4 2 3 3 4 85
Petr 25 23 25 3 3 3 4 86
SS 9 0 0 4 3 2,5 1 1 20,5
Surmik 13 18,5 25 4 1,5 3 4 69
Thrayld 25 24 25 4 3 3 4 88
Trollweryne 8 15 24 8 0 0 3 2 60
V. 21 20 22 4 3 3 4 8 85
Will 23 23 24 4 3 3 4 1 85

Náplň cvičení a úkoly

22.05.2019

Řešení 2. velké písemky. Celočíselné mnohostěny, (totálně) unimodulární matice.

15.05.2019

2. velká písemka!

24.04.2019 (Opáčko)

Podmínky komplementarity.

17.04.2019

Dualita, optimalita vs. přípustnost.

10.04.2019

Simplexová metoda: pomocná úloha, neomezenost, nepřípustnost a degenerace.

03.04.2019

Řešení 1. velké písemky. Simplexová metoda.

27.03.2019

1. velká písemka!

20.03.2019 (Opáčko)

Konvexní mnohostěny a jejich stěny.

13.03.2019

Afinní podprostory. Konvexní množiny a mnohostěny.

06.03.2019 (Opáčko)

Lineární programy a ostré nerovnosti. Formulace (celočíselných) lineárních programů.

27.02.2019

Celočíselné programování. Maticové hry.

20.02.2019

Formulace lineárních programů a transformace. Grafická metoda.

Odkazy a studijní materiály