48902 img318 (3)

nej prezentacji algorytmu transportowego (którego omówienie można znaleźć np. w pracach W. Sadowskiego [62], Z. Czerwińskiego [14] i R.L. Childressa [13], gdyż w praktyce rozwiązując problemy transportowe korzysta się z gotowych programów komputerowych (np. pakiety QSB, LINDO i CMMS).

Przykład 15. Trzy magazyny: M₁₅ M₂ i M₃ zaopatrują w mąkę cztery piekarnie: P₁₍ P₂, P₃ i P₄. Jednostkowe koszty transportu (w zł za tonę), oferowane miesięczne wielkości dostaw A_t (w tonach) oraz miesięczne zapotrzebowanie piekarń B_i (w tonach) podaje tabl. 73.

Tablica 73

Magazyny	Piekarnie				+
	Pi	P2	P3	P*
M,	50	40	50	20	70
m2	40	80	70	30	50
m3	60	40	70	80	80
Bj	40	60	50	50	200

Opracować plan przewozu mąki z magazynów do piekarń, minimalizujący całkowite koszty transportu.

Rozwiązanie. Jest to przykład zagadnienia transportowego zamknię-

3    4

tego (w skrócie TZ), bo £ A_t = £ B_} = 200 t.

i=i    ;=i

Zmienne decyzyjne x_tj oznaczają ilość ton mąki, która powinna być dostarczona z i-tego magazynu (i = 1, 2, 3) do y-ej piekarni (j = 1,...,4); zmiennych decyzyjnych będzie 3 -4 = 12. Ponieważ jest to zagadnienie transportowe zamknięte, dostawcy sprzedadzą całą ilość oferowanego towaru, a zapotrzebowania piekarń zostaną w całości zaspokojone. Wyrażają to warunki:

a) dla dostawców

4

■*11 + *12 + x₁₃ +3^14 = ^]*i₂- ⁼ 70, j=1

tzn. suma wielkości dostaw mąki z magazynu M_x do wszystkich piekarń powinna być równa podaży magazynu, i analogicznie, dla magazynów M₂ i M₃:

4

*21 +*22 +*23 + *24 ⁼ X *2j ~ ^0;

1=1

4

*31 + *32 + *33 +*34 ⁼ X *3J ⁼ 80 J 1=1

b) dla odbiorców:

*11 + *21 + *31 = I*n = 40,

i= 1

tzn. suma dostaw otrzymanych przez piekarnię P_x ze wszystkich trzech magazynów powinna być równa całkowitemu jej zapotrzebowaniu; podobnie dla pozostałych odbiorców (piekarń):

3

*12 + *22 + *32 = Z *i2 = ⁶⁰-i = 1

3

*13 + *23 + *33 ~ Z *i3 = 50 > i=l

3

*14 + *24 *b *34 = Z *i4 = 50.

i= 1

Muszą być także spełnione warunki brzegowe ^xu >0(i= 1, 2, 3;y =

W funkcji celu należy zminimalizować łączne koszty transportu, czyli:

K{x_ij) = 50x_n+40x₁₂ + 50x₁₃ + 20x₁₄ +

+ 40x₂ x + 80x₂₂ + 70x₂₃ + 30x₂₄ +

+ 60x₃₁+40x₃₂ + 70x₃₃ + 80x₃₄-4min.

Dla tak sformułowanego modelu wyznaczymy początkowe rozwiązanie dopuszczalne - przykładowo za pomocą dwu wybranych metod. Pierwsza z nich - metoda kąta północno-zachodniego polega na tym, że wypełnianie macierzy przewozów [x_jj] rozpoczyna się od klatki w lewym górnym rogu (stąd nazwa kąta północno-zachodniego). Wpisujemy do niej mniejszą z liczb (A^B^ odpowiadających tej klatce, a następnie przesuwamy się w prawo lub w dół: w prawo, gdy towar pierwszego dostawcy nie został jeszcze całkowicie rozdysponowany, a w dół, gdy całą podaż tego dostawcy rozdzielono odbiorcom.

W naszym przykładzie do klatki MjPj wpisujemy 40 t (x_xl = 40) i przesuwamy się w prawo (ponieważ zapotrzebowanie piekarni P₃ zostało zaspokojone, a magazynowi M _t pozostało jeszcze 30 t mąki, którą dostarczy do piekarni P₂(*i₂ = 30). Obecnie przesuwamy się w dół - do magazynu M₂, który dostarczy brakujące 30 t mąki do piekarni P₂(*2₂ ⁼ 30) i pozostałe 20 t - do piekarni P₃(x₂₃ = 20). Przesuwamy się powtórnie w dół do magazynu M₃, który dostarczy brakujące piekarni P₃ 30 t mąki (x₃₃ = 30) i pozostałe 50 t - piekarni P₄(x₃₄ = 50). Rozwiązanie to przedstawiono w tabl. 74. Rozwiązaniu temu odpowiadają następujące koszty transportu:

K{_Xij) = 50-40 + 40-30 +

+ 80-30 + 70-20 +

+ 70-30 + 80-50= 13 100 zł.

93