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]


11

Figure 3.10 Range of for aU Optimal.

hence for which the line goes through a,. Then in 0„ the line goes through another point only if a, = ai.

Property 3.6 [ cannot be optimal in ].

proof: Let:

0,) = \j\a% < a?2, (3.18a)

) = {7 2 > fl?2, , 1 (3.18b)

The sets { ) and { ) merely identify those points that are "below" and "above" in the range .

Using equation (3.16) we can restate equation (3.18) in a more operational form. For jtUjj)) we have:

-a,, sin + a,2 cos > - ai sin + a cos

(<2,2- ) COS 0 > (a,, - ,,) sin . Performing similar calculations for jtU{ , we find that for jiL{ ).

i,a,2-aj2) cos > (an-aji) sin , (3.19a)

and for ] ( .

{aj2-a,2) cos > (aj,-an) sin . (3.19b)

Conditions (3.19) can easily be used to find the endpoints of <,. This will be illustrated in Example 3.3. We now show that the optimum angle cannot occur in ,. For ( :

PAGe) = 2 W>?2 - (fr\

= E w,{{aa-a,2) cos - (a„-aj,} sin )

,)

+ S Hiai2-aa) cos - (a„-a„) sin ) = 5 { Wj{a,2~a,2) + X Hj2-a,2))

-sin 61 (21 Wjia-aj,) + vvXa,i-a„)).

It can easily be verified that:

PeiGe) = -PlGd,

which is always negative. This means that ) is concave in and that the minimum must occur at the endpoints of ,.

This leaves the possibility that G is not a point but a range. Figure 3.11 illustrates such a case. It can be verified that G? = {a?n,a?i2\ for et[e„e2]. In general, let , = { [, £) be an open interval of angles for which GJ = [a?2,<2], where < a,,- Note that the angles \ and Si, where the line would pass through "new" points, are again not included in Let:

{ ,) = !;K2 < aa, ,\

,) = UK > <2, 1

(3.20a)

(3.20b)

Using conditions (3.19) we can now identify the conditions that define

For7ˆL(0,): (0,2-72) cos 9 > (a„-a„) sin . (3.21a)

For>«/(</.,): (a/2-a,2) cos 6» > (ay,-fl„) sin 6». (3.21b) But <2 a?2.

Therefore, ( - / ) cos 9 > (a,-a„) sin . (3.2lc)



Figure 3.11 G* = [ \, ,\.

Exercise 3.11 asks the reader to show that the optimum angle can also not occur in , for the case where G* is a range.

Finding *, the best angle, can therefore be accomplished by systematically eliminating intervals 0, from [0°,180°) and evaluating the cost function at the endpoints of these intervals. As can be verified by checking Figure 3.9, the slope and intercept of the best line are:

A* = Gf./cos * S* = tan *.

(3.22a) (3.22b)

Example 3.3 illustrates the notation and equations. Example 3.4 illustrates a graphical, nearly "equationless" version of the method that is simple to apply for small problems.

Example 3.3 Table 3.8 gives the coordinates and weights of three demand points.

We can start our search at 0°. Table 3.9 reproduces Table 3.8, but with the points ordered by the magnitudes of a% so that we can more easily find GJ. It is evident that the median weight is at a?2 and hence GJ = 5. We find that L(0,) = {2} and ,) = (3), and using conditions (3.19) we draw the following conclusions.

I 3 1

2 1 4

3 2 6

Table 3.9 Ordering of ajj at 6> =

0°.

j w, a„ a,2

2 1 4 2

13 15

3 2 6 6

For jtL(0,): (al2-ay cos & > (a«„-a!,) sin

or (5-2) cos > (1-4) sin

or -cos 0 < sin ,

which is true for in ( - 45,135). For> /( ): ( " 2-< 2) cos > ( ,- ,,) sin

or (6-5) cos e > (6-1) sin

0.2 cos < sin ,

which is true for in (-168.6901,11.3099).

This can be verified by setting:

Z = 0.2 cos - sin e

= cos .2 - tan ).

Z is positive for cos > 0 and 0.2 > tan or for cos < 0 and tan < 0.2. It follows that , = (-45,11.3099).

To eliminate the next interval, we consider in Table 3.10 the new ordering of <2 that begins at 11.3099°. Conditions (3.21) now define ,. Hence, L(03> = and (6-2) cos (9 > (6-4) sin , which gives 2 cos > sin 6. This inequality is true for 0e[-116.565,63.435]. Note that {7(0 ) is an empty set.

Since q = I and = 3 in , > aa and (5-6) cos0 > (1 -6) sin .

Table 3.10

Ordering at fl

= 11.31°

/71!.31

2 1

1.1767

3 2

4.7068

1 3

4.7068

Table 3.8 Parameters for Example 3.3.



Table 3.11

Ordering at e = 63.435°.

63.435

3 2

6 6

-2.6833

2 1

4 2

-2.6833

1 3

1 5

1,34174

Table 3.12

Comparison of Costs.

PAGt)

11.3009

4.7068

3.5301

63.435

[-2,6833,1.34164]

12.0748

135.0

-4.2426

8.4852

Therefore, 0.2 cos > sin , which is true for ˆ[11.3099,191.3099]. We now have , = (11.3099,63.435). Thea% are reordered for the next interval in Table 3.11.

Again, conditions (3.21) apply: (2-6) cos 0 > (4 -6) sin (9 or 2 cos 0 < sin , which is true for [63.435,243.43]. Also, (5-2) cos > (I -4) sin or -cos « < sin , which is true for (-45°, 135°). Hence, = (63.435,135).

Because a new Une with = 135° is the same as one with = -45°, we have exhausted 180°. We now need only evaluate the cost P/G«) at the endpoints of <„ , and 0 to find the best line. This is done in Table 3.12.

Using equation (3.22) gives A* = 4.7068/cos 11.3099° = 4.8, S* = tan 11.3099° = 2. The cost function P„(G*) is plotted in Figure 3.12. We observe that cost is rather sensitive to changes in angle in the vicinity of the optimum. The concavity of the function in each region , is also apparent.

Simplifications

Two simplifications suggest themselves. First, note that the optimum line must cut through at least two points. This suggests a simple search approach. We can simply calculate the intercepts A and slopes S of the ( -1 )/2 lines cutting all pairs of points and use P(A,S) in problem (3.14) to choose the least-cost line. Second, the algorithm can be viewed as rotating the line and using pivot point after pivot point such that the line continues to be median. This can readily be done graphically for small problems. Both procedures are illustrated in the following example.

Example 3.4 Table 3.13 gives the coordinates and weights of four points.

There are six possible lines through two points at a time. The indices of the pairs of points are (1,2), (1,3), (1,4), (2,3), (2,4), and (3,4). Table

150 180

Figure 3.12 Plot of ( ?).

3.14 gives the intercepts, slopes, and costs of these lines. The line through points «1 and «2 is optimal.

Figure 3.13 illustrates the rotation procedure. If we begin with a hor-izontalhne, it must go through point 1 in order to divide the weights in two. However, this line intersects only one point and cannot be optimal. We therefore rotate this line counterclockwise with point 1 as a pivot until we obtain line #1 in Figure 3.13. In order for the line to remain median, point 3 becomes the pivot until line #2 is produced. Then point 4 becomesthe pivot until line #3 is produced. Point 1 then becomes a pivot to create line #4. It then remains a pivot until the line is again horizontal. Only four lines need now be evaluated. The lines through

Table 3.13 Parameters for Example 3.4.



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