Figure 5E.1 Geometrical Arrangement for Primal-Dual Example.

Section 1.3. The line segments azA, a,B, and a,C correspond to so-called Simpson lines that intersect at X*

a. Using the observation of Rochat, Vecten, Fanguier, and Pilatte in Section 1.3, graph the equilateral triangle requested by Mr. Moss (the "Moss triangle").

b. By direct measurement verify that the altitude of the Moss triangle equals the sum of the lengths of the segments aX*, 2 *, and aX*.

c. Let the locations of the three trees be given by a, = (0,0), «2 = (16,0), anda, = (6.6250,7.4906). Then X* = (6.8149,4.5425)and W(X*) = 2.1391. Solve the associated dual problem (5.10) using a nonlinear programming algorithm and perform an analysis similar to that carried out in Example 5.1. Comment on the relationship between the direction vectors U, lA, and 1 and the Simpson lines.

5.2 a. Perform the analysis to arrive at problem (5.31) starting with problem

(5.27).

b. Show how to incorporate linear constraints into the development of Exercise 5.2a to arrive at problem (5.33).

5.3 Francis and Cabot (1972)

a. Consider problem (5.25). Show that C/2,J< Wj,, implies vtT = A, whereas X X*, implies C/2,J = H2„. (Hint: Consider the analysis demonstrated in the Appendix, mathematical note 5.2.)

b. Generalize the "line through each a,..." statement after Property 5.1 to the case of new facility locations X*; and X*, in problem (5.25). Justify the result.

5.4 Use a nonlinear programming algorithm to solve the constrained multi-facility location problem posed in Exercise 4.6, assuming Euclidean distances. Do this by solving a dual problem.

5.5 Verify that the quasilinearization implemented in equations (5.28) and (5.29) satisfies the requirements of mathematical note 5.1 in the Appendix.

REFERENCE NOTES

SECTION 5.1 An historical perspective on the dual problem is contained in Kuhn (1976). Using quasilinearization. Bellman (1965) implicitly gave a form to the single-facility Euclidean dual that is close to that of problem (5.10); however, the nonlinear constraints were written as equalities. This occurred because Bellman assumed away the discontinuities in the derivatives of the primal. The first formally published development of the single-facility Euclidean dual was given by Kuhn (1967). There Witzgall and Rockafellar are mentioned as having independently discovered the same dual [see Witzgall (1964)]. For general background on duality, the reader is referred to Geoffrion (1971) who provided an apphcations-oriented synthesis of duality in nonhnear programming.

SECTION 5.2 Francis and Cabot (1972) obtained and interpreted the multi-facility Euclidean dual, and a method for treating linear constraints was discussed.

SECTION 5.3 Love (1974) developed the constrained multi-facility S„ dual using quasilinearization. Juel and Love (1981a) formulated the linearly constrained dual with generalized distance norms using conjugate function theory as exposited by Witzgall (1964). A decomposition method tailored to solving the constrained Euclidean dual problem was described in Love and Kraemer (1973), and subsequently extended to distance problems by Love (1974). Another version of the decomposition method was given by Planchart and Hurter (1975) for mixed Euclidean, and rectangular distances.

APPENDIX-CHAPTER 5 Mathematical Notes

5.1 [Quasilinearization]. Let a = («,,0:2,.and /3 = (;3,, ,...,; be vectors whose components are real numbers. Denote the scalar prod-

uct 2 oLSk by otfi and denote [ ViY" by Let p > I and 1/p + \lq = 1. Then vvap = max a.

proof: [Beckenbach and Bellman (1965)]. Holders inequality can

be stated: ¨ hli>

Equality holds if and only if liSI" =

cajf, = l,...,K, where is a non-negative scalar. Thus, if fi/, has the

same sign as a, = l,...,Aand /3,=w (through a suitable choice of

c) we have a/J=X « 3 = ;, , as required.

In equation (5.3), where p = 2 and A" = 3 we have a, = (x, -a,,), «2 = (x2-a,2) and « = e, whereas /3, = u,, 1 2 = v, and / 3 = - z,. A geometrical perspective is gained by noting a;3=a2;32 cos 6, where is the angle between a and (representable as directed line segments in three-dimensional space). We have

max ai3 = max a2/32 cos 6. I¹ = vv, M2 = w,

The maximum is attained = 0°, which means /3 = ca for » 0. ( > 0 unless Wi = 0, an uninteresting case.) From equation (5.4) it is seen that = vv,/a2. The case a2 = 0 is avoided because «3 is always positive.

5.2 Prove Property 5.1

The optimal Lagrange multipliers for the equality constraints of problem (5.11) solve the primal problem (5.1).

proof: For the dual form given by problem (5.11), let the vector of multipliers for the two equality constraints be X = (x,,x2). To attain differentiability, let the inequality constraints be written < wj, where Uj = Let the vector of associated multipliers be X = ( ,7 2,...,1 „). The Lagrangian function to be used is:

, , ) = - , + ,+ Y ,{wj ~ Uj).

7-1 j-1 J=l

Applying the Karush-Kuhn-Tucker necessary conditions for problem (5.10) and setting / = 0 gives:

- Uj + X - 2TrjUj = 0 for j = l,...,n, (5A.1)

and setting dL/dX = 0 gives:

These conditions are also sufficient for problem (5.10). There are two cases to consider.

Case 1

All 7 * > 0. Then from condition (5A.3), \\UJ\\ = w, for all j- and from equation (5A.1), * = X-<a:J/2vv,. Upon substituting * into (5A.1) we have U* = wXX*-a)/\\X*-al Substituting the U* into equation (5A.2), yields the necessary and sufficient conditions for optimality in problem (5.1) when X* a,, for all j = \,...,n [see equation (2.3)].

Case 2

Some 1 * = 0. From equation (5A.1), X* = a,, and because no existing facilities coincide, > 0 for j r. From condition (5A.3), i7f w„ and \U*\ = w, for i r. The three conditions are satisfied with:

If LT < w,., this is equivalent to condition (2.4) holding with strict inequality.

S /, = 0.

(5A.2)

As dLjb-Kj » 0, X, » 0, and Trj{dL/dwj) = 0, it follows that:

wj - Uj 0, and Tjiwj - Uj) = 0. (5A.3)

chapter g

Site Generation Under the Minimax Criterion

In previous chapters the adopted criterion for optimal locations has been the minimization of a sum of distances multiphed by non-negative weights such as:

WMiX) = 22 ujUaj) +22 2 ( . ,).

I-I j-l /-I C-1+1

But a minimizer for WMiX) is also a minimizer for WMiX)/C where > 0. Let

= 2 2

/-11-\

+ 22

/-1 f-l+1

Then it becomes clear that minimizing WMiX) is equivalent to mini-mizirife the (weighted) average distance. This efficiency criterion is not appropriate if system performance is directly related to extreme distances. Consider the radio reception problem described by Brady and Rosenthal (1980).

Supposb a set of radio transmitters are located at points a„...,a„ and are broadcasting mutually incoherent signals with intensities /„...,/„. The problem is to choose the size and the site of a receiver with two considerations entering into the decision: first, the receiver should be as small (i.e., insensitive) as possible yet able to monitor every signal; second, the receivers location X must not fall within a previously specified (and arbitrarily configured) forbidden zone.... The rationale for the second consideration is obvious; the reasons for the first are cost, speed of construction, and possibly, vulnerability. By the inverse-square law, a signals intensity diminishes with the square of Euclidean distance as it leaves its source. Thus the