back start next


[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [ 14 ] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]


14

Table 3E.4 Weights by Period.

Period j

Consider a rectangle bounded by the corners (f,,,,,), ), (djdj), and (Cj,d,2), with d„ > c,i and rf,, > Cj2. Show that:

where: R, = I when c,, < x, < i/,,, = - 1 otherwise; /, = 1 when c,i < X < u?,,, = - 1 otherwise,

and that:

EW,ix,) = -X w,R,{x,-d,, + l(x-c,Mdn-c and that £ -,( ,) is convex, where E denotes expected value.

3.18 Derive a formula for finding a minimizer xT for EW,(x,) in Exercise 3.17, given that the values of the indicators / and R at the optimum are known.

3.19 Derive an efficient search procedure for solving the problem in Exercise 3.17. Apply this method to the problem defined by the data in Table 3E.5.

3.20 Discuss the relationship between the problem of minimizing EW,{xd in Exercise 3.17 and the problem in Section 3.2.

3.21 Show that equation (3.31) implies that xf is, in a sense, the location of the median weight. (Hint: Be careful in defining "weight.")

3.22 Solve the problem of Example 3.7 by the median weight method.

3.23 The mean of a uniform probability distribution with range [a,b] is {b + a)/ 2, and the standard deviation is (b - a)/Vl2. Solve the example in Table 3.18 assuming uniform distributions with the same means and standard deviations as the normal distributions.

Table 3E.5 Data for Exercise 3.19.

- 7.12

17.12

5.12

12.31

-17.71

37.71

3.15

14.51

-16.18

46.18

- 5.12

15.12

- 1.18

61.18

-12.12

42.12

19.22

60.78

5.12

12.12

REFERENCE NOTES

SECTION 3.1 This section is based primarily on the paper by Drezner and Wesolowsky (1978). This problem was previously investigated by, among others, Litwhiler (1977), and Katz and Cooper (1980); also, see Litwhiler and Aly (1979). For a summary of the literature on spherical surface location problems, see Wesolowsky (1982).

SECTION 3.2 The material presented here originally appeared in Wesolowsky and Love (1971a). The somewhat more complex problem created when straight-line distances are used was discussed by Love (1972), and Drezner and Wesolowsky (1980b).

SECTION 3.3 The discussion here is from Wesolowsky (1974). Related analysis was carried out by Morris and Norback (1980). There is evidence of increasing interest in the location literature in incorporating expressways and corridors into models.

The topic of orthogonal curve fitting has a long and interesting history. Early references include Adcock (1878), Kermack and Haldane (1950), and Pearson (1901). However, these works referred to the problem of fitting using the sum of squared perpendicular distances.

SECTION 3.4 This introduction to the topic follows Wesolowsky (1973). Further work includes Wesolowsky and Truscott (1975), Roodman and Schwarz (1977), Erlenkotter (1981), and Van Roy and Erlenkotter (1982).

SECTION 3.5 The corresponding problem with straight-line distances was introduced by Katz and Cooper (1974, 1976). The rectangular distance case was discussed by, Wesolowsky (1977).

SECTION 3.6 For an extension of the problem to jP distances, see Drezner and Wesolowsky (1981).

APPENDIX-CHAPTER 3 Mathematical Notes

3.1 Prove Property 3.1

A{X,a) is convex on a spherical disk with radius v/l centered on point j.



proof: To prove convexity for a continuous function such as A(X,aj), it is enough to prove [see equation (3.3)] that

f{V) .5f(Y) + .5/(Z).

We can choose the upper hemisphere for our disk of radius ir/2 without loss of generality.

Choose any two points with coordinates Y = ( ) and Z = (zhZ) on the sphere provided that y„Zt 0. Let p = (x/2,0) be the north pole. Then:

AiY,p) =

7 /2 -

AiZ,p) =

7 /2 -

A(V\p) =

x/2 -

By the median formula [Donnay (1945), p. 59] sin ¥( = sin ((j, + z,)/2) cos (iy, - z,)/2) cos (A(Y,Z)/2). Using equation (3.2) to evaluate A{Y,Z), we can obtain;

sin =

sin ((y, + z,)/2

(I - ty

where t is given by:

1 - sin2((y, - z2)/2) cos y, cos z,/cos2(Ch, - z,)/2). As < 1, and < 7 /2,

Vf O, + z,)/2.

Therefore:

7 /2 - F, < (t/2 - y, + 7 /2 - z,)/2 and AiV,\p) < ( ( ,/7) + A(Z,p))/2,

which means (X,p) is a convex function north of the equator, and Property 3.1 follows immediately.

3.2 Prove Property 3.2

A local minimizer of a convex function f{X) on a convex subset D of a sphere is also a global minimizer.

proof: Suppose that Y and Z are global and local minimizers on D, respectively. Because D is convex, the arc connecting Y and Z is included in D. Let be defined as in equation (3.3). Now:

f{V>-) < X/(Y) + (1 - \)/(Z),

and if/( ) < /(2), then /(V) < /(Z) for X as small as desired. This

contradicts the assumption that Z is a local minimizer. Thus Z cannot be a local minimizer without being a global minimizer.

3.3 Prove Property 3.4

) has a local minimum at a, if and only if, CF, < w,.

proof: It can be shown that for movement from point a/.

dW{X) = wXidx.y + cos a.idxyy"

-dx, 2 H-X-sin „ cos aj, cos (a.2-«>2)

+ cos a„ sin <3yi)/sin A(a„aj)

-dx2 2 w/cos o„ cos a,, sin (ay2-a,2)/sin A(a,,a).

For a local minimum, dW{X) > 0, and, hence, we must show wfldx.y + cos2 a,,{dxyyyi-F,4x,-F,2 cos a„rfx, > 0. Letting L = dx cos ajdx, we have:

Iflx.luXl + L)/2 > x,(F„ + LFr, and so: H-,, > dx,{Fry + Z/-,2)(l + UYil\dx\. Note that ,/!,! is ± 1. It can be shown that:

-(i, + ?2)" < {Fn + Z.i=,2)/(1 + V-yi

and hence, the condition:

(7, + 72)" is necessary and sufficient for dW{X) > 0 for every L. 3.4 Derive EW\{x, in equation (3.31)

From equations (3.29) and (3.30), EW,{x,) = 2 INT,,

where:

INT, = J x,-J;„(/2 a,)- exp {-{{ ,.

)/a,,yi2)dyj,.



VARIATIONS ON THE SINGLE-FACILITY MODEL

We break up INT into two integrals:

INT,

Chapter

+ J ( ,- :,)(>/2 <r,)- exp (-(( ,,- „) .)72 7.1-Differentiating with respect to x,:

iJbr ;)- exp (-(( - ,) ,)72

< ,

-J {sjbcy exp {-((y;,-M;,)/<j.)V2)u(y„

= 1 - 2 J ( /27 ( ,)- exp (-((y „-Ai „)/ffji)V2My,i

and hence,

£ ;( :,) = £ w,(l - 2 ( :,- ;,)/< ;,)).

Multi-Facility Location

It often occurs that more than one new facility must be located. If no pair of new facilities interact (have inter-facility flow), we can treat the location of each new facility as a separate problem and apply the techniques of Chapter 2. Otherwise, the new facility locations are interdependent and must be optimized simultaneously. The resultant problem is termed a multi-facility location problem. We will continue to assume that the cost per unit flow between any pair of facilities is proportional to the distance between them. In general form, the multi-faciUty problem is:

in n in-I m

minimize, /(- = S S uAiX.a,) +22 W2 (..), (4-1) where

m is the number of new facilities to be located, n is the number of existing facilities, W„ converts distance between new facility / and existing

facility j into cost and wj 0, Wjii- converts distance between new facility / and new facility r into cost and w,,, 0, X = {Xi,...,X„) is the vector of new facility locations, X, = ( :,, ,,) is the location of new facility i, Uj = {aj,,ap is the location of existing facility j,

S„{X„a is the distance between new facility i and existing facility j, and

Si,{Xi,Xi) is the distance between new facility / and new facility r.



[start] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [ 14 ] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51]