142 143

142 Zadanie transportowe i problem komiwojażera

Rozwiązanie zapisane w macierzy X jest rozwiązaniem bazowym i zawiera 3 + 3 — 1 = 5 zmiennych bazowych. Są nimi węzły: (1,3), (2,3), (3, 1), (3,2), (3, 3). Węzły odpowiadające zmiennym bazowym nazwiemy węzłami bazowymi. Przypomnijmy, że wartość zmiennej niebazowej w rozwiązaniu bazowym wynosi zero. Węzły ustalonego wiersza lub ustalonej kolumny tworzą linię. Linią są na przykład węzły drugiego wiersza macierzy C, czyli węzły (2, 1), (2, 2) i (2, 3), lub trzeciej kolumny: (1, 3), (2, 3) i (3, 3).

Omówimy trzy metody uzyskiwania pierwszego bazowego rozwiązania dopuszczalnego: metodę minimalnego elementu, metodę VAM oraz metodę kąta północno-zachodniego. Sposób postępowania we wszystkich tych metodach jest podobny. Należy znaleźć kolejny element bazowy, a następnie na trasie (i, /), określonej przez ten węzeł, zaplanować przewóz na poziomie:

x,j = min (a_;, bj),

gdzie a_: oraz b, oznaczają, odpowiednio, aktualną podaż i aktualny popyt. Z kolei modyfikujemy wartość a, oraz b_p przyjmując:

a, = a_i~x_ij,

bj = bj-^xij.

Przynajmniej jedna z tych wartości jest zerem. Jeżeli a, = 0, to planujemy przewozy na pozostałych nierozpatrywanych trasach od i-tego dostawcy na poziomic zero. Jeżeli b] = 0. planujemy przewozy na pozostałych nierozpatrywanych trasach do y-tego odbiorcy na poziomie zero.

Omówimy kolejne metody znajdowania pierwszego dopuszczalnego rozwiązania bazowego, posługując się danymi liczbowymi przykładu 3.1.

3.3.1. Metoda minimalnego elementu macierzy kosztów

Rozwiązanie początkowe (aktualnie nieznane) i macierz jednostkowych kosztów transportu zawiera tablica 3.2.

Podamy wartości rozwiązania początkowego zgodnie z metodą minimalnego elementu. W macierzy kosztów jednostkowych szukamy elementu najmniejszego. Znajduje się on w węźle (I, 1). Maksymalne możliwości wykorzystania trasy od pierwszego dostawcy do pierwszego odbiorcy określone są przez mniejszą z liczb opisujących podaż dostawcy D_{ oraz popyt odbiorcy O,. Szukamy więc wartości minimalnej wśród liczb określających podaż pierwszego dostawcy i popyt pierwszego odbiorcy, czyli 20 i 10. Jest nią liczba 10 i określa ona przewóz na rozpatrywanej trasie w konstruowanym przez nas rozwiązaniu.

Jednocześnie stwierdzamy, że zapotrzebowanie pierwszego odbiorcy zostało w len sposób zaspokojone, stąd też nie należy go uwzględniać w dalszych rozważaniach. Planujemy więc przewozy w linii odpowiadającej temu odbiorcy

Tablica 3.2

Rozwiązanie początkowe (metoda minimalnego elementu)			Podaż
			20
			20
			30
10	15	45	Popyt
Macierz kosztów jednostkowych
i	4	7
3	5	11
6	7	9

Tablica 3.3

Rozwiązanie początkowe (metoda minimalnego elementu)			Podaż
10*			10
0			20
0			30
0	15	45	Popyt
Macierz, kosztów jednostkowych
1*	4	7
3	5	II
6	7	9

(czyli w węzłach (2, 1) i (3, 1)) na poziomie 0. Węzeł (1, 1) jest pierwszym węzłem bazowym rozwiązania początkowego. Oznaczamy go gwiazdką. Wykonane dotychczas czynności zapisano w tablicy 3.3.

Kontynuując postępowanie, znajdujemy wśród niewypełnionych elementów macierzy rozwiązania początkowego ten, dla którego koszt jednostkowy jest najmniejszy. Jest nim węzeł (1, 2). Uwzględniając zmodyfikowaną wielkość podaży dostawcy D,, równą obecnie 10, znajdujemy min (10, 15)= 10, co wskazuje na to, że należy zaplanować na trasie od dostawcy /), do odbiorcy 0₂ przewóz na poziomie 10. Podaż pierwszego dostawcy zostaje w ten sposób zredukowana do zera, co uniemożliwia zaplanowanie niezerowego przewozu na trasie, określonej przez węzeł (1, 3). Wynik postępowania zawiera tablica 3.4.

Kolejne kroki metody ilustrują tablice 3.5-3.7.