Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja I – 15. Zagadnienie transportowe – MIM UW

Zagadnienia

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].

Ćwiczenie 15.1

Dane jest zagadnienie transportowe opisane tabelą:

Koszty O_{1} O_{2} O_{3} O_{4} Podaże
D_{1} 1 3 7 9 15
D_{2} 5 7 5 10 5
D_{3} 6 2 4 8 10
D_{4} 6 0 2 10 5
Popyty 7 8 10 10

Znajdź wierzchołek startowy stosując algorytm:

a) Wierzchołka północno - zachodniego.

b) Minimalnych kosztów.

Ćwiczenie 15.2

W zagadnieniu transportowym opisanym tabelą:

Koszty O_{1} O_{2} O_{3} O_{4} Podaże
D_{1} 1 3 7 9 9
D_{2} 6 9 5 10 13
D_{3} 6 4 4 10 21
Popyty 10 7 9 17

aktualnie realizowany jest następujący schemat przewozów P_{1}.

Przewozy O_{1} O_{2} O_{3} O_{4} Podaże
D_{1} x x x 9
D_{2} x x 5 8
D_{3} 10 7 4 x
Popyty

Stosując metodę sympleks popraw ten schemat przewozów do optymalnego i znajdź wszystkie optymalne schematy przewozów.

Ćwiczenie 15.3

Znajdź wszystkie optymalne schematy przewozów dla zadania transportowego:

Koszty H_{1} H_{2} H_{3} H_{4} Popyty
S_{1} 9 2 1 10 8
S_{2} 3 3 0 6 5
S_{3} 9 5 6 15 11
Podaże 5 5 10 4

Zalecaną jest metoda minimalnych kosztów.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.