5. seminář:
Optimalizace v grafech
Příklad 1: Aplikujte ručně metodu větví a mezí na následující modifikaci úlohy o batohu (použijte bivalentní proměnné a relaxace dílčích podúloh řešte bez pomoci simplexové metody):
Máme k dispozici sklad o celkové skladovací ploše 8400m2. O pronájem skladu má zájem 5 zájemců s různými požadavky na skladovou plochu a různými nabídkami za pronájem této plochy. Požadavky musí být splněny buď v plné výši nebo vůbec. V tabulce jsou uvedeny požadavky na plochu Pí a ceny za pronájem uvedené plochy q od každého zájemce i = 1,..., 5.
i	1	2	3	4	5
Pl[m2}	5000	1600	2800	6200	2200
Ci[Kč]	39000	9000	33000	63000	18000
Rozhodněte, kterým zájemcům poskytneme skladovací plochu, aby příjem z pronájmu byl co nejvyšší.
Příklad 2: Nalezněte v orientovaném grafu nejkratší cestu z uzlu 1 do ostatních uzlů. (použijte Dijkstrův algoritmus)
Příklad 3: Nalezněte v neorientovaném grafu nejkratší cestu z uzlu 1 do ostatních uzlů. (použijte Dijkstrův algoritmus)
Příklad 4: Navrhněte propojení 7 míst, tak aby se spotřebovalo co nejméně kabelu.
Příklad 5: Sestrojte síťový diagram znázorňující přípravu vědecké konference, která si vyžádá tyto hlavní činnosti:
a) A Plánování akce - organizační tým (7d)
b) B Výběr přednášek (2d)
c) C Oslovení a smlouvy s přednášej ími (14 d)
d) D Zajištění prostor a občerstvení (dodavatelsky) (21 d)
e) E Pozvánka - grafický návrh (2d)
f) F Tisk a distribuce pozvánek přes všechna dostupná média (14 d)
g) G Web konference (5d)
h) H Tvorba sborníku (14 d)
i) I Tisk sborníku, převoz (6d)
j) J Vlastní průběh konference (ld)
Příklad 6: Je dán projekt skládající se ze 7 elementárních činností, jejichž návaznosti a doba trvání je uvedena v následující tabulce:
činnost	trvání	bezprostředně předcházející činnost
A	5	-
B	9	-
C	11	A, B
D	6	B
E	7	A
F	5	C,D
G	9	C, E
a) sestavte síťový graf projektu
b) pomocí metody CPM určete minimální dobu projektu a vyznačte kritickou cestu
c) sestavte časový diagram realizace činností projektu
Příklad 7: Je dán projekt skládající se z 8 elementárních činností, jejichž návaznosti a doba trvání je uvedena v následující tabulce:
činnost	trvání	bezprostředně předcházející činnost
A	4	-
B	1	-
C	3	B
D	3	A, B
E	1	B
F	5	B
G	4	C, D
H	4	C, D, F
a) sestavte síťový graf projektu
b) pomocí metody CPM určete minimální dobu projektu a vyznačte kritickou cestu
c) sestavte časový diagram realizace činností projektu