rectangular distances may adequately approximate actual travel distances. In this case the Xq-distance sets become:

) = \X= (x„X2) I w,-[x,-a,, + \K,-aj2 < Xo).

Figure 6.4 illustrates the intersection set C(Xo) for Xq = 5. It is unlikely that C(xJ) will contain only a single point because the sides of the C/Xq) sets are parallel. This means problem (6.3) will typically have multiple optima when distances are rectangular, even in the single-facility case.

The interactive graphics method of the previous section is directly applicable here, with diamond-shaped C/xq) sets replacing the circular shapes. However, the Lawson-Charalambous algorithm is replaced by a linear programming approach when distances are rectangular.

A Linear Programming Representation

The following property enables a linear programming formulation. Figure 6.4 Graphic Analysis with Rectangular Distances.

Property 6.4 [Transformation of absolute value constraints]. The inequality:

Xo » w,„ [\x„ - a„\ + x,2 - a,2] is equivalent to the following quadruple of inequalities: Xo » vv,„ [ (x„ - a„) + (x,2 - a,2)] 0 wu, [-(X,, - „) -I- (x,2 - a,2)] Xo wuj [ (x„ - „) - (x,2 - aj2)] Xq » w,ij [-(x„ - a„) - (x,2 - aJ].

(6.15)

(6.16)

The equivalence follows because at least one constraint in inequalities (6.16) is equivalent to that in inequality (6.15), and the greatest lower bound on Xq in inequalities (6.16) must equal the lower bound on Xq in inequality (6.15). (The -dimensional extension of inequality (6.15) can be replaced by an analogous set of 2 inequahties.) Problem (6.3), for location in the plane using rectangular distances, can now be written as the following linear program:

minimize Xo

Xo,X

subject to

(6.17)

x,i + x,2 + Xo/w„j » aji + 0,2 - X,-, -H x,2 -H Xo/Wuj -aji -H aj2

X„ - X,2 + Xo/W„

a,, - a,-

- Xi - x,2 + Xq/Wuj -aj - 0,2 i = l,...,m;j = l,...,n

x,i - X,, + x,2 - x,2 + X0/W2,, » 0

- X, -I- Xh -I- X,2 - X,2 + X0/W21, » 0 X,i - Xh - X,2 -H X,2 + Xo/W2,> » 0

- X„ -I- Xri - X,2 + X,2 + X0/W2,, = 0

i = l,...,w-1; r = +1,..., .

Constraints corresponding to zero weights are to be omitted; variables are unrestricted in sign. Problem (6.17) has 4mn + 2{m - m) constraints

and 2m + I variables when all weights are positive. If all a,i, > 0, then all xfl, 2 will be non-negative and problem (6.17) could be augmented with non-negativity conditions, is a weighted distance and therefore must be non-negative. (An alternative approach decomposes the original problem into two relatively small independent linear programs; this is the subject of Exercise 6.5.)

Unweighted Single-Facility Problems

The single-facility problem can be solved in closed form when all weights are equal. In this case the second set of constraints is absent and the problem reduces to:

minimize Xo

Xo,X 1 ,X2

subject to (6.18)

X, -t- X2 + Xq max ( a, + Uj) = m j

- X, + Xj + Xo max (-a,, + a) = 2

Xl - X2 + Xo » max ( a,, - 0,2) = m, J

- X, - X2 + Xo » max ( -a;i - 0,2) = m.

There are four constraints, regardless of the number of existing facilities. Adding the first and fourth constraints gives Xo » (w, + m)/!, and adding the second and third constraints gives Xo > (Wj + )/2. If ms = max \{m, + m), (wj + m], then mJ2 is a lower bound on xJ. By direct substitution we find that this lower bound is attained for (x„X2) = /2(W3 - w4, - Wj - m4 + W5) or (w, - , m, - wtj - m,), and each of these two-tuples represents an optimal location for the new facility. As convex combinations (non-negative weighted averages) of optimal solutions to linear programming problems are also optimal solutions, all points on the line segment between the two optimal locations are also optimal.

Example 6.3 A hub facility for a rapid delivery service in a city is to be located in relation to five distribution sectors (idealized as points). Their locations are as given in Example 6.1; but all w, = 1. We find w,

= 12, W2 = 2, W3 = 7, m4 = -5 and ms = max (12-5, 24-7) = 9. Then, xJ = 4.5 and:

A*ˆX(6.0,3.5) -f (l-\)(5.0,2.5); 0 < X < 1)

represents the line segment of optimal locations. This segment is depicted in Figure 6.5.

The Dual Problem

Because the computational effort in solving a hnear programming problem depends primarily on the number of constraints, it is expedient to solve the dual of problem (6.17), given by:

m n

maximize Z (« + ) < + (.- ,, + afl)v,2 u,v -=i,/-i

+ (O/i - aj2)v,j3 + (-aji - a,.2)v,y4 Figure 6.5 Graphic Solution of Hub Facility Problem.

Z E + V2 + V,y3 + V,4)/

/- 1 7= 1

+ 2 S (".1 + + ",>3 + „-4)/ 2,. = 1,

where all variables are non-negative.

Sums have no terms whenever the initial subscript value is greater than the terminal subscript value. Problem (6.19) has only 2m +1 constraints, regardless of the number of existing facilities. The variable Vy, corresponds to the rectangular distance between existing facility j and new facility /. The value of the subscript s, s = 1,2,3,4, refers to that primal constraint of the first four forms in problem (6.17) to which the dual variable is related. In similar fashion corresponds to the distance between new facilities i and r. The pair (x,x) is the pair of dual variables associated with the and m + i constraints, respectively, when problem (6.19) is solved.

From the theory of linear programming, the following complementary slackness conditions must hold at optimality:

vfj\± ,± 2 + Jwuj - (± ± %)] = 0

i = l,...,w,j= l,...,n, 5 = 1,...,4,

M*[± x?; + ± + ?2 + x/w2,r] = 0

/ = l,...,m-l; r = i+l,...,m; s = 1,...,4.

The signs in the brackets are to be in accordance with the signs in the s form of the associated constraint in problem (6.17). As in Example

6.2, these conditions can be used to indicate the full set of optimal locations, analogous to the situation depicted in Figure 6.3.

6.3 ADDENDA TO MINIMAX LOCATION

Upper bound constraints, such as:

UX„aj) < a„ and/or J?,(X„X,) /3,,

maybe included in problem (6.3) to avoid unacceptable placement. When included in problem (6.17) where p = I, these constraints become:

x„+x,2 < a„+a„-ba,2 x„-x„+x,2-x,2 <

- x„+x,2 ay-a + a,2 ( j - x,,+x,,+x,2-x,2

> and/or <

x„-x,2 < a„-Ha„-<2,2 I I x„-x„-x,2+x,2 <

- x„-x,2 < a„-a„-a2 - ,- - ,2+ ,2 ;3„.

The need for such constraints may naturally arise in a service-oriented application.

Linear constraints can also be included to Hmit feasible locations of the new facilities. For example, if the constraints - , - X32 -40, X3, 3= 10, and X32 > 10, were appended to problem (6.17), the third new facility location would be constrained to be within or on the boundaries of the triangle with vertices (30,10), (10,30), and (10,10). If new facility / is to be located along a linear corridor, an equality constraint will serve the pu ose. A constraint of the form x,2 - ax,, = b is imposed. It is a straightforward matter to alter the form of problem (6.19) when linear constraints and/or interfacility distance constraints are included in problem (6.17). The effect on computational efficiency is minimal because to add constraints to problem (6.17) is to add variables to problem (6.19).

Contours

The mathematically "optimal" solution to a location problem frequently represents a point of departure, a reference point against which to measure the goodness of alternative solutions. Decision problems are typically multi-objective in nature. Location under the minimax criterion satisfies but a single objective. Construction of contour lines (points with equal objective value) provides a convenient visual means of comparing satisfaction of other locational goals against the suboptimality induced by deviations from a minimax location. For example, the set of points on the boundary of the shaded region in Figure 6.1 constitutes the contour for M(X) = 4. There, Euclidean distances define M{X).

subject to (6.19)

E ( 2 + V„ , - Vy4) + X + ""2 - "r,3 + M„4)

+ S ( . ~ «>2 + "w - «,>4) = 0 (• = I,...,m

n i-1

S (..1 + V,j2 - V„3 - V„4) + X - ,2 + " + "„ )

,-1 r-1

+ S (""1 + ""2 - - «,m) = 0 / = \,...,m