29

6.6. Zagadnienie transportowe – algorytm transportowy

Do problemów decyzyjnych rozwiązywanych przy pomocy metod programowania

liniowego należy klasyczne zagadnienie transportowe. Polega ono na ustaleniu takiego planu
przewozów, aby ponieść jak najmniejsze łączne koszty.
W zagadnieniu transportowym wyróżniamy:
1. Punkty nadania towaru - nazywane dostawcami. Przyjmujemy, że w analizowanym

problemie występuje m dostawców, których oznaczamy symbolami:

m

D

D

D

,

,

,

2

1

K

.

2. Punkty odbioru towaru - nazywane odbiorcami. Przyjmujemy, że w analizowanym

problemie występuje n odbiorców, których oznaczamy symbolami:

n

O

O

O

,

,

,

2

1

K

.

Zakładamy, że każdy z dostawców posiada taki sam towar, takiej samej jakości (bez

braków), odpowiednio w ilościach:

m

a

a

a

,

,

,

2

1

K

(ilości te określają podaż towaru u

dostawców). Na ten sam towar zgłosili zapotrzebowanie odbiorcy odpowiednio w ilościach:

n

b

b

b

,

,

,

2

1

K

(popyt odbiorców). Jednostkowy koszt przewozu towaru od dostawcy „i” do

odbiorcy „j” wynosi

ij

c

dla

m

i

,

,

2

,

1

K

=

oraz

n

j

,

,

2

,

1

K

=

.

Oznaczmy przez

ij

x

(zmienna decyzyjna) ilość towaru przewożoną na od dostawcy „i” do

odbiorcy „j” ( na trasie

)

,

(

j

i

) wówczas plan przewozów zapiszemy jako macierz

























=

mn

m

m

n

n

x

x

x

x

x

x

x

x

x

L

M

M

M

M

M

M

L

L

2

1

2

22

21

1

12

11

X

.

Zakładamy, że macierz X jest macierzą o nieujemnych elementach (dla wszystkich dostaw:

0

≥

ij

x

- towar jest przewożony od dostawcy do odbiorcy a nie odwrotnie).

Model zadania transportowego można zapisać następująco:

Znaleźć najmniejszą wartość funkcji

∑∑

=

=

⋅

=

m

i

n

j

ij

ij

x

c

f

1

1

)

(X

na zbiorze rozwiązań

dopuszczalnych

X

,w którym spełnione są:

a. warunki dla dostawców













≤

+

+

+

≤

+

+

+

≤

+

+

+

m

mn

m

m

n

n

a

x

x

x

a

x

x

x

a

x

x

x

L

L

L

L

L

L

L

L

L

L

L

L

L

2

1

2

2

22

21

1

1

12

11

30

b. warunki dla odbiorców













=

+

+

+

=

+

+

+

=

+

+

+

n

mn

n

n

m

m

b

x

x

x

b

x

x

x

b

x

x

x

L

L

L

L

L

L

L

L

L

L

L

L

L

2

1

2

2

22

12

1

1

21

11

c. warunki brzegowe

0

≥

ij

x

dla

m

i

,

,

2

,

1

K

=

oraz

n

j

,

,

2

,

1

K

=

.

Macierz współczynników przy niewiadomych jest macierzą wymiaru

)

(

)

(

n

m

n

m

⋅

×

+

, której

elementy przyjmują wartości ze zbioru

}

1

,

0

{

.

Zauważmy, że zgodnie z wcześniejszymi założeniami - łączna podaż dostawców

wynosi:

∑

=

m

i

i

a

1

natomiast łączne zapotrzebowanie odbiorców jest równe:

∑

=

n

j

j

b

1

. Mogą zajść

następujące przypadki:

1.

∑

=

m

i

i

a

1

≥

∑

=

n

j

j

b

1

- zadanie transportowe nazywamy zadaniem otwartym;

2.

∑

=

m

i

i

a

1

=

∑

=

n

j

j

b

1

- zadanie transportowe nazywamy zadaniem zamkniętym;

3.

∑

=

m

i

i

a

1

≤

∑

=

n

j

j

b

1

- zadanie transportowe jest wówczas zadaniem sprzecznym.

Zadania transportowe otwarte (1.) można przekształcić na zadania zamknięte

zwiększając liczbę dostawców. Przyjmujemy, że w problemie występuje dostawca dodatkowy
(fikcyjny, traktowany jako magazyn dostawców) oznaczamy go symbolem

1

+

n

O

, którego

zapotrzebowanie jest równe różnicy między podażą i popytem;

∑

∑

=

=

+

−

=

n

j

j

m

i

i

n

b

a

b

1

1

1

.

Przyjmujemy, że jednostkowe koszty przewozu towaru od dostawcy „

i” do odbiorcy „n+1”

wynoszą

0

1

,

=

+

n

i

c

dla

m

i

,

,

2

,

1

K

=

.

Klasyczne zadanie transportowe jest więc zadaniem programowania liniowego i do

jego rozwiązania można zastosować algorytm simpleks. Jest on jednak mało efektywny ze

względu na dużą liczbę niewiadomych występujących w modelu. Stąd też dla zadań

transportowych opracowano nowy, efektywniejszy sposób wyznaczania rozwiązania

optymalnego nazywany algorytmem transportowym (zostanie on zaprezentowany w

następnym punkcie). Opis tej metody można znaleźć także, np. w pozycji [3] s.92-111.

Algorytm transportowy

Jest, podobnie jak algorytm simpleks, metodą numeryczną realizowaną w sposób

iteracyjny. Algorytm transportowy stosujemy do wyznaczania rozwiązania optymalnego
zadań transportowych zamkniętych. Jego zastosowanie nie wymaga zapisu modelu
matematycznego zadania (było to konieczne przystosowaniu algorytmu simpleks) lecz

31

jedynie informacji o parametrach zadania. W algorytmie tym wykonuje się dwa powtarzające
się na przemian etapy: wyznaczanie rozwiązania bazowego i sprawdzania czy jest ono
optymalne. Schemat działania tego algorytmu podano na Rys 2.

Poda

ć

parametry zadania

m

a

a

a

,

,

,

2

1

K

;

n

b

b

b

,

,

,

2

1

K

ij

c

dla

m

i

,

,

2

,

1

K

=

oraz

n

j

,

,

2

,

1

K

=

W yznaczy

ć

dowolny

bazowy plan dostaw

i zapisa

ć

go w tablicy

Sprawdzi

ć

, czy wyznaczone

rozwi

ą

zanie bazowe jest

optymalnym planem

przewozów?

Koniec

oblicze

ń

1. W ybra

ć

tras

ę

przewozu

)

,

(

j

i

na której uzyskujemy

najwy

ż

sz

ą

obni

ż

k

ę

kosztów:

2. Ustali

ć

wielko

ść

przewozu

ij

x

na wybranej trasie

TAK

NIE

W yznaczy

ć

nowy poprawiony

(bazowy) plan dostaw

i zapisa

ć

go w tablicy

Rys. 2. Schemat blokowy postępowania w algorytmie transportowym

Omówimy teraz poszczególne fragmenty tego postępowania.

A. Wyznaczanie startowego rozwiązania bazowego i zapis tego rozwiązania w tablicy
transportowej

Postępowanie iteracyjne rozpoczynamy od wyznaczenia dowolnego, ale bazowego

dopuszczalnego planu dostaw (spełniającego warunki dla dostawców, warunki dla odbiorców
oraz warunki brzegowe). Rozwiązanie bazowe (bazowy plan dostaw) zamkniętego zadania
transportowego zawiera (

m+n-1) zmiennych decyzyjnych

ij

x

(co wynika z faktu, że dla

zadania zamkniętego warunki dla dostawców są spełnione jako równości i rzędy: macierzy
współczynników otrzymanego układu (

m+n) równań i układu uzupełnionego o kolumnę

wyrazów wolnych są równe (

m+n-1)). Wobec tego należy zbudować taki plan dostaw aby

liczba dodatnich dostaw (

0

>

ij

x

) była nie większa niż (

m+n-1).

Wśród metod wyznaczania takiego planu wyróżnimy: metodę kąta północno

zachodniego i metodę minimalnego elementu macierzy kosztów. Sposoby te omówimy
dokładnie w przykładzie AT-1.

B. Sprawdzenie, czy wyznaczone rozwiązanie bazowe określa optymalny plan dostaw,

czyli taki w którym łączne koszty transportu są najmniejsze

Polega to na wyznaczeniu wskaźników optymalności

ij

∆

dla każdej z tras

)

,

( j

i

odpowiadających zmiennym niebazowym

ij

x

. Wskaźniki te wyznaczamy jako różnice

32

ij

ij

ij

c

c

~

−

=

∆

,

gdzie

ij

c~

są tzw. kosztami pośrednimi, które obliczamy jako sumy

j

i

ij

v

u

c

+

=

~

.

Liczby

i

u i

j

v

wyznacza się jako dowolne rozwiązanie szczególne nieoznaczonego układu

(

m+n-1) równań postaci:

ij

j

i

c

v

u

=

+

,

otrzymanego dla tych kosztów jednostkowych, które odpowiadają bazowym zmiennym
decyzyjnym

ij

x

.

Jeżeli wskaźniki optymalności spełniają warunek

0

)

,

(

≥

∆

∀

ij

j

i

,

to plan dostaw jest planem optymalnych, czyli takim przy którym łączne koszty
transportu są najmniejsze.

Postępowanie przy sprawdzaniu optymalności planu dostaw będzie omówione szczegółowo
w przykładzie AT-2.

C. Budowa nowego, poprawionego rozwiązania bazowego

Jeśli sprawdzając optymalność planu dostaw otrzymamy ujemne wartości wskaźników

ij

∆

, to plan ten nie jest optymalny i poszukujemy nowego lepszego planu dostaw. W

pierwszej kolejności ustalamy trasę

)

,

( j

i

, na którą należy skierować dostawę tak aby

najbardziej obniżyć łączne koszty transportu. Wybieramy taką trasę

)

,

( l

k

dla której

kl

∆

jest

najmniejsza z ujemnych

ij

∆

:

{ }

ij

kl

ij

∆

=

∆

<

∆

0

min

.

W następnej kolejności szukamy cyklu, który tworzy wybrana trasa

)

,

( l

k

z tymi

trasami (niekoniecznie z wszystkimi), które odpowiadały niewiadomym bazowym

ij

x

,

a następnie ustalamy wielkość dostawy

kl

x na trasie

)

,

( l

k

. Szczegóły tego postępowania

zilustrowane będą w przykładzie AT-3.

Zagadnienia związane z modelowaniem i rozwiązywaniem zadań transportowych

omówione są, np. w pozycjach: [3] , s.91-104, [5] s. 88-111.

Inne problemy takie jak: degeneracja w zadaniu transportowym, zagadnienie częściowej

i całkowitej blokady tras przewozu oraz zagadnienie transportowe z kryterium czasu znaleźć
można w kursie: Ekonometria – studia II stopnia, a także np. [5] s. 112-137.