154 155

154 Zadanie transportowe i problem komiwojażera

Tworzymy nowe rozwiązanie dopuszczalne. Dotychczasowe rozwiązanie dopuszczalne i nowe rozwiązanie dopuszczalne zawarto w tablicy 3.17.

Tablica 3.17

Dotychczasowe rozwiązanie dopuszczalne				Podaż
itr	0	10*		20
			5-	20
U ^	1 -j
fi m	A		30	30
		• ;.ŃV
10	15	45		Popyt
Nowe rozwiązanie dopuszczalne				Wartość funkcji celu (iteracja 2) 470
5	0	15
5	15	0
0	0	30

Iteracja 3

Wykorzystując macierz wskaźników optymalności uzyskaną w iteracji 2, tworzymy układ równań liniowych, odpowiadający nowemu rozwiązaniu, otrzymanemu w tej iteracji (tablica 3.18).

Tablica 3.18

Macierz wskaźników optymalności

0*	3	0«
o	0*	0
3	4	0*

Układ równań », + r, = 0 «, + >S=0 m, + v_|-2 = 0 Uj + v j = 0 u, + v,=0

Na podstawie wzoru (3.11) znajdujemy macierz wskaźników optymalności (tablica 3.19).

Ponieważ wartości wszystkich wskaźników optymalności są nieujemne, aktualnie rozpatrywane rozwiązanie jest optymalne. Optymalna wartość funkcji celu wynosi 470.

Tablica 3.19

Dotychczasowa macierz wskaźników optymalności			ut
0*	3	0*	0
-2	0*	0*	2
3	4	0*	0
0	-2	0	V. J
Nowa macierz wskaźników optymalności
0*	1	0*
0*	0*	2
3	2	0*

3.4.6. Degeneracja w zadaniu transportowym

Każda baza w zadaniu transportowym składa się z m + n- I elementów. Degeneracja występuje wtedy, kiedy liczba zmiennych bazowych o wartościach niezerowych jest mniejsza od m + n- 1. Jeżeli degeneracja występuje już w etapie tworzenia pierwszego bazowego rozwiązania dopuszczalnego, to konieczne jest wówczas uzupełnienie bazy zmiennymi o wartościach równych 0, jeżeli natomiast degeneracja pojawi się w trakcie rozwiązywania zadania, należy pamiętać, które zera są zerami bazowymi, a które — niebazowymi.

Przykład 3.2

Rozwiążemy zadanie transportowe z trzema dostawcami i trzema odbiorcami, w którym podaż równa jest, odpowiednio, a,= 10, a, = 20, a, = 30, popyt wynosi £>i = 10, b₂ = 20, b₂ = 30, natomiast koszty jednostkowe transportu przedstawiono w postaci macierzy:

1	4
3	6
2	3

4

1 .

5

Znajdujemy rozwiązanie początkowe metodą kąta północno-zachodniego. W pierwszym kroku mamy:

min (a,, /z,) = min (10, 10)= 10,

czyli