Wykonawcy: Data oddania prezentacji:

Dominika Percula 08.11.2013r.

Andrea Szczygieł

Rok II semestr I

Logistyka przedsiębiorstw przemysłowych

na wydziale Organizacji i Zarządzania

na Politechnice Śląskiej w Zabrzu

PREZENTACJA NR 16

„Zamknięte zagadnienia transportowe”

Źródła:

„Badania operacyjne w przykładach i zadaniach” pod. red. Karola Kukuła, Wydanie piąte, Wydawnictwo Naukowe PWN Warszawa

Zagadnienia transportowe

Zagadnienie transportowe zostało sformułowane po raz pierwszy, w 1941 r. przez, Hitchocka, jako problem opracowania planu przewozu pewnego jednorodnego produktu z kilku różnych źródeł zaopatrzenia do kilku punktów zgłaszających zapotrzebowanie na ten produkt. Kryterium optymalizacji planu przewozów jest najczęściej minimalizacja łącznych kosztów transportu.

Do tak sformułowanego zagadnienia można sprowadzić wiele różnych zagadnień, które mają taką samą strukturę matematyczną.

Uniwersalną metodą rozwiązywania modeli transportowych jest algorytm transportowy, który podobnie jak algorytm simpleks jest procedurą literacyjną.

Zamknięte zagadnienie (zadanie) transportowe ma postać następującego zadania optymalizacji liniowej:

$$\mathbf{z = \ }\sum_{\mathbf{i = 1}}^{\mathbf{m}}{}\sum_{\mathbf{j = 1}}^{\mathbf{n}}{}\mathbf{C}_{\mathbf{\text{ij}}}\mathbf{\ }\mathbf{X}_{\mathbf{\text{ij}}}\mathbf{\rightarrow min}$$

Przy spełnieniu następujących warunków ograniczających:

$\sum_{\mathbf{j = 1}}^{\mathbf{n}}{}\mathbf{X}_{\mathbf{\text{ij}}}\mathbf{= \ }\mathbf{A}_{\mathbf{i}}$ dla i = 1,  2,  …, m

$\sum_{\mathbf{i = 1}}^{\mathbf{m}}{}\mathbf{X}_{\mathbf{\text{ij}}}\mathbf{= \ }\mathbf{B}_{\mathbf{j}}$ dla j = 1,  2,  …, n

X_ij  ≥ 0 dla i = 1,  2,  …, m oraz j = 1,  2,  …, n

Oraz przy spełnieniu warunku bilansowego:

$$\sum_{\mathbf{i = 1}}^{\mathbf{m}}{}\mathbf{A}_{\mathbf{i}}\mathbf{= \ }\sum_{\mathbf{j = 1}}^{\mathbf{n}}{}\mathbf{B}_{\mathbf{j}}$$

W pierwszym etapie stosując jedną, ze znanych metod, wyznacza się początkowe rozwiązanie dopuszczalne, które następnie poprawia się w kolejnych iteracjach.

Przykład: Trzy magazyny M_1, M_2, M₃ zaopatrują w mąkę cztery piekarnie P₁,P_2,P_3,P₃,P₄ . Jednostkowe koszty transportu (w zł na tonę) oferowane miesięcznie wielkości dostaw A_i(w tonach) oraz miesięcznie zapotrzebowanie piekarń B_J (w tonach)

Dane przedstawia tabela

Magazyny	Piekarnie
	P1
M1	50
M2	40
M3	60
Bj	40

Naszym zadaniem jest opracować plan przewozu mąki z magazynów do piekarń, minimalizując całkowite koszty transportu.

Zmienne decyzyjne x_ij oznaczają ilość ton mąki, która powinna być dostarczona z i-tego magazynu (i = 1, 2, 3) do j-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:

1. dla dostawców

x₁₁ + x₁₂ + x₁₃ + x₁₄ = $\sum_{\mathbf{j = 1}}^{\mathbf{4}}{}\mathbf{x}$_1j = 70

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

x₂₁ + x₂₂ + x₂₃ + x₂₄ = $\sum_{\mathbf{j = 1}}^{\mathbf{4}}{}\mathbf{x}$_2j = 50,

x₃₁ + x₃₂ + x_3 3+ x₄₄ = $\sum_{\mathbf{j = 1}}^{\mathbf{4}}{}\mathbf{x}$_3j = 80;

1. dla odbiorców:

x₁₁ + x₂₁+ x₃₁ = $\sum_{\mathbf{j = 1}}^{\mathbf{4}}{}\mathbf{x}$_i1 = 40,

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

    x₁₂ + x₂₂ + x₃₂ = $\sum_{\mathbf{j = 1}}^{\mathbf{4}}{}\mathbf{x}$_i2 = 60,

x₁₃ + x₂₃+ x₃₃ = $\sum_{\mathbf{j = 1}}^{\mathbf{4}}{}\mathbf{x}$_i3 = 50,

x₁₄ + x₂₄+ x₃₄ = $\sum_{\mathbf{j = 1}}^{\mathbf{4}}{}\mathbf{x}$_i4 = 50.

Muszą być spełnione takie warunki brzegowe x_ij ≥ 0 (i = 1, 2, 3; j = 1,…,4).

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

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

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

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

Dla tak sformułowanego modelu wyznaczamy 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łnienie macierzy przewozów [x_ij] rozpoczyna się od klatki w lewym górnym rogu (stąd nazwa kąta północno-zachodniego). Wpisujemy do niej mniejszą z liczb (A_1, 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 M₁  P₁wpisujemy 40t (x₁₁ =40) i przesuwamy się w prawo (ponieważ zapotrzebowanie piekarni P₁ zostało zaspokojone, a magazynowi M₁ pozostało jeszcze 30t mąki, którą dostarczy do piekarni

P₂ (x₁₂= 30). Obecnie przesuwamy się w dół – do magazynu M₂, który dostarczy brakujące 30t mąki do piekarni P₃ 30 t mąki (x₃₃ = 30) i pozostałe 50t – piekarni P₄ (x₃₄ = 50). Rozwiązanie to przedstawiono w tablicy:

Magazyny	Piekarnie
	P1
M1	40
M2
M3
BJ	40

Rozwiązaniu temu odpowiadają następujące koszty transportu:

K(x_ij) = 50 ∙ 40 + 40 ∙ 30 +

+ 80 ∙ 30 +70 ∙ 20 +

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

Rozwiązanie powyższe będzie poprawione w kolejnych iteracjach algorytmu transportowego, aż do momentu uzyskania rozwiązania optymalnego.

Ponieważ jednak metoda kąta północno-zachodniego abstrahuje od kosztów transportu, dlatego też algorytm transportowy wymaga zwykle większej liczby iteracji niż wówczas, gdy rozwiązanie początkowe wyznaczymy metodą minimalnego elementu macierzy.

Metoda minimalnego elementu macierzy polega na rozmieszczeniu przewozów na tych trasach, na których koszty są najniższe. Punktem wyjścia jest przekształcenie macierzy kosztów do takiej postaci, by w każdym wierszu i w każdej kolumnie występowało, co najmniej jedno zero. Można to uzyskać, odejmując od elementów poszczególnych wierszy macierzy kosztów najmniejszy element znajdujący się w danym wierszu, a następnie od poszczególnych kolumn otrzymanej w ten sposób macierzy odejmując element najmniejszy znajdujący się w danej kolumnie.

Mając tak przekształconą macierz kosztów staramy się rozmieścić przewozy na trasy, gdzie koszty są najniższe (występują zera).

Rozmieszczanie przewozów rozpoczynamy od dowolnej klatki zawierającej zero
(klatki zerowej). Jeżeli uda się rozmieścić przewozy wyłącznie w klatkach, w których występują zera, to otrzymane rozwiązanie jest już optymalnym planem przewozów. Jeżeli nie, należy je poprawiać stosując algorytm transportowy.

Odejmując najmniejsze elementy poszczególnych wierszy od pozostałych elementów tych wierszy, otrzymujemy tablicę:

Magazyny	Piekarnie	Ai
	P1	P2
M1	30	20
M2	10	50
M3	20	0
BJ	40	60

Ponieważ jeszcze nie wszystkich kolumnach występują zera, również
od poszczególnych kolumn odejmujemy ich najmniejsze elementy. Rezultatem
jest tablica:

Magazyny	Piekarnie	Ai
	P1	P2
M1	20	20
M2	0	50
M3	10	0
BJ	40	60

Rozdysponowanie przewozów rozpoczynamy np. od klatki MjP1, gdzie możemy wpisać tylko 40 (tyle wynosi zapotrzebowanie piekarni PJ. Przechodząc do drugiej kolumny - do klatki M₃P₂ wpisujemy 60, w kolumnie trzeciej wpisujemy np. 20 na trasę M₃P₃ i 30 na trasę MJ. Dla zbilansowania wpisujemy 40 na trasę M₁P₄ i 10 na trasę M₂P₄, ponieważ w tym wypadku udało się rozmieścić wszystkie przewozy w klatkach z zerami, otrzymane
rozwiązanie jest optymalne. Rozwiązanie to przedstawiono w kolejnej tabeli:

Magazyny	Piekarnie	Ai
	P1	P2
M1	40	60
M2
M3
BJ	40	60

Związane są z nim następujące koszty transportu:

K(x_ij) =  50 • 30 + 20 • 40 + 40 • 40 + 30 • 10 +  40•60 + 70 • 20 = 8000zl

a więc znacznie niższe niż wtedy, gdy rozwiązanie początkowe wyznaczono metodą kąta północno -zachodniego. A zatem najniższe całkowite koszty transportu (8000 zł) można osiągnąć, jeżeli magazyn M_J dostarczy 30 t mąki do piekarni P₃ i 40 t do piekarni  P₄, magazyn M₂ - 40 t do piekarni  P_J i 10 t do piekarni  P₄, a magazyn M₃ - 60 t do piekarni P₂ i 20 t do piekarni P₂.