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(xc,Mdnc 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 straightline 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 straightline 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). APPENDIXCHAPTER 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 HXsin „ cos aj, cos (a.2«>2) + cos a„ sin <3yi)/sin A(a„aj) dx2 2 w/cos o„ cos a,, sin (ay2a,2)/sin A(a,,a). For a local minimum, dW{X) > 0, and, hence, we must show wfldx.y + cos2 a,,{dxyyyiF,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 + Vyi 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 SINGLEFACILITY MODEL We break up INT into two integrals: INT, Chapter + J ( , :,)(>/2 <r,) exp ((( ,, „) .)72 7.1Differentiating 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 ( :, ;,)/< ;,)). MultiFacility Location It often occurs that more than one new facility must be located. If no pair of new facilities interact (have interfacility 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 multifacility 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 multifaciUty problem is: in n inI m minimize, /( = S S uAiX.a,) +22 W2 (..), (41) 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]

