Systemy
transportowe II
WYKŁAD 4
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 WW, tj.
LWW
,
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, bW
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, bW).
• DROGĄ CYKLICZNĄ
w grafie G=(W, L)
nazywamy drogę pP
ab
taką, że a=b dla
a,bW.
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