Transport19

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

Przykład 15. Trzy magazyny: M_t, M₂ i M₃ zaopatrują w mąkę cztery piekarnie: P_1; P₂, P₃ i P₄. Jednostkowe koszty transportu (w zł za tonę) oferowane miesięczne wielkości dostaw A_t (w tonach) oraz miesięczne zapo> trzebowanie piekarń B_} (w tonach) podaje tabl. 73.

Tablica 73

Magazyny	Piekarnie				A,
	P !	P2	P3	P4
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ń, minimalizujiyi cy całkowite koszty transportu.

Rozwiązanie. Jest to przykład zagadnienia transportowego zamknif<

3    4

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

i=i    j= 1

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

a) dla dostawców

4

x_ll + x₁₂ + x₁₃ + x_l4. = X^Xlj ^{= 70}’ i'=l

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

4

-'■Zl ■h'^2 2 "h -^23    ^,1C24 ” J]x2^ = 50,

/-I

b) dla odbiorców:

*11+*21+*3i = Z *u = ⁴⁰ >

i=l

''ii. suma dostaw otrzymanych przez piekarnię P_x ze wszystkich trzech "ingazynów powinna być równa całkowitemu jej zapotrzebowaniu; podobnie •Ilu pozostałych odbiorców (piekarń):

3

*12 + *22 + *32 ⁼ Z *>2 ⁼ ^0 >

i= 1

3

*13 +*23 + *33 ⁼ Z *i3 ⁼    >

i= 1

3

*14 + *24+*34 ⁼ Z *«4 ⁼ i = 1

Muiizą być także spełnione warunki brzegowe x_tj ^ 0 (i = 1, 2, 3; j =

(tinkcji celu należy zminimalizować łączne koszty transportu, czyli:

K(x_iJ) = 50xj! 4- 40x₁₂ + 50x₁₃ 4- 20x₁₄ +

4“ 40x₂₁ 4~ 80x₂₂ 4” 70x₂₃ 4“ 30x₂₄ 4~

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

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

W naszym przykładzie do klatki M_tPj wpisujemy 40 t (x₃₁ = 40) i prze-•wiiiny się w prawo (ponieważ zapotrzebowanie piekarni P₃ zostało za-imlojone, a magazynowi Mj pozostało jeszcze 30 t mąki, którą dostarczy do '4unii P₂(*₁₂ = 30). Obecnie przesuwamy się w dół - do magazynu M₂,

>omV dostarczy brakujące 30 t mąki do piekarni P₂(*₂₂ = 30) i pozostałe •i I do piekarni P₃(*₂₃ = 20). Przesuwamy się powtórnie w dół do magazy-u M który dostarczy brakujące piekarni P₃ 30 t mąki (x₃₃ = 30) i pozostałe " I piekarni P₄(*₃₄ = 50). Rozwiązanie to przedstawiono w tabl. 74. •u#wlt|ZHniu temu odpowiadają następujące koszty transportu:

K(x,j) - 50 ■ 40 i 40-30+

I HO 10 | 70-20 +

| 70 U) | HO-50 - 13 KH) zł.