Actually, as can easily be verified firom a comparison of procedure (2.6) and equation (2.7), if the starting point is very far outside the convex hull, X<" will be approximately the center-of-gravity solution.

2.2 THE RECTANGULAR DISTANCE PROBLEM

Rectangular distances were described in Chapter I. In addition to being applicable in a wide variety of location problems, their use greatly simplifies many problems that are quite difficult with straight-line distances. For p = I, problem (2.1) becomes:

minimize W(X) = Wj{\x, - aj,\ + \x2 - ajj}. (2.10) X

There are two properties that are useful in finding (xf ,x?). The first will be called separability. Problem (2.10) can be rewritten:

minimize W{X) = W,{x,) + Wix) (2.11)

where:

Note that there will now be ;< coordinates, where = n. The reason for this may be seen in the following example. Suppose a,, = flai = 4 and W = 3, w, = 2. We can combine the sum of terms 3\x, - 4\ + 2\x, - 4 into the single term 5\x, - 4. We can thus create a sequence ofays that are strictly increasing in value. As a result, however, we may have fewer a,)ks than there are as.

The superscript in wj denotes ordering and consolidation in the corresponding weights. The reason is that there can now be an ordering of weights in the x, dimension different from that in the X2 dimension, and we use the superscript to distinguish these orderings.

Problem (2.12) becomes:

"*

minimize W,(Xk) = X " for = 1,2. (2.13)

The function Wi,(Xk) is now in a form convenient for calculating its derivative (see Exercise 2.8). We can write:

for Xj, < a

(2.14a)

W2(X2) = S - ,2.

Minimizing W(X) is equivalent to separately finding an x, that minimizes W,{Xt) and an X2 that minimizes 2(-2)- The problem now becomes:

minimize W{Xk) = X jk* ~ <A fo 1>2- (2-12)

This problem is rather easy to solve. An analog approach is given near the end of this section (in Example 2.5) that makes the use of formulas unnecessary. However, the method of analysis that immediately follows gives mathematical conditions and relationships that will be needed in later chapters; in addition, it validates the analog approach.

We must first verify that wx. - aji\ is a convex function of x,,. This can be done by simply plotting the term against . for any w, > 0 and . A more formal proof is the subject of Exercise 2.7. Because the sum of convex functions is convex, it follows that Wilxd is convex.

To facilitate analysis, a change in notation is made in problem (2.12). Let the values of for j = \,...,n be reordered to produce «(„ < 0(2,* < a,3n < ... < <2(„)b and let w\,...,w„ be the corresponding p sitive weights.

Wi:(x,) = X - S < for <x,< a(,+ „, (2.14b)

for Xi, > <2(„)t.

(2.14c)

It is easy to see that the slope of WJx,) is made up of linear segments and changes only at points (,,4.. To sum up, Wiix, is a continuous, convex, piecewise-linear function with points of discontinuity in the first derivatives occurring at the as.

Before formally stating optimaUty conditions for minimizing Wiixi), let us consider a numerical example to illustrate the notation and the characteristics of W{x) and «2(2)-

Example 2.3 A new facility must be located among four existing ones at (1,1), (2,4), (2,3), and (4,2). The corresponding weights are 2, 3, I, and 2, respectively. We are about to solve the associated rectangular distance location problem graphically. Table 2.4 summarizes the data and notation. For example, with A; = 1 in problems (2.12) and (2.13), we obtain:

W,(x,) = 2x, - 1 + 3, - 2 -b lx, - 2 + 2\k, - 4

WWx,) = 2, - I + 4x, - 2 + 2\x, - 4.

Table 2.4 Data for Example 2.3.

Wi(x,) and Wzte) are plotted in Figures 2.2(a) and 2.2(b), respectively. It is evident that Wi(x,) has a minimum value of 6 at xt = 2, whereas the minimum value of ) is 9 for x? in the interval [2,3]. Hence, WiX) has a minimum of 15 at (2,[2,3]). We can use equation (2.14) to check the slopes. For example, when 2 < x, < 4, then / = 2 and we compute:

W{x{) = (2 + 4) - 2 = 4,

as can be verified in Figure 2.2(a).

Because the slope W[{x) in equation (2.14) obviously increases with increasing t, the condition for a minimum to Wilx,,) to occur must be that the slope either changes from negative to positive, or changes from negative to zero at some point. In the latter case, the minimum occurs over a range of values for x*, as in Figure 2.2(b). However, at least one point „) must be a minimizer of *( ). The following makes these claims precise.

Property 2.5 [Conditions for a minimum to W/xJ ]. Suppose:

X - S < 0

(2.15a)

0 (2.15b)

are satisfied at some t*. If condition (2.15b) is met as a strict inequality, then xf =

then xf = If condition (2.15b) is met as an equality, then xf e

It is possible to express the conditions of Property 2.5 in a form more convenient for finding t*. We can write condition (2.15a) as:

1-1 r-l n,

2 w)- + X < - S < < 0

J=l >-l 7-1

♦ x, 5

Figure 2.2 Plots of W,(x,) and - ( ,). and condition (2.15b) as:

X Hj + - X - E vv 0.

,-1 /-1 y-l

If we let:

"/

= X for fe = 1,2,

then the conditions of Property 2.5 become:

+ 2 X < 0

-C + 2 X 3= 0.

(2.16a)

(2.16b)

Inequalities (2.16) now suggest a computational procedure. To - we add twice the weight of each point a,k, starting from = 1, until the sum first equals or exceeds zero. Note that we are merely using another expression for the slope of WJx,,). We will then have found the optimal range or the optimal point, respectively, for x,,.

Example 2.4 We return to Example 2.3 and the data in Table 2.4 to demonstrate the use of inequalities (2.16). We first calculate:

C=5w) = 2 + 4 + 2 = 8. Now, to find jct, we calculate:

-C + 2w) = -8 + 4 = -4

-C + 2 X = -8 + 12 = 4 > 0

and find that condition (2.16b) is satisfied as a strict inequality. So =

«(2)1 = 2.

To find xf, we calculate:

-C + 2 2 w/ = -8 + 4 = -4

-C+22 = -8 + 8 = 0

and find that condition (2.16b) is satisfied as an equality. So xf <[ (2)2, ( )2] = [2,3].

But there is an easier way of solving our problem. Example 2.5 illustrates the method.

Example 2.5 We consider the same problem. Recall that there are four existing facilities at points (1,1), (2,4), (2,3), and (4,2) with weights of 2, 3, 1, and 2, respectively.

Let us imagine that the weights are "dropped" on the x,-axis, and at the same time (in defiance of gravity) the same weights are dropped on the X2-axis (Figure 2.3). Let us then divide the x,-axis into two parts such that the weights are bisected. Clearly this point is at x, = 2 if we assume that weights acting on a mathematical point may be split as we wish. Similarly the weights on the X2-axis are bisected when 2 = = 3. As can be checked in the previous examples, these bisections produce and xf. As the reader should verify, what we have really done is to apply inequalities (2.15) or (2.16) in slightly disguised form. We can now describe the minimum to W{x,) as occurring at the point(s) of median weight.

W2 = 3 <<-----f W3 = 1

Figure 2.3 Median Weight Illustration. 2.3 THE jpp DISTANCE PROBLEM

Suppose distances are modeled by the 2p function. As discussed in Chapters 1 and 10, 2p distances can often provide a better measure of actual travel distances than either the straight-line or rectangular distances, which, are special cases given by p = 2 and p = 1, respectively. For convenience, we repeat problem (2.1) here:

minimize W(X) = 2] w,i\xi - a, + \x2 ~ ajp)".

(2.17)

We first state two properties that characterize 2p{X,a):

(i) llp{X,a) decreases as p increases, ie, for X Uj, (x, - a + - aj2W" > (11 - cijY + \X2 - aj2Yr\ for p < p,

and

(ii) as p -, oo, Sp(X,aj) becomes the larger of x, - and \x2 - aj-.

The following property bears upon the optimization specified by problem (2.17). A proof is given in the Appendix, mathematical note 2.3.

Iioperty 2.6 [Convexity of Wj£„(X,aj)]. WjS/X.Uj) is a convex function ofX.

As each of the terms of WtX) in problem (2.17) is convex, we can again use the fact that the sum of convex functions is convex to conclude that