Geoscience Reference
In-Depth Information
5
20
5
.
11
v
1
v
2
v
3
v
4
v
5
|
|
|
|
|||
|
|
Fig. 10.5
Illustration of Example
10.5
Table 10.6
Evaluation of the candidate pairs of Example
10.5
Candidate pair X
2
Va l u e
Candidate pair X
2
Va l u e
p.f1;2g;0/;p.f3;4g;0/
11:81
p.f1;2g;2:05/;p.f3;4g;3:05/
8:455
p.f1;2g;0/;p.f3;4g;2:55/
11:6
p.f1;2g;2:45/;p.f3;4g;2:55/
9:005
p.f1;2g;0/;p.f3;4g;3:05/
10:6
p.f1;2g;2:5/;p.f3;4g;0/
14:31
p.f1;2g;0/;p.f4;5g;0/
10:61
p.f1;2g;2:5/;p.f3;4g;2:5/
9:06
p.f1;2g;0/;p.f4;5g;0:5/
11:66
p.f1;2g;2:5/;p.f3;4g;2:55/
8:955
p.f1;2g;0/;p.f4;5g;1/
11:71
p.f1;2g;2:5/;p.f3;4g;2:6/
8:95
p.f1;2g;0:5/;p.f4;5g;0:5/
11:16
p.f1;2g;2:5/;p.f3;4g;3:05/
8:905
p.f1;2g;1/;p.f4;5g;0/
10:61
p.f1;2g;2:5/;p.f3;4g;3:6/
8:96
p.f1;2g;1/;p.f4;5g;1/
11:71
p.f1;2g;2:5/;p.f4;5g;0/
9:11
p.f1;2g;1:45/;p.f3;4g;2:55/
10:005
p.f1;2g;2:5/;p.f4;5g;0:5/
9:16
p.f1;2g;1:95/;p.f3;4g;3:05/
8:455
p.f1;2g;2:5/;p.f4;5g;1/
10:21
p.f1;2g;2/;p.f3;4g;3:1/
8:41
The w-weights are all equal to one and the -weights are
1
D
0;
2
D
1;
3
D
0;
4
D
1;
5
D
1:1,seeFig.
10.5
.
In Fig.
10.5
, we use the same notation as in Fig.
10.4
and pairs of T are
represented by .?/. By domination and symmetry arguments not all the candidates
are necessary and therefore, they are not depicted.
In this example the optimal solution is given by x
1
D
p.
f
1;2
g
;2/ and x
2
D
p.
f
3;4
g
;3:1/(see Table
10.6
). Therefore the optimal pair .x
1
;x
2
/ belongs to the
set T . Indeed, d.v
1
;x
1
/
D
d.v
4
;x
2
/ and d.v
2
;x
1
/
D
d.v
5
;x
2
/ and the slopes of
d.v
1
;
/;d.v
2
;
/ in the edge
f
1;2
g
at x
1
are 1;
1 respectively; and the slopes of
d.v
4
;
/;d.v
5
;
/ in the edge
f
3;4
g
at x
2
are
1;
1 respectively.
Once we have proved that F is an essential set to describe the set of optimal
solutions of the 2-facility ordered median problem we want to know its cardinality.
Proposition 10.2
The cardinality of
F
is
O.m
3
n
6
/
.
Proof
In each edge there are at most two equilibrium points associated with each
pair of nodes. Thus
j
EQ
jD
O.
mn
2
/ and
j
R
jD
O.
mn
3
/. The maximum degree of a
node v
i
2
V is m (the star network) so
j
Y.r/
jD
O.
mn
/ with r
2
R. Thus,
j
Y
jD
O.m
2
n
4
/. On the second hand, on each edge, each pair of nodes may determine
an element of a pair in T . Therefore, the set T has a cardinality O..n
2
m/
2
/.In
conclusion
j
F
jD
O.m
3
n
6
C
m
2
n
4
/
D
O.m
3
n
6
/.
It is worth noting that F is an actual set of finite elements to be optimal solutions
of problem (
10.30
). The difference with previous approaches is that this set is not a
