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

Degenerace řešení v dopravních úlohách 

Degenerace řešení nastává, pokud je počet buněk obsazených zbožím v dopravní tabulce menší než 
m+n-1, kde m = počet řádků, n = počet sloupců. Neboli v bázi (řešení) je menší počet buněk, než by 
měl být.  

Degenerace řešení může vzniknout 2 způsoby: 

1 ) Degenerace při konstrukci výchozího řešení – nastává, pokud obsadíme buňku, která najednou 
naplní dodavatele i spotřebitele se stejnými kapacitami. Vyškrtnu najednou oba dva (dodavatele i 
spotřebitele), ubyde mi jedno řešení z báze, a mám méně než m+n-1 plných buněk.  

Náprava: U dodavatele, nebo spotřebitele zvýšíme kapacitu o malý kousek ε (zanedbatelné množství 
např 1 g). 

2 ) Degenerace při přesunu po Dantzigově obvodu – nastává, pokud v rozích označených zápornými 
znaménky jsou 2 stejné hodnoty. Při přesunu zboží po obvodu se namísto obvyklé 1 buňky vynulují 2 
a počet obsazených buněk klesne pod m+n-1.  

28 

Náprava: K jednomu ze 2 stejných čísel přidáme malý kousek +ε (zanedbatelné množství např. 1 g). 

Domácí úkol 

Příklad: Jsou dány vzdálenosti mezi dodavateli a spotřebiteli: 

a)  Je úloha vyvážená? Zdůvodněte 
b)  Pomocí VAM přejděte na výchozí řešení 
c)  Přejděte na optimální řešení a napište optimální hodnotu účelové funkce 

29 

5. Použití síťových grafů při tvorbě projektu  

Postup při sestavování sítě:  

1)  Nejdříve vyhledáme tzv. počáteční činnosti – činnosti, kterým žádná činnost nepředchází. 

V našem případě činnosti 1,5,7,8. Tyto činnosti budou vycházet z počátečního uzlu sítě. 

2)  Následně vyhledáme činnosti, po kterých již žádná činnost nenásleduje. V našem případě 

činnost 12. Tato činnost bude končit v koncovém uzlu sítě.  

3)  Postupujeme podle tabulky činností a na počáteční činnosti postupně napojujeme další