Dantzigův uzavřený obvod
Výchozí tabulka
Sklad 1
Sklad 2
14
Farma 1
100
14
-
7
Farma 2
Sklad 3
50
8
-
18
130
6
Sklad fiktivní
7
9
ui
100
7
0
-
70
Kapacity
Test optimality
Přes duální hodnoty ui a vj
0
250
0
12
0
0
Farma 3
-
-
50
150
Požadavky
150
130
120
150
vj
7
18
7
-5
Degenerované řešení
m+n-1=3+4-1=6
obsazených políček: 6
úloha není degenerovaná
5
200
Políčko uvnitř tabulky
Stránka 1
V řádku ui a ve sloupci vj.
Zvolíme si nulu (0), kde je nejobsazenější řádek.
Dopočítávání hodnot u a v přes obsazená pole.
Nula a kolik je 7 => 7.
7=0+7
Nula a kolik je 18 => 18.
18=0+18
Nula a kolik je 7 => 7.
7=0+7
Zespoda 7 a kolik je 14 => 7.
14=7+7
Zespoda 7 a kolik je 12 => 5.
12=5+7
Zprava 5 a kolik je 0 => -5.
0=5+(-5)
cij = ui + vj
Test optimality u neobsazených políček a první Dantzigův uzavřený obvod.
Sklad 1
Sklad 2
14 11
Farma 1
100
Farma 2
50
6
14
-
7
Farma 3
Sklad 3
-
6
8
18
14
70
9
-
2
-
130
-
6
Sklad fiktivní
-5
+
100
7
250
0
200
5
0
0
12
50
ui
0
-
7
+
Kapacity
0
150
-
Požadavky
150
130
120
150
vj
7
18
7
-5
Stránka 2
U neobsazených políček
ui + vj - cij
U obsazených
ui + vj - cij = 0
11=7+18-14
6=7+7-8
2=7+(-5)-0
-5=0+(-5)-0
6=5+7-6
14=5+18-14
100: 7+7-14=0
50: 0+7-7=0
130: 0+18-18=0
70: 0+7-7=0
50: 5+7-12=0
150: 5+(-5)-0=0
Jedna hodnota je záporná, která je zhoršující.
Ostatní hodnoty jsou kladné a zlepšující.
Proto toto řešení není optimální.
Vybereme nejvyšší hodnotu. V tomto případě je to 14.
Začínáme na volném políčku,
ale všechna ostatní musí být obsazená.
Na neobsazené políčko navážíme a následně střídáme.
Minimum, které lze odečíst je 50 (50,130).
Střídavě odečítáme a přičítáme příslušnou hodnotu.
Po úpravě č. 1
Sklad 1
Sklad 2
14 11
Farma 1
100
Sklad 3
14
6
Sklad fiktivní
8
-
16
-
-
Farma 2
18
50
80
+
-8
Farma 3
7
7
-
Znovu test optimality.
Výpočet duálních hodnot.
Test optimality u neobsazených políček.
Nulu necháme na původním místě.
Vytvoříme nový Dantzigův uzavřený obvod.
Minimum je 80 z odečítání (80, 100, 150).
250
0
200
-9
Kapacity
ui
Takto pokračovat až do nalezení optimálního řešení.
100
7
Řešení je optimální, pokud pro všechna
neobsazená pole platí, že
250
0
6
9 -14
-
50
12
0
-
150
+
Požadavky
vj
100
+
0
9
120
ui
0
7
Kapacity
-
150
7
130
18
120
7
150
9
Sklad 1
Sklad 2
Sklad 3
Sklad fiktivní
Po úpravě č. 2
0
Farma 1
14 -5
20
0
Farma 2
14
7 -16
130
8
6
18
0
6
0
8
0
7
-7
120
9
2
0
80
0
-
12
0
ui + vj – cij ≤ 0
0
Farma 3
-
130
-
70
Požadavky
vj
150
7
130
2
120
7
150
-7
200
7
Stránka 3
Hodnota perspektivy u obsazených políček je nula (0).
Kladné zlepšující hodnoty
u neobsazených políček: 2, 6 a 8.
Pro další Dantzigův uzavřený obvod bude využito
políčko s hodnotou 8.
Ostatní políčka jsou záporná a zhoršující.
Download

Dantzigův uzavřený obvod Výchozí tabulka Degenerované řešení m