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

punkty

nadania

odbioru

(i)

(j)

podaż

popyt

x c

a

D

11 11

O

b

1

1

1

1

x c

x c

12 12

x c

21 21

1n 1n

a

D

x c

O

b

2

2

22 22

2

2

x c

●

2n 2n

●

●

●

●

x

c

x

c

m1 m1

m2 m2

●

a

D

x

c

O

b

m

m

mn

mn

n

n

Klasyczne zadanie transportowe – definicja (2) Założenia klasycznego zadania transportowego:

x

- zmienne decyzyjne; ilo

ij

ść przewożonego jednorodnego dobra

na trasie pomiędzy i-tym dostawcą a j-tym odbiorcą [ i=1,2,…, m; j=1,2,…, n; ]

a

- parametr problemu; zasób dobra u i-tego dostawcy (poda

i

ż)

[ i=1,2,…, m]

a = [a ,a ,…,a ]

1

2

m

b

- parametr problemu; zapotrzebowanie na dobro j-tego odbiorcy

j

(popyt) [ j=1,2,…, n]

b = [b ,b ,…,b ]

1

2

n

c

- parametr problemu; koszt przewozu jednostki dobra na trasie

ij

pomiędzy i-tym dostawcą a j-tym odbiorcą [ i=1,2,…, m; j=1,2,…, n; ]

 c

c

L

c 

11

12

1 n





m

c

c

L

c

∑

21

22

2 n

a

b





C =

i ≥ n

∑ j

 M

M

O

M 

i =1

j =1





 c

c

L

c

m 1

m 2

mn 

1

Klasyczne zadanie transportowe – definicja (3) Klasyfikacja zadań transportowych:

1. Zamknięte

m

∑ a

b

i = n

∑ j

i =1

j =1

2. Otwarte

m

∑ a

b

i > n

∑ j

i =1

j =1

Otwarte ⇒ Zamknięte:

a) dodać n+1 punkt odbioru

b) zapotrzebowanie b

dodanego punktu odbioru – ró

n+1

żnica między

całkowitą podażą a całkowitym popytem:

b

a

b

n 1 = m

n

∑

∑

+

i −

j

i=1

j =1

Klasyczne zadanie transportowe – model decyzyjny

Funkcja celu: ( łą czny koszt transportu) m

n

F (x) = ∑ ∑ c x

ij ij → min

i 1

= j 1

=

Ograniczenia:

n

∑ x = a

i = 1,2,…, m

(bilanse dla punktów nadania)

ij

i

i =1

m

∑ x = b

j = 1,2,…, n

(bilanse dla punktów odbioru)

ij

j

i =1

Warunki brzegowe:

x

i = 1,2,…, m

j = 1,2,…, n

ij ≥ 0

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

50

110

70

120

350

odbiorców

2

Klasyczne zadanie transportowe – przykład (2)

F(χ ) =

2x

+2x

+3x

+5x

+3x

+x

+x

+2x

+2x

+4x

+4x

+4x

11

12

13

14

21

22

23

24

31

32

33

34

→

min

x

+x

+x

+x

=

140

11

12

13

14

żado

+x

+x

+x

+x

=

80

21

22

23

24

p

+x

+x

+x

+x

=

130

31

32

33

34

x

+x

+x

=

50

11

21

31

t

x

+x

+x

=

110

12

22

32

ypop

x

+x

+x

=

70

13

23

33

x

+x

+x

=

120

14

24

34

x

x

x

x

x

x

x

x

x

x

x

x

11≥0

12≥0

13≥0

14≥0

21≥0

22≥0

23≥0

24≥0

31≥0

32≥0

33≥0

34≥0

Klasyczne zadanie transportowe – algorytm transportowy (1) 1

Początkowy

6

Skoryguj program

program przewozowy

przewozowy

5

Ustal maksymalny

przewóz na trasie

Program

ustalonej w [3]

NIE

2

optymalny?

4

Zbuduj cykl

TAK

Korygujący przewozy

KONIEC

3

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 = min( a ,b ) ij

i

j

2. skoryguj podaż w i-tym punkcie nadania: a = a – x i popyt w j-tym i

i

ij

punkcie odbioru: b = b – x

i

i

ij

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 >0 zawieraj ij

ą jedną

liczbę: jednostkowy koszt transportu cij 2. pozostałe pola tabeli wskaźników optymalności zawierają dwie liczby: ( u + v ) oraz wska

= c –( u + v )

i

j

źnik optymalności ∆ ij

ij

i

j

3. program przewozowy jest optymalny, jeżeli wszystkie ∆ ≥0

ij

4. wyznaczenie trasy dającej największą obniżkę kosztów (jeżeli uzyskany program przewozowy nie jest optymalny):

dla wszystkich ∆ <0

∆ = min{∆ }

ij

kl

ij

Klasyczne zadanie transportowe – algorytm transportowy (5) Sprawdzenie optymalności programu przewozowego O1

O2

O3

O4

ui

2

2

D1

2

2

0

1

3

1

1

D2

1

1

-1

2

1

4

4

D3

4

4

2

-2

0

vj

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 δ poprzez wybór wartości najmniejszej oznaczonej znakiem „-”: δ = min( x -” )

ij”

4. skoryguj rozpatrywany program przewozowy poprzez: x * = x + δ dla tras oznaczonych znakiem „+”

ij

ij

x * = x + δ dla tras oznaczonych znakiem „-”

ij

ij

x * = x

dla tras nieoznaczonych

ij

ij

Klasyczne zadanie transportowe – algorytm transportowy (7) Korekta programu przewozowego

O1

O2

O3

O4

podaż

D1

50

90

140

–

-10

+

+10

D2

20

60

80

–

-10 +

+10

D3

10

120

130

+

+10

–

-10

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

Klasyczne zadanie transportowe – algorytm transportowy (9) Sprawdzenie optymalności programu przewozowego – iteracja 2

O1

O2

O3

O4

ui

2

4

D1

2

2

0

1

1

1

1

D2

1

1

-1

2

-1

2

2

D3

2

4

0

2

2

vj

2

2

2

4

×

Klasyczne zadanie transportowe – algorytm transportowy (10) Korekta programu przewozowego

O1

O2

O3

O4

podaż

D1

40

100

140

–

-10

+

+10

D2

10

70

80

–

-10

+

+10

D3

10

120

130

+

+10

–

-10

popyt

50

110

70

120

350

min{40,10,120} = 10

Klasyczne zadanie transportowe – algorytm transportowy (11) Poprawiony program przewozowy

O1

O2

O3

O4

podaż

D1

30

110

140

D2

70

10

80

D3

20

110

130

popyt

50

110

70

120

350

Koszt = 2×30 + 2×110 + 1×70 + 2×10 + 2×20 + 4×110 = 850

lub

Koszt = 860 + 10×(–1) = 860 – 10 = 850

6

Klasyczne zadanie transportowe – algorytm transportowy (12) Sprawdzenie optymalności programu przewozowego – iteracja 3

O1

O2

O3

O4

ui

3

4

D1

2

2

0

0

1

0

0

D2

1

2

-2

3

1

2

3

D3

2

4

0

2

1

vj

2

2

3

4

×

Rozwiązanie optymalne

Klasyczne zadanie transportowe – zadanie otwarte

O1

O2

O3

O4

podaż

D1

2

2

3

5

140

400

D2

3

1

1

2

130

D3

2

4

4

4

130

popyt

50

110

70

120

350

O1

O2

O3

O4

M

podaż

D1

2

2

3

5

0

140

D2

3

1

1

2

0

130

D3

2

4

4

4

0

130

popyt

50

110

70

120

50

400

Klasyczne zadanie transportowe – całkowita blokada trasy lub tras

O1

O2

O3

O4

podaż

D1

2

2

3

5

140

D2

3

1

1

2

80

D3

2

4

4

4

130

popyt

50

110

70

120

350

O1

O2

O3

O4

podaż

D1

2

2

3

5

140

D2

3

1

T

2

80

T → ∞

D3

T

4

4

4

130

popyt

50

110

70

120

350

7

Klasyczne zadanie transportowe – częś ciowa blokada trasy

O1

O2

O3

O4

podaż

D1

2

2

3

5

140

D2

3

1

1 (max. 50)

2

80

D3

2

4

4

4

130

popyt

50

110

70

120

350

O1

O2

O3(a)

O3(b)

O4

podaż

D1

2

2

3

3

5

140

D2

3

1

1

T

2

80

D3

2

4

4

4

4

130

popyt

50

110

50

20

120

350

Zadanie transportowe – kryterium czasu I rodzaju

Funkcja celu: ( łą czny czas transportu) m

n

F (x) = ∑ ∑ t x

t – czas transportu jednostki dobra ij ij → min

ij

i 1

= j 1

=

Ograniczenia:

n

∑ x = a

i = 1,2,…, m

(bilanse dla punktów nadania)

ij

i

i =1

m

∑ x = b

j = 1,2,…, n

(bilanse dla punktów odbioru)

ij

j

i =1

Warunki brzegowe:

x

i = 1,2,…, m

j = 1,2,…, n

ij ≥ 0

Zadanie transportowe – kryterium czasu II rodzaju

Funkcja celu: ( najdłuż szy czas przewozu w optymalnym programie przewozowym jest najkrótszy spoś ród wszystkich dopuszczalnych programów przewozowych – program przewozu zakoń czy się najszybciej) F (x) = min ma {

x t }

t – czas przejazdu pomiędzy punktem ij

∈

ij

x X

x >0

nadania i a punktem odbioru j

ij

Ograniczenia:

n

∑ x = a

i = 1,2,…, m

(bilanse dla punktów nadania)

ij

i

i =1

m

∑ x = b

j = 1,2,…, n

(bilanse dla punktów odbioru)

ij

j

i =1

Warunki brzegowe:

x

i = 1,2,…, m

j = 1,2,…, n

ij ≥ 0

8

Zagadnienie przydziału

Zadanie przydziału – definicja (1) Zadanie optymalnego przydziału – problem najkorzystniejszego skojarzenia n środków z m celami, przy czym każdy środek może być użyty tylko jeden raz.

Założenia klasycznego zadania transportowego:

n

- liczba środków

m

- liczba celów

x

- zmienne decyzyjne; x =1 je

ij

ij

żeli i-ty cel jest realizowany przez j-ty środek; x =0 jeżeli i-ty cel nie jest realizowany przez

ij

j-ty środek; [ i=1,2,…, m; j=1,2,…, n; ]

c

- parametr problemu; korzy

ij

ść związana z realizacją i-tego celu przez j-ty środek [ i=1,2,…, m; j=1,2,…, n; ]

Zadanie przydziału – model decyzyjny ( n = m) Liczba celów = liczba środków = n

Funkcja celu: ( łą czna korzyść) n

n

U (x) = ∑ ∑ c x

ij ij → max (

min)

i 1

= j 1

=

Ograniczenia:

n

∑ x

i = 1,2,…, n

(bilanse dla celów)

ij = 1

i 1

=

n

∑ x

j = 1,2,…, n

(bilanse dla środków)

ij = 1

i 1

=

Warunki brzegowe:

x

i = 1,2,…, n

j = 1,2,…, n

ij ∈

}

1

,

0

{

9

Zadanie przydziału – model decyzyjny ( n > m) Nadwyżka środków nad celami Funkcja celu: ( łą czna korzyść) m

n

U (x) = ∑ ∑ c x

ij ij → max (

min)

i 1

= j 1

=

Ograniczenia:

n

∑ x

i = 1,2,…, m

(bilanse dla celów)

ij = 1

i 1

=

m

∑ x

j = 1,2,…, n

(bilanse dla środków)

ij ≤ 1

i 1

=

Warunki brzegowe:

x

i = 1,2,…, m

j = 1,2,…, n

ij ∈

}

1

,

0

{

Zadanie przydziału – model decyzyjny ( n < m) Nadwyżka celów nad środkami Funkcja celu: ( łą czna korzyść) m

n

U (x) = ∑ ∑ c x

ij ij → max (

min)

i 1

= j 1

=

Ograniczenia:

n

∑ x

i = 1,2,…, m

(bilanse dla celów)

ij ≤ 1

i 1

=

m

∑ x

j = 1,2,…, n

(bilanse dla środków)

ij = 1

i 1

=

Warunki brzegowe:

x

i = 1,2,…, m

j = 1,2,…, n

ij ∈

}

1

,

0

{

Zadanie przydziału – przykład

Kooperant (ś rodki)

I

II

III

IV

V

VI

VII

VIII

A

10

8

8

12

6

8

10

12

)le

B

12

15

6

12

15

9

12

9

e

C

10

10

9

9

8

8

9

9

(cdła D

15

14

12

15

13

13

15

15

kU

E

16

12

14

16

10

10

16

20

F

10

8

10

11

7

7

12

12

U → min

I

II

III

IV

V

VI

VII

VIII

A

0

0

0

0

1

0

0

0

B

0

0

1

0

0

0

0

0

C

0

0

0

0

0

0

1

0

D

0

0

0

0

0

0

0

1

E

0

0

0

0

0

1

0

0

F

0

1

0

0

0

0

0

0

U

= 54

min

10