152 153

152 Zadanie transportowe i problem komiwojażera

Tablica 3.13

Rozwiązanie początkowe (metoda minimalnego elementu)				Wartość funkcji celu 510
10	io-		-• 0*
0	5*		->15-
0	0		30
Nowe rozwiązanie dopuszczalne (iteracja I)				Wartość funkcji celu (iteracja 1) 480
10*	0		10*
0	15*		5*
o	0		30*

cyklu dodatniego o znalezioną uprzednio wartość minimalną (równą 10 w rozpatrywanej iteracji) oraz zmniejszamy wartości zmiennych półcyklu ujemnego o tę samą wartość. Nowe rozwiązanie bazowe przedstawiono w dolnej części tablicy 3.13.

Widzimy, że wartość funkcji celu dla rozwiązania utworzonego w pierwszej iteracji zmniejszyła się o 30 jednostek w stosunku do wartości funkcji celu dla rozwiązania początkowego.

3.4.5. Kolejne iteracje

Iteracja 2

Wykorzystując macierz wskaźników optymalności C' uzyskaną w iteracji 1 (w której gwiazdką oznaczono węzły bazowe nowego rozwiązania dopuszczalnego, otrzymanego w tej iteracji), tworzymy układ równań liniowych odpowiadający temu rozwiązaniu (tablica 3.14).

Tablica 3.14

Macierz wskaźników optymalności

0*	0	-3*
1	0*	0*
6	4	0*

Układ równali

u, + _V|=0 «, + !',-3 = 0

_Uj + v₂ = 0

u₂ + V, = 0

u, + v, = 0

Przyjmując w,=0, otrzymujemy następujące rozwiązanie:

u,    = 0, «₂ = -3, «₃ = -3,

v, =0, v₂= 3,    t'₃ = 3.

Wykorzystujemy wzór (3.11)^-’ i znajdujemy nową macierz wskaźników optymalności (tablica 3.15).

Tablica 3.15

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

Ponieważ w nowej macierzy wskaźników optymalności znajduje się element ujemny, rozwiązanie nie jest optymalne. Do bazy wprowadzamy wezeł (2, 1). Tworzymy cykl, który składa się z węzłów (2, 1), (2, 3), (1, 3), (I, 1). Dzielimy go na pólcykl dodatni i ujemny. Z bazy usuwamy węzeł (2, 3), co przedstawiono w tablicy 3.16.

Tablica 3.16

Rozwiązanie dopuszczalne			Podaż
10-	0	10*	20
0*	15	5-	20
0	0	30	30
10	15	45	Popyt
Macierz wskaźników optymalności
0*	3	0*
-2	o*	0*
3	4	0*

¹ W bieżącej iteracji we wzorze (3.11) za podstawiamy odpowiednio wartości współczynników optymalności znalezione w iteracji poprzedniej.