•
Problem:
istnieje zbiór n miast (punktów), pomiędzy którymi odbywa się wymiana
towarów; każdy punkt jest dostawcą i odbiorcą towarów.
•
Cel:
określić taki plan przejazdu pustych środków transportu, aby łączna
odległość jaką pokonują była jak najmniejsza.
2
•
d
ij
– odległość pomiędzy i-tym a j-tym punktem
•
w
i
– niezbędna liczba środków transportu do wywozu masy towarowej
z i-tego punktu (wywóz)
•
p
i
– niezbędna liczba środków transportu do przywozu masy towarowej
do i-tego punktu (przywóz)
•
Warunek:
3
∑
∑
=
=
=
n
i
i
n
i
i
p
w
1
1
•
Ustalić, które miasto jest dostawcą lub odbiorcą pustych środków
transportu oraz wielkości ich podaży i popytu.
•
Zdefiniować zmienne decyzyjne x
ij
– liczba pustych środków transportu
przewożona pomiędzy i-tym a j-tym punktem.
•
Określić macierz kosztów (odległości).
4
•
Zbiór dostawców – zbiór tych punktów, dla których w
i
< p
i
oraz a
i
= p
i
– w
i
(a
i
jest podażą pustych środków transportu)
•
Zbiór odbiorców – zbiór tych punktów, dla których w
i
> p
i
oraz b
i
= w
i
– p
i
(b
i
jest popytem na puste środki transportu)
•
Jeśli dla danego punktu p
i
= w
i
, to takiego punktu nie rozpatrujemy.
5
Zminimalizować puste przebiegi samochodów przewożących
towar między 7 miastami. Dzienne przywozy p
i
i wywozy w
i
(wyrażone liczbą samochodów) oraz odległości między
miastami przedstawia tablica.
L
M
N
O
P
R
S
w
i
L
0
20
50
100 150 200 100
20
M
0
40
20
30
50
20
40
N
0
100 150 200 100
20
O
0
40
30
150
2
P
0
80
70
4
R
0
60
20
S
0
10
p
i
10
20
40
20
20
6
0
116
6
p
i
w
i
Nadmiar pustych
samochodów
Niedobór pustych
samochodów
L
10 20
-
10
odbiorca
M
20 40
-
20
odbiorca
N
40 20
20
-
dostawca
O
20
2
18
-
dostawca
P
20
4
16
-
dostawca
R
6
20
-
14
odbiorca
S
0
10
-
10
odbiorca
7
L
M
R
S
podaż
N
20
O
18
P
16
popyt
10
20
14
10
L
M
N
O
P
R
S
w
i
L
0
20
50
100
150
200 100
20
M
0
40
20
30
50
20
40
N
0
100 150
200 100
20
O
0
40
30
150
2
P
0
80
70
4
R
0
60
20
S
0
10
p
i
10
20
40
20
20
6
0
116
8
L
M
R
S
podaż
N
50
40 200 100
20
O
100 20
30 150
18
P
150 30
80
70
16
popyt
10
20
14
10
9
L
M
R
S
podaż
N
50
40 200 100
20
O
100 20
30 150
18
P
150 30
80
70
16
popyt
10
20
14
10
•
Zadanie zapisane w powyższej postaci rozwiązujemy zwykłym algorytmem
transportowym
(X
1
, potencjały, V
1
, itd., …)