WCX) is a convex function of X. Hence, a local minimizer of ) is also a global minimizer. As with p = 2, we can check to see aforehand whether the new facility would be optimally located at the site of some existing facility. The following criterion, which generalizes Property 2.2, is derived in Juel and Love (1981b).

Property 2.7 [Minimum of W(X) at an existing facility location: 2,, distances]. W(X) is minimum at (a,„aj if and only if

CRP, = (l,,,!"/"-" + = w,, for p > 1, (2.18a)

max ( ,.,, RJ < w,, for p = 1, (2.18b)

where:

R =Y sign(a,., - a,)\a,, -

h ,; ) --Lforfe=l,2.

We observe that

dXL- t

X - .,, in (2.18a).

Terms on the left-hand side of inequality (2.18a) are not defined at p = 1. Using Property (ii) of 2„ distances and letting p decrease toward 1 so that p = pl{p-1) CO, we can easily deduce inequality (2.18b).

Example 2.6 Table 2.5 gives the parameters of the problem with n = 5 together with the point optimality calculations for p = 1, 1.3, 1.5, 2, and 5. We see that (x-T,x?) = (7,3) for p = 1 and p = 1.3; actually this point is optimal for p 1.385.

It is convenient at this point to introduce a hyperbolic (see Exercise 2.11) approximation to W(X) in problem (2.17). This approximation will

Table 2.5 Evaluation of CRP,.

be especially useful in the more complex multi-facility location problem discussed in a later chapter. We replace each absolute term \y\in problem (2.17) by (y + ( where e is a small positive number. The approximation is always larger than the original term, but approaches the original term gSf-tO. Problem (2.17) is then approximated by:

minimize WH(X) = w,(((jc, - + X

+ ax2 - ajy + yyi".

(2.19)

We first note that WH{X) is strictly convex (as proved on a do-it-yourself basis in Exercise 2.12), and that all orders of derivatives are continuous at all points (as will become apparent shortly). Therefore, WH{X) is a well-behaved candidate for general nonlinear descent and programming algorithms that converge to the minimizer if the function is smooth and strictly unimodal.

The question arises: If we find the location that minimizes WH{X), what progress have we made in minimizing W{Xf> We will show that we can come as close as we wish to minimizing W(X) by minimizing WHtJC) and simply choosing small values for 6.

Property 2.8 [Maximum difference between WH{X) and W(X)\.

max {WH{X) - W{X)\ X

( ) = 1\ Wj) (2.20)

proof: It is shown in the Appendix, mathematical note 2.4, that:

(((X, - a,,y + + {{x, - aj,y + - " - (x, - a.l" + \X2 - ajf)"" 2/ /2,

from which the property follows.

(2.21)

As the difference between WH{X) and W{X) never exceeds A{e), solving problem (2.19) will give us a solution to problem (2.17) that is at most (£) from the optimum value. To see this, let be a minimizer for ) and X** be the minimizer for WH{X). Because WH{X*) - W{X*) (ˆ) and WHiX**) < WH(A), we have WH(X**) - W{X*) < («). Therefore, W{X**) - WiX*) < («).

The Weiszfeld procedure discussed in Section 2.2 can be generalized to the distance case. Differentiating WH{X) with respect to x, and Xj,

setting the partial derivatives to zero, and then "isolating" x, and on the left-hand side (the details are requested in Exercise 2.13), we obtain:

(2.22)

where

d(X,a,) = (((x, - a.y + «)"/2 + ((X, - ,2 + ( -" and d"{x„a,,) = ((x, - a,,y + e)-V

When p = 2 and e = 0, iterative procedure (2.22) is identical to procedure (2.6). Convergence is guaranteed for I < p < 2, provided e > 0. Actually, the procedure will work well with t = 0. However, setting e to a very small quantity (relative to the weights and computer resolution of zero) does protect one against the embarrassing possibility of dividing by zero on a computer. This occurs in procedure (2.6) when X coincides with an existing facility location, or in procedure (2.22) when xif* coincides with even one coordinate a,( of an existing facility location. It is possible to inadvertently choose a starting point that falls in that category, or it is possible that X will move too close to an existing facility location during iteration. In a slow convergence problem, a large initial value of e may get us to the vicinity of an optimum solution relatively quickly. Then a smaller value can be used. However, the use of «> 0 is a practical necessity for Weiszfeld iterations only in the multi-facility case that is discussed in Chapter 4.

2.3 THE £, DISTANCE PROBLEM Table 2.6b Iterations with p = 1.5 and e = 0.01.

Example 2.7 Table 2.6 illustrates the iteration method [initiated using equation (2.7)] on the single-facility location problem with data given in Table 2.5. The bound Lfi<« and the Sf that were calculated are those defined in equations (2.8) and (2.9); LB¹> and S¹ were calculated by the same expressions, but using WH(X) instead of W(X). We observe that using £ = 0.01 speeded up convergence as measured by 5 < or by movement in {xff,xff), although using e = 0 gave a better value of W{X) at each iteration.

EXERCISES

2.1 Consider the sum /(x,,x,), where each /(X,X2) is convex. Using the def-

initiori of convexity given in the Appendix, mathematical note 2.1, prove that the sum is also convex.

2.2 The Varignon frame is a mechanical analog for the minimization of iV(X) in problem (2.2). It consists of a board with holes drilled in it to correspond to fixed fafcility locations. A string is passed through each hole J, and the ends are tied together in a knot on top of the board. Under the board a weight is attached to each string, and the weight on string j is proportional to w, in problem (2.2). In the absence of friction and tangled strings, the knot will come to rest at the optimum new facility location. This analog has been used in actual location studies. The analog can be analyzed in terms of forces acting to move the knot. Assume that the knot is in equilibrium. In Figure 2E.1 the weight w, for example, acts with a force 4, which can be broken up into the orthogonal components vc and w,, where:

vvv4 = W4 COS S4 and w,.i -- sin 4.

INTRODUCTION TO SINGLE-FACILITY LOCATION

EXERCISES

Figure 2E.1 Varignon Frame.

Note that wl = wu + wl.

a. Show that:

where (xx,) is the equilibrium position.

b. Show that a balance of x-direction force components and a balance of j;-direction force components is, in general, equivalent to conditions (2.3).

c. Explain condition (2.4) in terms of forces. If condition (2.4) holds for point (3,1,3,2), what would be observed on the Varignon frame?

2.3 Show that ) = Wj(e2(X,a)Y is strictly convex. (Hint: Since the second

partial derivatives of Ware continuous everywhere, showing strict convexity is equivalent to showing that the Hessian matrix is positive definite everywhere; see Exercise 2.12.)

2.4 Write a computer program to perform the iterations described by procedure (2.6). The program should calculate the lower bound L5"> and stop when S" is below a predetermined value. Use the program to recalculate Table 2.3 for the cases where:

a. w, = 10.0, using equation (2.7) to define the starting point,

b. w, = 4.9, using equation (2.7) to define the starting point,

c. iv, = 4.9, using the starting point *» = (0.99,4.01).

2.5 a. Show that X<> in procedure (2.6) will always fall in Q, the convex hull of

of the existing facility locations. (Hint: This is equivalent to showing that

X"> can be written as a weighted sum of the as with positive weights that sum to one.)

b. Show that X* in problem (2.2) is in . (Hint: If # a„ for any j then use conditions (2.3)).

2.6 Apply Property 2.7 to the problem in Example 2.1. Then calculate (Jf") based on (X»>) = (0,0) using procedure (2.22) with e = 0.

2.7 Using the definition of convexity given in the Appendix, mathematical note 2.1, prove that fV(x) = \ - a is a convex function for any real positive w and any real a. (Hint: For any real numbers p and 9, p + < p + .)

2.8 Derive equation (2.14).

2.9 A facility is to be located on a shop floor where travel is possible only along aisles that are perpendicular to each other. Deliveries will have to be made to two "demand points" located (using rectangular axes corresponding to the directions of the aisles) at (1,1) and (3,2). The weights for the demand points were estimated to be equal (thus taken to be 1 and 1, respectively). Problem (2.10) is to be used as the location model.

a. On a graph showing the locations of the demand points, draw the equal-cost contour where ), the total cost, is equal to 5. (Hint: Divide the XX, plane into regions such that ) can be described in each without using absolute values.)

b. Plot the contour W{X) = 3.

c. Plot the contour W(X) = 1.

2.10 Jack Smooth, an industrial sales and service representative, wants to find a new office location. His business involves several trips a week to seven factories in a large suburban area. From a travel expense diary, he has made up some averages based on several months experience. He has marked the location of each plant on a map and, using the left and bottom borders of the map as coordinate axes, has given a location to each plant. This information is compiled in Table 2E.1. Jack Smooths objective is to find an office location that minimizes total travel distance. He considers rectangular

Table 2E.1 Average Trips and Locations of Customers.

Customer

Average Number of Weekly Trips

Location