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]


13

C(1) = 37

= 51

COST - 53

Figure 3.15 Tree Diagram for Example 3.6.

3.5 PROBABILISTIC DESTINATION LOCATIONS

So far we have assumed that both the locations of existing facilities and all costs in the system were known exactly. In practice, we seldom encounter this ideal. In this section we allow "knowledge" about the exact location of an existing facility to take the form of a probability distribution. In other words, though we may not know where the demand vrill be located, by using an appropriate distribution we are able to calculate the probability that it will occur in any given area of the plane. An example of such a situation arises when there is a large population of potential demand points and it is unknown which particular ones will become "active."

Let us consider a single-facility problem with rectangular distances. As usual, rectangular distances (versus 2 distances) allow for considerable simplification in the problem. Let each of the n existing facilities (demand points) have random coordinates ( ,1, ,2), as specified by a bivariate normal probabiUty density /{ , 2). We are required to find a facility location {x,xf) that minimizes the expected sum of weighted rectangular distances in the system. Each distance is weighted by the known cost Wj. The total expected cost in the system is then:

where:

Y /-I

Yj = ( ,„ ,2)

= (,yji,Yj2,...,Y„i,Y„2)-

(3.27)

It follows that:

EW{X) = 2 WjE , ,)),

j-x Y,

= 2 w,E \x, - y„ + 2 w,E \X2 - Y2\, . Yj Yj

= 1 wE \k, - y,, + 2 H.,£ \k2 - Y,2\

= EW,{x,) + EW2{x,

(3.28)

which means:

min EW{X) = min EW,(x,) + min EW2(x2). X X, X2

This makes it possible to concentrate on minimizing \{ \ because the minimization of EW2{x2) is analogous. From equation (3.28) we can write:

EW,(,x,) = 2 f ~ \ fiVjdy,,, (3.29)

where /(jyi) is the marginal (normal) distribution of ,. Let Yj, have mean , and standard deviation tr,,. Then:

( ) = (V2x ff,,)- exp(-((y„ - M,,)V2). (3.30)

Note that the analysis is unaffected by whether or not ,, and ,2 are correlated!

Fortunately, EWXx,) has a unimodal shape. As is shown in the Appendix, mathematical note 3.4, the derivative is:

Emixd = i W,(l - 2PXZ (X, - ,)/< ;,)), (3.31)

where z is the standardized normal variate and P, denotes probabiHty. As EW(xt) is easily evaluated with the aid of cumulative normal tables, we may use a method such as interval bisection to find xf.

Example 3.7 Table 3.18 gives the data for an example of three proba-bihstic destination locations.

Suppose the locations of the three points are deterministic at the means of their marginal distributions; that is, suppose that we were trying to



Table 3.18 Parameters for the Marginal Distributions of Three Points.

<J,2

find the location of a faciHty among existing faciHties located at (3,20), (10,25), and (15,10). Using the median weight method of Chapter 2, we find that (,x\,xV) = (10,25). This solution minimizes EW{X) under the assumption that all standard deviations Oj,, are zero. We shall see that the solution is different when they are not all equal to zero.

As an illustration, let us find EW\{2). By equation (3.31) and cumulative standardized normal probability tables:

EW\0) = l(l-2P,(z > (3-3)/l)) + 4(l-2PXz > (3-10)/3)) + 2(l-2PXz > (3-15)/4)) = -5.9947.

Table 3.19 shows the steps in the method of interval bisection as applied to finding the minimum of EW{x,). The interval [3,15] is a logical starting point. After three steps the derivative can be successively used to bisect the interval within which xf must lie, because EW,{x,) is unimodal. At xf = 10.602, the expected cost EW,{x,) is 27.2524. A similar computation shows that xf is 20.632, and the cost £ ,(20.632) is 46.2159. In sum-

Table 3.19 Steps in Interval Bisection.

X, EW\(x,)

-5.99477

4.90467

-2.1174

2.06679

10.5

-0.145819

11.25

0.966502

10.875

0.40155

10.6875

0.124198

10.5937

-0.0119195

10.6406

0.0558858

10.6172

0.0219169

10.6055

0.00498343

10.5996

-0.00347376

10.6025

0.000754356

10.6011

-0.00135994

10.6018

-0.000303268

10.6022

0.000223637

, the facility location that gives the lowest expected cost EW{X) is (10.602,20.632).

EXERCISES

3.1 Justify the following properties of problem (3.1).

a. A point is a minimizer for w, ( , } if, and only if, its antipode is a maximizer.

b. A point and its antipode with equal weights can be added to the problem without a change in the optimal location of the facility.

c. A point with weight w, can be replaced by its antipode with weight - w-without changing the optimallocation of the facility.

d. Every problem can be transformed to an equivalent one that has only positive weights.

3.2 a. Write a computer program to perform the Weiszfeld procedure on the

sphere. It should include a preliminary check of Property 3.4 for each point.

b. Use an atlas to find the coordinates of 10 cities on the globe: two in North America, two in Europe, two in the Middle East, and four in Asia. Weight the cities by their approximate population size. Apply the program developed in Exercise 3.2a. Discuss your confidence in having found the optimum solution.

3.3 a. Find the optimum solution to problem (3.1) if the distance function

d{X,a) = 7 sin2 (A(X,a,)/2) is used, b. When might d(X,a,) be used?

3.4 Derivf equations (3.6) from equations (3.4). (Warning: This requires a bit of trigonometry.)

3.5 Drezner and Wesolowsky (1978a) Show that Property 3.3 is "tight" in the sense that an example with two or more local minima can be constructed if the radijis is /4 + t, where « > 0.

3.6 Show that ,*( ) in equation (3.10) is strictly convex.

3.7 Show that problem (3.8) can be solved for (xT,xf) by finding the location of the medians of weights on the respective axes. (Hint: Define a value XT and divide the sums in problem (3.8) into three parts; areas and points to the left of xT, areas and points to the right of xf, and points coinciding with XT. Equate dWA(xT}/dXi, to zero and consider the implications.)

3.8 A post office box must be optimally located among three "area" destinations and four point destinations. Problem parameters are given in Table 3E. 1.



Table 3E.1 Problem Parameters for Exercise 3.8.

a. Display the area and point destinations graphically.

b. Find the optimum location for the post office box.

3.9 Find an expression for Tj{xi,x in equation (3.7) when straight-line distances are used. Perform any integration; then express WA{X) in problem (3.8) for straight-line distances. Suggest a solution method.

3.10 Show that the shortest (or perpendicular) distance from a point {aj,ap) to the line 2 = A + 5 , is:

- (a,2 - Sa,i (52 + 1)1/2 •

3.11 Show that the optimum angle for a line that minimizes the sum of weighted perpendiculars cannot occur in a range </>„ where </>, is specified preceding Property 3.6.

3.12 Table 3E.2 gives the data for locating a linear facility.

a. Plot the seven points and their weights on a diagram.

b. By inspection, find the 12 lines whose slopes represent the only angles that can be optimal.

c. Use the results of Exercise 3.12b and P{A,S) in problem (3.14) to evaluate the 12 candidate lines. Choose the best one.

Table 3E.2 Seven Points and Their Weights.

3.13 For the case p = 1, express problem (3.24) in the text as a zero-one linear programming problem. (Hint: A reading of the first part of Section 4.1 will help here.)

3.14 Show that if all possible change plans were to be evaluated in single-facility dynamic location, 2-((r- l)/2+ 1) static problems would have to be solved.

3.15 Repeat Example 3.5 for straight-line distances.

3.16 Tables 3E.3 and 3E.4 give the data for a six-period dynamic facility location problem. Distances are rectangular. Find the optimal location plan by using the branch-and-bound method of Section 3.4. It is not necessary to find all tied solutions.

3.17 Assume that each demand point can occur within a rectangular area (this shape is chosen to make analysis easier) and that the probabiUty density of occurrence anywhere within that area is the same (uniform). Note that overlapping rectangles of various sizes can be used to represent complex spatial configurations of probability.

Table 3E.3 Location of Destinations by Period.

Period

Destination

Number j

a,2,

I 5



[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]