KCKurzy - Jak udělat zkoušku z EMM 1

33 

Domácí úkol 

Projekt je dán výčtem činností: 
 
Činnost 

Předcházející činnost 

Délka trvání  

1 2 

- 

2 

1 3 

- 

4 

2 4 

1 2 

5 

2 3 

1 2  

7 

3 4 

1 3    2 3 

6 

4 5 

2 4    3 4  

1 

a)  Nakreslete síťový graf 
b)  Určete kritickou dobu projektu (délku projektu) 
c)  Najděte a v grafu označte kritickou cestu 
d)  Jak se změní kritická cesta doplněním fiktivní hrany 3 5? 

34 

6. 

Přiřazovací úloha (Maďarská metoda) 

Používá se k optimálnímu přiřazení n prvků k n místům. Je to v podstatě analogie dopravního 
problému, ale mám stejný počet dodavatelů a spotřebitelů a všichni mají kapacitu 1. Nejčastějším 
úkolem je rozvést při minimálních nákladech n strojů do n míst, přičemž máme v zadání jednotlivé 
vzdálenosti. 

Důležitým termínem je tzv. Nezávislá nula – je to taková nula, která je sama v příslušném řádku nebo 
sloupci

Příklad 1: Máme tabulku vzdáleností mezi středisky a hony. Z každého střediska má být dopraven 
jeden traktor na jeden hon tak, aby počet ujetých km byl minimální.  

Krok 1: Provedeme řádkovou redukci tak, že od sazeb v jednotlivých řádcích odečteme vždy 
nejmenší sazbu (5,3,7,8,6) a dostaneme: 

V každém řádku i sloupci je již nula, nemusíme tedy už následně provádět sloupcovou redukci. 

Krok 2:  V redukované matici sazeb vybíráme nezávislé nuly (nuly, které jsou samy v řádku nebo 
sloupci). Nejdříve vybereme za nezávislé nuly ty, které jsou samostatné v řádku i sloupci (tzv. silně 
nezávislé nuly) a dáme je do rámečku. Dále vybíráme za nezávislou nulu takovou nulu, která má 
v řádce nebo sloupci co nejmenší počet nul. Nulu označíme rámečkem a ostatní nuly ve stejném 
řádku a sloupci škrtneme. Takto pokračujeme, dokud je možno vybírat nezávislé nuly. Postupujeme 
v pořadí: