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, (tj. nalezněte minimální kostru)
Příklad 5: Pomocí řešitele určete maximální tok znázorněnou sítí.
Příklad 6: Sestrojte síťový diagram znázorňující přípravu vědecké konference, která si vyžádá tyto hlavní činnosti:
a) vypracování programu konference (2dny)
b) zajištění termínu a místa konání konference (3dny)
c) dojednání účasti přednášejících (7dní)
d) vypracování a zaslání tezí od přednášejících (14dní)
e) rozeslání pozvánek na konferenci (4 dny)
f) příjem a zpracování přihlášek od zájemců o účast (20dní)
g) zorganizování pořadatelské služby (2dny)
h) tisk a rozmnožení tezí přednášek (3 dny)
i) předání tezí a seznamu účastníků pořadatelské službě, rozpis ubytování a stravování (2dny)
Příklad 7: 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 8: 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