3848093734

1.1. Zagadnienie transportowe    11

Tablica 1.3. Wyznaczenie rozwiązania początkowego metodą najmniejszego elementu macierzy

atj ilość przesłana    wartości    zredukowana pozostała

zmiennych    macierz    podaż

£12 — 4000	' 3 7 6 ’		1000 ‘
ai2 min(5000, 4000) £22 = 0	7 2 3		6000
£32 = 0	.2 4 5.		. 2500 .

pozostały popyt    [6000 0 2000 1500]

£31 = 2500 r 1 7 6 1    1000

min(6000, 2500)    x₃₃ = 0    7 o q    ⁶⁰⁰⁰

x₃₄ = 0 L ⁷ 2 6 J [o

pozostały popyt    [3500 0 2000 1500]

031

023    min(4000, 2000)

£23 = 2000 £13 = 0

pozostały popyt

3 6 7 3

[3500 0 0 1500]

1000

4000

0

o₂₄    min(2500, 1500)

£24 — 1500

£14 = 0

[3500 0 0 0]

1000

2500

0

pozostały popyt

0 ' 2500 0

on min(1000, 3500) £n = 1000    [7]

pozostały popyt    [2500 0 0 0]

021    min(2500, 2500)    £21 = 2500

pozostały popyt

[0 0 0 0]

0

0

o

Metoda VAM

W metodzie VAM jako następny wybieramy element, którego pominięcie może spowodować znaczny wzrost kosztów w kolejnej iteracji. Jest ona nieco bardziej złożona niż poprzednie, ale otrzymane rozwiązanie jest zwykle bliskie optymalnemu. Aby wyznaczyć kolejny element macierzy najpierw wyznaczamy różnice r*, i = 1,..., m, między dwoma najmniejszymi elementami w każdym wierszu i różnice dj,j = 1,... ,n, między dwoma najmniejszymi elementami w każdej kolumnie zredukowanej macierzy kosztów. Następnie znajdujemy = ma,Xi{ri} oraz di = maxj{dj}. Jeżeli r^ > di, to następnym elementem macierzy jest a^h, gdzie akh = mirij{akj}, czyli najmniejszy element w wierszu A:-tym. Jeżeli    < di, to następnym elementem macierzy

jest ahi, gdzie ahi = mini{au}, czyli najmniejszy element w kolumnie l-tej.

Przebieg obliczeń dla danych z tablicy 1.1 przedstawiono w tablicy 1.4. Ponieważ redukcja macierzy przebiega identycznie jak w metodach omówionych powyżej, w tablicy przedstawiono wartości ri oraz dj oraz wartości elementów Xij macierzy przewozów wyznaczone w każdej iteracji.

W końcowych iteracjach, gdy pozostały już tylko elementy w wierszu drugim, wybieramy elementy tego wiersza począwszy od najmniejszych wartości. Rozwiązanie otrzymane metodami najmniejszego elementu macierzy oraz VAM dały w tym przykładzie to samo rozwiązanie. Każde z otrzymanych rozwiązań jest dopuszczalne, ale nie koniecznie optymalne.