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

Krok 5: Vznikne nám nová tabulka (viz podrobné dopočítání na doučování), v ní pokračujeme 
stejným způsobem (znova u, v, dopočítám rohy buněk atd….). Provádíme tak dlouho, dokud nám 
nevyjdou všechny levé horní rohy r záporné. V tu chvíli jsme hotovi a máme optimální řešení.  

Krok 6: Dopočítáme výslednou hodnotu účelové funkce 

Rozbor optimálního řešení dopravní úlohy 

Perspektivita spoje (IrijI - absolutní hodnota levých horních rohů rij) - je to hodnota testu optimality 
v optimálním řešení u nerealizovaného spoje (tedy u prázdných buňek, kde nic nevezu). U 
optimálních spojů (obsazené buňky) je perspektivita rovná 0. Určuje míru zhoršení účelové funkce, 
pokud bychom využili tento spoj. Čím je toto číslo menší, tím je spoj výhodnější.  Je li tato hodnota 
malá, můžeme po této trase převážet zboží se zanedbatelným zhoršením účelové funkce. Čím je tedy 
hodnota IrijI nižší, tím je spoj perspektivnější. Je-li hodnota IrijI dokonce nulová, existuje rovnocenné 
alternativní řešení. Po tomto spoji můžeme tedy převážet zboží až do výše propustnosti spoje (viz 
dále) a účelová funkce se nezmění.  

Propustnost spoje – říká, jaké je maximální možné množství zboží, které může být na daném spoji 
přepraveno. U optimálních spojů (obsazené buňky) je propustnost rovná přímo přepravovanému 
množství zboží (uprostřed buňky). U nerealizovaných spojů (prázdné buňky) se propustnost rovná 
hodnotě, kterou je možno přesunout po Dantzigově obvodu sestrojeném k tomuto spoji (tedy 
minimální hodnotě v buňkách tohoto obvodu označených -). 

27 

Nevyvážené (nevybilancované) dopravní úlohy 

Nevyvážená (nevybilancovaná) dopravní úloha = kapacity dodavatelů nejsou rovny kapacitám 
spotřebitelů. Řešíme přidáním fiktivního dodavatele nebo fiktivního spotřebitele, který má kapacitu 
rovnou rozdílu, který chybí do vyvážení.