150 151

150 Zadanie transportowe i problem komiwojażera

3.4.2.    Wybór zmiennej wprowadzanej do bazy

Zajmiemy się sytuacją, w której istnieją ujemne wskaźniki oplymalności. Każdy z nich wskazuje na zmienną, której wprowadzenie do bazy zmniejsza wartość całkowitych kosztów transportu. Podobnie jak w przypadku prymalnej metody simpleks, najkorzystniej jest wybrać do dalszych rozważań tę zmienną, dla której spadek wartości funkcji celu przypadający na jednostkę zmiennej jest największy. Otrzymujemy w ten sposób kryterium wejścia.

Kryterium wejścia

■ W macierzy wskaźników oplymalności znajdujemy element najmniejszy Odpowiadającą mu zmienną wprowadzamy do nowej bazy. Jeżeli najmniejszej wartości wskaźnika optymalności odpowiada więcej niż jedna zmienna, to do nowej bazy wprowadzamy zmienną o najmniejszym numerze wiersza, a gdy numer wiersza dla dwóch zmiennych jest taki sam, wówczas do nowej bazy wprowadzamy zmienną o najmniejszym numerze kolumny.

W rozważanym przykładzie wprowadzimy do nowej bazy zmienną x_n.

3.4.3.    Wybór zmiennej opuszczającej bazę

Odpowiemy na pytanie, jakie konsekwencje dla rozwiązania początkowego ma przyjęcie przez zmienną a'_l, wprowadzaną do bazy wartości równej 1. Niewątpliwie wymaga to skorygowania dotychczasowej wartości jednej ze zmiennych z drugiej kolumny w macierzy przewozów. Tą zmienną jest x,₂ i trzeba ją zmniejszyć o 1, stąd nowa wartość x,₂ = 9. Zmniejszenie tej wartości powoduje konieczność zbilansowania przewozów dla drugiego odbiorcy, stąd zwiększona musi być wartość przewozu dla węzła (2, 2) do x₂₂ = 6, co jednocześnie jest przyczyną niezbilansowania przewozów dla drugiego dostawcy. Aby osiągnąć równowagę, zmniejszamy przewóz dla węzła (2,3) do poziomu x₂₂=14, co równocześnie bilansuje popyt trzeciego odbiorcy.

Określony powyżej zbiór węzłów: {(1, 3), (I, 2), (2, 2), (2, 3)} tworzy cykl. Jest to taki zbiór węzłów, który rozpoczyna się od węzła wprowadzanego do bazy i zawiera dodatkowo wszystkie (lub też tylko niektóre) węzły dotychczasowej bazy. Prawidłowo zbudowany cykl charakteryzuje się tym, że w każdej linii (a więc w każdym wierszu lub kolumnie) mamy dokładnie 0 lub 2 węzły cyklu.

Sprawdzając ten warunek dla utworzonego powyżej cyklu, widzimy, że w pierwszym i drugim wierszu mamy po 2 elementy cyklu, natomiast w wierszu trzecim — 0 elementów, podobnie w kolumnie pierwszej nie ma elementów cyklu, natomiast w drugiej i trzeciej mamy po 2 elementy. Łatwo zauważyć, że

Tablica 3.12

10	9-		-• 1*
0	6*		->-14:
0	0		45

w rozpatrywanym przez nas przykładzie w skład cyklu może wchodzić 4 lub 6 węzłów.

Tablica 3.12 ilustruje dotychczas uzyskane wyniki. Podano w niej zmiany spowodowane dołączeniem do dotychczasowego rozwiązania bazowego zmiennej je 13 = 1 oraz zaznaczono za pomocą symboli + oraz - te węzły, w których nastąpiła zmiana wartości.

Widzimy, że dokonaliśmy w ten sposób podziału cyklu na dwa półcyklc — dodatni i ujemny. Do półcykłu dodatniego zaliczamy te węzły, w których nastąpił wzrost wartości przewozu, natomiast do półcykłu ujemnego te, w których nastąpił spadek. W naszym przypadku półcykl dodatni składa się z węzłów (1,3) oraz (2, 2), a półcykl ujemny — z węzłów (1, 2) i (2, 3).

Zastanówmy się teraz, jaki jest maksymalny możliwy przyrost wartości zmiennej jc,₃, dołączanej do dotychczasowego rozwiązania. Przyrost ten związany jest z jednoczesnym obniżaniem wartości zmiennych, zaliczonych do półcykłu ujemnego. Nic możemy dopuścić do tego, aby wartość którejkolwiek ze zmiennych stała się ujemna. Oznacza to, że maksymalna wielkość, jaką może osiągnąć wprowadzana do rozwiązania zmienna x_t,, jest uwarunkowana najmniejszą wartością przewozu wśród węzłów półcykłu ujemnego. W rozpatrywanej przez nas iteracji mamy min (10, 15)= 10 i liczba ta określa maksymalną zmianę. Bazę opuszcza więc zmienna x₂₂-

Na podstawie przedstawionych powyżej uwag możemy sformułować kryterium wyjścia dla metody potencjałów.

Kryterium wyjścia

Bazę opuszcza ta zmienna należąca do półcykłu ujemnego, dla której wielkość przewozu w dotychczasowym rozwiązaniu jest minimalna. W przypadku niejednoznaczności postępujemy tak samo, jak w przypadku wystąpienia niejednoznaczności w kryterium wejścia.

3.4.4. Przejście do rozwiązania bazowego sąsiedniego

Górna część tablicy 3.13 zawiera rozwiązanie początkowe z zaznaczonymi węzłami tworzącymi półcyklc: dodatni i ujemny. Chcąc przejść do nowego rozwiązania bazowego sąsiedniego, zwiększamy wartości zmiennych dla węzłów pól-