E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
WYKŁAD 12
ZAGADNIENIA (ZADANIA) TRANSPORTOWE
– BADANIA OPERACYJNE
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.
Jeżeli w zadaniu decyzyjnym funkcja celu i wszystkie warunki ograniczające są liniowe, to zadanie takie nazywa się Liniowym Zadaniem Decyzyjnym. Jeśli dodatkowo wszystkie zmienne są ciągłe, to zadanie takie nazywamy Zadaniem Programowania Liniowego.
Ogólna postać takich zadań jest następująca:
• funkcja celu:
n
∑ c x
max(min)
j
j
→
j = 1
• ograniczenia:
n
∑ a x
b
ij
j
≤
i
dla (i = 1,2,...,m)
j = 1
n
∑ a x
b
ij
j
≥
i
dla (i = m+1,...,p)
j = 1
n
∑ a x
b
dla (i = p+1,...,p)
ij
j
=
i
j = 1
x j ≥ 0 dla (j = 1,2,..., n1)
oraz n
1
≤ n
gdzie:
cj - np. koszt wykonania zadania „ j”
Każdy wektor zmiennych decyzyjnych:
1
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
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.
Przy rozwiązywaniu zadań decyzyjnych istotne jest założenie, że zadanie z funkcją celu:
n
∑ c x
max
j
j
→
j = 1
jest równoważne zadaniu z funkcją celu:
n
∑ ( − c ) x
min
j
j
→
j = 1
Zadania programowania liniowego w postaci macierzowej możemy zapisać następująco:
cx → max(min)
Ax = b
x ≥ 0
gdzie:
a
a
L
a
11
12
1 n
a
a
L
a
21
22
2 n
A =
- macierz współczynników,
M
M
M
a
L
m
a
1
m
a
2
mn
b
1
b 2
b
=
- wektor wyrazów wolnych,
M
b m
x
1
x 2
x
=
M
- wektor zmiennych decyzyjnych,
x n
c = [ c
c
L
c
1
2
n ] - wektor wag funkcji celu.
Podstawową metodą pozwalającą na rozwiązanie dowolnego zadania programowania
liniowego jest metoda Simpleks. Polega ona na sekwencyjnym, ściśle określonym przeglądzie tworzonych kolejno tablic simpleksowych.
2
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
Z każdą zmienną xj związany jest wskaźnik kryterium optymalności. Dla zmiennych bazowych ma on zawsze wartość zero, natomiast dla zmiennych niebazowych wskaźnik ten określa, jak zmieni się wartość funkcji celu, gdy zmienna xj przyjmie wartość 1, a wartości zmiennych bazowych zostaną odpowiednio zmienione w celu zachowania
dopuszczalności rozwiązania.
Metoda Simpleks
Załóżmy, że dane jest zadanie programowania liniowego w postaci:
cx
→
max
Ax
=
b
x ≥ 0
Przez B oznaczamy macierz kwadratową m- tego stopnia, składająca się z m liniowo niezależnych kolumn macierzy A.
Macierz B nazywamy bazą, jej kolumny – kolumnami bazowymi, a pozostałe kolumny macierzy A – kolumnami niebazowymi.
Zmienne związane z kolumnami bazowymi nazywamy zmiennymi bazowymi, a
pozostałe zmienne – niebazowymi.
Z każdą bazą związane jest rozwiązanie bazowe.
Jeżeli układ Ax = b jest niesprzeczny oraz n>m,
to układ ten ma nieskończenie wiele rozwiązań, ale skończenie wiele rozwiązań bazowych.
n !
Układ taki ma co najwyżej: m ! ( n −
rozwiązań bazowych.
m
)
Dla zadań programowania liniowego prawdziwe jest twierdzenie:
Jeżeli zadanie ma rozwiązanie optymalne, to ma również rozwiązanie optymalne bazowe.
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.
3
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
punkt
przewóz na
punkt
nadania i
trasach ( i, j)
odbioru j
p
o daż
popyt
a1
b1
a2
b2
.
.
.
.
.
.
an
bm
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
∑ x
a
=
ij
=
i ,
i
1 , 2 ,...,
n
j = 1
oraz:
≥
x
0 ,
=
=
ij
i
1 , 2 ,..., n ; j
1 , 2 ,..., m
dla których funkcja celu:
m
n
z = ∑ ∑ c
x
ij
ij
min
i = 1
j = 1
osiąga wartość minimalną.
Dodatkowo musi być spełniony warunek równości popytu i podaży:
4
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
jest to tzw. Zamknięte Zadanie Transportowe (ZZT) .
m
n
∑ a
b
i
= ∑
j
i = 1
j = 1
W praktyce spotykamy się przeważnie z problemami, w których podaż przewyższa popyt, bądź
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
∑ a
b
i
< ∑
j
i = 1
j = 1
Aby uzyskać postać zbilansowaną do zadania wprowadzamy „fikcyjnego” dostawcę
posiadającego dokładnie am+1 produktów:
n
m
a
b
a
m + 1
= ∑
j
− ∑
i
j = 1
i = 1
Dodatkowo do macierzy kosztów wprowadzamy współczynniki
cm+1,1=0,...,cm+1,n=0 (koszty „fikcyjnego” transportu) .
• Przypadek 2 – zapotrzebowanie na produkty jest mniejsze niż zapasy magazynowe
(podaż większa od popytu).
m
n
∑ a
b
i
> ∑
j
i = 1
j = 1
W celu uzyskania postaci zbilansowanej, wprowadzamy „fikcyjnego” odbiorcę,
który potrzebuje dokładnie bn+1 produktów:
m
n
b
a
b
n
1
= ∑
i
−
∑
∑
+
j
i = 1
j = 1
Dodatkowo do macierzy kosztów wprowadzamy współczynniki
cn+1,1=0,...,cn+1,m= 0 (koszty „fikcyjnego” transportu).
W postępowaniach prowadzących do wyznaczenia wielkości dostaw wyróżnia się dwa etapy:
5
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
1. 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,
• aproksymacji Vogel’a,
• minimalnego elementu macierzy kosztów.
2. Na podstawie pierwszego rozwiązania bazowego wyznaczane jest rozwiązanie
optymalne.
Najczęściej stosowaną metodą jest metoda MODI (Modified Distribution Methode).
•
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.
6
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
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.
3. PRZYKŁAD
Trzech dostawców: D1, D2, D3
zaopatruje w odpady 4 spalarnie: 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 spalarni Bj (w tonach)
podano w tablicy 1.
Tab. 1. Jednostkowe koszty transportu
Spalarnie
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 odpadów do utylizacji:
od dostawców do spalarni, minimalizujący całkowite koszty transportu z (xij). .
Rozwiązanie:
bilans podaży i popytu:
3
4
∑ A = ∑ B
= 1000
[ton]
i
j
i = 1
j = 1
a więc jest to przykład zamkniętego zagadnienia transportowego (ZZT).
Zmienne decyzyjne xij oznaczają ilość ton odpadów, jaka powinna być dostarczona Od i-tego dostawcy (i=1,2,3) do j-tej spalarni (j=1,2,3,4): Liczba zmiennych: 3 * 4 = 12.
Wyrażają to warunki:
7
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
a) dla dostawców
4
x
+ x
+ x
+ x
= ∑ x
= 350
11
12
13
14
1 j
(dostawca D1)
i = 1
tzn:
suma wielkości dostaw odpadów od dostawcy D1 do wszystkich spalarni powinna być równa podaży dostawcy;
i analogicznie dla dostawców D2, D3:
4
x
+ x
+ x
+ x
= ∑ x
= 250 (dostawca D2)
21
23
24
2 j
22
i = 1
4
x
+ x
+ x
+ x
= ∑ x
= 400 (dostawca D3)
31
32
33
34
3 j
i = 1
b) dla odbiorców:
3
x
+ x
+ x
= ∑ x
= 200
11
21
31
i 1
(odbiorca S1)
i = 1
tzn . suma dostaw odpadów otrzymanych przez spalarnię S1 od wszystkich trzech dostawców powinna być równa całkowitemu jej zapotrzebowaniu;
podobnie dla pozostałych odbiorców (spalarni):
3
x
+ x
+ x
= ∑ x
= 300
12
22
32
i 2
(odbiorca S2)
i = 1
3
x
+ x
+ x
= ∑ x
= 250
13
23
33
i 3
(odbiorca S3)
i = 1
3
x
+ x
+ x
= ∑ x
= 250
14
24
34
i 4
(odbiorca S4)
i = 1
Muszą być także spełnione warunki brzegowe:
x
≥
ij
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 w rozdziale 2 (lub inne, np.
wykorzystujące algorytmy ewolucyjne).
8