where the s notation is from the discussion of contours in Section 6.3. Consider the rectangle defined by these constraints.

a. Show that the corners of the rectangle are as given in the text.

b. Show that in the case of addends [see equation (6.1)] the expressions for s,(Xo), r = 1,2,3,4, are as before, except that x„ is replaced by {Xg-gj).

6.12 a. Solve Example 6.3 using Euclidean distances and the Elzinga-Hearn

graphic algorithm.

b. Sketch two contours for the problem.

c. Solve Example 6.3 using Euclidean distances and formulation (6.4) with the constraint x, + Xj 5.

d. Attempt to generalize formulation (6.4) to accommodate a fixed addition g, to each Euclidean distance.

e. Attempt to generalize formulation (6.4) to three-dimensional problems.

f. Attempt to generalize formulation (6.4) to weighted problems.

g. Attempt to generalize formulation (6.4) to unweighted multi-facility problems.

6.13 The one-dimensional, single-facility case of problem (6.19) is given by the linear programming problem;

maximize a,{Vj, - v,)

7= I

subject to

(6E.1)

S v„ - v,2 = 0

S (v„ + vj/w = 1

Vj„vj2 > 0 7 = l,...,n.

a. Show that problem (6E.1) reduces to finding max{vf, u-Ja, - a/(w+w,), g r = l,...,n!, where a, is the coordinate of existing facility J on the line. (Hint: As there are only two constraints, there will be two basic variables in an optimal basic feasible solution.)

b. Using primal-dual cotnplementary slackness conditions, show that this means X* = (a„.w,. -I- a,,w,.)/{w. + ,,), where * indicates optimality.

6.14 Kolen (1986) Consider the minimization of:

M{X) = max{w,(\x,-a„\ + Ix-a.D+gjJ = 1,...,«. (6E.2)

From Exercise 6.5 we know that minimizing M(X) given by equation (6E.2) is equivalent to:

minimize Zo subject to

Zo > w,(max\\x[-a„\, [x-a) + j = \,...,n.

a. Show that this means we can minimize M{X) given by equation (6E.2) by solving two (k = 1,2) independent, one-dimensional problems of the form:

minimize z,

subject to (6E.3)

x[ + zjwj > aj, + gJWj -xl -f- zjw, -a,, + gjw, j = \,...,n.

b. Using insight from Exercise 6.13, show that problem (6E.3) can be written as:

zf = max jw,n/,(a;-a; + gJw, -I- wM-f-w,), q r = l,...,n\.

6.15 Suppose Example 6.3 represents an ambulance base location problem and the existing facilities are centers of response neighborhoods. Use the result developed in Exercise 6.14 (or a straightforward linear programming approach) to locate the base. Assume that multiplying 0.95 times distances closely approximates actual travel distances. Also assume that all medical service is performed at a hospital located at (5,2.5).

6.16 Spath (1978)

a. Develop the three-dimensional analog of formulation (6.18).

b. Consider six existing facilities with locations given by (0,0,0), (0,0,1), (2,1,3), (4,0,0), (0,2,0), and (3,2,0). Then verify that the optimal solution sets for the problems with the first 3, 4, 5, and then all 6 of the points are given by:

= 3 0<xT=s2, 0<xf<l, 0< 2(xt -t- xf) < 5, x* + xt + x* = 3, x? = 3 - n = 4 X* = 2, x? = 1 - -rf, 1 2x; < 2, X? = 3

(xf,x?,x?) = /4(7,3,1), X* = 13/4.

« = 5

= 6

. Describe a practical application for this problem.

6.17 Considen Example 6.4.

a. Illustrate the intersection of the sets C(4) and F using the shading conventions adopted in Figure 6.6.

b. Compute /,„„ and

c. Perform one iteration of the associated interactive graphics algorithm.

d. Verify (graphically) that X* = (-0.94425,0.66550).

REFERENCE NOTES

SECTION 6.1 The quadratic programming formulation is from Nair and Chandrasekaran (1971), as is the previous discussion centered on Figure 6.2. A dual

quadratic program was given in Elzinga and Hearn (1972a). The Elzinga-Heam algorithm for unweighted problems was introduced in Elzinga and Heam (1972b). Heam and Vijay (1982) provided a computational study and classification scheme for algorithms that solve the Euclidean single-facility problem. They extended the Elzinga-Heam algorithm to weighted problems, and their computational study, which includes starting-point generators, shows this to be the most efficient among the competitors considered.

The interactive computer graphics approach is fi-om Brady and Rosenthal (1980) and Brady, Rosenthal and Young (1983). Lawson (1965) gave an algorithm that successively approximates the dual variables for the unweighted single-facility Euclidean problem, in the applications context of "multiple airborne target tracking with a ground-based radar." The discussion here and in the Appendix follows that of Charalambous (1981), who provided a generalization to weighted, multi-facility Euclidean problems. Convergence and the generalization to distances were discussed in Morris (1982).

SECTION 6.2 Francis (1967) provided eariy results for rectangular distances. The closed-form result for problem (6.18) is from Francis (1972) and Elzinga and Heam (1972b). Wesolowsky (1972) provided an early linear programming formulation, and Elzinga and Hearn (1973) and Morris (1973) studied the linear programming approach further. Dearing and Francis (1974) offered a network flow approach.

SECTION 6.3 Convex programming approaches were suggested in Love, Wesolowsky, and Kraemer (1973) and Chatelon, Heam, and Lowe (1978). Drezner and Wesolowsky (1978b) developed a numerical analytic approach. The discussion of the maximin problem is from Drezner and Wesolowsky (1980c) who described implementation of the algorithm in algebraic terms.

APPENDIX-CHAPTER 6

Mathematical Notes

6.1 problem (6.10)

When m > 1, the analytical solution of problem (6.10) can be conveniently stated in matrix form. Setting

= 1,2; i = l,...,m, to zero and rearranging produces the system of equations:

= 1,2; / = \,...,m. Now, define m X 1 column vectors x,, and ,, as

Let , = Z i> + Z 20- then define the mXm matrix A

l-[ r-l

given by:

/3, -W2,2 .- -W2,„,

- w,,,., -Wr

Then the system of equations can be expressed as: Ax = flb = 1,2.

(6A.1)

If /3, = 0, then the (•• row of A, the " column of A, and the element of both a, and are all equal to zero and should be removed before solving for x, and Xj. The location of the facility is not unique in this case. The matrix A is positive semidefinite and symmetric.

6.2 Prove Xo = xJ in Step 2 of the Lawson-Charalambous algorithm

proof: We have xJ = min MM(X) =

m n >ii-l m

X =1 J-l i-i •=,+ 1

[as v!+> and u*+> satisfy equation (6.13)]

min(X Z WuA{X„a,)

/=1 /-=1+1

[from the definition of MM(X)]

m n ;-l y-l

[from equation (6.14) which indicates is a minimizer]

= Xo.

Chapter

Site-Generating

Location-Allocation

Models

Heretofore we have been concerned with location models where the flows between the new facilities and the existing facilities are given. However, in situations where there is more than one new facility to be located, determining the flows is often part of the problem. Figure 7.1 shows 19 demand locations over a geographical area. Each of these locations has a requirement, which is the associated decimal number. The numbers could be tonnage to be shipped, sales dollars, or simply units demanded. It is only important that all numbers be in a common unit and that it is possible to calculate shipping cost per unit requirement per unit distance. Figure 7.2 shows one possible solution to the problem of locating three distribution centers. The indicated allocations are arbitrary, but the locations of the centers (marked by crosses) minimize the sums of weighted distances with respect to the allocations. When the distances are rectangular and in kilometers, and the requirements are in tons, the total weighted-distance cost for this solution is 17,389 ton-kilometers. Figure 7.3 shows the optimal solution, which has a cost of 15,203 ton-kilometerj.

The number of new facihties may also be part of the problem. The cost of adding a new facility must then be balanced against the transportation cost saved by utilizing that new facility. In this chapter, we develop techniques for addressing this general problem.

We first consider the location-allocation problem when the number of new facilities is known. The structure of this problem may be characterized by a set of existing facility locations Uj and their known requirements, Wj > 0,7 = I,The problem is to determine the optimal location for each of the m new facilities and the optimal allocation of existing facility requirements to the new facilities so that all requirements are satisfied.