Dantzigův obvod - teorie
Test optimality
• Jiné výchozí řešení
• Řešení není optimální
Políčko uvnitř tabulky
Test optimality
• 1. krok
o Určíme m+n hodnot duálních proměnných ui, vj ze vztahu ui+vj = cij, tj. pro (i,j)∈B (obsazená
pole). Protože soustava rovnic má jeden stupeň volnosti (o jednu proměnnou víc než je
rovnic), volíme ji libovolně (např. položíme u1= 0).
• 2. krok
o Pro všechny indexy (i,j)∉B (neobsazená pole) prověříme, zda platí ui+vj <= cij.
o Platí-li to pro všechny (i,j)∉B, řešení DÚ je optimální.
o V opačném případě se dá řešení zlepšit:
• 3. krok
o Vybereme největší z rozdílů ui+vj - cij > 0 a buňku DiSj obsadíme maximálním možným
množstvím zboží (to se provede tzv. Dantzigovým uzavřeným obvodem).
První krok testu optimality
Druhý krok testu optimality
Přechod na nové řešení
• Jedná se o změnu báze
• Změna přepravovaného množství musí být vyrovnána pro všechny dodavatele i spotřebitele
• Provádíme graficky v dopravní tabulce
• Grafické schéma se nazývá Dantzigův uzavřený obvod
−
+
−
+
−
+
+
+
−
−
+
+
−
−
+
−
−
+
+
−
+
−
+
−
−
+
−
+
+
+
−
−
Dantzigův obvod – definice
• Je to lomená čára, která vychází z neobsazené buňky (i,j)∉B, lomí se v obsazených buňkách
(r,s)∈B a končí v původní buňce.
• Buňky, ve kterých se obvod lomí, označujeme střídavě znaménky + a − podle toho, zda
příslušnou hodnotu xij k trase přidáváme nebo z trasy odebíráme.
• Aby nové řešení bylo bazické, tj. obsahovalo opět m+n−1 kladných hodnot cij, volíme za
přesunovanou hodnotu xij minimální z hodnot xij na rozích uzavřeného obvodu označených
znaménkem −.
Řešení je optimální.
-1-
Danzigův uzavřený obvod
Nové řešení
Degenerace ve výchozím řešení
Přesun t=5 po Danzigově obvodu
Řešení je degenerované
Vyčerpána zároveň kapacita i požadavek
Degenerace
• Říkáme, že řešení je degenerované, když počet kladných hodnot xij (tj. počet obsazených spojů) je
menší než m+n-1.
• Degenerace vzniká:
o Při konstrukci výchozího řešení
o Při přesunech po Dantzigových obvodech
• Odstranění degenerace
o Vložíme malé množství ε na neobsazené pole, které s ostatními obsazenými netvoří uzavřený
okruh. Toto pole pak považujeme za obsazené.
Degerace při přesunu po Dantzigově obvodu
Nové řešení
Odstranění degenerace
Vložíme malé množství ε na neobsazené pole,
které s ostatními obsazenými netvoří uzavřený
okruh. Toto pole pak považujeme za obsazené.
-2-
Nové řešení
Optimální řešení
Download

- 1 - Dantzigův obvod - teorie Políčko uvnitř tabulky Test optimality