Metoda transportowa


Trzy lokale pobierajÄ… z trzech hurtowni alkohole. Zapotrzebowanie lokali w
alkohol wynoszÄ… odpowiednio: (lokal L1) 100, (lokal L2) 300, (lokal L3) 200
butelek (jednostek). Hurtownie dysponują odpowiednio następującymi ilościami
butelek alkoholu : (hurtownia H1) 100, (hurtownia H2) 100, (hurtownia H3) 400
butelek (jednostek).

Macierz jednostkowych kosztów przewozu między każdą hurtownią a każdym lokalem
przedstawia się następująco:


1 2 4

C = 2 1 3

2 1 2


Należy znaleźć taki plan przewozów, przy którym łączne koszty przewozu będą
najniższe.

Oznaczenia:

xij
wielkość dostawy z i (hurtowni) do j (lokalu),
ai
zasoby (możliwości) hurtowni,
bj
zapotrzebowanie lokalu,
(i = 1, 2, 3 , j = 1, 2, 3)

Należy określić wartości zmiennych xij , które minimalizują całkowity koszt:

K = 1x11 + 2x12 + 4x13 + 2x21 + 1x22 + 3x23 + 2x31 + 1x32 + 2x33


przy ograniczeniach:


x11 + x12 + x13 = 100 warunki ograniczajÄ…ce dla hurtowni
xij
x21 + x22 + x23 = 100

x31 + x32 + x33 = 400


x11 + x21 + x31 = 100 warunki ograniczajÄ…ce dla lokali
xij
x12 + x22 + x32 = 300

x13 + x23 + x33 = 200



xij > 0 i = 1, 2, 3, j = 1, 2, 3



Podane informacje wygodnie jest przedstawić w postaci tzw. tabliczki
transportowej:

j


i

LOKALE


Możliwości dostaw
ai


L1
L2
L3

HURTOWN I E
H1
1

x11
2

x12
4

x13


100

H2
2

x21
1

x22
3

x23


100

H3
2

x31
1

x32
2

x33


400
Zapotrzebowa-nie
bj


100

300

200
600

600


RozwiÄ…zujemy w/w zagadnienie transportowe metodÄ… algorytmu transportowego.
Postępowanie w tej metodzie składa się z trzech zasadniczych etapów:
wyznaczenia wstępnego dopuszczalnego rozwiązania bazowego,
oceny optymalności otrzymanego rozwiązania,
przejścia do nowego rozwiązania bazowego lepszego od poprzedniego.

Wstępne dopuszczalne rozwiązanie bazowe wyznaczone zostanie metodami:
A) metodą kąta północno-zachodniego,
metodÄ… minimum w wierszu,
metodÄ… minimum w kolumnie,
metodÄ… minimalnego elementu w macierzy.




A) Metoda kąta północno-zachodniego

Wypełnianie tablicy transportowej:

x11 = min { a1, b1 } = min { 100, 100 } = 100
a1 = b1
x12 = x13 = 0
x21 = x31 = 0

Zapotrzebowanie pierwszego lokalu zostało zaspokojone (pozostałe pola w
pierwszej kolumnie i w pierwszym wierszu zostanÄ… puste). Zasoby pierwszej
hurtowni zostały wyczerpane.
x22 = min { a2 , (b2
x12)} = min { 100, (300
0)} = min { 100, 300 } = 100

Zasoby drugiej hurtowni zostały wyczerpane, gdyż x23 = 0.

X32 = min { a3 , (b2
x22)} = min { 400, (300
100)} = min { 400, 200 } =
200

x33 = min { (a3
x32) , b3 } = min { (400-200 ) , 200 } = min { 200, 200 } =
200

Możliwości dostaw zostały wyczerpane.


Macierz wygląda następująco:

j

i

LOKALE


Możliwości dostaw
ai


L1
L2
L3

HURTOWN I E
H1
1

100
2

-
4

-


100

H2
2

-
1

100
3

-


100

H3
2

-
1

200
2

200


400
Zapotrzebowa-nie
bj


100

300

200
600

600


Całkowity koszt dla powyższego rozwiązania wynosi:

K = 100 + 100 + 200 + 2 · 200 = 800


Sprawdźmy czy istnieje inne optymalne rozwiązanie.
Wyznaczamy cykl dla pierwszego pustego pola i obliczamy odpowiadajÄ…cÄ… temu polu
ocenÄ™ zgodnie ze wzorem:

D ij =


D - wskaźnik optymalności,
I1 - zbiór nieparzystych numerów pól cyklu,
I2 - zbiór parzystych numerów pól cyklu,
S I1 Cij - suma całkowitych przewozów jednostkowych dla zbioru nieparzystych
pól cyklu,
S I2 Cij - suma całkowitych przewozów jednostkowych dla zbioru parzystych
pól cyklu,
* - liczba o którą będzie się zmieniać pole w cyklu.

Aby zmniejszyć wartość funkcji kryterium musi istnieć co najmniej jedno
swobodne pole, któremu odpowiada ocena ujemna. Istnienie takiego pola oznacza,
że możemy znaleźć lepsze rozwiązanie.

j

i

LOKALE


Możliwości dostaw
ai


L1
L2
L3

HURTOWN I E
H1
1

100








100

H2



1
100
-
3

+


100

H3



+ 1

200
- 2

200


400
Zapotrzebowa-nie
bj


100

300

200
600

600

Rozpoczynamy od obliczenia pola (2, 3).
Cykl dla tego pola (2, 3) (3, 3) (3, 2) (2, 2) wynosi

D23 = (3 + 1)
(2 + 1) = 4
3 = 1

D23 > 0

Jeżeli rozwiązanie optymalne oceny D23 dla pola swobodnego jest dodatnie to
zbilansowane rozwiązanie transportowe posiada dokładnie jedno
dokładnie jedno
- rozwiÄ…zanie optymalne.

Odpowiadająca temu rozwiązaniu wartość funkcji celu wynosi K = 800.



Metoda minimum w wierszu

Minimalnym elementem w wierszu macierzy kosztów jednostkowych pierwszym jest
C1k. Zatem w pierwszej kolejności rozpoczynamy wypełnianie od pola x11.

x11 = min { a1 , b1 } = min { 100, 100 } = 100
x12 = x13 = 0 ,a także x21 = x31 = 0

następnym minimalnym elementem w wierszu drugim będzie

x22 = min { a2 , (b2
a2)} = min { 100, (300
100)} = 100

zatem x23 = 0.

Kolejnym najmniejszym elementem jest w trzecim wierszu

X32 = min { (b2
x22) , a3 } = min {(300
100) , 400} = min { 200 , 400 } =
200

x33 = min {b3, (a3
x32) } = min { 200 , (400-200 ) } = min { 200, 200 } =
200



Macierz wygląda następująco:

j

i

LOKALE


Możliwości dostaw
ai


L1
L2
L3

HURTOWNIE
H1
1

100
2

-
4

-


100

H2
2

-
1

100
3

-


100

H3
2

-
1

200
2

200


400
Zapotrzebowa-nie
bj


100

300

200
600

600




Otrzymane rozwiązanie jest identyczne jak przedstawione wcześniej metodą kąta
północno-zachodniego.
Odpowiadająca temu rozwiązaniu wartość funkcji celu wynosi K = 800.






Metoda minimum w kolumnie


Przy tej metodzie wykonujemy obliczenia podobne jak przy minimum w wierszu.
Wypełnianie tablicy rozpoczyna się od pola znajdującego się w pierwszej
kolumnie, któremu odpowiada najniższy jednostkowy koszt transportu. Następnie
kontynuuje się postępowanie przechodząc kolejno pozostałe kolumny, aż do
ostatniej.

Rozwiązanie za pomocą tej metody przedstawia się następująco:



j

i

LOKALE


Możliwości dostaw
ai


L1
L2
L3

HURTOWNIE
H1
1

100
2

-
4

-


100

H2
2

-
1

100
3

-


100

H3
2

-
1

200
2

200


400
Zapotrzebowa-nie
bj


100

300

200
600

600


























Otrzymane rozwiązanie odpowiada rozwiązaniom wcześniejszym. Wartość funkcji
celu wynosi K = 800.





Metoda minimum elementu w macierzy


W przypadku tej metody badana jest cała macierz kosztów jednostkowych, by
znaleźć minimalny element. Rozpoczynamy od pola, któremu ten element odpowiada.
Następnie kolejno szukamy minimalnego elementu wśród jednostkowych kosztów
odpowiadających pustym polom. Wyznaczamy w ten sposób następne pole, które
należy wypełnić.

Wyznaczone tą metodą rozwiązanie ma postać:

j

i

LOKALE


Możliwości dostaw
ai


L1
L2
L3

HURTOWNIE
H1
1

100
2

-
4

-


100

H2
2

-
1

100
3

-


100

H3
2

-
1

200
2

200


400
Zapotrzebowa-nie
bj


100

300

200
600

600

























Otrzymaliśmy identyczne rozwiązanie.

RozwiÄ…zanie dla przedstawione w tej pracy problemu transportowego jest jedynym
rozwiÄ…zaniem optymalnym.