3848093736

13

1.1. Zagadnienie transportowe

1.1.5. Algorytm transportowy

Algorytm transportowy (nazywany też metodą potencjałów) jest metodą rozwiązywania zadania transportowego wykorzystującą własności macierzy przewozów oraz zadanie dualne do zadania transportowego. Jeżeli oznaczymy przez pi, i = 1,... ,m, oraz qj,j = 1,... n, zmienne dualne związane z ograniczeniami odpowiednio (1.7) oraz (1.3), to zadanie dualne przyjmuje postać:

m    n

zmaksymalizować ^ aipi + ^ bjqj    (1.8)

i=1    j=1

przy ograniczeniach pi + qj < cy, i = 1,..., m, j = 1,..., n (1.9)

Zmienne pi oraz qj są dowolne co do znaku. Z własności ?? rozwiązań optymalnych zagadnienia dualnego wynika, że jeśli X{j jest zmienną bazową to odpowiednia zmienna uzupełniająca w ograniczeniu zadania dualnego przyjmuje wartość zero, a zatem spełniony jest następujący układ równań:

Pi + qj = c^, (i,j) £ B    (1-10)

gdzie B oznacza bazę. Aby sprawdzić, czy jest to rozwiązanie optymalne należy wyznaczyć wartości Zij — c^. Zauważmy że wartości wskaźników Zij w zadaniu transportowym przyjmują wartości Zij = Pi + qj, a zatem wartości    odpowiadające elementom wiersza wskaźnikowego macierzy

sympleks obliczamy jako Pi+qj—Cij. Jeżeli wszystkie wartości wiersza wskaźnikowego są mniejsze lub równe zeru, to rozwiązanie jest optymalne. Jest to równoważne warunkowi, aby wszystkie elementy przeciwne: c- = Cij—pi~qj były nieujemne. Dla ułatwienia zapisu przyjmijmy zatem Ui = —pi oraz Vj = — qj i oznaczmy

Ą] = Ui+ Vj + Cij    (1.11)

Macierz [c-] nazywamy równoważną macierzą zerową, a współczynniki Ui,i = 1,..., m oraz Vj,j = 1,..., n potencjałami. Jeżeli zmienna Xij jest zmienną bazową, to z równania (1.10) i definicji potencjałów wynika, że c- = 0. Otrzymujemy układ (m + n — 1) równań z (m + n) niewiadomymi. Jest to układ nieoznaczony, a zatem posiadający nieskończenie wiele rozwiązań. Można wykazać, że wszystkie rozwiązania tego układu wyznaczają tę samą równoważną macierz zerową, a zatem wystarczy znaleźć jedno, dowolne z tych rozwiązań. Dla ułatwienia zwykle przyjmuje się, że u\ = 0 i wtedy kolejne wartości potencjałów można łatwo wyznaczyć przez podstawienie. Znając wartości potencjałów równie łatwo wyznaczamy pozostałe wartości zerowej macierzy równoważnej.

Macierz zerową rozwiązania początkowego otrzymanego metodą VAM przedstawiono w tablicy 1.6. Dla każdej pary (i,j) (odpowiadającej zmiennej decyzyjnej Xij) w tablicy umieszczono trzy wartości. Liczba w górnym wierszu to wartość zmiennej decyzyjnej (wartość z macierzy przewozów), w prawym dolnym narożniku znajduje się wartość z macierzy kosztów c^, a w lewym dolnym narożniku obliczona wartość zerowej macierzy równoważnej

c?-¹³ ’

Rozwiązanie nie jest optymalne, gdyż wartość c®2 < 0. Dalsze postępowanie polega na zmianie bazy przez usunięcie z grafu wierzchołka odpowia-