CHAP05 - Solutions for Ragsdale 2015 PDF

Preview

Summary

Chapter 5 Network Modeling : Chapter 5 Network Modeling 1. If supplies are represented positive numbers and demands are represented numbers, the rule would be stated as follows: For Minimum Cost Network Apply This Rule Flow Problems Where: At Each Node: Total Supply Total Demand Outflow Inflow Suppl...

Description

Chapter 5 - Network Modeling : S-1 —————————————————————————————————————————————

Chapter 5 Network Modeling 1.

If supplies are represented by positive numbers and demands are represented numbers, the balance-of-flow rule would be stated as follows: For Minimum Cost Network Apply This Balance-of-Flow Rule Flow Problems Where: At Each Node: Total Supply > Total Demand Outflow - Inflow  Supply or Demand Total Supply < Total Demand Outflow - Inflow  Supply or Demand Total Supply = Total Demand Outflow - Inflow = Supply or Demand

2.

Multiply both sides of the constraint by -1 and reverse the sign of the inequality.

3.

See file: Prb5_3.xlsm a.

Total cost = $3,398

1 2 3 4 5 6 7 8 9 b.

d.

Net Flow -80.0

Supply/Demand -80

-50.0

-50

-30.0 -40.0 0.0 0.0 60.0 40.0 50.0

-30 -40 0 0 60 40 50

Total cost = $3,129

1 2 3 4 5 6 7 8 9 c.

Node Newspaper Mixed Paper White Office Cardboard Process 1 Process 2 Newsprint Packaging Print Stock

Node Newspaper Mixed Paper White Office Cardboard Process 1 Process 2 Newsprint Packaging Print Stock

Net Flow -80.0 -50.0 -30.0 -25.4 0.0 0.0 60.0 40.0 50.0

Supply/Demand -80 -50 -30 -40 0 0 60 40 50

In part a, if we assume supply is inadequate the demand (when, in fact, it is adequate) we require all the supply to be used – even if it is not all needed. This results in higher than necessary costs. In part b, assuming supply is adequate to meet demand (when, in fact, it is) resulted in a smaller total cost as this solution does not require all the supply to be used. The shortage on print stock pulp can be reduced to 4 units (without sacrificing newspaper or packing paper pulp) at an additional cost of $307.

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-2 ————————————————————————————————————————————— 4.

Because there is a 10% loss of flow on all arcs going to node 4, a total of 702/0.9 = 780 units must flow into node 4. Thus, we can simply increase the demand at node 4 to 780 and assume no loss of flow occurs on arcs leading into this node. Similarly, only 608/1.05 = 579.05 units must flow into node 5. Thus, we can simply decrease the demand at node 5 to 579.05 and assume no gain of flow occurs on the arcs leading into this node.

5.

-5 1 6

7 4 +4

4

5

2

3

3

+0

9

+8 8

5 5 -7

6.

This is a transportation problem.

3

+5

2 -8

1

6 5 4

+5

5

+5

4 -7

7.

2

3 7

The cost on each arc increases by $2,000. The optimal plan under both leasing options is to replace the equipment at the beginning of years 3 and 5. However, leasing option 2 provides the lowest total cost ($122,965 + $62,000) and is therefore the preferred alternative. See file: Prb5_7.xlsm

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-3 —————————————————————————————————————————————

8.

a. One solution is:

b. 9.

310 feet.

a.

-30

Reg

-40

Reg

-25 -35 -33

$6.5 $7.5 0 $7.00

$8.00 0 Reg 8.2 5 $7.2 $6.7 5 Reg 7.7 5 $7.0 0$7.5 Reg 0 $6.7

Pine Hills

60 Eustis 70

40

Sanfor

5

b. c.

See file Prb5_9.xlsm 20,000 from Region 1 to Pine Hills, 10,000 from Region 1 to Eustis, 40,000 from Region 2 to Pine Hills, 25,000 from Region 3 to Eustis, 35,000 from Region 4 to Sanford, 25,000 from Region 5 to Eustis, 5,000 from Region 5 to Sanford. Total cost $1,132,500.

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-4 ————————————————————————————————————————————— 10. a.

+410 Beg Inv 1

+310

+580

$0

D1

$1.50

lb = 0

3

lb = 50

D2 5

+50

+540

$1.50

D3

$1.50

D4

$1.50

lb = 50

7

lb = 50

9

lb = 50

Fin Inv 10

-120 $49 lb = 400

$45 lb = 400

$46 lb = 400

P1

P2

P3

2

4

6

-500

-520

-450

$47 lb = 400

P4 8

-550

note: lb =lower bound

b. c.

d.

See file Prb5_10.xlsm Produce 420 in month 1, 520 in month 2, 400 in month 3, 450 in month 4, carry 110 in inventory from month 1 to 2, 50 from month 2 to 3, 140 from month 3 to 4, and 50 at the end of month 4. Total Cost = $83,565. Not much, only $45.

11. a. Production costs (per 1000) in January, February, March, April, May and June are $7,100, $7,700, $7,600, $7,800, $7,900, and $7,400, respectively.

Costs for each arc are shown in the spreadsheet. © 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-5 ————————————————————————————————————————————— b. c.

See file: Ship 0 1 0 1 0 1 0 1 6 1 10 1 0 2 0 2 0 2 0 2 13 2 0 2 14 3 0 3 0 3 0 3 6 3 0 3 20 4 0 4 0 4 0 4 0 4 26 5 0 5 0 5 0 5 33 6 3 6 0 6

Prb5_11.xlsm From Jan 13 Jan 14 Jan 15 Jan 16 Jan 17 Jan 18 Feb 13 Feb 14 Feb 15 Feb 16 Feb 17 Feb 18 Mar 13 Mar 14 Mar 15 Mar 16 Mar 17 Mar 18 Apr 14 Apr 15 Apr 16 Apr 17 Apr 18 May 15 May 16 May 17 May 18 Jun 16 Jun 17 Jun 18

To Mar Apr May Jun July Aug Mar Apr May Jun July Aug Mar Apr May Jun July Aug Apr May Jun July Aug May Jun July Aug Jun July Aug

Total Cost

Unit Cost $7,265 $7,320 $7,375 $7,430 $7,485 $7,540 $7,810 $7,865 $7,920 $7,975 $8,030 $8,085 $7,600 $7,720 $7,775 $7,830 $7,885 $7,940 $7,800 $7,935 $7,990 $8,045 $8,100 $7,900 $8,050 $8,105 $8,160 $7,400 $7,555 $7,610 $1,006,675

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-6 ————————————————————————————————————————————— 12. a. Legend: (Cost, Upper Bound)

($20, 50)

C-O

C-N

($156.5, 250)

($135, 200)

150

4

-300

200

($178, 200)

H-O

10 ($159.5, 250)

1 ($20, 50)

Dn-O 5

150

200

11 ($152.5, 250)

($139, 200)

($160.5, 250) ($20, 50)

Da-O

Da-N ($157.5, 250) 9

3

($176, 200)

150

2

8

A-O

($173, 200)

-40

($153.5, 250) ($20, 50)

A-N ($154.5, 250)

6

150

200

12

See file: Prb5_12.xlsm Flow 0 200 0 100 200 0 150 50 0 150 0 150 150 0 200 50 50 50

B-N

200

($132, 200)

b. c.

7

Dn-N

($171, 200)

-400

H-N

($155.5, 250)

($134, 200)

B-O

-3

From 1 Huntington-O 1 Huntington-O 1 Huntington-O 1 Huntington-O 2 Bakersfield-O 2 Bakersfield-O 2 Bakersfield-O 2 Bakersfield-O 7 Huntington-N 7 Huntington-N 7 Huntington-N 7 Huntington-N 8 Bakersfield-N 8 Bakersfield-N 8 Bakersfield-N 8 Bakersfield-N 3 Dallas-O 4 Chicago-O

To 3 4 5 6 3 4 5 6 9 10 11 12 9 10 11 12 9 10

Dallas-O Chicago-O Denver-O Atlanta-O Dallas-O Chicago-O Denver-O Atlanta-O Dallas-N Chicago-N Denver-N Atlanta-N Dallas-N Chicago-N Denver-N Atlanta-N Dallas-N Chicago-N

Cost $139.00 $135.00 $134.00 $132.00 $176.00 $178.00 $171.00 $173.00 $160.50 $156.50 $155.50 $153.50 $157.50 $159.50 $152.50 $154.50 $20.00 $20.00

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-7 ————————————————————————————————————————————— 0 0

5 6

Denver-O Atlanta-O

11 12

Denver-N Atlanta-N

$20.00 $20.00 $220,050.0 0

Total Cost 13. a. 57.429

27.800 37.913

43.7

1

30.825

3

0.0

21.3

4

22.529

5

23.813

6

8.000

+1

36.629

0

17.100

51.613

-1

7

37.000 20.125

16.0

2

35.4

50.329

63.313

77.155

Notes: 0-1 = keep current equipment to use during the coming year 0-2 = trade-in current equipment immediately and use new equipment during the coming year b.

See file: Prb5_13.xlsm The solution is: X01=X13= X37=1 with a minimum total cost of $67,825.

c.

The problem could be made more realistic by considering the tax savings associated with depreciation on the equipment. Also, the current problem does not consider the time value of money (i.e., we might attempt to minimize the net present value of the cash flows). Both of these considerations could be accommodated easily by altering the objective function coefficients.

14. a.

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-8 ————————————————————————————————————————————— NY

17

Chic.

7 6

+1 18

24

18

95

Denver

50

LA

27 19

2

5

32

13

25 30

3

Memp

24

14

5

35

14

35

St Lou

105

4 San Diego

45

1

-1 b.

c.

MIN

5 X12 + 13 X13 + 45 X15 + 105 X17 + 27 X23 + 19 X24 + 50 X25 + 95 X27 + 14 X34 + 30 X35 + 32 X36 + 14 X43 + 35 X45 + 24 X46 + 35 X54 + 18 X56 + 25 X57 + 24 X64 + 18 X65 + 17 X67

ST

-X 12 - X13 - X15 - X17 = -1 +X12 - X23 - X24 - X25 - X27 = 0 +X13 + X23 + X43- X34 - X35 - X36 = 0 +X24 + X34 + X54 + X64 - X43 - X45 - X46 = 0 + X15 + X25 + X35 + X45 + X65 - X54 - X56 - X57 = 0 + X36 + X46 + X56 - X64 - X65 - X67 = 0 + X17 + X27 + X57 + X67 = +1 Xij  0

See file: Prb5_14.xlsm The solution is: X13=X36=X67=1 with a minimum total cost of $62.

15. a. 70 0

Sbo

$24 -$23

$0.5 50 0

Brk

-$25

$0.5 b.

See file Prb5_15.xlsm

ub = 700 Clx b = 350 -$10

Clx

ub = 600 Mln b = 300 -$11

$48 Mln $42

Hvl

-50

$50

Sav

$44 $45

40 0

Pry

30 0

Val

45 0

$43

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-9 ————————————————————————————————————————————— c.

16. a. b.

Ship 250 from Statesboro to Claxton, 450 from Statesboro from Millen, 450 from Brooklet to Claxton, 50 from Brooklet to Hinesville, 250 from Claxton to Perry, 450 Claxton to Valdosta, 400 Millen to Savannah, 50 from Millen to Perry. Total Profit = $12,750. See file: Prb5_16.xlsm

c.

17. a.

b.

18.

Supply nodes: 1, 2 Demand node: 6 Transshipment nodes: 3, 4 & 5 See file: Prb5_17.xlsm The solution is: X13=20, X24=10, X25=30, X36=40, with a minimum total cost of $2,700. MAX

X71

ST

+X71 -X12 - X13 - X14 = 0 +X12 -X23 - X25 = 0 +X13 +X23 +X43 -X35 -X36 - X37 = 0 +X14 -X43 -X46 = 0

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-10 ————————————————————————————————————————————— +X25 +X35 -X57 = 0 +X36 +X46 -X67 = 0 +X37 +X57 +X67 = 0 0  X12  8 0  X13  9 0  X14  7 0  X23  7 0  X25  10 0  X35  8 0  X36  7 0  X37  9 0  X43  6 0  X46  9 0  X57  9 0  X67  11 See file: Prb5_18.xlsm The optimal solution is: X12 = 8, X13 = 9, X14 = 7, X25 = 8, X37 = 9, X46 = 7, X57 = 8, X67 = 7. Maximal flow = 24 tons of sewage per hour. 19. a.

This is a transportation problem. Note that demand exceeds supply by 20 units.

Stores

Warehouses

1

+20

2

+25

3

+30

4

+35

5

1

-30

4 6 5

3 6

-30

2

4 4

4

-30

b.

3

3 2

MIN

5 X11 + 4 X12 + 6 X13 + 5 X14 +3 X21 + 6 X22 + 4 X23 + 4 X24 +4 X31 + 3 X32 + 3 X33 + 2 X34

ST

-X 11 - X12 - X13 - X14 = -30 -X 21 - X22 - X23 - X24 = -30 -X 31 - X32 - X33 - X34 = -30 +X11 + X21 + X31 + XD1  +20 +X12 + X22 + X32 + XD2  +25

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-11 ————————————————————————————————————————————— +X13 + X23+ X33 + XD3  +30 +X14 + X24+ X34 + XD4  +35 Xij  0 c.

See file: Prb5_19.xlsm The optimal solution is: X12 = 25, X14 = 5, X21 = 20, X23 = 10, X34 = 30, XD3 = 20. Minimum total cost = $285. Note that store 3 receives 20 units less than demanded.

d.

Assign arbitrarily large costs (such as $999) to the arcs representing these flows. The optimal solution is then: X13 = 30, X21 = 20, X24 = 10, X32 = 5, X34 = 25. Minimum total cost = $345. Note that store 2 receives 20 units less than demanded.

20. The LP model is: MIN

12 X12 + 8 X13 + 15 X14 + 9 X23 + 16 X25 + 6 X34 + 7 X35 + 12 X54

ST

-X12 - X13 - X14 = -15 -X23 - X25 = -15 +X13 + X23 -X34 -X35 = 0 +X14 + X34 + X54 = 20 +X25 +X35 -X54 = 10 0  Xij  10

The solution is: X13 = 5, X14 = 10, X23 = 5, X25 = 10, X34 = 10 Minimum total cost = $455 See file: Prb5_20.xlsm 21. a.

Dallas

San Diego $750

-1

3/2

$487.5

3/6

+1

3/12

+1

3/20

+1

$487.5 $412.5

-1

$562.5 $750

3/9

$487.5 $487.5 $487.5 $562.5

-1

3/17

$750 $562.5

$487.5

$487.5 $562.5

-1

3/23

$750

3/25 +1

Note: each arc represents a possible round trip ticket departing from nodes with the earliest dates (e.g., we could buy a round trip ticket departing San Diego on March 6, returning to San Diego March 23).

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-12 —————————————————————————————————————————————

b. c.

See file: Prb5_21.xlsm The optimal solution is to buy the following 4 tickets: Leave Dallas March 2, returning March 25 Leave Dallas March 9, returning March 20 Leave San Diego March 6, returning March 17 Leave San Diego March 12, returning March 23 Total cost = $1,875. This saves $1,125 off the full-fare price of $3,000.

22. a.

L.B. = 7.5

-30

Tanker

($0, 999)

Rotterd am

($1.20, 999)

+6

5

Doha 1

($1.40, 999)

0 ($1.35, 999)

Toulon

($0.35, 22.5)

($0.25, 999)

+15 6

Damietta

+0

($0.20, 999) 4 ($0.15, 999)

($0.16, 15) Suez +0

Palermo

($0.27, 999)

+9

2 ($0.28, 999) ($0.20, 999)

3

+0

b. c.

7

P. Said ($0.19, 999)

Legend: (cost, upper bound)

See file: Prb5_22.xlsm Total Cost = $25.43 million

Flow 22.5 7.5 6 1.5

L.B. 0 7.5 0 0

U.B . 22.5 999 999 999

From 0 Doha 0 Doha 1 Tanker 1 Tanker

To 2 1 5 6

Suez Tanker Rotterdam Toulon

Unit Cost ($1,000,000s ) $0.35 $0.00 $1.20 $1.40

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-13 ————————————————————————————————————————————— 0 7.5 15 0 0 7.5 0 13.5 1.5

0 0 0 0 0 0 0 0 0

999 999 15 999 999 999 999 999 999

1 2 2 3 3 3 4 4 4

Tanker Suez Suez Port Said Port Said Port Said Damietta Damietta Damietta

7 3 4 5 6 7 5 6 7

Palermo Port Said Damietta Rotterdam Toulon Palermo Rotterdam Toulon Palermo

$1.35 $0.20 $0.16 $0.27 $0.28 $0.19 $0.25 $0.20 $0.15

© 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Chapter 5 - Network Modeling : S-14 ————————————————————————————————————————————— 23. a.

Atlanta

Los Angeles

-1

1

1

+1

-1

2

2

+1

-1

3

3

+1

-1

4

4

+1

-1

5

5

+1

-1

6

6

+1

-1

7

7

+1

Note: each arc represents a possible round trip flight assignment departing from nodes with the earliest times. See spreadsheet for arc costs. b. c.

See file: Prb5_23.xlsm Leave Atlanta at 6 am Atlanta at 8 am Los Angeles at 5 am Los Angeles at 6 am Atlanta at 4 pm Los Angeles at noon Los Angeles at 2 pm

Return flight leaves at 9 am 5 pm 10 am Noon 7 pm 6 pm 7 pm

Total layover hours...