minimalizacja pustych przebiego Nieznany

background image
background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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


Wyszukiwarka

Podobne podstrony:
Minimalizacja pustych przebiegów, Zadania
minimalizacja pustych przebiegow(1)
Arabska wiosna przyczyny przebi Nieznany (2)
Choroby zakazne przebiegajace z Nieznany
Chomsky A Minimalist Program Fo Nieznany
8 Scinanie, Skrecanie, Przebici Nieznany (2)
przyczyny wybuchu, przebieg i s Nieznany
Deficyty poznawcze a przebieg s Nieznany
Minimalizacja oddzialywania na Nieznany
Minimalizacja funkcji 3 lub 4 z Nieznany
Arabska wiosna przyczyny przebi Nieznany (2)
Choroby zakazne przebiegajace z Nieznany
Generatory przebiegow niesinuso Nieznany
przebieg negocjacji PL UE id 91 Nieznany
AMI 21 Przebieg zmiennosci fun Nieznany (2)
Modul 1 Wzorcowy przebieg zaje Nieznany
Przebicie LT wersja do druku i Nieznany
PROGRAM PRZEBIEGU CYKLU SZKOLEN Nieznany

więcej podobnych podstron