148 149

148

Zadanie transportowe i problem komiwojażera

Opiszemy dalej sposób postępowania w kolejnych iteracjach metody potencjałów.

3.4.1. Badanie optymalności rozwiązania

Iteracja 1

Przypomnijmy zapisane uprzednio w tablicy 3.7 pierwsze rozwiązanie dopuszczalne, otrzymane metodą minimalnego elementu (tablica 3.11). Węzły bazowe zaznaczone są gwiazdką.

Tablica 3.1 I

Rozwiązanie początkowe (metoda minimalnego elementu)			Podaż
10*	10*	0	0
0	5*	15*	0
0	0	30*	0
0	0	0	Popyt
Macierz kosztów jednostkowych			Wartość funkcji celu
1	4	7
3	5	11
6	7	9	510

Przypuśćmy, że jest to rozwiązanie optymalne interesującego nas zadania. Wtedy spełnione są warunki (3.8). Ponieważ zmienne x_lt, x_]2, x₂₂, x_2i i x_n są dodatnie, więc odpowiadające im warunki ograniczające w zadaniu dualnym muszą być spełnione jako równania. Oznacza to więc:

dla węzła (1, 1): «, + v, + 1=0, dla węzła (1,2): M| + v₂ + 4 = 0, dla węzła (2, 2): u₂ + v₂ + 5 — 0, dla węzła (2, 3): »₂ + ^,+ 11=0, dla węzła (3, 3): u_i+v_i + 9 = 0.

Otrzymujemy w ten sposób układ 5 równań liniowych o 6 niewiadomych. Aby go rozwiązać, jedną ze zmiennych potraktujemy jako parametr. Przyjmijmy, że «,=«. Mamy wówczas rozwiązanie:

u | =«,    v, =— 1 -a,

u₂ = — 1 + a, v₂ = — 4 — a,

«₃=l+a, v₅ = — 10 — a.

Obliczymy wartości współczynników optymalności c-j, którymi są lewe strony warunków ograniczających zadania dualnego, zapisane wzorami (3.7). Wykorzystując wzór:

clj=Ui+Vj+Cij,    (3.11)

otrzymujemy:

Ci | = Ui + i’i + 1 ⁼ a + (— 1 — a) + I =0,

C|₂ = W| + i>₂ + 4 = a + (—4 —<2)+4 = 0, c_l3 = «| + v₃ + 7=a + (- 10 — a)+ 7 =-3, c_2l = u₂ +    + 3 = (- 1 + a) + (- 1 - a) + 3 = 1,

c₂2 — u2 + v₂ ■*" 5 — (— 1 + a) + (— 4 — a) + 5 = 0, c₂3 = w₂ +    + 11 = (- 1 + a) + (— 10 - a) + 11 = 0,

c,| = u₃ + v'i + 6 = (1 + a) + (- 1 — a) + 6 = 6, cj₂ = u₃ + v₂ + 7 = (l -ł-a) + (-4-«) + 7 = 4,

Cj3 = «3+ Vj + 9 = (1 +a) + (- 10-zr) + 9 = 0.

Widzimy, że wartości współczynników optymalności nie zależą od wyboru wartości parametru a. W dalszych rozważaniach przyjmiemy więc dla wygody, że mamy a = 0.

Wyniki obliczeń zestawimy w postaci macierzy współczynników opiymal-ności C'. Otrzymujemy:

0    0-3

C' =

1    0 0

6 4    0

Gdyby rozpatrywane przez nas rozwiązanie początkowe było optymalne, wówczas odpowiadające mu rozwiązanie zadania dualnego musiałoby spełniać warunki ograniczające tego zadania, czyli wartości wszystkich współczynników optymalności powinny być nieujcmne. Widzimy, że tak jednak nie jest, co oznacza, że nasze przypuszczenie co do optymalności rozwiązania początkowego było fałszywe. Rozwiązanie początkowe nie jest więc optymalne i wymaga poprawy.

Powyższe postępowanie można zastosować w stosunku do dowolnego rozwiązania bazowego zadania transportowego. Otrzymujemy jednocześnie sformułowane poniżej kryterium optymalności.

Kryterium optymalności

Jeżeli wartości wszystkich wskaźników optymalności są nieujemne, to rozpatrywane rozwiązanie jest optymalne. Jeżeli choć jeden ze wskaźników optymalności jest ujemny, to istnieje możliwość poprawy tego rozwiązania.