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

Dostali jsme soustavu pěti krycích čar, pokryli jsme jimi všechny nuly matice, postupovali jsme tedy 
správně a můžeme určit nejmenší prvek z nepřeškrtnutých prvků.  

38 

Krok 5:  Provedeme sekundární redukci matice  

a)  určíme nejmenší prvek z nepřeškrtnutých prvků (1) 
b)  prvky přeškrtnuté 1 x necháme beze změny 
c)  prvky přeškrtnuté dvakrát o minimální prvek zvětšíme 
d)  prvky nepřeškrtnuté o minimální prvek snížíme 

Krok 6:  Vybíráme nezávislé nuly v tomto pořadí: 

1: 2.ř    5.sl 
2: 5.ř    6.sl 
3: 1.ř    3.sl 
4: 3.ř    2.sl 
5: 4.ř    1.sl 
a provedeme opět kontrolu pomocí krycích čar, postup byl správný. 

Krok 7:  Provedeme další sekundární redukci matice – nejmenší prvek z nepřeškrtnutých prvků je 
opět 1. 

39 

Krok 8:  Pokračujeme výběrem nezávislých nul v tomto pořadí: 

1: 2.ř    5.sl 
2: 5.ř    6.sl 
3: 1.ř    4.sl 
4: 3.ř    2.sl 
5: 4.ř    1.sl 
6: 6.ř    3.sl 
 a zkontrolujeme řešení pomocí krycích čar. 
 

Krok 9: Nezávislých nul je nyní 6, dostali jsme tedy optimální řešení. Výsledný plán přepravy je 
uveden v tabulce.  

Optimální program přesunů kombajnů tedy je: 

z 1.závodu do 4. střediska 
z 2.závodu do 5. střediska 
z 3.závodu do 2. střediska 
z 4.závodu do 1. střediska 
z 5.závodu do 6. střediska 
z 6.závodu do 3. střediska 
Hodnota účelové funkce je Z = 9+4+9+6+15+11 = 54. Celkové minimální náklady jsou tedy 54 tisíc Kč. 
 

40 

7. 

Jednookruhový okružní problém 

Používá se k nalezení nejkratší cesty, která obsahuje všechny vrcholy. Nejčastějším úkolem je projet 
co nejkratší cestou všechna města a vrátit se zpět do původního. Někdy též nazýváno „Úloha 
obchodního cestujícího“.