Solutions to Selected Problems from Chapter 10

Solutions For Chapter 10

Solutions To Selected Problems From Chapter 10

10.3a) Number of trips

required

Products (Forecasted Prod./50)

1 4

2 18

3 8

4 13

The number of trips required for A-B would be 4 + 8 = 12 since this path corresponds to both products 1 and 2. Other entries are computed similarly

A B C D E

______

A | |12 | | 18| | Note: These figures include the 8

|___|___|___|___|___| trips required forproduct 3

B | | | 12| | | from departments C to E.

|___|___|___|___|___| Since there is no direct con-

|___|___|___|___|___| parts must be routed through

D | | | | |43*| D.

|___|___|___|___|___|

E | | | | | |

|___|___|___|___|___|

b) A B C D E

______

A | |24 | | 36| |

|___|___|___|___|___|

B | | | 24| | |

|___|___|___|___|___|

FromC | | | | 50| |

|___|___|___|___|___|

D | | | | | 86|

|___|___|___|___|___|

E | | | | | |

|___|___|___|___|___|

B I

C X

d)Yes. If activity D is moved to the middle of the area, it will be closer to both A and C.

10.8

A B C D E A B C D E

1 26 20 22 21 25 1 6 0 2 1 5

--->

2 35 31 33 0 26 2 9 5 7 14 0

3 15 18 23 16 25 3 0 3 8 1 10

4 31 34 33 30 M 4 1 4 3 0 M

5 0 0 0 0 0 5 0 0 0 0 0

The objective function equals 20 + 26 + 15 + 30 = 91. The optimal solution is:

Machine 1 2 3 4 No machine

Location B E A D C

10.10

djr =

fik =

aijkr=

Since the problem says to ignore relocation costs, we set cij = 0. We list the non-zero values of the constants:

a11d22 = (3)(6) = 18

a12 d21 = (3)(9) = 27

a11 d32 = (1)(6) = 6

a12 d31 = (1)(9) = 9

a21 d32 = (5)(6) = 30

a22 d31 = (5)(9) = 45

a31 d22 = (4)(6) = 24

a32 d21 = (4)(9) = 36

Hence the formulation is:

min[18x11x22 + 27x12x21 + 6x11x32 + 9x12x31 + 30x21x32 + 45x22x31 + 24x31x22 + 36x32x21]

Sub to: = 1 for j=1,...,3

= 1 for i=1,...,3

xij = 0 or 1

10.25The new facility is to be located at (8,8).

Existing facility: (5,15) (10,20) (6,9)

Rectilinear distance: 3+7 = 10 2+12 = 14 2+1 = 3

Euclidean distance:= 7.62 = 12.17 = 2.24

10.26Location: (8,16)

Existing facility: (5,15) (10,20) (6,9) Total

Rectilinear distance: 3 + 1 = 4 2 + 4 = 6 2 + 7 = 9 19

Euclidean distance: = 3.16 = 4.47 = 7.28 14.91

Location: (6,15)

Total

Rectilinear distance: 1+0 = 1 4+5 = 9 0+6 = 16 16

Euclidean distance: = 1 = 6.40 = 6 13.40

Location: (4,18)

Rectilinear distance: 1+3 = 4 7+2 = 9 2+9 = 11 23

Euclidean distance: = 3.16 = 6.32 = 9.22 18.70

Hence, in both cases (a) and (b), the optimal location is (6,15).

10.28

Location of Normalized

machines Weight weight

(3,3) 1/8 6

(3,7) 1/8 6

(8,4) 1/4 12

(12,3) 1 48

(14,6) 1/6 8

x location: 3---3 8---8 12---12 14---14

12 12 48 8

Hence, 12 is the median location for the x coordinates.

y location: 3---3 4---4 6---6 7---7

54 12 8 6

Hence, 3 is the median location for the y coordinate.

The solution is therefore(12,3).

10.30Building location Weight

34th & 7th (34,14) 3

44th & 8th (48,16) 1

38th & 3rd (38,6) 1

42nd & 5th (42,10) 1

x: 34, 34, 34, 38, 42, 48  the optimal x coordinate is between 34th and 38th streets.

y: 6, 10, 14, 14, 14, 16 the optimal y coordinate is 14. This corresponds to 7th avenue.

Therefore he should park at 7th avenue between 34th and 38th streets.

10.31

location distance

1) 40th & 8th (40,16) 3 x (6+2) + (8+0) + (2+10) + (2+6) = 52 *

2) 40th & 6th (46,12) 3 x (12+2) + (2+4) + (8+6) + (4+2) = 68

3) 33rd & 5th (33,10) 3 x (1+4) + (15+6) + (5+4) + (9+0) = 54

Hence, he should park at 40th Street8th Avenue.

10.36(3,3)

(3,7)

(8,4)

(12,3)

(14,6)

c1 = min (6,10,12,15,20) = 6

c2 = max (6,10,12,15,20) = 20

c3 = min (0,4,-4,-9,-8) = -9

c4 = max (0,4-4,-9,-8) = 4

c5 = max (20-6, 4+9) = 14

x1 = (6 + 9)/2 = 7.5

y1 = (6 - 9 + 14)/2 = 5.5

x2 = (20 - 4)/2 = 8

y2 = (20 + 4 - 14)/2 = 5

All points on the line connecting (7.5, 5.5) and (8,5) are optimal.

10.39

x = = 10.25

y = = 3.925

b)a) Note: This problem is very tedious to solve by hand. We do not recommend assigning it unless the student has access to a computer.

Let x0 = 10.25, y0 = 3.925

Weights: w = (1/8, 1/8, 1/4, 1, 1/6)

Coordinates a = (3, 3, 8, 12, 14)

b = (3, 7, 4, 3, 6)

(x1,y1) = (11.0362,3.4232)

(x2,y2) = (11.5409,3.2403)

(x3,y3) = (11.7885,3.1245)

(x4,y4) = (11.9026,3.0603)

(x5,y5) = (11.9550,3.0284)

(x6,y6) = (11.9792,3.0133)

(x7,y7) = (11.9904,3.0062)

(x8,y8) = (11.9954,3.0029)

The solution is converging to (12,3).

10.400,0),(5,5), and (10,10) lie on a single line the optimal location should be on this line too.  x = y.

Therefore f(x,x) =

= x + 2(5-x) + 3(10-x)

= -4x + 40

i)For 0  x  5, this is minimized when x = 5 giving an objective function value of f(5,5) = 20.

ii)10  x  5; f(x,x) = x + (x-5) 2 + 3(10-x)

= 20 for any value of x.

Hence, all points on the line connecting (5,5) to (10,10) are optimal.

10.41Location of

switching

center Cable required

1 ++ + = 39.44 *

11.66 6.40 10.20 11.8

2 + + + = 56.34

11.66 11.27 17.89 15.52

3 + + + = 41.81

6.40 12.53 5.39 17.49

4 + + + = 54.67

10.20 17.89 5.39 21.19

5 + + + = 65.38

11.18 15.52 17.49 21.19

Therefore the optimal location is Building 1.

10.43Assume that (x1,y1), (x2,y2) are the locations for new machines A & B.

a)min f1(x) + f2(y)

where f1(x) = 2|x1-x2| +|x1 -3| + |x1 -3| + |x1 -8| + |x1 -12|

+ |x1 -14| + |x2 -3| + |x2 -3| + 3|x2 -8| + |x2 -12|

+|x2 - 14|

f2(y) = 2|y1 -y2| + |y1 -3| + |y1 -7| + |y1 -4| + |y1 -3|

+ |y1 -6| + |y2 -3| + |y2 -7| + 3|y2 -4| + |y2 -3|

+ |y2 -6|

The complete linear programming formulation of the problem of finding the optimal x coordinate is:

min 2(c12 + d12) + 1/8(e11 + f11) + 1/8(e12 + f12 + 1/4(e13 + f13) + (e14 + f14) + 1/6(e15 + f15) + 1/4(e21 + f21) + 1/6(e22 + f22) + 3(e23 + f23) + 1/5(e24 + f24) + 1/2(e25 + f25)

Subject to:

x1+ - x1- - x2+ + x2- - c12 + d12 = 0

x1+ - x1- - 3 - e11 + f11 = 0

x1+ - x1- - 3 - e12 + f12 = 0

x1+ - x1- - 8 - e13 + f13 = 0

x1+ - x1- - 12 - e14 + f14 = 0

x1+ - x1- - 14 - e15 + f15 = 0

x2+ - x2- - 3 - e21 + f21 = 0

x2+ - x2- - 3 - e22 + f22 = 0

x2+ - x2- - 8 - e23 + f23 = 0

x2+ - x2- - 12 - e24 + f24 = 0

x2+ - x2- - 14 - e25 + f25 = 0

x1+, x2+, x1-, x22, eij, fij 0

The L.P. formulation for finding the optimal y coordinate is the same with y2+, y2- and the appropriate values for the weights wijand locations bi.

b)The problem formulated in part (a) was solved using LINDO. The output is given below:

XP1 = x1+ XN1 = x1-

XP1 = x2+ XN2 = x2-

The solution is x1 - 8, x2 = 8.

OBJECTIVE FUNCTION VALUE

1) 11.8837000

VARIABLE VALUE REDUCED COST

C12 .000000 1.208300

D12 .000000 2.791700

E11 5.000000 .000000

F11 .000000 .250000

E12 .000000 .250000

F12 3.000000 .000000

E13 .000000 .000000

F13 .000000 .500000

E14 .000000 2.000000

F14 4.000000 .000000

E15 .000000 .333400

F15 6.000000 .000000

E21 5.000000 .000000

F21 .000000 .500000

E22 5.000000 .000000

F22 .000000 .333400

E23 .000000 1.925000

F23 .000000 4.075000

E24 .000000 .400000

F24 4.000000 .000000

E25 .000000 1.000000

F25 6.000000 .000000

XP1 8.000000 .000000

XN1 .000000 .250000

XP2 8.000000 .000000

XN2 .000000 .000000

The optimal y values are found similarly. The L.P. solution for yis:

OBJECTIVE FUNCTION VALUE

1) 3.78350000

VARIABLE VALUE REDUCED COST

C12 .000000 3.083300

D12 .000000 3.083300

E11 1.000000 .000000

F11 .000000 .250000

E12 .000000 .250000

F12 3.000000 .000000

E13 .000000 .000000

F13 .000000 .500000

E14 1.000000 .000000

F14 .000000 2.000000

E15 .000000 .333400

F15 2.000000 .000000

E21 1.000000 .000000

F21 .000000 .500000

E22 .000000 .333400

F22 3.000000 .000000

E23 .000000 3.866600

F23 .000000 2.133400

E24 1.000000 .000000

F24 .000000 .400000

E25 .000000 1.000000

F25 2.000000 .000000

YP1 4.000000 .000000

YN1 .000000 .000000

YP2 4.000000 .000000

YN2 .000000 .000000

Hence y = (4,4) and the optimal solution calls for locating both machines at (8,4). If this is not feasible, then additional constraints would have to be included to guarantee that the locations don't coincide. For example, the constraints |x1 - x2| >  and |y1 - y2| >  would guarantee that both the x and y coordinates are separated by at least where is a positive constant.