Biology Reference
In-Depth Information
Table 2.4. Summary of computation results for 3 examples. See Sec. 2.5(a) for
explanation of the EM running time and iterations count.
PDQ Algorithm
EM Algorithm
Example
Iterations
Time (sec.)
Iterations
Time (sec.)
Example 2.4
0.01
5
3.32
1
1.783
0.1
2
1.42
1
1.682
Example 2.5
0.01
8
3.89
55
37.73
0.1
2
1.02
9
7.28
Example 2.6
0.01
11
2.29
7
3.28
2.6. Multi-Facility Location Problems
The
location problem
is to locate a facility, or facilities, to serve optimally a given
set of customers. The customers are given by their coordinates and demands.
Assuming
N
customers, the data of the problem is a set of points
A
=
n
and a corresponding set of positive weights (demands)
{
x
1
,
x
2
,...,
x
N
}
in
R
{w
1
,w
2
,...,w
N
}
.
2.6.1.
Fermat-Weber Location Problem
n
that minimizes
The
Fermat-Weber location problem
is to find a point
c
in
R
N
f
(
c
)=
w
i
c
−
x
i
,
(2.36)
i
=1
the sum of the weighted Euclidean distances between the customers
x
i
and the
facility
c
. The gradient of
f
N
w
i
c
−
x
i
c
−
x
i
∇
f
(
c
)=
(2.37)
i
=1
A point
c
∗
is optimal iff
0
∈
∂f
(
c
∗
), which reduces to
exists for all
c
∈A
.
f
(
c
∗
)=
0
if
f
is differentiable at
c
∗
. It follows from (2.37) that
c
∗
is a convex
combination of the points of
∇
A
,
N
c
∗
=
λ
i
(
c
∗
)
x
i
,
(2.38)
i
=1
with weights
w
i
c
−
x
i
−
1
λ
i
(
c
)=
.
(2.39)
j
=1
N
w
j
c
−
x
j
−
1
Search WWH ::
Custom Search