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: D1, D2 , K, Dm .
2. Punkty odbioru towaru - nazywane odbiorcami. Przyjmujemy, że w analizowanym
problemie występuje n odbiorców, których oznaczamy symbolami: O1, O2 , K, On .
Zakładamy, że każdy z dostawców posiada taki sam towar, takiej samej jakości (bez
braków), odpowiednio w ilościach: a1, a2 , K, am (ilości te określają podaż towaru u
dostawców). Na ten sam towar zgłosili zapotrzebowanie odbiorcy odpowiednio w ilościach:
b1, b2 , K, bn (popyt odbiorców). Jednostkowy koszt przewozu towaru od dostawcy  i do
odbiorcy  j wynosi cij dla i = 1, 2, K, m oraz j = 1, 2, K, n .
Oznaczmy przez xij (zmienna decyzyjna) ilość towaru przewożoną na od dostawcy  i do
odbiorcy  j ( na trasie (i, j) ) wówczas plan przewozów zapiszemy jako macierz
x11 x12 L x1n
îÅ‚ Å‚Å‚
ïÅ‚
x21 x22 L x2n śł
ïÅ‚ śł
X = .
ïÅ‚ śł
M M MMM M
ïÅ‚ śł
xm2 L xmn ûÅ‚
ðÅ‚xm1
Zakładamy, że macierz X jest macierzą o nieujemnych elementach (dla wszystkich dostaw:
xij e" 0 - towar jest przewożony od dostawcy do odbiorcy a nie odwrotnie).
Model zadania transportowego można zapisać następująco:
m n
Znalez
ć najmniejszÄ… wartość funkcji f (X) = Å" xij na zbiorze rozwiÄ…zaÅ„
""cij
i=1 j=1
dopuszczalnych X ,w którym spełnione są:
a. warunki dla dostawców
x11 + x12 + L + x1n d" a1
Å„Å‚
ôÅ‚x + x22 + L + x2n d" a2
ôÅ‚
21
òÅ‚
ôÅ‚LLLLLLLLLL
ôÅ‚xm1 + xm2 + L + xmn d" am
ół
29
b. warunki dla odbiorców
x11 + x21 + L + xm1 = b1
Å„Å‚
ôÅ‚x + x22 + L + xm2 = b2
ôÅ‚
12
òÅ‚
ôÅ‚LLLLLLLLLL
ôÅ‚x1n + x2n + L + xmn = bn
ół
c. warunki brzegowe
xij e" 0 dla i = 1, 2, K, m oraz j = 1, 2, K, n .
Macierz współczynników przy niewiadomych jest macierzÄ… wymiaru (m + n) × (m Å" n) , której
elementy przyjmują wartości ze zbioru { 0, 1}.
Zauważmy, że zgodnie z wcześniejszymi założeniami - łączna podaż dostawców
m n
wynosi: natomiast łączne zapotrzebowanie odbiorców jest równe: . Mogą zajść
"ai "bj
i=1 j=1
następujące przypadki:
m n
1. e" - zadanie transportowe nazywamy zadaniem otwartym;
"ai "bj
i=1 j=1
m n
2. = - zadanie transportowe nazywamy zadaniem zamkniętym;
"ai "bj
i=1 j=1
m n
3. d" - zadanie transportowe jest wówczas zadaniem sprzecznym.
"ai "bj
i=1 j=1
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 On+1 , którego
m n
zapotrzebowanie jest równe różnicy między podażą i popytem; bn+1 = - .
"ai "bj
i=1 j=1
Przyjmujemy, że jednostkowe koszty przewozu towaru od dostawcy  i do odbiorcy  n+1
wynoszÄ… ci,n+1 = 0 dla i = 1, 2, K, m .
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 znalez
ć 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
30
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
a1 , a2 , K, am ; b1 , b2 , K , bn
cij dla i = 1, 2, K , m oraz
j = 1, 2, K , n
Wyznaczyć dowolny
bazowy plan dostaw
i zapisać go w tablicy
Wyznaczyć nowy poprawiony
(bazowy) plan dostaw
i zapisać go w tablicy
Sprawdzić, czy wyznaczone
NIE
rozwiÄ…zanie bazowe jest
TAK
optymalnym planem
przewozów?
1. Wybrać trasę przewozu (i, j)
Koniec
na której uzyskujemy
obliczeń
najwyższą obniżkę kosztów:
2. Ustalić wielkość przewozu
xij na wybranej trasie
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 xij (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 ( xij > 0 ) 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 wskaz
ników optymalności "ij dla każdej z tras (i, j)
odpowiadajÄ…cych zmiennym niebazowym xij . Wskaz
niki te wyznaczamy jako różnice
31
~
"ij = cij - cij ,
~ ~
gdzie cij są tzw. kosztami pośrednimi, które obliczamy jako sumy cij = ui + v .
j
Liczby ui i v wyznacza się jako dowolne rozwiązanie szczególne nieoznaczonego układu
j
(m+n-1) równań postaci:
ui + v = cij ,
j
otrzymanego dla tych kosztów jednostkowych, które odpowiadają bazowym zmiennym
decyzyjnym xij .
Jeżeli wskaz
niki optymalności spełniają warunek
"ij e" 0 ,
"
(i, j)
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 wskaz
ników
"ij , to plan ten nie jest optymalny i poszukujemy nowego lepszego planu dostaw. W
pierwszej kolejności ustalamy trasę (i, j) , na którą należy skierować dostawę tak aby
najbardziej obniżyć łączne koszty transportu. Wybieramy taką trasę (k,l) dla której "kl jest
najmniejsza z ujemnych "ij :
"kl = min {"ij }.
"ij < 0
W następnej kolejności szukamy cyklu, który tworzy wybrana trasa (k,l) z tymi
trasami (niekoniecznie z wszystkimi), które odpowiadały niewiadomym bazowym xij ,
a następnie ustalamy wielkość dostawy xkl na trasie (k,l) . 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 znalez
ć
można w kursie: Ekonometria  studia II stopnia, a także np. [5] s. 112-137.
32