To tylko jedna z 5 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
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)
... zobacz całą notatkę
Komentarze użytkowników (0)