2.11 a. Graph the function = -\x - x„\ where a and b are positive. Then overlay the graph of the hyperbola whose equation is:

y ( - - x,y

= 1.

b. Relate a to the vertical distance between the graphs at x = „.

c. Discard the lower branch of the hyperbola. Solve for and comment on the result in relation to its use in problem (2.19) in the text.

2.12 Prove that IVH{X} in problem (2.19) is strictly convex. Hint: First prove thatgixx.) = (((x, - a„y- + + ((x. - + e)")* is strictly convex by showing that for all X = ( ,, 2 .

> 0

> 0.

2.13 Derive iterative procedure (2.22) from the extremal conditions (partial derivatives set equal to zero) for W1I(X).

2.14 Consider the problem data Table 2E.1 in Exercise 2.10.

a. Check each plant location for candidacy as the optimal office location, assuming g„ distances first with = 1, and then with p = 1.5.

b. Use any available computer package for nonlinear optimization to find the optimum location for jP„ distances with p= 1.1, 1.5, 2, and 5.

c. Write a computer program to perform the Weiszfeld iteration procedure (2.22), and repeat Exercise 2,14b.

d. Write the additional coding for the program written in Exercise 2.14c to begin by testing for optimality at the existing facility locations. Repeat Exercise 2.14b.

APPENDIX-CHAPTER 2 2.15 a. Prove that:

where:

X% = ( , ? ) is an optimum location for the rectangular distance problem with WiiXi) as defined in problem (2.12); and XJ = (xTt,X2i) is an optimum location for the jP,, distance problem with WJiX) representing W{X) in problem (2.17). (Hint: Consider the Minkowski inequality stated in the Appendix, mathematical note 2.3.)

b. Apply the above result to Example 2.6 with p = 1.3.

REFERENCE NOTES

SECTION 2.1 The Weiszfeld procedure appeared in a paper by "Weiszfeld" (1937). It should be noted that it is one of the methods for iteratively solving nonlinear equations that appear in numerical analysis texts (eg, Dahlquist and Bj6rck (1974), Chapter 6). Convergence properties have been discussed by, among others, Katz (1969, 1974), Kuhn (1973), and Ostresh (1978). The stopping criterion presented in this section is one of those given by Love and Yeong (1981). A somewhat tighter lower bound was given by Elzinga and Heam (1983) and Juel (1984); Love and Dowling (1986) generalized Drezners rectangular bound to the jP, distance case.

SECTION 2.2 Some of the foundation work with rectangular distances includes that by Bindschedler and Moore (1961) and Francis (1963). The single-facility problem is closely related to the problem of finding a weighted median of a data set, as was seen in Example 2.5. Algorithms that can solve such problems in 0(n) time are available.

SECTION 2.3 The hyperbolic approximation used here is from Wesolowsky and Love (1972. Eyster, White, and Wierwille (1973) used a hyperboloid approximation procedure (HAP) to extend the original Weiszfeld procedure to both Euclidean and rectangular distances. Convergence properties including the extension to distances have been discussed by Morris and Verdini (1979) and Morris (1981). An acceleration of the HAP procedure is discussed by Charalambous (1985).

APPENDIX-CHAPTER 2 Mathematical Notes 2.1 Prove Property 2.1

/(x, - a,-,y + - ,2 is convex.

distances to be the best representations of the actual travel distances involved.

a. Solve Jack Smooths office location problem,

b. Show that conditions (2.15) are satisfied at the optimal location.

c. Plot WXx,) against x,.

W(X) = 2 vv/fx, - a,,y + (X2 - a,2F) occurs at a,, if, and only if, CR, < w,..

proof: Consider a movement of the new facility from ( :,) a distance t to (x, -I- td„ Xj + td), where {d\ + diy = 1. Here d and ?2 are components of a unit direction vector d. Let us find the rate of change of W{X+td) with respect to as / approaches zero when X = a,:

HX(a,. + td, - aj,)d, + (a,2 + td - 0,2)2 ((a,, -H /, - a,,) -H {a,2 + td2 -

wltd\ - fag)

-I- td, - 0,1)

((a,, + td, - a,,y + (a,2 + 2 - «,2))"

"4 ((a,, + fJ, - ajy + (a,2 + td2 - ,2

We can write this derivative as:

= + 2)- + u,/?,(0 + d2R2{t), dt

where ,(0 and /2(0 are defined as implied above. Therefore,

dW dt

= wid\ -H )/ - ?,/?, - 22

= w, -I- ?,/ , -I- 2-2,

We can use elementary calculus and the condition d} + dl = I to find that the minimum of:

dW dt

occurs at:

{R] + Riy- {R] + Riy dW

and so min , o = - {R] + R\

When this derivative is positive, W{X) will increase as {x„x is moved in any direction from (a,„ar2)- Since W{X) is convex, X = («,„02) if, and only if, w, {R\ + Riy = CR„ as required.

2.3 Prove Property 2.6

w/ilX,aj) = w,(\pc, - a,,!" + \X2 - asl")"" is convex.

proof: Following note 2.1 we can equivalently prove that/(j,,j2) °= (IVil" + ")"" is convex. We will appeal to a well-known (to math-

proof: As w, is a positive constant we can, without loss of generality, let Wj = 1. As Uj, and are constants, we can equivalently prove that /(j/bj,) = + !)" is convex. This merely changes the coordinate system to one with an origin at ( ,, 2)- Recall that /( „ 2) is said to be convex if, given any two points, iyyi) and (ylyi),

/ „ 2) + (1 - xXyUyD) < ViyUyd + (1 - \)/( 1 1) where 0 < X < 1.

Therefore, the convexity requirement is:

((\y[ + (1 - x)y;y + (xyi, + (1 -

< { [ + (ym + (1 - x){(y;r + ( ; .

To show that this must be true, we turn to what is known as the triangle inequality for vectors. For two real-valued vectors p = ( ) and q = (<?„2),

(iPi + Q,y + {P2 + q2yy < (Pf + Piy + {qj + qiy\

If we set p, = Xy\, p = Xy., , = (1 - X)y{, and 2 = (1 - XM,

we see that this is equivalent to our requirement.

2.2 Prove Property 2.2 The minimum of:

ematicians, at least), inequality called the Minkowski inequality, given by:

where p 1 and and /3 are real numbers. We have/(X7; + (1 - \)y[, + {\ ~ \) ?)

< +1(1 - W[\y + (Ml

+ 1(1 - \)y2\fY" (triangle inequality)

+(1 - \)y"}(Y (Minkowski inequality)

= KW + + (1 - )( + W

= / ;, 2) + (1 - X)/(X,>2), as required.

2.4 Prove X„(X,a) - Wa,) < 2" e where

;, ,) = (((x, - a„y + 6)"/ + ((x - 0,2) + £>")"".

proof: Let y, = x, - ,\ 0, yj = x, - aJ 0 and = e/ > 0. Then:

L„{X,a} = [( + + iyl + yiyV"

< [{{y, + + (02 + ]""

(Minkowski inequality; see note 2.3) = [x, - a,,!" + X2 - ai"]" + { + V" = ll,{X,a;) + 2/e/2, as required.

2.5 Prove [Rectangular bound on W{X*)l W{X*) Rm

= min 2! 7 l-i - + niin ""j k2 - «72!, x, x2

where ( ) is defined in problem (2.2) in the text while

= - a,]IU%a,y and

Wj = wJa-S - ,2/-?2(, ,).

proof: We may write the following inequality:

\k, - aj\ [ « - a„ + X2 - a,2 W - %l

[x, - a„p + 2 - ,2 ]"[ « - fl„P + - a,2p]" (since m-v < v; Schwartz inequality)

or equivalently,

UX,a) [ « - a,,/i2(«,fl,.)]x, - a„

+ [ - afl\IUX\a,)]\x2 - fl,2.

Multiplying both sides by Wj, summing over j and then taking the min on both sides with respect to X yields the required result.

(Note: The bound R(X) is due to Drezner (1984). The solution " at each iteration of the Weiszfeld procedure is used to compute the weights wj and wj that are used in calculating RXy While it may appear that adding another optimization problem and solving it at each iteration has increased the work required to find a lower bound, this approach has several advantages. Using techniques from Section 2.2, each part of the optimization involved in calculating /?(X«) can be accomplished rapidly. Also, it is not necessary to find the hull points that are used in Property 2.4.)