E. Michlowicz: LP  Zagadnienia transportowe
WYKA
AD 11
ZAGADNIENIA (zadania) TRANSPORTOWE
1.Zagadnienia programowania liniowego
Działanie intuicyjne rzadko prowadzi do podjęcia optymalnej decyzji, co może
narazić nas utratę pewnych korzyści. Z pomocą przychodzą różnego typu metody
rozwiązywania problemów decyzyjnych. Opisanie sytuacji decyzyjnej w języku
matematycznym ma na celu sprowadzenie problemu wyboru najlepszej decyzji do
rozwiązania jednoznacznie określonego zadania matematycznego.
Aby rozwiązanie takiego zadania umożliwiło wybór najlepszej decyzji przy
ustalonych ograniczeniach należy określić:
jakie wielkości mają być wyznaczone (określenie zmiennych decyzyjnych),
jakie wielkości są dane (określenie parametrów zadania),
jakie są warunki ograniczające dla danych zmiennych decyzyjnych,
funkcję celu jako funkcję zmiennych decyzyjnych.
Ogólna postać takich zadań jest następująca:
funkcja celu:
n
c x max(min)
j j
j 1
ograniczenia:
n
aij x bi (i=1,2,...,m)
j
j 1
n
aij x bi
(i=m+1,...,p)
j
j 1
n
aij x bi
(i=p+1,...,p)
j
j 1
x 0
n1 n
(j = 1,2,...,n1) gdzie:
j
Każdy wektor zmiennych decyzyjnych:
x = ( x1, x2 ,... ,x n)
spełniający warunki ograniczające nazywamy rozwiązaniem dopuszczalnym.
Rozwiązanie dopuszczalne, dla którego funkcja celu osiąga maksimum (minimum),
nazywamy rozwiązaniem optymalnym.
1
E. Michlowicz: LP  Zagadnienia transportowe
Zadania programowania liniowego w postaci macierzowej możemy zapisać następująco:
cx max(min)
Ax b
x 0
gdzie:
a11 a12 L� a1n
a21 a22 L� a2n
A
- macierz współczynników,
M� M� M�
am1 am2 L� amn
b1
b2
b
- wektor wyrazów wolnych,
M�
bm
x1
x
2
x
- wektor zmiennych decyzyjnych,
M�
x
n
c = [ c1, c2 ,... , c n ] - wektor wag funkcji celu.
2. Zadania (Zagadnienia) transportowe
Jednym z ciekawszych szczególnych przypadków liniowych zadań decyzyjnych są z
tzw. zadania transportowe.
Charakteryzują się one specyficznym układem macierzy współczynników oraz
warunków ograniczających. Zadanie transportowe (sformułowane w 1934 r. przez L.
Kantorowicza) było jednym z pierwszych rozwiązanych problemów programowania
liniowego.
Noszą one czasem nazwę problemu Hitchcoca od nazwiska angielskiego badacza,
który w 1941 r. opublikował wersję zadania i algorytmu zwanego dziś pod nazwą
klasycznego zadania transportowego.
Sytuację klasycznego zagadnienia transportowego ilustruje rysunek 1.
2
E. Michlowicz: LP  Zagadnienia transportowe
Rys.1. Schemat klasycznego zadania transportowego
Przy użyciu algorytmu służącego do rozwiązywania zadań transportowych można
rozstrzygać problemy decyzyjne:
dotyczące przepływu dóbr pomiędzy -n-  dostawcami dysponującymi ai
jednostkami produktu (i=....n)
oraz -m-  odbiorcami wyrażającymi zapotrzebowanie na
bj jednostek produktu (j=1 .. m).
ponadto:
każdy  dostawca może zaopatrywać dowolnego  odbiorcę , a każdy
 odbiorca może odbierać towar od dowolnego  dostawcy ,
muszą być znane koszty jednostkowe cij związane z przepływem dóbr od
dostawcy i do odbiorcy j.
Określając przez xij (zmienne decyzyjne) wielkość dostawy od i-tego dostawcy do j-tego
odbiorcy,
zadanie transportowe można zapisać w następująco:
n
x b ,
ij j j 1,2,...,m
i 1
m
xij ai , i 1,2,...,n
oraz:
j 1
x 0 ,
i 1,2,...,n; j 1,2,...,m
ij
dla których funkcja celu:
m n
z cij xij Ł� min osiąga wartość minimalną.
i 1 j 1
3
E. Michlowicz: LP  Zagadnienia transportowe
Dodatkowo musi być spełniony warunek równości popytu i podaży:
jest to postać Ł� Zamkniętego Zadania Transportowego (ZZT) .
m n
ai b
j
i 1 j 1
W praktyce spotykamy się przeważnie z problemami, w których podaż przewyższa popyt,
bądz
też zapotrzebowanie jest większe od dostępnej ilości towaru.
W takim przypadku mówimy o zadaniu niezbilansowanym i określamy je:
Otwartym Zadaniem Transportowym (OZT).
W celu rozwiązania tak postawionego problemu należy go sprowadzić do postaci
zbilansowanej:
Przypadek 1  ze względu na niedobór zapasów nie możemy zaspokoić potrzeb
wszystkich klientów (podaż mniejsza od popytu):
m n
ai b
j
i 1 j 1
Aby uzyskać postać zbilansowaną do zadania wprowadzamy  fikcyjnego dostawcę
posiadającego dokładnie am+1 produktów:
n m
am 1 b ai
j
j 1 i 1
Dodatkowo do macierzy kosztów wprowadzamy współczynniki
cm+1,1=0,...,cm+1,n=0 (koszty  fikcyjnego transportu).
Rys.2. Schemat otwartego zadania transportowego  przypadek 1
4
E. Michlowicz: LP  Zagadnienia transportowe
Przypadek 2  zapotrzebowanie na produkty jest mniejsze niż zapasy
magazynowe (podaż większa od popytu).
m n
ai b
j
i 1 j 1
W celu uzyskania postaci zbilansowanej, wprowadzamy  fikcyjnego odbiorcę, który
potrzebuje dokładnie bn+1 produktów:
m n
bn 1 ai b
j
i 1 j 1
Dodatkowo do macierzy kosztów wprowadzamy współczynniki:
cn+1,1=0,...,cn+1,m= 0 (koszty  fikcyjnego transportu).
Rys.3. Schemat otwartego zadania transportowego  przypadek 2
W postępowaniach prowadzących do wyznaczenia wielkości dostaw należy wyróżnić dwa
etapy:
I. Wyznaczany jest wstępny plan dopuszczalnego transportu, tzw. pierwsze bazowe
rozwiązanie dopuszczalne.
W tym celu można zastosować jedną z metod:
kąta północno-zachodniego;
minimalnego elementu macierzy kosztów;
aproksymacji Vogel a.
II. Na podstawie pierwszego rozwiązania bazowego wyznaczane jest rozwiązanie
optymalne.
Najczęściej stosowaną metodą jest metoda MODI (Modified Distribution Methode).
5
E. Michlowicz: LP  Zagadnienia transportowe
Metoda kąta północno-zachodniego (kąta N-W)
Poszukiwanie rozwiązania bazowego rozpoczynamy od wartości xij dla trasy (1,1).
Wartość xij wyznaczamy wg wzoru:
xij = min{a1, b1}
Następnie od wartości a1, b1 odejmujemy x11 i otrzymane wyniki wstawiamy odpowiednio
zamiast a1, b1. Z dalszych rozważań eliminujemy wiersz lub kolumnę, dla której różnica
wynosi 0. W kolejnym kroku przechodzimy do elementu xij położonego w północno-
zachodnim rogu, powstałej po eliminacji wiersza lub kolumny, macierzy i powtarzamy
poprzednie czynności. Wyznaczanie rozwiązania kończymy po wyeliminowaniu wszystkich
wierszy i kolumn.
Metoda aproksymacyjna Vogel a (metoda VAM)
Wybierając zmienną xij do wyznaczenia sprawdzamy różnicę pomiędzy najniższym a
kolejnym co do wartości kosztem w każdej kolumnie lub wierszu i tam gdzie jest ona
największa określamy najniższy koszt, a dla jego współrzędnych określamy wartość zmiennej
xij. Dla wybranego wiersza lub kolumny określamy:
xij=min {ai, bj}
Następnie, podobnie jak w przypadku metody kąta północno-zachodniego, od wartości ai,
bj odejmujemy xij i otrzymane różnice wstawiamy odpowiednio zamiast ai, bj. Z dalszych
rozważań eliminujemy wiersz lub kolumnę, dla której różnica wynosi 0. Dla pozostałych
wierszy i kolumn ponownie wybieramy zmienną xij i powtarzamy operacje. Iteracje kończymy
w momencie, gdy w macierzy nie ma już wierszy ani kolumn zawierających co najmniej dwa
puste pola. W polu nie posiadającym przypisanej wartości przewozu wpisujemy pozostałą
wartość dostawcy dla odpowiedniego wiersza lub odbiorcy dla kolumny.
Metoda minimalnego elementu macierzy kosztów (MEM)
Z macierzy kosztów wybieramy element o najmniejszej wartości i dla jego
współrzędnych określamy wartość xij.
Tak jak w przypadku poprzednich metod, z dalszych rozważań eliminujemy wiersz lub
kolumnę, dla której różnica pomiędzy wartością odpowiednio ai lub bj a xij wynosi 0.
Następnie dokonujemy kolejnego wyboru współrzędnych zmiennej xij według kryterium
najmniejszego kosztu. Iteracje powtarzamy aż do momentu, gdy nie ma już żadnych wierszy
ani kolumn zawierających co najmniej dwa pola bez przypisanych wartości przewozów. W
polu nie posiadającym przypisanej wartości wpisujemy pozostałą dla danego wiersza i
kolumny wartość. Po znalezieniu jednego z rozwiązań dopuszczalnych przechodzimy do etapu
sprawdzania jego optymalności.
6
E. Michlowicz: LP  Zagadnienia transportowe
Przykład:
ZADANIE TRANSPORTOWE (rozdział zadań przewozowych)
Trzech dostawców: D1, D2, D3
zaopatruje w towary 4 sklepy: S1, S2, S3 i S4.
Dane:
- jednostkowe koszty transportu (w jzł za tonę);
- oferowane miesięcznie wielkości dostaw Ai (w tonach),
- miesięczne zapotrzebowanie sklepów Bj (w tonach)
podano w tablicy 1.
Tab. 1. Jednostkowe koszty transportu, podaży i popytu
Sklepy
Dostawcy
podaż
S1 S2 S3 S4 Ai [ton]
D1 40 30 40 10 350
D2 30 70 60 20 250
D3 50 30 60 70 400
popyt
Bj [ton] 200 300 250 250 1000
Opracować plan przewozu towarów od dostawców do sklepów,
minimalizujący całkowite koszty transportu z (xij).
Rozwiązanie:
bilans podaży i popytu:
3 4
Ai Bj 1000
[ton]
i 1 j 1
a więc jest to przykład zamkniętego zagadnienia transportowego (ZZT).
Zmienne decyzyjne xij oznaczają ilość ton towarów, jaka powinna być dostarczona
od i-tego dostawcy (i=1,2,3) do j-tego sklepu (j=1,2,3,4):
Liczba zmiennych: 3 * 4 = 12.
Wyrażają to warunki:
a) dla dostawców
4
x x x x x1 j 350
(dostawca D1)
11 12 13 14
i 1
tzn:
suma wielkości dostaw odpadów od dostawcy D1 do wszystkich sklepów powinna
być równa podaży dostawcy;
7
E. Michlowicz: LP  Zagadnienia transportowe
i analogicznie dla dostawców D2, D3:
4
x x x23 x x2 j 250 (dostawca D2)
21 24
22
i 1
4
x31 x32 x33 x34 x3 j 400
(dostawca D3)
i 1
b) dla odbiorców (sklepy):
3
x x x xi 1 200
(odbiorca S1)
11 21 31
i 1
tzn. suma dostaw towarów otrzymanych przez sklep S1 od wszystkich trzech
dostawców powinna być równa całkowitemu jej zapotrzebowaniu;
podobnie dla pozostałych odbiorców (S1, S2):
3
x x x xi 2 300
(odbiorca S2)
12 22 32
i 1
3
x13 x x xi 3 250
(odbiorca S3)
23 33
i 1
3
x x x xi 4 250
(odbiorca S4)
14 24 34
i 1
Muszą być także spełnione warunki brzegowe:
xij 0 dla (i = 1,2,3; j = 1,2,3,4),
a w funkcji celu należy zminimalizować łączne koszty transportu, czyli:
z (xij) = 40x11 + 30x12 + 40x13 + 10x14 +
30x21 + 70x22 + 60x23 + 20x24 +
50x31 + 30x32 + 60x33 + 70x34 Ł� min
Rozwiązanie:
do wyboru jedna z metod przedstawionych na wykładzie KP-Z, MEM, MODI lub
inne, np. wykorzystujące algorytmy ewolucyjne.
x11 = & , x12 = & , x13 = & , x14 = & ,
x21 = & , & ..
x31 = & , & .. x34 = & ,
8