wyklad_3_zagadnienia_transportowe_przydzial.pdf

(90 KB) Pobierz
Wykład 3 - Zagadnienia transportowe i przydziału
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
2913087.014.png 2913087.015.png
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
2913087.016.png 2913087.017.png 2913087.001.png
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
2913087.002.png 2913087.003.png 2913087.004.png 2913087.005.png 2913087.006.png 2913087.007.png
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
2913087.008.png 2913087.009.png 2913087.010.png
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
2913087.011.png 2913087.012.png 2913087.013.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin