Systemy

transportowe II

WYKŁAD 4

GRAF STRUKTURY

SYSTEMU

TRANSPORTOWEGO

systemy transportowe II – W4 J.

Żak

2

G = <W, L>

gdzie:

W

- zbiór wierzchołków grafu

G

W = {1, 2, ..., a, ..., i, j, ...,

b, ..., N};

L

- jest relacją określoną na iloczynie

kartezjańskim WW, tj.

LWW

,

Drogą

Drogą

w grafie G, z węzła

a

do węzła

b

nazywać będziemy ciąg:

p(a,b) = a, k, ..., i, j, ...,

l, b

gdzie a, k, i, j, l, bW

p(a,b) = (a, k); (k, ...); ...; (i, j); ...; (..., l); (l, b)

gdzie (a, k);...; (i, j)...; (l,
b)L

3

systemy transportowe II – W4 J.

Żak

DROGĄ

w grafie G, z węzła

a do węzła b nazywać

będziemy ciąg

systemy transportowe II – W4 J.

Żak

4

(i,

j)

l

b

i

j

a

k

..

.

..

.

..

.

..

.

(a,

k)

(l,
b)

(...,

i)

(j, ...

)

(...,

l)

...

...

..

.

..

.

(k, ..

.)

(...,

i)

(a, ..

.)

(...,

b)

...

..

.

..

.

...

...

...

...

(...,

l)

(a, ..

.)

węzeł

końca drogi

węzeł

początku

drogi

węzły pośrednie

p(a,b)= <(a, k), (k, ...), ..., (..., i), (i, j),
(j, …), ...,

,(..., l), (l, b)>

Zbiór wszystkich dróg łączących
węzeł początkowy a z węzłem
końcowym b oznaczymy przez

P

ab

5

systemy transportowe II – W4 J.

Żak

P

ab

= {p(a,b): a, bϵW

}

Węzeł a -węzeł początku drogi
(

ŹRÓDŁO)

węzeł b - węzeł końca drogi
(

UJŚCIE

).

Zbiór wszystkich dróg w sieci
transportowej oznaczać będziemy przez

P

,

P

ab

P

.

6

systemy transportowe II – W4 J.

Żak

Dla jednoznaczności dalszych rozważań,
przyjmujemy następującą notację:

p

- numer (nazwa) drogi

rozpoczynającej się w węźle a, a ∈ W i
kończącej się w węźle b, b ∈ W, przy
czym zakładamy, że p=1, …, n;

P

ab

- zbiór wszystkich dróg łączących a z

b;

P

- zbiór wszystkich dróg w grafie

(strukturze) G, przy czym P

ab

 P;

W

p

- zbiór węzłów p-tej drogi;

L

p

- zbiór łuków p-tej drogi.

• DROGĄ PROSTĄ

w grafie G, z węzła a do b

nazywamy drogę, w której wszystkie
wierzchołki są różne.

•DŁUGOŚCIĄ

p-tej drogi

(p



P

ab

), w

sensie

STRUKTURY

jest liczba węzłów lub

liczba łuków tworzących tą drogę.

• DROGĄ MINIMALNĄ

w zbiorze P

ab

nazywamy drogę p



P

ab

z węzła a do b o

minimalnej liczbie węzłów i łuków, (a, bW).

• DROGĄ CYKLICZNĄ

w grafie G=(W, L)

nazywamy drogę pP

ab

taką, że a=b dla

a,bW.

systemy transportowe II – W4 J.

Żak

7

Jeżeli założymy, że między dwoma węzłami
a i b,

zbiór dróg P

ab

nie jest

zbiorem

pustym

, to między tymi wierzchołkami

istnieje zawsze droga.

STRUKTURA SYSTEMU TRANSPORTOWEGO

jest wówczas

SPÓJNA

w sensie dróg.

Graf G=W, L jest

SILNIE SPÓJNY

(w sensie

dróg), gdy:

tzn. gdy między każdą parą węzłów istnieje
co najmniej jedna droga.

 

systemy transportowe II – W4 J.

Żak

8

ab

a,b

; a,b

P

"�ι�W

W

Siecią S

będziemy nazywać

uporządkowaną

trójkę postaci:

S = <G, F

W

,

F

L

>

gdzie

:

G = <W, L>

jest grafem

struktury;

9

systemy transportowe II – W4 J.

Żak

F

W

= {f

1

, f

2

, ..., f

2

,…, f

K

}

jest

zbiorem

funkcji

, określonych na zbiorze

W

grafu

G, tzn

. f

k

: W →R

+

{0};

f

k

(i)R

+

{0} k = 1,2, ... , K;

F

L

={g

1

, g

2

, ... ,g

n

,…, g

N

}

jest

zbiorem

funkcji

, określonych na zbiorze łuków

L

grafu

G

, tzn

. g

n

:

L

→R

+

{0};

g

n

(i, j) R

+

{0}; n= 1,2, ... ,

N;

systemy transportowe II – W4 J.

Żak

10

W zależności od celu badań zbiory
funkcji F

W

oraz F

L

opisują

charakterystyki, m.in.:

TECHNICZNE

(

np. przepustowość,

pojemność, czas przejścia itp.),

EKONOMICZNE

(

np. koszt

przemieszczania

),

MATEMATYCZNE

(

np.

prawdopodobieństwo przejścia od węzła do
węzła),elementów systemu transportowego

.

11

systemy transportowe II – W4 J.

Żak

W przypadku gdy: F

W

=F

L

=∅, to

sieć S jest grafem.

CHARAKTERYSTYKI OKREŚLONE NA

ŁUKACH LUB WĘZŁACH MOGĄ BYĆ

ZAPISANE W POSTACI LICZB,

PARAMETRÓW LUB FUNKCJI

12

systemy transportowe II – W4 J.

Żak

Na

potrzeby

modelowania

systemów

transportowych przyjmujemy oznaczenia

c

ij

-

KOSZT PRZEJŚCIA JEDNOSTKI POTOKU RUCHU

ODCINKIEM DROGI

odwzorowanym łukiem (i,j);

c

p,ab

-

KOSZT PRZEJŚCIA JEDNOSTKI POTOKU

RUCHU p-tą DROGĄ

z węzła początkowego

o numerze a, do węzła końcowego o numerze b;

d

ij

-

PRZEPUSTOWOŚĆ ODCINKA

drogi

odwzorowanego łukiem (i, j);

d

p,ab

-

PRZEPUSTOWOŚĆ p-tej DROGI

pomiędzy

węzłem początkowym o numerze a, oraz węzłem
końcowym o numerze b;

13

systemy transportowe II – W4 J.

Żak

ZAŁOŻENIA

 S = <G, F

W

, F

L

> jest siecią

transportową,

w zbiorze F

L

istnieje funkcja postaci

c, przyjmująca wartości ze zbioru liczb
rzeczywistych dodatnich, tj. c

ij

∈R

+

dla

każdego (i, j), (i, j) ∈ L;

wartościom c

ij

nadamy interpretację

kosztu przejścia jednostki potoku
ruchu łukiem (i, j),

14

systemy transportowe II – W4 J.

Żak

Istnieje funkcja ze zbioru F

L

postaci

d, przyjmująca wartości ze zbioru liczb
rzeczywistych dodatnich, tj. d

ij

∈ R

+

dla każdego (i, j) ∈ L;

wartościom d

ij

nadamy interpretację

przepustowości łuku (i,j) ∈ L;
kosztem przejścia jednostki potoku
ruchu p-tą drogą, przy czym p ∈ P

ab

,

będzie suma wartości c

ij

po wszystkich

łukach tej drogi

15

systemy transportowe II – W4 J.

Żak







p

c

L

)

j

,

i

(

ij

p

c

gdzie c

p

jest kosztem p-tej drogi, wyrażonym w

ustalonych jednostkach.

16

systemy transportowe II – W4 J.

Żak

KOSZTEM p-tej DROGI

BĘDZIE SUMA

KOSZTÓW PRZEJŚCIA JEDNOSTKI POTOKU RUCHU
ODCINKIEM DROGI ODWZOROWANYM ŁUKIEM
(i,j) P ∈ P

ab

,











ab

b

a

b

,

a

P

W:

}

{c

min

c

*

p

p

p

ab

ab

p

P

P









:

*

}

{c

*

p

p

p

min

ab

c

P





wtedy

:

Powiemy wówczas, że p* jest

DROGĄ

O MINIMALNYM KOSZCIE

łączącą

węzeł a z węzłem b, gdy:

17

systemy transportowe II – W4 J.

Żak

Jeżeli

:

PRZEPUSTOWOŚCIĄ

p-tej

DROGI

będzie

największa

intensywność

potoku

ruchu,

którą

możemy

obciążyć tę drogę, co oznacza, że
przepustowość drogi jest okreslona

NAJMNIEJSZĄ

PRZEPUSTOWOŚCIĄ

odcinka (i,j) wchodzącego w skład
drogi p, tj. (i ,j)∈L

p

, co zapisujemy.:

 

 

ij

L

i,j

p

d

min

d

p





18

systemy transportowe II – W4 J.

Żak

}

{

min

*

p

p

p

d

d

ab

P





}

{

max

*

p

p

p

d

d

ab

P





DROGA O MINIMALNEJ

(MAKSYMALNEJ) PRZEPUSTOWOŚCI

,

tj.:

w tym przypadku droga p* jest drogą o

najmniejszej (największej) przepustowości między
węzłem a i węzłem b.

19

systemy transportowe II – W4 J.

Żak

PRZYKŁAD 1
Graf opisujący strukturę systemu transportowego ,
G =<W, L>, dla którego:

systemy transportowe II – W4 J.

Żak

20

(3,5)

(4,5)

(1,3)

(1,2)

(2,3)

(2,4)

(3,4)

1

2

3

4

5

21

systemy transportowe II – W4 J.

Żak