Przykład AT-3.
Wyznaczyć poprawiony (o mniejszych kosztach całkowitych) plan dostaw dla rozwiązania
startowego z przykładu AT-2.
Rozwiązanie:
Wyznaczony w przykładu AT-2 startowy, bazowy plan dostaw był następujący:
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
210 90 0 0 300
D1
0 80 70 0 150
D2
0 0 290 140 430
D3
880
popyt
210 170 360 140
Na trasie (3,1) otrzymaliśmy "31 = -1 - oznacza to, że kierując jednostkową dostawę
na trasę (3,1) obniżamy całkowite koszty transportu o 1 jednostkę. Zatem, jeśli w nowym
planie dostaw zmienna x31 będzie zmienną bazową to "KC = "31 �" x31 .
Należy teraz ustalić, która z poprzednich zmiennych bazowych zostanie z bazy
usunięta oraz wartość dla nowej zmiennej bazowej x31 . Odpowiednia procedura polega
znalezienia cyklu, który tworzy pole (3,1) z pozostałymi polami odpowiadającymi
niewiadomym bazowym. W tablicy zaznaczamy pola (zacieniowane), którym odpowiadają
niewiadome bazowe oraz znakiem  + pole na które kierujemy dostawę.
O2 O3 O4
O1
D1
- +
D2
- +
D3
+ -
Przenosząc dostawę na trasę (3,1) musimy: zmniejszyć dostawę na trasie (1,1) (co
zaznaczamy znakiem  .-  ) oraz zwiększyć dostawę na trasie (1,2) (co zaznaczamy znakiem
 .+  ), następnie zmniejszyć dostawę na trasie (2,2) oraz zwiększyć dostawę na trasie (2,3)
i konsekwentnie zmniejszyć dostawę na trasie (3,3) . Ponieważ liczba znaków  .+  i  .-  jest
w każdym wierszu i w każdej kolumnie taka sama to szukany cykl został znaleziony.
Aby ustalić wartość dostawy x31 , korzystamy z warunku xij e" 0: dla pól oznaczonych
znakiem  -  wielkości dostaw nie mogą być ujemne stąd:
x31 = min {x11, x22 , x33} = min{210, 80, 290} = 80
Aby otrzymać poprawiony plan dostaw musimy dodać po 80 do wielkości dostaw na polach
oznaczonych znakiem  +  oraz odjąć po 80 od wielkości dostaw na polach oznaczonych
znakiem  -  .
Nowy (poprawiony) plan przewozów jest zatem następujący
Odbiorca  j
O2 O3 O4
O1
podaż
Dostawca  i
130 170 0 0 300
D1
0 0 150 0 150
D2
80 0 210 140 430
D3
popyt
210 170 360 140 880
Dla nowego poprawionego planu dostaw KC + "KC = 2920 + (-1) �"80 = 2840 .
Dociekliwa Osoba zauważy, że to rozwiązanie otrzymaliśmy metodą minimalnego elementu
macierzy kosztów (był to oczywiście przypadek a nie reguła).
Sprawdzając optymalność nowego rozwiązania otrzymamy:
O2 O3 O4
O1
ui
3 1 0*
D1
6 3
+5 +5
5 2 0 -1
D2
2
-1 +1 +5
3 0
D3
3 1
6
+2
6 3 3 1
v
j
Na trasie (2,1) otrzymaliśmy ujemną wartość wskaz
nika optymalności "21 = -1 co oznacza,
że wyznaczone rozwiązanie nie jest optymalne. Wyznaczenie nowego planu przewozów (po
skierowaniu dostawy na trasę (2,1) ) pozostawiamy Osobie studiującej.