Consider the single-facility rectangular distance criterion function given ( ) = max {Wj(\x, - al + - aj2\),J = l,...,n\- Contours oiM{X) are defined by the set:

S(Xo) =\X= (x„X2) I M{X) = Xo).

Let:

5,(Xo) = min i(Xo/w,) + + aj2, j =

52(4)) = max {(-Xo/w,) 4- a, -f a, j = \,...,n\,

5 (4) = min \(Xo/w) - aj, -H a2,7 = 1,..-, , and

54(Xo) = max K-Xo/w,) - a,, 4- a,2,j = !,...,«!.

Then the set 5(xo) is comprised of the sides of a (possibly degenerate) rectangle with comers at i/2(.J,(Xo) - s,{x\ + 5 ( )), /2(s,(xo) -

S,{Xq), 5,(Xo) + S,(X,)), /2(52(Xo) - 54(4), 2(4) + 54(Xo)), and l/2(S2(Xo) -3(4), 2(4) + 5 ( )).

In Example 6.3, the contour for = 4.5 should correspond to the degenerate rectangle given by the line segment between (6.0,3.5) and (5.0,2.5). Indeed, we find that 5,(4.5) = 9.5, 2(4.5) = 7.5, s,(4.5) = -2.5, and 54(4.5) = -2.5, which means the comers of the rectangle are at (6.0,3.5), (6.0,3.5), (5.0,2.5), and (5.0,2.5), respectively.

A Convex Programming Approach

Let us return to formulation (6.3b). The functions in the brackets are convex, as they are compositions of increasing convex functions of convex functions, ie, „ ) and [jPXXJ]", respectively. As mentioned, these composite functions are everywhere differentiable for p > 1. Together with the linear objective function this formulation represents a differentiable convex programming problem. These facts guarantee that standard convex programming algorithms will converge to an optimum solution.

Limitations on interfacility distances can be included as:

«5 - + 12,-«2/] > 0 and/or

- [\xu-x,!f + \X2-X2)f] > 0,

where a,j and are the bounds on the respective jP distances. The addends introduced in equation (6.1) are easily accommodated within this convex programming approach. With the increasing availability of convenient computer codes for nonlinear programming for use even on personal computers,this general approach to 4, distance problems will likely gain practical appeal.

Maximin Location

Let fiX) = vam{Wi£2iX,aX j = !,...,«). Then, / measures the least Euclidean distance from the new facility to an existing facility. An example of location under the maximin criterion is:

maximize f{X), XeF

(6.20)

where F {X\e2(X,a) a„ j = 1,..., . The constraints that make up F impose mandatory closeness requirements. We note that some of the existing facility locations may be dummy points to produce a desired geometrical shape for F. This model might be appropriate when locating an "obnoxious" facility.

Let C(xo) - {X- (x„X2) I fiX) Xo.

Then C(Xo) can be realized graphically by constructing a circle with radius Xo/w, about each existing facility, and then considering the region that is outside all these circles simultaneously.

Example 6.4 To illustrate, consider Table 6.3, which gives data from Drezner and WesolowskyJ 1980c) for three existing facilities. Figure 6.6 shows the intersection of C(xo) and for Xo = 3 as the two darkly shaded areas. The solid circle about each existing facility represents the associated mandatory closeness constraint; the lightly shaded region is F. The dotted circles have radius Xq/Wj = 3/Wj. As Xo is increased, the two darkly shaded areas will shrink until X* = (-0.94425,0.66550) emerges as the only point in the intersection of C(Xo) and F.

Let fiX*) = J* denote the optimal value in problem (6.20). Then the following property is self-evident.

Property 6.5 [Relating/* to x„]. If for a given value of Xg, C(xJ and F do not intersect, then f* < Xj,; otherwise, f* > Xq.

This suggests an interactive graphics bisection search procedure to solve problem (6.20). Color graphics capability would enhance the appeal of this approach.

Table 6.3 Locations, Weights, and Maximum Distances.

1:31

Figure 6.6 Illustration of the Intersection of C(3) and F.

(Figure from "A Maximin Location Problem with Maximum Distance Constraints" by Z. Drezner and G. Wesolowsky, AIIE Transactions, vol. 12, no. 3. Copyright Institute of Industrial Engineers, 25 Technology Park/Atlanta. Norcross, GA 30092.)

Drezner-Wesolowsky Algorithm

Step 0 Choose « > 0, establish LB = /„,„ and UB = f„ and determine if problem (6.20) is feasible (see below). Display the sets C,(aj) = {X\ £ { , ) aj,7 = \,...,n graphically and determine their intersection, which is F.

Step 1 Set Xo = (UB+LB)/2. If UB-LB < e, terminate.

Step 2 Otherwise, display the sets C/Xq) = {X \ !1 { , ]) xjw}, j = graphically and determine C(Xo) as the area outside the union of these sets. The user observes whether or not C(xo) and F intersect. If not, set UB = Xo; otherwise, set LB = Xq. Return to Step 1.

Some detail is needed to implement Step 0. To find a point in the feasible region F, consider solving the minimax problem of minimizing M{X) given by equation (6.1) where w, = l/aj. We could use the Lawson-

Charalambous algorithm for this. Let X solve this problem. If, ( < 1, then £2{ , ) aj, for all J = l,...,n and so XeF. Otherwise, problem (6.20) is infeasible, and the Uj bounds must be reconsidered. We have found an unexpected use of the minimax model!

Suppose MiXO !• Then we can use LB = = /(X«) in Step 0 of the algorithm. To value f„,„ we compute:

fmv = min{w,(a + £2ia„a)), i j = !,...,«).

To justify the calculation of /„„, consider the requirement that for feasibility each pair of sets C,(a,) and Cja) must have a nonempty intersection. The farthest point from a, that is within C/a) can be no further away than £2ia„aj) + a, or the intersection wouldnt be possible.

Hence, the computer provides and f. The human user provides recognition skills in Step 2. With the benefit of human pattern recognition, F could actually be of general shape-not restricted to the intersection of circles. A verification step could be added to the algorithm to assure "infallibility," much like that discussed for the interactive graphics minimax algorithm.

EXERCISES

6.1 Use rectangular distances and solve the problem given in Example 6.1 as a linear programming problem using formulation (6.17).

6.2 Show the calculations to verify that = 3.9101 and Xo = 3.2076 after one iteration of the Lawson-Charalambous algorithm applied to Example 6.1, as reported in Table 6.1.

6.3 a. Use rectangular distances and solve Example 6.2 using formulation (6.17).

b. Repeat Exercise 6.3a using formulation (6.19) instead of formulation (6.17)\

c. Provide a graphic exposition as was done in Figure 6.3.

6.4 Prove that h{x) = njx - a\" is everywhere differentiable for /? > 1, where w > 0 and a are given constants.

6.5 Dearing and Francis (1974) The transformation ( „ 2) = (x, + Xj, -x, + ) = (x;,x;), say, both rotates the coordinate axes counterclockwise through a 45° angle and expands the axes.

a. Showthatx, -a,-l-x2-a,! = max(x; -al, ; - . You will have shown that £,{X,a) = £„{X,a) where X and a are points in the plane, and X and a are the images of those points under T, respectively. (Figure 10.1 motivates this idea.)

b. Exercise 6.5a enables the following formulation of the constrained multi-facility rectangular distance problem with addends:

minimize Za subject to

Zo * w,,, max(x;,-a;,, \x\2-a,j) + g,

Zo > - ,, max(x;,-x;,, [x-KiD max(x„-fl;,, ;,- ;4) < a, max(x;,-X,, x;,-X2) < A,

/ = \,...,m;j = \,...,n l,...,w-1; r = i+i,...,m i = l,...,m;J =

/ = I; r = i + l,...,m.

Show how this problem can be solved by solving two independent linear programming problems, one in the variables z„ x,„ xU, and the other in the variables Zj, xa, x,..

c. Use rectangular distances and solve Example 6.1 using the approach in Exercise 6.5b.

d. Use rectangular distances and solve Example 6.2 using the approach in Exercise 6.5b.

6.6 Chatelon, Heam, and Lowe (1978) Two ships are to be stationed in the Caribbean sea "and must be ready to intervene, in case of trouble at any one of nine given cities of the Caribbean Islands." Need for assistance occurs with estimated probabilities that are the weights (scaled). The Euclidean distance between the two ships is to have weight 1, reflecting the need for the two ships to communicate.

Parameters for the problem are given in Table 6E.1, The value for the &„ distance between ship / and city j is denoted The differing p-values

Table 6E.1 Caribbean Islands Problem.

Source: Chatelon, Heam and Lowe, 1978. Mathematical Programming, Amslerdam, North Holland.

represent anticipated indirect paths that must be taken by the ships to avoid land masses.

6.6 a. Use a nonlinear programming software package and the convex pro-

gramming approach based on problem (6.3b) in the text to locate the two ships under the minimax criterion. Verify that xt = 26.0836, with = (13.817,24.358) and * = (25.818,22.454). b. Obtain the optimal values of the dual variables for this problem and give their interpretation here.

6.7 B. Write a computer program to implement the Lawson-Charalambous al-

gorithm for single-facility problems. Use the algorithm to locate ship 1 in Table 6E.1, letting all p = 2 and ignoring the distance to ship 2. Verify that = (15.19,21.77). b. Let a, = (0,1), a. = (1,0), a, = (0,-1), and a, = („ ). Use the algorithm to solve the single-facility problem with all = 1, e = 10-", and a„ = -I.O, -0.99, and -0.9999, successively. Comment on the results.

6.8 a. Retracing the developmental steps, attempt to generalize the single-fa-

ciUty Lawson-Charalambous algorithm to three-dimensional problems. Describe a practical application.

b. Retracing the developmental steps, attempt to generalize the single-facility Lawson-Charalambous algorithm to accommodate addends.

c. Attempt to generalize the single-facility Lawson-Charalambous algorithm to the case of £„ distances.

6.9 a. Verify that the lower bound on Xo in problem (6.18) is attained for (Xi.Xj)

= /2(W3 - W4, - W3 - W4 -I- w,). Show that this is a feasible solution, b. State the dual of problem (6.18). Then consider all possible basic feasible solutions for the dual and show that an optimal basic solution has value W5/2. Derive an optimal primal solution from an optimal dual solution.

6.10 Using the data from Example 6.3, graph the contours 5(4), S(6), and 5(8), as defined in Section 6.3. Give a practical example of the use of such contours.

6.11 Francis and White (1974) Write the constraints of problem (6.17) in the text for the single-facility case, as: