A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
1
ZAGADNIENIE TRANSPORTOWE (ZT)
Danych jest p dostawców, których podaż wynosi a
1
, a
2
, . . . , a
p
i q odbiorców,
których popyt wynosi b
1
, b
2
, . . . , b
q
. Zakładamy, że problem jest zbilansowany, tj.
P
p
i=1
a
i
=
P
q
i=1
b
i
czyli całkowita podaż jest równa całkowitemu popytowi. Dane
są również koszty przewozu c
ij
jednostki towaru od i-tego dostawcy (i = 1, . . . , p)
do j-tego odbiorcy (j = 1, . . . , q). Należy wyznaczyć plan transportu towaru od
dostawców do odbiorców o minimalnym łącznym koszcie przewozu.
Model liniowy dla ZT:
Zmienne decyzyjne:
• x
ij
- ilość towaru przewożona od i-tego dostawcy do j-tego odbiorcy.
Model:
min z =
P
p
i=1
P
q
j=1
c
ij
x
ij
P
q
j=1
x
ij
= a
i
i
= 1, . . . , p [Podaż dostawców]
P
p
i=1
x
ij
= b
j
j
= 1, . . . , q [Popyt odbiorców]
x
ij
≥ 0
Przykład.
. Rozpatrzmy następujący rysunek:
Fabryka 1
Fabryka 2
Fabryka 3
Miasto 1
Miasto 2
Miasto 3
Miasto 4
35
50
40
45
20
30
30
8
6
10
2
9
12
13
7
14
9
16
10
W przykładzie tym mamy p = 3 dostawców (fabryki) i q = 4 odbiorców (miasta).
Podaż wynosi: a
1
= 35, a
2
= 50, a
3
= 40 a popyt b
1
= 45, b
2
= 20, b
3
= 30,
b
4
= 30. Problem jest zbilansowany ponieważ 35+50+40=45+20+30+30. Jed-
nostkowe koszty transportu wynoszą c
11
= 8, c
12
= 6 itd...
Zmienne decyzyjne:
• x
ij
- ilość towaru przewożona od i-tej fabryki do j-tego miasta.
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
2
Model liniowy:
min z = 8x
11
+ 6x
12
+ 10x
13
+ 2x
14
+ 9x
21
+ 12x
22
+ · · · + 10x
34
x
11
+ x
12
+ x
13
+ x
14
= 35 [Podaż fabryki 1]
x
21
+ x
22
+ x
23
+ x
24
= 50 [Podaż fabryki 2]
x
31
+ x
32
+ x
33
+ x
34
= 40 [Podaż fabryki 3]
x
11
+ x
21
+ x
31
= 45
[Popyt miasta 1]
x
12
+ x
22
+ x
32
= 20
[Popyt miasta 2]
x
13
+ x
23
+ x
33
= 30
[Popyt miasta 3]
x
14
+ x
24
+ x
34
= 30
[Popyt miasta 4]
x
ij
≥ 0
Tablica transportowa:
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
35
30
30
30
x
11
x
12
x
13
x
14
x
21
x
22
x
23
x
24
x
31
x
32
x
33
x
34
Modele niezbilansowane
1. Przypadek
P
p
i=1
a
i
>
P
q
i=1
b
i
(nadwyżka podaży). Dodajemy fikcyjnego od-
biorcę q+1 o popycie b
q+1
=
P
p
i=1
a
i
−
P
q
i=1
b
i
i kosztach przewozu c
iq+1
= 0,
i
= 1, . . . , p.
Przykład.
Rozpatrzmy tablicę:
8
6
10
9
12
13
40
50
20
30
20
8
6
10
0
9
12
13
0
20
20
30
20
40
50
x
11
x
11
x
12
x
12
x
13
x
13
x
14
x
21
x
21
x
22
x
22
x
23
x
23
x
24
W problemie tym występuje nadwyżka podaży równa 20. Dodajemy fik-
cyjnego odbiorcę numer 4 o popycie 20. Optymalne rozwiązanie wynosi:
x
12
= 20, x
13
= 20, x
21
= 20, x
23
= 10, x
24
= 20. Fikcyjny odbiorca odbie-
ra 20 jedn. od dostawcy 2. Oznacza to faktycznie, że towar ten zostanie u
dostawcy 2.
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
3
2. Przypadek
P
p
i=1
a
i
<
P
q
i=1
b
i
(nadwyżka popytu). Dodajemy fikcyjnego do-
stawcę p+1 o podaży a
p+1
=
P
q
i=1
b
i
−
P
p
i=1
a
i
i kosztach przewozu c
p+1i
= 0,
i
= 1, . . . , q.
Metoda sympleks (potencjałów) dla zbilansowanego ZT Specjalna struk-
tura macierzy ograniczeń dla zagadnienia transportowego pozwala na dokonanie
wielu uproszczeń w metodzie sympleks. Wszystkie iteracje sympleksowe realizu-
je się na tablicy transportowej, która ma znacznie mniejszy wymiar niż tablica
sympleksowa. Bazowe rozwiązanie dopuszczalne ma tylko p + q − 1 zmiennych
bazowych (gdyż rząd macierzy ograniczeń jest równy p + q − 1) i może być ła-
two wyznaczone bez stosowania M-metody. Wskaźniki optymalności w metodzie
sympleks dla zagadnienia transportowego można wyznaczyć nie konstruując ta-
blicy sympleksowej lecz wykorzystując tzw. potencjały tj. zmienne związane z
dostawcami u
i
, i
= 1, . . . , p i odbiorcami v
j
, j
= 1, . . . , q. Przejście od jedne-
go bazowego rozwiązania dopuszczalnego do innego realizowane jest również na
tablicach transportowych.
Wyznaczanie pierwszego dopuszczalnego rozwiązania bazowego
Ogólną idę konstrukcji podaje poniższy schemat:
1. Wybierz wśród nie skreślonych elementów tablicy transportowej dopusz-
czalną
klatkę, powiedzmy (r, k) i wstaw do niej maksymalnie możliwą wiel-
kość przewozu, tj. minimum z podaży wiersza r i popytu kolumny k czyli
x
rk
= min(a
r
, b
k
). Klatka ta staje się klatką bazową – odpowiada jej zmien-
na bazowa x
rk
.
2. Zmniejsz podaż r-tego dostawcy i popyt k-tego odbiorcy o wielkość ustalo-
nego w kroku 1 przewozu x
rk
, tj. a
r
:= a
r
− x
rk
, b
k
:= b
k
− x
rk
.
3. Jeśli a
r
= 0, to skreśl w tablicy transportowej r-ty wiersz. Jeśli natomiast
a
r
>
0, to skreśl w tablicy transportowej k-tą kolumnę (wtedy b
k
= 0).
4. Jeśli wszystkie elementy tablicy transportowej zostały skreślone, to KO-
NIEC. Wyznaczono początkowe bazowe rozwiązanie dopuszczalne z dokład-
nie (jeśli w każdym kroku skreślamy dokładnie jedną linię, tj. wiersz lub ko-
lumnę macierzy) p + q − 1 zmiennymi bazowymi. W przeciwnym przypadku
przejdź do kroku 1.
W zależności od sposobu wyboru dopuszczalnej klatki w kroku 1 powyższego
schematu otrzymujemy różne metody konstrukcji początkowego bazowego roz-
wiązania dopuszczalnego:
metoda kąta północno-zachodniego - dopuszczalną jest klatka leżąca w pierw-
szym wierszu i pierwszej kolumnie nie skreślonej części tablicy;
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
4
minimum macierzy - dopuszczalną jest klatka o minimalnym koszcie w nie
skreślonej części tablicy;
metoda Vogel’a - VAM - dopuszczalną jest klatka o minimalnym koszcie w
linii (wierszu lub kolumnie) z największym współczynnikiem kary. Współ-
czynnik kary (liczba nieujemna) jest różnicą między dwoma najmniejszymi
kosztami w linii.
Metoda kąta północno-zachodniego - przykład
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
35
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
35
10
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
35
10
20
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
35
10
20
20
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
35
10
20
20
10
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
35
10
20
20
10
30
Zaczynamy od lewego górnego rogu (kąta północno zachodniego) macierzy nie-
skreślonych elementów tj. klatki [1,1]. Wpisujemy do niej maksymalną wartość
nie naruszającą popytu i podaży czyli x
11
= min{35, 45} = 35. Pierwszy wiersz
czyli pierwszy dostawca wysłał wszystko co posiadał - skreślamy go i modyfiku-
jemy popyt pierwszego odbiorcy (kolumna 1) b
1
= 45 − x
11
= 10. Przechodzimy
do lewego górnego rogu macierzy nie skreślonych elementów tj. klatki [2,1] czyli
zmiennej x
21
nadajemy największą możliwą wartość, tj. x
21
= min{50, 10} = 10
i zmniejszamy podaż drugiego wiersza o wartość x
21
= 10. Kolumna 1 tj. pierw-
szy odbiorca otrzymał tyle ile wynosi jego popyt zatem skreślamy tę kolumnę
. Przechodzimy następnie do klatki [2,2] tj. zmiennej x
22
nadajemy wartośc 20
itd.. W każdym kroku przechodzimy do klatki leżącej w lewym górnym rogu ma-
cierzy nie skreślonych elementów. Otrzymujemy następujące bazowe rozwiązanie
dopuszczalne: x
11
= 35, x
21
= 10, x
22
= 20, x
23
= 20, x
33
= 10, x
34
= 30, pozo-
stałe zmienne mają wartość 0. Koszt tego rozwiązania (przewozu) wynosi 1330.
Metoda minimum z macierzy
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
5
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
30
30
5
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
30
5
45
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
30
5
45
15
5
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
30
5
45
5
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
30
5
45
15
5
25
Zaczynamy od klatki o najmniejszym koszcie, czyli klatki [1,4]. Zmiennej odpo-
wiadającej tej klatce tj. x
24
nadajemy maksymalną wartość x
24
= min{35, 30} =
30. Skreślamy czwartą kolumnę i modyfikujemy podaż pierwszego wiersza a
1
=
35 − 30 = 5. Przechodzimy do klatki o najmniejszym koszcie w macierzy nie skre-
ślonych elementów, czyli klatki [1,2] i nadajemy zmiennej bazowej x
12
wartość
5 itd... Otrzymujemy następujące bazowe rozwiązanie dopuszczalne: x
14
= 30,
x
12
= 5, x
21
= 45, x
23
= 5, x
32
= 15, x
33
= 25 (pozostałe zmienne mają wartość
0). Koszt tego rozwiązania wynosi 1095.
Klatki odpowiadające zmiennym bazowym nazywamy klatkami bazowymi.
Uwaga: Jeśli w każdym kroku skreślamy tylko jeden wiersz albo jedną kolumnę,
to otrzymamy bazowe rozwiązanie dopuszczalne o dokładnie p + q − 1 zmiennych
bazowych.
Ocena klatek i iteracja sympleksowa.
Ciąg klatek ([i
1
, j
1
], [i
2
, j
2
], ..., [i
l
, j
l
]), gdzie l ≥ 4 tablicy transportowej nazywamy
cyklem
jeżeli:
• każde dwie sąsiednie klatki znajdują się w jednej linii tj. w jednej kolumnie
lub jednym wierszu,
• ostatnia klatka znajduje się w tej samej linii co klatka pierwsza czyli i
1
= i
l
lub j
1
= j
l
• żadne trzy kolejne kolejne klatki tego ciągu nie leżą w jednej linii.
Przykładowe cykle utworzone przez szare klatki pokazane są na poniższym ry-
sunku:
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
6
Ciągi (szare klatki), które nie tworzą cyklu:
Twierdzenie 1. Zestaw p + q − 1 klatek odpowiada zmiennym bazowym wtedy i
tylko wtedy, gdy klatki te nie zawierają cyklu. Dodanie jednej klatki niebazowej
do klatek bazowych powoduje powstanie dokładnie jednego cyklu.
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
7
Rozpatrzmy początkowe bazowe rozwiązanie dopuszczalne rozważanego przykła-
du uzyskane metodą kąta północno - zachodniego. Zmiennymi bazowymi są:
ZB
= {x
11
, x
21
, x
22
, x
23
, x
33
, x
34
}. Załóżmy, że chcemy wprowadzić do bazy zmien-
ną x
14
. Dodajemy klatkę [1,4] do klatek bazowych. W ten sposoób, na mo-
cy Twierdzenia 1 powstaje cykl zawierający klatkę [1,4] i pewne (niekoniecznie
wszystkie!) klatki bazowe. Klatki należące do tego cyklu zaznaczone są na rysun-
ku kolorem szarym. Oznaczmy klatkę [1, 4] znakiem +. Następnie przesuwając
się po cyklu oznaczamy klatki na przemian znakami - lub +.
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
35
10
20
20
10
30
+
-
+
-
+
-
Jaką maksymalną wartość możemy wprowadzić do klatki [1,4]? Jeżeli wprowa-
dzimy do klatki [1,4] pewną wartość δ to, aby zachować bilans podaży i popy-
tu musimy odjąć δ od wszystkich klatek oznaczonych znakiem - i dodać δ do
wszystkich klatek oznaczonych znakiem +. Do klatki [1,4] wprowadzamy więc
najmniejszą wartość występującą w klatkach oznaczonych minusem czyli 20 z
klatki [2,3]. Oznacza to, że zmienna x
23
wychodzi z bazy (zostaje wyzerowana).
Nowymi zmiennymi bazowymi są {x
11
, x
14
, x
21
, x
22
, x
33
, x
34
} a bazowe rozwiąza-
nie dopuszczalne jest następujące: x
11
= 15, x
14
= 20, x
21
= 30, x
22
= 20,
x
13
= 30, x
14
= 10.
35-20
10+20
20-20
10+20 30-20
+
-
+
-
+
-
+20
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
15
30
20
30
10
20
Czy wartość funkcji celu (FC) zmaleje po wprowadzeniu x
14
do bazy? Zmiana
FC wyniesie:
20 ∗ (2 − 10 + 16 − 13 + 9 − 8) = 20 ∗ (−4) = −80,
czyli zmniejszy się o 80. Liczba -4 jest oceną klatki niebazowej [1, 4].
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
8
Twierdzenie 2. Aktualne rozwiązanie bazowe dopuszczalne w tablicy transpor-
towej jest optymalne jeżeli współczynniki optymalności (oceny) wszystkich klatek
niebazowych są nieujemne. Jeżeli istnieje klatka niebazowa o ujemnej ocenie to
można wyznaczyć lepsze rozwiązanie wprowadzając tą klatkę do bazy i wprowa-
dzając do niej pewien niezerowy przewóz.
Obliczanie ocen (współczynników optymalności) klatek niebazowych
(zmiennych niebazowych)
Współczynniki optymalności c
ij
dla zmiennej niebazowej x
ij
można wyzna-
czyć bez znajomości tablicy sympleksowej wykorzystują tzw. potencjały tj. liczby
u
i
, i
= 1, . . . , p oraz v
j
, j
= 1, . . . , q. Znając bazowe rozwiązanie dopuszczalne
wiemy, że współczynniki optymalności dla zmiennych bazowych są zerami. War-
tości potencjałów (są to tzw. mnożniki sympleksowe za pomocą których można
wyznaczyć - znając bazę - współczynniki optymalności w tablicy sympleksowej. W
optymalnej tablicy transportowej potencjały są optymalnymi wartościami zmien-
nych dualnych. ) wyznacza się następująco:
dla każdej zmiennej bazowej x
ij
mamy równanie c
ij
= 0 = c
ij
+ u
i
+ v
j
.
Mamy zatem układ p + q − 1 równań o p + q niewiadomych. Przyjmując za jedną
niewiadomą zero np. u
1
= 0 można go łatwo rozwiązać. Znajomość wartości u
i
, v
j
pozwala już wyznaczyć współczynniki optymalności za wzoru:
c
ij
= c
ij
+ u
i
+ v
j
dla każdej zmiennej niebazowej x
ij
.
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
35
10
20
20
10
30
u
1
u
2
u
3
v
1
v
2
v
3
v
4
Potencjały dobieramy tak aby wyzerować współczynniki optymalności dla zmien-
nych bazowych, tj.:
8 + u
1
+ v
1
= 0 (x
11
)
9 + u
2
+ v
1
= 0 (x
21
)
12 + u
2
+ v
2
= 0 (x
22
)
13 + u
2
+ v
3
= 0 (x
23
)
16 + u
3
+ v
3
= 0 (x
33
)
10 + u
3
+ v
4
= 0 (x
34
)
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
9
Powyższy układ można rozwiązać bardzo prosto. Zaczynamy od podstawienia
u
1
= 0. Wówczas z pierwszego równaia v
1
= −8. Z drugiego równania u
2
= −1. Z
trzeciego równania v
2
= −11 itd... Ostatecznie otrzymujemy potencjały pokazane
na poniższym rysunku. Obliczamy oceny klatek niebazowych c
ij
= c
ij
+ v
i
+ v
j
.
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
35
10
20
20
10
30
0
-1
-4
-8
-11
-12
-6
-5
-2
-4
0
2
-6
35
50
40
45
20
30
30
35
10
20
20
10
30
Przekształcone koszty wyznaczają oceny klatek niebazowych. Aby poprawić roz-
wiązanie należy wprowadzić do bazy klatkę dla której ocena jest ujemna tj. jedną
z klatek [1, 2], [1, 3], [1, 4] lub [3, 2]. Jeżeli wszystkie oceny byłyby nieujemne to
aktulane rozwiązanie byłoby optymalne.
Algorytm transportowy
KROK 1 Na wejściu podajemy zbilansowane zagadnienie transportowe. Jeżeli
model nie jest zbilansowany to należy go zbilansować wprowadzając fikcyjnego
dostawcę albo fikcyjnego odbiorcę.
KROK 2 Skonstruuj tablicę transportową i pierwsze bazowe rozwiązanie do-
puszczalne (dowolną z podanych metod ).
KROK 3 Oblicz potencjały u
i
, i = 1, . . . , p i v
i
= 1, . . . , q oraz oceny klatek
niebazowych c
ij
= c
ij
+ u
i
+ v
i
. Jeżeli wszystkie oceny c
ij
≥ 0 to KONIEC -
rozwiązanie jest optymalne. W przeciwnym wypadku przejdź do kroku 4.
KROK 4 Wybierz klatkę z najmniejszą ujemną oceną. Dodaj tą klatkę do kla-
tek bazowych i zbuduj cykl zawierający dodawaną klatkę i pewne klatki bazowe
(istnieje dokładnie jeden taki cykl). Oznacz dodawaną klatkę symbolem +. Na-
stępnie przesuwając się wzdłuż cyklu oznaczaj kolejne klatki cyklu na przemian -
i +. Znajdź klatkę oznaczoną - dla której aktualna wielkość przewozu δ jest naj-
mniejsza. Klatka ta wychodzi z bazy. Do klatek + dodaj przewóz δ a od klatek -
odejmij przewóz δ. Jeżeli δ > 0, to otrzymałeś rozwiązanie o mniejszym koszcie.
Wróć do kroku 3.
Przykład
. Rozwiążemy przykładowe zadanie ze strony 1. Zagadnienie jest zbi-
lansowane. Konstruujemy tablicę transportową i pierwsze rozwiązanie bazowe
metodą minimalnego elementu. Otrzymujemy tablicę:
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
10
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
30
5
45
15
5
25
Obliczamy potencjały:
6 + u
1
+ v
2
= 0
zmienna bazowa x
12
2 + u
1
+ v
4
= 0
zmienna bazowa x
14
9 + u
2
+ v
1
= 0
zmienna bazowa x
21
13 + u
2
+ v
3
= 0
zmienna bazowa x
23
9 + u
3
+ v
2
= 0
zmienna bazowa x
32
16 + u
3
+ v
3
= 0
zmienna bazowa x
33
Otrzymujemy:
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
30
5
45
15
5
25
0
-6
-2
-3
-13
0
-9
-1
-3
6
5
2
5
35
50
40
45
20
30
30
30
5
45
15
5
25
Rozwiązanie nie jest optmalne ponieważ pewne klatki niebazowe mają ujemne
oceny. Wybieramy klatkę z najmniejszą ujemną oceną, czyli [1,3]. Dodajemy tą
klatkę do klatek bazowych i konstruujemy cykl:
-1
-3
6
5
2
5
35
50
40
45
20
30
30
30
5
45
15
5
25
+
-
+
-
Najmniejszy przewóz dla klatek oznaczonych znakiem minus(-) znajduje się w
klatce [1,2]. Klatka ta wychodzi z bazy. Do klatek oznaczonych znakiem plus(+)
dodajemy 5 a od klatek oznaczonych - odejmujemy 5. Otrzymujemy kolejne,
lepsze rozwiązanie bazowe i ponownie obliczamy potencjały
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
11
8
6
10
2
9
12
13
7
14
9
16
10
35
50
40
45
20
30
30
30
5
45
20
5
20
0
-3
-2
-6
-10
-3
-6
2
3
6
2
2
2
35
50
40
45
20
30
30
30
5
45
20
5
20
Ponieważ wszystkie oceny klatek niebazowych są nieujemne to tablica zawiera
optymalne rozwiązanie.
Przykład - rozwiązania zdegenerowane
. Rozpatrzmy zagadnienie dla którego po-
daż, popyt, koszty oraz pierwsze rozwiązanie bazowe (metoda kąta północno-
zachodniego) podane są w tabeli:
12
6
10
9
12
4
3
9
2
10
10
10
10
10
10
10
0
10
0
10
W pierwszym rozwiązaniu pewne zmienne bazowe mają wartość 0. Rozwiązanie
takie nazywamy rozwiązaniem zdegenerowanym. Należy odróżniać klatki z zerami
bazowymi od klatek niebazowych! Obliczamy potencjały:
12
6
10
9
12
4
3
9
2
10
10
10
10
10
10
10
0
10
0
10
0
-12
3
-15
6
-8
-9
2
-1
-3
10
10
10
10
10
10
10
0
10
0
10
0
-12
3
-15
6
-8
Do bazy wprowadzamy klatkę [1,2]. Tworzymy cykl i wykonujemy iterację:
-9
2
-1
-3
10
10
10
10
10
10
10
0
10
0
10
0
-12
3
-15
6
-8
+
-
+
-
12
6
10
9
12
4
3
9
2
10
10
10
10
10
10
0
10
10
0
10
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
12
Należy uważać, aby nie usunąć z bazy dwóch klatek [1,1] i [2,2]. Z bazy wycho-
dzi tylko jedna z tych klatek (obojętnie która). Druga pozostaje klatką bazową.
Otrzymujemy kolejne rozwiązanie zdegenerowane.
Trasy zakazane. Jeżeli połączenie między dostawą i a odbiorcą j nie istnieje to
podstawiamy c
ij
= M , gdzie M jest jakąś bardzo dużą liczbą. Jeżeli w końcowej
tablicy transportowej otrzymamy x
ij
>
0, to wyjściowe zagadnienie jest sprzecz-
ne ( nie istnieje dopuszczalny plan przewozów).
Przykład.
Rozpatrzmy problem:
Fabryka 1
Fabryka 2
Fabryka 3
Miasto 1
Miasto 2
Miasto 3
Miasto 4
35
50
40
45
20
30
30
3
2
9
7
8
9
14
7
Pierwsza tablica ( bazowe rozwiązanie dopuszczalne wyznaczone metodą kąta
północno-zachodniego) i pierwsza iteracja są następujące:
3
M
M
2
9
M
7
M
M
12
14
7
35
50
40
45
20
30
30
30
35
10
20
20
10
0
-3
-6
-M+6
-1
-13
6
6
M-1
8
M
M-16
-M+5
35
50
40
45
20
30
30
30
35
10
20 20
10
+
-
+
-
3
M
M
2
9
M
7
M
M
12
14
7
35
50
40
45
20
30
30
30
35
10
10
30
10
...
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
13
Rozwiązenie to nie jest jeszcze optymalne. Należy wykonać kolejne iteracje. Opty-
malne rozwiązanie pokazane jest w poniższej tablicy:
3
M
M
2
9
M
7
M
M
12
14
7
35
40
40
45
10
30
30
0
30
10
35
10
30
Ponieważ przewóz na trasach zakazanych jest 0 to rozwiązanie to jest dopuszczal-
ne (i optymalne).
Wieloetapowe zagadnienie transportowe
Przykład.
Trzy fabryki F1, F2 i F3, których podaż wynosi 20, 10 i 30 mają do-
starczyć towar do dwóch odbiorców O1 i O2 , których popyt wynosi 20 i 40. To-
war może być przewożony po trasach pokazanych na rysunku (czyli niekoniecznie
bezpośrednio z fabryk do odbiorców). Wyznaczyć plan przewozu minimalizujący
łączny koszt.
F1
F3
F2
O1
O2
+20
+10
+30
-40
-20
1
2
F1
F2
F3
1
2
O2
F2
F3
1
2
O1
O2
20
10+s
30+s
s
s
s
s
s
s
s
20
40+s
2
3
7
1
3
5
4
7
1
1
2
3
1
0
1
7
0
0
4
0
5
3
1
7
0
Połączenia oraz odpowiednia tablica transportowa pokazane są na rysunku.
Uwaga: Do pustych klatek należy wpisać koszty M (ponieważ odpowiednie po-
łączenia nie istnieją).
Tablica jest skonstruowana następująco. Zaczynamy od wyróżnienia trzech ro-
dzajów punktów: dostawców, którzy tylko wysyłają towar (F1), odbiorców, któ-
rzy tylko odbierają towar (O1) oraz punktów pośrednich (F2, F3, 1, 2,O2). W
wierszach umieszczamy dostawców i punkty pośrednie a w kolumnach odbiorców
A. Kasperski, M. Kulej, Badania operacyjne, Wykład 4, Zagadnienie transportowe
14
i punkty pośrednie. Obliczamy całkowitą ilość towaru w problemie, czyli tzw. bu-
for s
= 20 + 30 + 10 = 60. Punkt F1 jest dostawca - jego podaż wynosi więc 20.
Punkt F2 jest punktem pośrednim z nadwyżką towaru 10. Przypisujemy mu po-
daż 10+s i popyt s. Punkt 1 jest punktem pośrednim, który nie ma ani nadwyżki
ani niedoboru towaru. Przypisujemy mu podaż i popyt równe s. Punkt O2 jest
punktem pośrednim, który ma niedobór towaru. Przypisujemy mu popyt 20 + s i
podaż s. Do tablicy wpisujemy koszty bezpośrednich połączeń między puntkami
i M jeżeli połączenie bezpośrednie nie istnieje.
Uwaga: Koszty przewozu między tymi samymi punktami, np: między F2 i F2
wynoszą 0. Są to tzw. przewozy fikcyjne.
Rozwiązanie optymalne pokazane jest na poniższym rysunku:
F1
F3
F2
O1
O2
+20
+10
+30
-40
-20
1
2
F1
F2
F3
1
2
O2
F2
F3
1
2
O1
O2
20
70
90
60
60
60
60
60
60
60
20
100
1
3
4
7
1
2
3
1
0
1
7
0
0
4
0
5
3
1
7
0
20
60
10
20
10
60
30
30
40
20
20
20
40
40
60
Końcowe uwagi na temat algorytmu transportowego:
1. Algorytm działa również wtedy, gdy koszty przewozów są ujemne.
2. Jeżeli celem jest maksymalizacja kosztów przewozu, to przed zastosowaniem
algorytmu należy przemnożyć wszystkie koszty przez -1.
3. Jeżeli podaże i popyty wszystkich dostawców i odbiorców są liczbami cał-
kowitymi, to algorytm zwraca optymalny przewóz całkowitoliczbowy.
Wyszukiwarka
Podobne podstrony:
Badania operacyjne wyklad 2 id Nieznany
Badania operacyjne, zadanie id Nieznany (2)
Kulej M, Badania Operacyjne w3m
badania operacyjne poss1 id 630 Nieznany (2)
Kulej M, Badania Operacyjne w1m
Badania operacyjne wyklad 1 id 76574 (2)
AM Badania operacyjne wyklad id 620139
Badania operacyjne wyklad 2 id Nieznany
Badania operacyjne, zadanie id Nieznany (2)
badania operacyjne 3 id 76767 Nieznany (2)
badania operacyjne 1 id 76766 Nieznany
badania operacyjne 9 id 76768 Nieznany
Badania operacyjne id 76520 Nieznany (2)
badania operacyjne 3 id 76767 Nieznany (2)
Jadczak R Badania operacyjne, Wykład 4 Optymalizacja w logistyce
Lab 1 Analiza wrazliwosci, Materiały AGH- zarządzanie finansami, badania operacyjne
progr siec, Materiały Ekonomiczna, badania operacyjne
Kolorowanie grafów, badania operacyjne
bo2T, Szkoła, Semestr 3, Semestr 3, Badania operacyjne
więcej podobnych podstron