Geoscience Reference
In-Depth Information
X
p
Df
x
1
;:::;x
p
g
that minimizes the following objective function
n
X
minimize
X
p
i
d
.i/
.X
p
/;
(10.30)
iD1
where d.v;X
p
/
WD
min
iD1;:::;p
d.v;x
i
/ with v
2
V ; d.X
p
/
WD
.
w
1
d.v
1
;X
p
/;:::;
w
n
d.v
n
;X
p
// and d
.X
p
/
WD
.
w
.1/
d.v
.1/
;X
p
/;:::;
w
.n/
d.v
.n/
;X
p
// a permutation
of the elements of d.X
p
/, verifying:
w
.1/
d.v
.1/
;X
p
/
:::
w
.n/
d.v
.n/
;X
p
/:
The main result of this section establishes a generalization of the well-known
theorem of Hakimi which states that always exists an optimal solution in V .
Theorem 10.7
If
1
2
:::
n
then Problem
(
10.30
)
has always an optimal
solution
X
p
contained in
V
.
Proof
Since by hypothesis
1
2
:::
n
we have that
n
n
X
X
f
.d.X
p
//
D
i
d
.i/
.X
p
/
D
minimize
f
i
d
.i/
.X
p
/
W
2
ǘ.
f
1;:::;n
g
/
g
:
iD1
iD1
Assume that X
p
6
V .
Then there must exist x
i
2
X
p
with x
i
62
V .Lete
Df
v;
w
g
be the edge
containing x
i
and `.e/ its length. Denote by X
p
.s/
D
X
p
nf
x
i
g[f
x.s/
g
where
x.s/ is the point on e with d.v;x.s//
D
s, s
2
Œ0;l.e/.
The function g defined as g.s/
D
P
iD1
i
d
.i/
.X
p
.s// is concave for all s
2
Œ0;`.e/ because it is the composition of a concave and a linear function, i.e.
(
n
i
d
.i/
.X
p
.s//
)
X
g.s/
D
min
2ǘ.f1;:::;ng/
iD1
and each
d
.j/
.X
p
.s//
D
min
f
d.v
.j/
;x
1
/;:::;min
f
d.v
.j/
;a/
C
s;d.v
.j/
;b/
C
`.e/
s
g
;:::;d.v
.j/
;x
n
/
g
is concave.
Hence, g.s/
D
F.X
p
.s//
min
f
F.X
p
.0//;F.X
p
.`.e//
g
and the new solution
set X
p
.s/ contains instead of x
i
one vertex of V .
Repeating this scheme a finite number of times the result follows.
In the previous section we proved that the set V
[
EQ
always contains the set of
optimal solutions of the problem (independent of the structure of ). It might seem
natural to expect that the same result holds for the p-facility case as it happens for
the p-center problem. However, Example
10.4
shows that this property fails to be
true.
