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

35 

1: 3.ř    1.sl 
2: 2.ř    2.sl 
3: 1.ř    3.sl 
4: 5.ř    4.sl 
5: 4.ř    5.sl 

Krok 3:  Nezávislých nul je právě 5, získali jsme tedy optimální řešení. Vrátíme se k výchozí tabulce a 
určíme, jaké budou přesuny traktorů 

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

z 1.střediska na 3. hon 
z 2.střediska na 2. hon 
z 3.střediska na 1. hon 
z 4.střediska na 5. hon 
z 5.střediska na 4. hon 
 
Hodnota účelové funkce je Z = 5.1+3.1+7.1+8.1+6.1 = 29. Celkový minimální počet ujetých km je tedy 
29. 

36 

Příklad 2: Z 6 závodů máme přesunout do 6 středisek kombajny, aby náklady na dopravu byly 
minimální. Náklady na dopravu mezi daným závodem a střediskem jsou uvedeny v tabulce.  

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

Krok 2:  Protože 3. a 6. sloupec neobsahuje nulu, provedeme sloupcovou redukci tak, že 
v jednotlivých sloupcích odečteme nejnižší sazbu (0,0,1,0,0,5) a dostaneme: 

37 

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

1: 3.ř    2.sl 
2: 2.ř    5.sl 
3: 1.ř    3.sl 
4: 5.ř    6.sl 
5: 4.ř    1.sl 
 

Krok 4:  Vybrali jsme pouze 5 nezávislých nul, je potřeba jich vybrat 6. Správnost výběru nezávislých 
nul prověříme krycími čarami, které navíc slouží k určení nejmenšího prvku z nepřeškrtnutých prvků 
pro další postup. Řadu (řádek či sloupec), z které jsme vybrali nezávislou nulu, označíme vždy x a 
kolmo na ni uděláme krycí čáru (snažíme se „ulovit“ čarami co nejvíce nul).  

Königova věta: Minimální počet krycích čar, kterými lze pokrýt všechny nuly matice, se rovná 
maximálnímu počtu nezávislých nul. Pokud se počet krycích čar rovná počtu nezávislých nul, provedli 
jsme výběr správně.