•

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., …)