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
(i=1,2,...,m)
j = 1
n
∑ a x
b
ij
j
≥
i
(i=m+1,...,p)
j = 1
n
∑ a x
b
(i=p+1,...,p)
ij
j
=
i
j = 1
x
n 1 ≤
j
≥ 0 (j=1,2,...,n1)
gdzie:
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ą.
4
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
Dodatkowo musi być spełniony warunek równości popytu i podaży:
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).
5
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
W postępowaniach prowadzących do wyznaczenia wielkości dostaw wyróżnia się dwa etapy:
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.
6
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
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.
3. PRZYKŁAD
Trzech dostawców: D1, D2, D3
zaopatruje w odpady 4 spalarnie: S1, S2, S3 i S4.
Dane:
- jednostkowe koszty transportu (w zł 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
S1
S2
S3
S4
Ai
D1
50
40
50
20
70
D2
40
80
70
30
50
D3
60
40
70
80
80
B j
40
60
50
50
200
Opracować plan przewozu odpadów do utylizacji:
od dostawców do spalarni, minimalizujący całkowite koszty transportu.
Rozwiązanie:
bilans podaży i popytu:
3
4
∑ A = ∑ B
= 200 t ,
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):
jest ich 3 * 4 = 12.
7
E. Michlowicz: Logistyka przemysłowa – Zagadnienia transportowe
Wyrażają to warunki:
a) dla dostawców
4
x 11 + x 12 + x 13 + x 14 = ∑ x
= 70
1 j
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 dla dostawców D2, D3:
4
x 21 + x 22 + x 23 + x 24 = ∑ x
= 50
2 j
i = 1
4
x 31 + x 32 + x 33 + x 34 = ∑ x
= 80
3 j
i = 1
b) dla odbiorców:
3
11
21
31
x
+ x
+ x
= ∑ x i = 40
1
i = 1
tzn . suma dostaw odpadów otrzymanych przez spalarnię S 1 od wszystkich trzech dostawców powinna być równa całkowitemu jej zapotrzebowaniu; podobnie dla pozostałych odbiorców (spalarni):
3
12
22
32
x
+ x
+ x
= ∑ x i
= 60
2
i = 1
3
13
23
33
x
+ x
+ x
= ∑ x i = 50
3
i = 1
3
14
24
34
x
+ x
+ x
= ∑ x i = 50
4
i = 1
Muszą być także spełnione warunki brzegowe:
x
≥
ij
0 (i=1,2,3; j=1,2,3,4),
a w funkcji celu należy zminimalizować łączne koszty transportu, czyli:
K(xij) = 50x11 + 40x12 + 50x13 + 20x14 +
40x21 + 80x22 + 70x23 + 30x24 +
60x31 + 40x32 + 70x33 + 80x34 min
Rozwiązanie: do wyboru jedna z metod przedstawionych w rozdziale 2 (lub inne, np.
wykorzystujące algorytmy ewolucyjne).
8