Optimalizační metody (NOPT048)

Zápis zápočtu / konzultácie:
12.06.2014 14:00 – 15:00
16.06.2014 10:00 –
17.06.2014 10:00 – 15:00
19.06.2014 10:00 – 15:00
20.06.2014 10:00 – 17:00
Koncom augusta z MFF odchádzam: 1.9. nastupujem v TU Eindhoven. Ak odo mňa niečo potrebujete, skúste to vyriešiť dovtedy. Ak by niekto niečo potreboval po tomto termíne, snáď sa mi podarí dohodnúť s Martinom Böhmom, aby sa vám podpísal do indexu za mňa alebo niečo podobné. Ale ak to je možné, vyriešte to skôr.

Cvičenie sa koná každý utorok o 14:00 v S10

Kontakt:

email:
elias+opt@kam.mff.cuni.cz (píšte tam radšej to +opt)
konzultácie:
Malá strana, miestnosť číslo 325
konzultácie je lepšie dohodnúť vopred.

Orientačné podmienky zápočtu: budú sa písať dve písomky po 25 bodov, a budú zadané dve (programovacie) domáce úlohy tiež po 25 bodov. Ďalej získate jeden bod za účasť na každom cvičení a 2 body za predvedenie príkladu pri tabuli. Hranica zápočtu bude asi 65 bodov.

Elektronická zbierka príkladov: http://kam.mff.cuni.cz/~sbirka/

Zadania príkladov z cvičení

Cvičenie 1: Opakovanie LA, ADS a kombagry
Cvičenie 2: Formulácie LP problémov
Cvičenie 3: Afinita
Cvičenie 4: Konvexita
Cvičenie 5: Dokončenie konvexity + steny mnohostenov
Cvičenie 6: Steny mnohostenov
Cvičenie 7: Písomka 1
Cvičenie 8: Simplexová metóda I
Cvičenie 9: Simplexová metóda II + dualita.
Cvičenie 10: Dualita + komplementarita
Cvičenie 11: Komplementarita
Cvičenie 12: Komplementarita + totálna unimodularita

Písomka 2 bude na poslednom cvičení 20.05.2014

Domáce úlohy

Zadanie prvej domácej úlohy: ./du1.html
Deadline je do 08.05.2014 (do polnoci)

Zadanie druhej domácej úlohy: ./du2.html
Deadline je do 31.7.2014 (do polnoci)

Ďalšie materiály

TSP applet: http://www.math.uwaterloo.ca/tsp/methods/cpapp/index.html
Začína s LP programom
min ∑uv ∈ E cuv xuv za podmienok
uv ∈ E xuv pre každý vrchol v.
Môžeme dostať nesúvislý graf ako riešenie. Podmienku typu
∑_uv, u ∈ S, v ∉ S xuv ≥ 2
pre S podmnožinu vrcholov pridáte poklikaním na vrcholy, ktoré majú patriť do S. Takto sa dá zbaviť izolovaných cyklov, ale riešenie môže ostať neceločíselné. Na prvej mape sa dá takto dôjsť aj k celočíselnému riešeniu. Je tam k tomu aj tutorial.

optimalizačný software: ./sw.html
krátky zoznam software, ktorý je vhodné použiť napr. pri riešení domácich úloh.

Príklad zacyklenia simplexovej metódy: PDF, Maple.

Aktuálne počty bodov

           C1 C2 C3 C4 C5 C6 C7  P1         C8 C9 C10 C11 C12  DU1    C13 C14  P2                  DU2    Suma  
Maximum                          5 5 5 5 5                     10 15           5   5   5   5   5   5 20   100     Z/N  
-----------------------------------------------------------------------------------------------------------------------
?              1  1  3  1  1  1  0 0 4 5 5   1  1  1   1   1   10 15   1  1    5   2.5 2   0   0   2       65.5    Z   
Alex        1  1  1  1  1  1  1        1     1  1  1       1   10 15   1  1    5   0   0   3   0           47      N   
Beda        1  1     1  1  1  1  1 0 4 4 5   1  1  2   1       10 15   3  1    1   0   4   3.5 0   5       67.5    Z   
Citron      1  1  1  1  3  1  1  1   5 5 5   3  3  1       1   10 15   1  1    5   5   4   0   0           74      Z   
FIFACZ      1     1  1  1  1  1    0 4 4     1  1  1   1   1   10 15   1  1    5   0   0   0   0   5 12    68      Z   
Folwar      3  3  3     3  1                 3  1  1       1    9 15                               5 20    68      Z   
Freeman     1                                                                                               1      N   
FS          3  5  2  3  3  1  1  5 5 4 3 5   3         1       10 15                                       69      Z   
Helgrind    1  3  1  1     1  1  1 1 4 4 0   1  1  2   3   3   10 15   1  1    5   4.5 0   5   0           69.5    Z   
Houkl       1  1  1  1  1  1  1  1 1 4 1 5   1  1  1   1   1   10 15   2  1    5   2   5   5   0           69      Z   
istien            1  3  1     1  5 1 5 4 5   3  1              10 15   1  1    5   2.5 5   0   0           69.5    Z   
JB          1  1  1  1     1  1  5 3 4 4 5   1  1  1       3   10 15   1                           5  1    65      Z   
jon         3  5  1  1  3  1  1  0   5 4 5   1  3  1   3   1   10 15   3  1    5   5   3.5 0   0           80.5    Z   
Kiwi           1     1  1  1  1      3 4     1  1  1   1        9 14   1  1    5   0   0   3   0           49      N   
kuba        1                                                                                               1      N   
Kung Fu        1  1  1  1  1  1  1   5 4     1  1  1   1   1   10 15   1  1    1.5 0   3   0   0   5 10    67.5    Z   
Limetka     1  1  1  1  1  1  1      5 4 5   1  1  1       1   10 15   1  1    5   5   3.5 5   0           70.5    Z   
Martin      3  3  2  1  1  1  1  1 1 5 3 5   3  1  1       3    9 15      1    5   0   5   5   0           75      Z   
mop         3  1  1  3     1  1  5 5 5 5 5   3  1  1   1   1   10 15                                       67      Z   
Mzetko      1  1  1  1  1  1                                                                                6      N   
NaplavaJ    1  3  1  1  1  1  1  1 2 4 5 5   3  3  1   1       10 15   1  1    5   0   0   3   0           69      Z   
P47QAX      1                                                                                               1      N   
Peťan       1  1  1  1  2  1  1  1   3 5 0   1  1  1   1   1   10 15   1  1    5   2.5 4   5   0           65.5    Z   
Pomelo      3  3  1  1  3  1  1  0 2 5 5 5   3  2  1   1   1   10 15   1  1    5   5   3.5 0   0           78.5    Z   
Pomeranč    1  1  1  1  1  1  1  0 1 4 2 5   1  1  1   1   1    7 13   1  1    5   2.5 0   0   0           53.5    N   
Poolen      3  1  1  1     1  1  0   3 4 0   1  1  1   1   1   10 15   1                           5 20    71      Z   
p.rosomak   1        1     1                    2      1   1   10 15   1  1    5   0   2.5 5   0           46.5    N   
Semai       3  1  1  1  3  1  1  1   5 5 5   1  1  1   1   1   10 15   1  1    5   3.5 4   5   5           81.5    Z   
TRAN        1  1  1  1     1  1  ? 2 1 3 0   1                                                             13      N   

Hranica zápočtu:  65 bodov