Problem Solutions

Solutions for Text problems – Dynamic Programming

16.1Knapsack problem -- see dynamic programming file ch16-1.dpp.

Item / Decision / Return / Total Item / Capacity
Stage / Name / Quantity (X) / Function / Return Value / Left
1 / LIGHT / 0 / 4X / 0 / 650
2 / MEDIUM / 4 / 5X / 20 / 170
3 / HEAVY / 1 / 6X / 6 / 10
Total / Return / Value = / 26

4 barrels of medium oil, 1 barrel of heavy oil; profit = $26

16.2 Dynamic programming model

Stage variable i = region

State variable xi = troops left to allocate to regions i to 3

Optimal value function fi(xi) = max{r(di) + fi+1(xi-di)}

di xi

Stopping rule: f1(5)

Stage 3

f3(0) = 0, f3(1) = 160, f3(2) = 360, f3(3) = 600, f3(4) = 880, f3(5) = 1200

Stage 2

x2d2r(d2) + f3(x2-d2)|f2(x2)d2

______|______

00 0 + 0 = 0| 0 0

______|______

10 0 + 160= 160|400 1

1 400 + 0= 400|

______|______

20 0 + 360= 360|5601 or 2

1 400 + 160= 560|

2 560+ 0= 560|

______|______

30 0+ 600= 600|760 1

1 400+ 360= 760|

2 560+ 160= 720|

3 640+ 0= 640|

______|______

40 0+ 880= 880|1000 1

1 400+ 600= 1000|

2 560+ 360= 920|

3 640+ 160= 800|

4 800+ 0= 800|

______|______

50 0+1200= 1200|12801

1 400+ 880= 1280|

2 560+ 600= 1160|

3 640+ 360= 1000|

4 800+ 160= 960|

51040+ 0= 1040|

______|______

Stage 1

x1d1r(d1) + f2(x1-d1)|f1(x1)d1

______|______

50 0+1280= 1280|13601

1 360+1000= 1360|

2 560+ 760= 1320|

3 720+ 560= 1280|

4 840+ 400= 1240|

5 960+ 0= 960|

______|______

1 convoy to Chismayu, 1 convoy to Mogadishu, and 3 convoys to Hargeisa -- 1360 lives saved daily.

16.3See file ch16-3a.lpp.

a.MAX 7X1 + 3X2 + 4X3 + 5X4

S.T. X1 + X2 + X3 + X4  6

X1  5

X2  5

X3  5

X4  5

X1, X2, X3, X4  0 and integer

Decision / Solution / Unit Cost or / Total / Reduced / Basis
Variable / Value / Profit c(j) / Contribution / Cost / Status
1 / PLANT 1 / 5 / 7 / 35 / 0 / basic
2 / PLANT 2 / 0 / 3 / 0 / -2 / at bound
3 / PLANT 3 / 0 / 4 / 0 / -1 / at bound
4 / PLANT 4 / 1 / 5 / 5 / 0 / basic
Objective / Function / (Max.) = / 40

$5 million to plant 1; $1 million to plant 4; $40 million increase in expected annual profit

b.Dynamic programming -- cannot use simple knapsack, because return on $0 invested is $0, which is not proportional to the other units.

Stage variable i = the plant

State variable xi = amount left to allocate to plants i to 4

Optimal value function: fi(xi) = max (ri(di) + fi+1(xi-di)

di xi

di 5

Stopping rule: f1(6)

Stage 4

f4(0) = 0, f4(1) = 11, f4(2) = 16, f4(3) = 21, f4(4) = 26, f4(5) = 31, f4(6) = 31

Stage 3

x3d3r(d3) + f4(x3-d3)|f3(x3)d3

______|______

00 0 + 0 = 0| 0 0

______|______

10 0 + 11= 11|12 1

1 12 + 0= 12|

______|______

20 0 + 16= 16|23 1

1 12 + 11= 23|

2 16+ 0= 16|

______|______

30 0+ 21= 21|28 1

1 12+ 16= 28|

2 16+ 11= 27|

3 20+ 0= 20|

______|______

40 0+ 26= 26|33 1

1 12+ 21= 33|

2 16+ 16= 32|

3 20+ 11= 31|

4 24+ 0= 24|

______|______

50 0+ 31= 31|381

1 12+ 26= 38|

2 16+ 21= 37|

3 20+ 16= 36|

4 24+ 11= 35|

5 28+ 0= 28|

______|______

60 0+ 31= 31|431

1 12+ 31= 43|

2 16+ 26= 42|

3 20+ 21= 41|

4 24+ 16= 40|

5 28+ 11= 39|

6 28 + 0= 28|

______|______

Stage 2

x2d2r(d2) + f3(x2-d2)|f2(x2)d2

______|______

00 0 + 0 = 0| 0 0

______|______

10 0 + 12= 12|120 or 1

1 12 + 0= 12|

______|______

20 0 + 23= 23|24 1

1 12 + 12= 24|

2 15+ 0= 15|

______|______

30 0+ 28= 28|35 1

1 12+ 23= 35|

2 15+ 12= 27|

3 18+ 0= 18|

______|______

40 0+ 33= 33|40 1

1 12+ 28= 40|

2 15+ 23= 38|

3 18+ 12= 30|

4 21+ 0= 21|

______|______

50 0+ 38= 38|451

1 12+ 33= 45|

2 15+ 28= 43|

3 18+ 23= 41|

4 21+ 12= 33|

5 24+ 0= 24|

______|______

60 0+ 43= 43|501

1 12+ 38= 50|

2 15+ 33= 48|

3 18+ 28= 46|

4 21+ 23= 44|

5 24+ 12= 36|

6 24 + 0= 28|

______|______

Stage 1

x1d1r(d1) + f2(x1-d1)|f1(x1)d1

______|______

50 0+ 50= 50|583

1 9+ 45= 54|

2 16+ 40= 56|

3 23+ 35= 58|

4 30+ 24= 54|

5 37+ 12= 49|

6 37+ 0= 37|

______|______

$3 million to plant 1, $1 million to plant 2, $1 million to plant 3, $1 million to plant 4; $58 million increase in expected annual profit.

16.4Knapsack problem -- see file ch16-4.dpp.

a.

Item / Decision / Return / Total Item / Capacity
Stage / Name / Quantity (X) / Function / Return Value / Left
1 / MASHER / 1 / 240X / 240 / 2.2
2 / SMASHER / 0 / 300X / 0 / 2.2
3 / CRUSHER / 1 / 180X / 180 / 1.5
4 / POUNDER / 1 / 380X / 380 / 0
Total / Return / Value = / 800

1 masher container, 1 crusher container, 1 pounder container; profit = $800

b. Integer linear programming

16.5Stagecoach problem -- see file ch16-5.dpp.

From / To / Distance / Cumulative / Distance to
Stage / Input State / Output State / Distance / 19-Sep
1 / BEGIN / 20-Jun / 3000 / 3000 / 24000
2 / 20-Jun / 21-Jul / 5000 / 8000 / 21000
3 / 21-Jul / 20-Aug / 8000 / 16000 / 16000
4 / 20-Aug / 19-Sep / 8000 / 24000 / 8000
From BEGIN / To 19 SEP / Min. Distance / 24000

Keep 20 for June, hire 1 for July, fire 1 in August, fire 1 in September; total cost: $24,000.

16.6Stagecoach problem -- see file ch16-6.dpp.

a.

From / To / Distance / Cumulative / Distance to
Stage / Input State / Output State / Distance / LOS ANGELES
1 / NEW YORK / CLEVELAND / 411 / 411 / 2464
2 / CLEVELAND / CHICAGO / 311 / 722 / 2053
3 / CHICAGO / DENVER / 908 / 1630 / 1742
4 / DENVER / LOS ANGELES / 834 / 2464 / 834
From NEW YORK / To LOS ANGELES / Min. Distance / 2464

b.Total flight time = 2464/420 = 5.87 hrs. = 5 hrs. 52 min.

Total load/unload time (NY, CL, CHI, DEN, LA)= 10hrs.

TOTAL= 15 hrs. 52 min.

Time to prepare aircraft = 24 - 15 hrs. 52 min. = 8 hrs. 8 min.

16.7Production and inventory model -- see file ch16-7a.dpp and ch16-7b.dpp.

a.

Period / Net / Starting / Production / Ending / Setup / Variable Cost / Variable / Total
Stage / Description / Demand / Inventory / Quantity / Inventory / Cost / Function (P,H,B) / Cost / Cost
1 / BEGIN / 0 / 0 / 1 / 1 / 0 / 0 / 0 / 0
2 / APRIL / 1 / 1 / 4 / 4 / 0 / 20000P+800H / $83,200.00 / $83,200.00
3 / MAY / 3 / 4 / 3 / 4 / 0 / 21600P+800H / $68,000.00 / $68,000.00
4 / JUNE / 3 / 4 / 0 / 1 / 0 / 24000P+1000H / $1,000.00 / $1,000.00
5 / JULY / 4 / 1 / 3 / 0 / 0 / 23200P / $69,600.00 / $69,600.00
Total / 11 / 10 / 11 / 10 / 0 / $221,800.00 / $221,800.00

Produce 4 in April, 3 in May, and 3 in July -- total cost = $221,800

b.

Period / Net / Starting / Production / Ending / Setup / Variable Cost / Variable / Total
Stage / Description / Demand / Inventory / Quantity / Inventory / Cost / Function (P,H,B) / Cost / Cost
1 / BEGIN / 0 / 0 / 1 / 1 / 0 / 0 / 0 / 0
2 / APRIL / 1 / 1 / 4 / 4 / 0 / 20000P+800H+2000B / $83,200.00 / $83,200.00
3 / MAY / 3 / 4 / 3 / 4 / 0 / 21600P+800H+2000B / $68,000.00 / $68,000.00
4 / JUNE / 3 / 4 / 0 / 1 / 0 / 24000P+1000H+2000B / $1,000.00 / $1,000.00
5 / JULY / 4 / 1 / 3 / 0 / 0 / 23200P / $69,600.00 / $69,600.00
Total / 11 / 10 / 11 / 10 / 0 / $221,800.00 / $221,800.00

Same solution as part a.

16.8

Define: CC = renovate child care center, FF = refurbish high school football filed, GC = make improvements to the gerontology center, and TC = repave tennis courts

f.Using a dynamic programming model approach -- see file ch16-8f.dpp.

From / To / Distance / Cumulative / Distance to
Stage / Input State / Output State / Distance / FINISH
1 / BEGIN / CL-CC / 285 / 285 / 605
2 / CL-CC / P-FF / 95 / 380 / 320
3 / P-FF / CR-GC / 150 / 530 / 225
4 / CR-GC / T-TC / 75 / 605 / 75
5 / T-TC / FINISH / 0 / 605 / 0
From BEGIN / To FINISH / Min. Distance / 605

16.9See file ch16-9.dpp.

From / To / Distance / Cumulative / Distance to
Stage / Input State / Output State / Distance / FINISH
1 / YR1 / YR2-1 / 120 / 120 / 401
2 / YR2-1 / YR3-2 / 26 / 146 / 281
3 / YR3-2 / YR4-1 / 86 / 232 / 255
4 / YR4-1 / YR5-2 / 26 / 258 / 169
5 / YR5-2 / YR6-1 / 97 / 355 / 143
6 / YR6-1 / YR7-2 / 26 / 381 / 46
7 / YR7-2 / YR8-3 / 20 / 401 / 20
8 / YR8-3 / FINISH / 0 / 401 / 0
From YR1 / To FINISH / Min. Distance / 401

YearDecision Branch

1Purchase(Year 1 - Year 2-1)

2Keep(Year 2-1 - Year 3-2)

3Purchase(Year 3-2 - Year 4-1)

4Keep(Year 4-1 - Year 5-2)

5Purchase(Year 5-2 - Year 6-1)

6Keep(Year 6-1 - Year 7-2)

7Keep(Year 7-2 - Year 8-3)

Total cost = $401,000