Zagadnienia

15.1 Zagadnienie transportowe

15. Zagadnienie transportowe

15.1. Zagadnienie transportowe

Mamy n punktów wysyłających towar i t punktów odbierających. Istnieje droga od każdego dostawcy do każdego odbiorcy i znany jest koszt transportu jednostki towaru.

Jak zorganizować transport, żeby koszt był minimalny?

Zapiszmy dane w postaci tabeli:

$\begin{array}[]{|c|ccccc|c|}\hline&O_{1}&O_{2}&\cdots&\cdots&O_{t}&\text{podaż}\\ \hline D_{1}&a_{{1,1}}&a_{{1,2}}&\cdots&\cdots&a_{{1,t}}&b_{1}\\ D_{2}&a_{{2,1}}&a_{{2,2}}&\cdots&\cdots&a_{{2,t}}&b_{2}\\ \vdots&\vdots&\vdots&\ddots&&\vdots&\vdots\\ D_{n}&a_{{n,1}}&a_{{n,2}}&\cdots&\cdots&a_{{n,t}}&b_{n}\\ \hline\text{popyt}&c_{1}&c_{2}&\cdots&\cdots&c_{t}&\\ \hline\end{array}$

Wprowadźmy zmienne $x_{{i,j}}$ opisujące ilość towaru przewożonego od i - tego dostawcy do j - tego odbiorcy.

Niech $a_{{ij}}$ oznacza koszt przewiezienia jednostki towaru.

Jako funkcję celu przyjmijmy: $min\ x_{{0}}\ =\sum _{{i=1}}^{{n}}\sum _{{j=1}}^{{t}}a_{{i,j}}x_{{i,j}}$

Zadanie transportowe nazywamy zbilansowanym gdy podaż = popyt,

czyli $\sum _{{i=1}}^{{n}}\ b_{i}\ =\ \sum _{{j=1}}^{{t}}\ c_{{j}}$ .

W przypadku zbilansowanym obszar dopuszczalny opisany jest następującym układem równań i nierówności:

$\sum _{{j=1}}^{{t}}x_{{1,j}}=b_{1}$ , - pierwszy dostawca wysyła cały towar,

$\sum _{{j=1}}^{{t}}x_{{2,j}}=b_{2}$ , - drugi dostawca wysyła cały towar,

$\vdots$

$\sum _{{j=1}}^{{t}}x_{{1,j}}=b_{n}$ , - n-ty dostawca wysyła cały towar,

$\sum _{{i=n}}^{{t}}x_{{1,j}}=c_{1}$ , - pierwszy odbiorca dostaje cały towar,

$\sum _{{i=n}}^{{t}}x_{{2,j}}=c_{2}$ , - drugi odbiorca dostaje cały towar,

$\vdots$

$\sum _{{i=n}}^{{t}}x_{{1,j}}=c_{t}$ , - t-ty odbiorca dostaje cały towar,

Ponadto nie można przewozić ujemnej liczby towarów - a więc:

$\forall _{{1\leq i\leq n}}\forall _{{1\leq j\leq t}}\;\ x_{{i,j}}\geq 0$

Czasami towary są podzielne jak prąd czy woda, ale zwykle dodajemy warunki:

$\forall _{{i,j}}\; x_{{i,j}}\in Z$

Jeśli dodamy do siebie równania opisujące popyt otrzymamy

$\sum _{{i=1}}^{{n}}\sum _{{j=1}}^{{t}}x_{{i,j}}=\sum _{{i=1}}^{{n}}b_{i}$

Analogicznie jeśli dodamy do siebie równania opisujące podaż otrzymamy

$\sum _{{j=1}}^{{t}}\sum _{{i=1}}^{{n}}x_{{i,j}}=\sum _{{j=1}}^{{t}}c_{i}$ .

Zatem dla zadania niezbilansowanego układ równań opisujący obszar dopuszczalny jest sprzeczny zaś dla zadania zbilansowanego układ równań opisujący obszar dopuszczalny jest zależny. Można pokazać, że rząd macierzy układu jest równy $n+t-1$ a więc tyle musi być zmiennych bazowych.

Zakładamy, że zagadnienie jest zbilansowane.

Zadanie opisują dwie tablice mające tyle wierszy ilu jest dostawców i tyle kolumn ilu jest odbiorców plus wiersze i kolumny nagłówków.

W pierwszej zapisujemy koszty lub koszty zredukowane - czyli to co jest nad kreską w tablicy sympleks.

Druga tablica opisuje przewozy - dla zmiennej bazowej $x_{{i,j}}$ wstawiamy ilość towaru przewożonego od i - tego dostawcy do j - tego odbiorcy zaś dla zmiennych niebazowych krzyżyk x. Ta tablica opisuje to co jest w tablicy sympleks z prawej strony kreski i umiejscowienie zmiennych bazowych jak w zrewidowanej metodzie sympleks.

Szukanie wierzchołka startowego.

a) Metoda wierzchołka północno - zachodniego

1) Jeżeli mamy tylko jednego dostawcę lub tylko jednego odbiorcę to wszystkie zmienne są bazowe.

W tablicę przewozów wpisujemy popyty lub podaże odpowiednio.

2) Wybieramy wierzchołek północno - zachodni czyli miejsce w lewym górnym rogu.

2a) Jeżeli $b_{1}\geq c_{1}$ to w to miejsce tablicy wpisujemy $c_{1}$ zaś w pozostałe miejsca pierwszej kolumny krzyżyki.

( $x_{{1,1}}=c_{1}$ ). Teraz zamiast $b_{1}$ wpisujemy $b_{1}-c_{1}$ i usuwamy pierwszego odbiorcę.

2b) Jeżeli $b_{1}<c_{1}$ to w to miejsce tablicy wpisujemy $b_{1}$ zaś w pozostałe miejsca pierwszego wiersza krzyżyki.

( $x_{{1,1}}=b_{1}$ ). Teraz zamiast $c_{1}$ wpisujemy $c_{1}-b_{1}$ i usuwamy pierwszego dostawcę.

GO TO 1.

Przykład 15.1

Dane jest zagadnienie transportowe opisane tabelą:

$Min\{ 6,15\}=6$

Przewozy	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$	Podaże
$D_{1}$	6				15 $\setminus$ 9
$D_{2}$	X				5
$D_{3}$	X				10
$D_{4}$	X				5
Popyty	6 $\setminus$	4	10	15

$Min\{ 4,9\}=4$

Przewozy	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$	Podaże
$D_{1}$	6	4			15 $\setminus$ 9 $\setminus$ 5
$D_{2}$	X	X			5
$D_{3}$	X	X			10
$D_{4}$	X	X			5
Popyty	6 $\setminus$	4 $\setminus$	10	15

$Min\{ 10,5\}=5$

Przewozy	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$	Podaże
$D_{1}$	6	4	5	X	15 $\setminus$ 9 $\setminus$ 5 $\setminus$
$D_{2}$	X	X			5
$D_{3}$	X	X			10
$D_{4}$	X	X			5
Popyty	6 $\setminus$	4 $\setminus$	10 $\setminus$ 5	15

$Min\{ 5,5\}=5$

Przewozy	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$	Podaże
$D_{1}$	6	4	5	X	15 $\setminus$ 9 $\setminus$ 5 $\setminus$
$D_{2}$	X	X	5		5 $\setminus$ 0
$D_{3}$	X	X	X		10
$D_{4}$	X	X	X		5
Popyty	6 $\setminus$	4 $\setminus$	10 $\setminus$ 5 $\setminus$	15

Mamy teraz jedną linię.

Przewozy	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$	Podaże
$D_{1}$	6	4	5	X	15 $\setminus$ 9 $\setminus$ 5 $\setminus$
$D_{2}$	X	X	5	0	5 $\setminus$ 0 $\setminus$
$D_{3}$	X	X	X	10	10 $\setminus$
$D_{4}$	X	X	X	5	5 $\setminus$
Popyty	6 $\setminus$	4 $\setminus$	10 $\setminus$ 5 $\setminus$	15 $\setminus$

b) Metoda minimalnych kosztów.

Ta metoda różni się od poprzedniej tym, że zamiast wierzchołka północno - zachodniego wybieramy miejsce tabeli o minimalnym koszcie.

Metoda sympleks.

0) dana jest tablica kosztów K i tablica przewozów P opisująca wierzchołek startowy.

1) Test optymalności.

1a) W tablicy kosztów zaznaczamy miejsca odpowiadające zmiennym bazowym.

1b) Za tablicą w prawym górnym rogu wpisujemy 0.

1c) Uzupełniamy miejsca pod tabelą i z prawej strony takimi liczbami by w przypadku

zaznaczonych komórek - zmiennych bazowych,

suma liczby w tablicy, liczby dopisanej w wierszu i liczby dopisanej w kolumnie dawała 0.

1c) Wyliczamy tablicę kosztów zredukowanych dodając do każdego wiersza liczbę dopisaną z prawej strony

i dodając do każdej kolumny liczbę dopisaną poniżej.

2) Jeżeli nie ma liczb ujemnych w tablicy kosztów to STOP. Ostatni schemat przewozów jest optymalny.

Przykład 15.2

W zadaniu z poprzedniego przykładu koszty opisane są tabelą:

Zaznaczamy komórki zmiennych bazowych * i dopisujemy 0 w pierwszym wierszu.

Koszty	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$
$D_{1}$	1*	3*	7*	9	0
$D_{2}$	5	7	5*	10*
$D_{3}$	6	2	4	8*
$D_{4}$	6	0	2	10*

Wymusza to liczby -1,-3 i -7 w pierwszych kolumnach.

Koszty	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$
$D_{1}$	1*	3*	7*	9	0
$D_{2}$	5	7	5*	10*
$D_{3}$	6	2	4	8*
$D_{4}$	6	0	2	10*
	-1	-3	-7

Wymusza to 2 w drugim wierszu.

Koszty	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$
$D_{1}$	1*	3*	7*	9	0
$D_{2}$	5	7	5*	10*	2
$D_{3}$	6	2	4	8*
$D_{4}$	6	0	2	10*
	-1	-3	-7

Wymusza to -12 w czwartej kolumnie.

Koszty	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$
$D_{1}$	1*	3*	7*	9	0
$D_{2}$	5	7	5*	10*	2
$D_{3}$	6	2	4	8*
$D_{4}$	6	0	2	10*
	-1	-3	-7	-12

Wymusza to 4 i 2 w ostatnich wierszach.

Koszty	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$
$D_{1}$	1*	3*	7*	9	0
$D_{2}$	5	7	5*	10*	2
$D_{3}$	6	2	4	8*	4
$D_{4}$	6	0	2	10*	2
	-1	-3	-7	-12	2

Obliczając koszty zredukowane otrzymujemy.

$\mathbf{Koszty_{1}}$	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$
$D_{1}$	0	0	0	-3
$D_{2}$	6	6	0	0
$D_{3}$	9	3	1	0
$D_{4}$	7	-1	-3	0

3) Wędrowanie między wierzchołkami.

3a) Wybieramy drogę o ujemnym koszcie - w przykładzie drogę wyznaczoną zmienną $x_{{4,2}}$ i w tablicy przewozy do X dopisujemy $+\Delta$ .

3b) Wpisując przy odpowiednich zmiennych bazowych $\pm\Delta$ budujemy cykl tak by popyt i podaż z uwzględnieniem $\Delta$ nie zmieniła się.

3c) Wybieramy maksymalną $\Delta=min\{ x_{{i,j}}\ |\Delta\text{ występuje ze znakiem -}\}$

4) Podstawiamy wyliczoną wartość $\Delta$ i usuwamy z bazy jedną ze zmiennych na której ilość przewożonego towaru zmniejszyliśmy do 0.

Przykład 15.3

Przewozy	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$
$D_{1}$	6	4	5	X
$D_{2}$	X	X	5	0
$D_{3}$	X	X	X	10
$D_{4}$	X	X $+\Delta$	X	5

Budujemy cykl:

Przewozy	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$
$D_{1}$	6	4 $-\Delta$	5 $+\Delta$	X
$D_{2}$	X	X	5 $-\Delta$	0 $+\Delta$
$D_{3}$	X	X	X	10
$D_{4}$	X	X $+\Delta$	X	5 $-\Delta$

$\Delta=min\{ 4,5,5\}=4$ i nowym schematem przewozów jest:

Przewozy	$O_{1}$	$O_{2}$	$O_{3}$	$O_{4}$
$D_{1}$	6	X	9	X
$D_{2}$	X	X	1	4
$D_{3}$	X	X	X	10
$D_{4}$	X	4	X	1

Transport niezbilansowany

W przypadku gdy podaż przewyższa popyt zadanie można doprowadzić do zbilansowanego wprowadzając sztucznego odbiorcę o popycie równoważącym różnicę i kosztach przewozów 0. Po wyliczeniu optymalnego przewozu mówimy, że towary wysłane do sztucznego odbiorcy zostają u dostawców.

W przypadku gdy popyt przewyższa podaż, analogicznie, zadanie można doprowadzić do zbilansowanego wprowadzając sztucznego dostawcę o podaży równoważącym różnicę i kosztach przewozów 0.

Jako literaturę uzupełniającą do tego tematu polecamy książki [10] i [6].