wyklad 3 zagadnienia transportowe przydzial, Matematyka studia, Badania Operacyjne
[ Pobierz całość w formacie PDF ]
Zagadnienia transportowe
Klasyczne zadanie transportowe –
definicja
(1)
Klasyczne zadanie transportowe – problem najtańszego przewozu
jednorodnego dobra pomiędzy punktami nadania (dostawcy) a punktami
odbioru (odbiorcy).
punkty
nadania
(i)
punkty
odbioru
(j)
poda
Ŝ
popyt
x
11
c
11
a
1
D
1
O
1
b
1
x
12
c
12
x
21
c
21
x
1n
c
1n
a
2
D
2
x
22
c
22
O
2
b
2
●
●
●
x
2n
c
2n
●
●
●
x
m1
c
m1
x
m2
c
m2
a
m
D
m
x
mn
c
mn
O
n
b
n
Klasyczne zadanie transportowe –
definicja
(2)
ZałoŜenia klasycznego zadania transportowego:
x
ij
- zmienne decyzyjne; ilość przewoŜonego jednorodnego dobra
na trasie pomiędzy
i
-tym dostawcą a
j
-tym odbiorcą [
i
=1,2,…,
m;
j
=1,2,…,
n;
]
a
i
- parametr problemu; zasób dobra u
i
-tego dostawcy (podaŜ)
[
i
=1,2,…,
m
]
a
= [a
1
,a
2
,…,a
m
]
b
j
- parametr problemu; zapotrzebowanie na dobro
j
-tego odbiorcy
(popyt) [
j
=1,2,…,
n
]
b
= [b
1
,b
2
,…,b
n
]
c
ij
- parametr problemu; koszt przewozu jednostki dobra na trasie
pomiędzy
i
-tym dostawcą a
j
-tym odbiorcą [
i
=1,2,…,
m;
j
=1,2,…,
n;
]
c
c
12
3
c
1
n
m
n
c
c
22
3
c
2
n
a
³
b
C
=
∑
∑
i
j
4
4
6
4
i
=
1
=
1
c
c
3
c
m
1
m
2
mn
1
11
21
j
Klasyczne zadanie transportowe –
definicja
(3)
Klasyfikacja zada
ń
transportowych:
1. Zamknięte
∑
m
a
=
n
b
∑
i
j
i
=
1
j
=
1
2. Otwarte
∑
m
a
>
n
b
∑
i
j
1
Otwarte
⇒
Zamknięte:
a) dodać
n
+1 punkt odbioru
b) zapotrzebowanie
b
n+1
dodanego punktu odbioru – róŜnica między
całkowitą podaŜą a całkowitym popytem:
∑
i
=
j
=
1
b
=
m
a
-
n
b
∑
n
+
1
i
j
i
=
1
=
1
Klasyczne zadanie transportowe –
model decyzyjny
Funkcja celu: (
ł
ą
czny koszt transportu
)
min
F
x
(
)
=
∑ ∑
= =
m
n
c
ij
x
®
ij
i
1 1
j
Ograniczenia:
n
x
=
a
∑
=1
ij
i
i
= 1,2,…,
m
(bilanse dla punktów nadania)
i
m
x
ij
b
=
∑
=1
j
= 1,2,…,
n
(bilanse dla punktów odbioru)
j
i
Warunki brzegowe:
0
x
ij
³
i
= 1,2,…,
m
j
= 1,2,…,
n
Klasyczne zadanie transportowe –
przykład
(1)
jednostkowe koszty transportu
poda
Ŝ
dostawców
O1
O2
O3
O4
D1
2
2
3
5
140
D2
3
1
1
2
80
D3
2
4
4
4
130
zapotrzebowanie
odbiorców
50
110
70
120
350
2
j
Klasyczne zadanie transportowe –
przykład
(2)
F(
) =
2x
11
+2x
12
+3x
13
+5x
14
+3x
21
+x
22
+x
23
+2x
24
+2x
31
+4x
32
+4x
33
+4x
34
→
min
x
11
+x
12
+x
13
+x
14
=
140
+x
21
+x
22
+x
23
+x
24
=
80
+x
31
+x
32
+x
33
+x
34
=
130
x
11
+x
21
+x
31
=
50
x
12
+x
22
+x
32
=
110
x
13
+x
23
+x
33
=
70
x
14
+x
24
+x
34
=
120
x
11
≥0
x
12
≥0
x
13
≥0
x
14
≥0
x
21
≥0
x
22
≥0
x
23
≥0
x
24
≥0
x
31
≥0
x
32
≥0
x
33
≥0
x
34
≥0
Klasyczne zadanie transportowe –
algorytm transportowy
(1)
Początkowy
program przewozowy
1
6
Skoryguj program
przewozowy
5
Ustal maksymalny
przewóz na trasie
ustalonej w [3]
2
Program
optymalny?
NIE
4
Zbuduj cykl
korygujący przewozy
TAK
KONIEC
Wybierz trasę dającą
największą obniŜkę kosztów
Klasyczne zadanie transportowe –
algorytm transportowy
(2)
Początkowy program przewozowy
Metoda k
ą
ta północno-zachodniego
1. wprowadź maksymalny przewóz na trasie (
i
,
j
):
x
ij
= min(
a
i
,b
j
)
2. skoryguj podaŜ w
i
-tym punkcie nadania:
a
i
= a
i
– x
ij
i popyt w
j
-tym
punkcie odbioru:
b
i
= b
i
– x
ij
3
c
3
Klasyczne zadanie transportowe –
algorytm transportowy
(3)
Początkowy program przewozowy –
Metoda k
ą
ta północno-zachodniego
O1
O2
O3
O4
podaŜ
D1
50
90
140
90
0
D2
20
60
80
60
0
D3
10
120
130
120
0
popyt
50
110
70
120
350
0
20
10
0
0
0
Koszt
= 2
´
50 +
2
´
90 + 1
´
20 + 1
´
60 + 4
´
10 + 4
´
120 =
880
Klasyczne zadanie transportowe –
algorytm transportowy
(4)
Sprawdzenie optymalności programu przewozowego
Tabela wska
ź
ników optymalno
ś
ci
1. pola tabeli wskaźników optymalności, dla których
x
ij
>0
zawierają jedną
liczbę: jednostkowy koszt transportu
c
ij
2. pozostałe pola tabeli wskaźników optymalności zawierają dwie liczby:
(
u
i
+
v
j
) oraz wskaźnik optymalności
D
ij
=
c
ij
–(
u
i
+
v
j
)
3. program przewozowy jest optymalny, jeŜeli wszystkie
D
ij
≥0
4. wyznaczenie trasy dającej największą obniŜkę kosztów (jeŜeli uzyskany
program przewozowy nie jest optymalny):
dla wszystkich
D
ij
<0
D
kl
= min{
D
ij
}
Klasyczne zadanie transportowe –
algorytm transportowy
(5)
Sprawdzenie optymalności programu przewozowego
O1
O2
O3
O4
u
i
D1
2
2
2
2
0
1
3
1
1
D2
1
1
-1
2
1
4
4
D3
4
4
2
-2
0
v
j
2
2
2
2
´
4
Klasyczne zadanie transportowe –
algorytm transportowy
(6)
Korekta programu przewozowego
1. postaw znak „
+
” na wytypowanej trasie dającej największą obniŜkę
kosztów
2. w rozpatrywanym programie przewozowym znakuj trasy o przewozie
niezerowym znakami „
+
” i „
-
” w taki sposób, aby w kaŜdym wierszu i
kaŜdej kolumnie była para „
+
” „
-
” lub nie było ich w ogóle
3. wyznacz wielkość korekty
d
poprzez wybór wartości najmniejszej oznaczonej
znakiem „
-
”:
d
= min(
x
ij”
-”
)
4. skoryguj rozpatrywany program przewozowy poprzez:
x
ij
*
= x
ij
+
d
dla tras oznaczonych znakiem „
+
”
x
ij
*
= x
ij
+
d
dla tras oznaczonych znakiem „
-
”
x
ij
*
= x
ij
dla tras nieoznaczonych
Klasyczne zadanie transportowe –
algorytm transportowy
(7)
Korekta programu przewozowego
O1
O2
O3
O4
podaŜ
D1
–
50
-10
+
90
+10
140
D2
–
20
+
60
80
-10
+10
D3
+
+10
–
10
-10
120
130
popyt
50
110
70
120
350
min{50,20,10} = 10
Klasyczne zadanie transportowe –
algorytm transportowy
(8)
Poprawiony program przewozowy
O1
O2
O3
O4
podaŜ
D1
40
100
140
D2
10
70
80
D3
10
120
130
popyt
50
110
70
120
350
Koszt
= 2
´
40 + 2
´
100 + 1
´
10 + 1
´
70 + 2
´
10 + 4
´
120 =
860
lub
Koszt
= 880 + 10
´
(–2) = 880 – 20 = 860
5
[ Pobierz całość w formacie PDF ]