Problem transportowy
Metoda potencjałów
Metoda ta służy do sprawdzenia optymalności rozwiązania dopuszczalnego, zdegenerowanego otrzymanego w wyniku jednej z metod wcześniej opisanych lub przy pomocy cykli (opisanych nieco później).
Po obliczeniu zadania przy pomocy jednej z opisanych wcześniej metod (pn.-zach. kąta, najmniejszego elementu lub VAM) oraz ewentualnym pozbyciu się niezdegenerowania uzyskanego rozwiązania metodą e-perturbacji możemy przystąpić do sprawdzenia czy nasze rozwiązanie dopuszczalne jest optymalnym (czy koszt jest wystarczająco niski). Posłużymy się w tym celu metodą potencjałów.
Sprawdźmy czy uzyskane przez nas wcześniej metodą pn.-zach. kąta rozwiązanie dopuszczalne jest optymalne.
Zadanie (Tabelka.1.a) i jego rozwiązanie dopuszczalne uzyskane metodą pn.-zach. kąta (Tabelka.1.b) wyglądało następująco:
Tabelka.1. Zadanie transportowe (a)i jego rozwiązanie dopuszczalne uzyskane metodą pn.-zach. kąta (b)
Na początek musimy przygotować sobie tabelkę na wyniki (Tabelka.2). Ma ona wymiar równy tabelce kosztów. Dodatkowo dostawiamy pusty wiersz u góry i pustą kolumnę na końcu, do których wpisywać będziemy obliczone potencjały (w wiersz - potencjały V, w kolumnę potencjały U).
Wpisujemy w pierwszą komórkę pustej kolumny (w potencjały U) wartość U1=0. Następnie przepisujemy do tabelki koszty (z tabelki 1.a) ale tylko w miejscach odpowiadających pozycjom elementów bazowych w rozwiązaniu dopuszczalnym.
Tabelka.2. Tabelka na wyniki
Algorytm obliczeń.
Krok.1. Mamy na wejście ustawioną wartość potencjału U1 = 0, więc szukamy w wierszu odpowiadającym temu U1 (czyli w pierwszym wierszu) kosztu - jest nim koszt = 5 w pierwszej komórce. Następnie w potencjał V odpowiadający znalezionemu kosztowi (czyli V1) wpisujemy wartość równą różnicy kosztu i potencjału U1 (V1=5-0=5). (Tabelka.3.a)
Krok.2.Ustawiliśmy wartość potencjału V1 = 5, więc szukamy w kolumnie odpowiadającej V1 (czyli w pierwszej kolumnie) kolejnego kosztu - jest nim koszt = 3 (wiersz 2, kolumna 1). Następnie w potencjał U odpowiadający znalezionemu kosztowi (czyli U2) wpisujemy wartość równą różnicy kosztu i potencjału V1 (U2=3-5=-2) (Tabelka.3.b).
Poczym powtarzamy krok 1 i 2 aż do wyliczenia wszystkich potencjałów. Czyli kolejny krok:
Ustawiliśmy U2 = -2 - szukamy w wierszu drugim kolejnego kosztu (takiego który nie ma jeszcze ustawionego potencjału V) - jest nim koszt = 1 (wiersz 2, kolumna 2). Następnie w potencjał V2 wpisujemy wartość równą różnicy kosztu i potencjału U2 (V2=1-(-2)=3) (Tabelka.3.c).
Ustawiliśmy V2 = 3 - szukamy w kolumnie drugiej kolejnego kosztu (takiego który nie ma jeszcze ustawionego potencjału U) - jest nim koszt = 1 (wiersz 3, kolumna 2). Następnie w potencjał U3 wpisujemy wartość równą różnicy kosztu i potencjału V2 (U3=1-3=-2) (Tabelka.3.d).
itd.
Tabelka.3. Wyliczanie potencjałów U i V
Poniższa tabelka przedstawia już wyliczone potencjały U i V (Tabelka.4.)
Tabelka.4. Wyliczone potencjały U i V
Kolejnym krokiem jest wyliczenie kosztów pośrednich (Tabelka.5.).
Należy pozostałe (puste) komórki tabelki z wynikami wypełnić sumami potencjału Vi i Uj,
gdzie:
i=1,2,..,n
j=1,2,..,m
n - liczba dostawców
m - liczba odbiorców
Tabelka.5. Wyliczanie kosztów pośrednich
Następnie wyliczamy wskaźniki optymalności (Tabelka.7.).
W tym celu zestawmy obok siebie dwie tabelki: tabelkę obliczonych przed chwilą kosztów pośrednich i tabelkę kosztów z początku zadania (Tabelka.6.)
Tabelka.6. Tabelka kosztów pośrednich (a) i tabelka kosztów (b)
Wskaźniki optymalności wyliczamy odejmując od kosztów pośrednich (Tabelka.6.a) koszty (Tabelka.6.b)
Tabelka.7. Wskaźniki optymalności
Przyjrzyjmy się teraz wyliczonym wskaźnikom.
Jeżeli wśród nich znajdują się liczby dodatnie wówczas rozwiązanie nie jest rozwiązaniem optymalnym.
Rozwiązanie jest więc optymalne kiedy wszystkie liczby są niedodatnie (ujemne lub zera).
Wśród naszych wskaźników są wartości dodatnie - więc nasze rozwiązanie nie jest optymalne. W takim wypadku należy przekształcić rozwiązanie - zbudować cykl - następnie ponownie sprawdzić optymalność rozwiązania metodą potencjałów - znowu zbudować cykl - sprawdzić optymalność - i tak postępować aż do momentu uzyskania niedodatnich wskaźników optymalności.
karolinawalasek