|
Chapter 7 | 
|
DYNAMIC PROGRAMMING
Problems 7.1 to 7.5 | Problems 7.6 to 7.10 | Problems 7.11 to 7.18
problem7.11 | problem7.12 | problem7.13 | problem7.14
problem7.15 | problem7.16 | problem7.17 | problem7.18
7-11(10). Find the shortest and longest path from 0 to P in Figure 7-33. No backward movement (toward 0) is allowed.
Solution:
The results of the partial optimizations for the shortest and longest paths are shown on the diagram in Soln 7-11. The length of the shortest path is 29 and the longest path is 73. The half arrows indicate the direction of these paths.
7-12. Solve problem 7-7, but have four stirred reactors in series instead of three. Use the same upper limit on the catalyst concentration of 98% entering but have 87% > leaving.
Solution:
The dynamic programming partial optimizations are available for the first two stages in problem 7-7. It is only necessary to expand the partial optimization at stage 3 and perform the no-state, one decision partial optimization at stage 4.
Stage 3: The dynamic programming algorithm is:
The values of the state variable s3 are slected to vary from 98% to 94% H2SO4. As shown in the following table, an optimal decision for the feed rate d3 is selected which maximizes the return from stages 1, 2, and 3. The range on d3 is from 5 to 20.
Stage 4: The dynamic programming algorithm is:
The state variable s4 has only one value, 98%. The optimal value of d4 is determined as shown in the following table.
The results of the partial optimization are shown in the table in Soln 7-12. The optimal profit is 310, and the optimal policy is to have the feed rate be 10 units to each reactor.
7-13a. Extend the optimal equipment replacement problem 7-6, to determine the optimal equipment replacement policy over a ten year period starting with a process that is now two years old.
b. Extend the optimal equipment replacement illustration, Example 7-6, to determine the optimal equipment replacement policy over a ten year period starting with a process that is now two years old.
Theoretically, decision inversion would be required since s1 is less than 88%. However, s1 = 87.6%, and this is sufficiently close to the initial value of 88% not to use decision inversion.
Solution:
a. The dynamic programming optimization is shown in Soln 7-6 for problem 7-6. The tables for stages 1 through 10 are the same as those for problem 7-6; and a stage is the time period of one year. Also, the optimal solution is the same for the two year old plant over a ten year period as for the new plant over a 12 year period in problem 7-6 since the decisions are to keep in the first two years. From problem 7-6, the optimal profit is 104, and the optimal policy is:
Stage: 10 9 8 7 6 5 4 3 2 1
Decision: k k k k r k k k k k
Time(start of year): 1 2 3 4 5 6 7 8 9 10
b. The dynamic programming optimization is shown in Soln 7-13 for the extension of example 7-6. The first five stages are the same as those shown in Figure 7-26, and the second five stages were computed using the same procedure. The optimal profit is 63, and the optimal policy is k, k, r, k, k, k, r, k, k, k.
7-14. In Figure 7-34, the process flow diagram is given for a simplified pentane isomerization plant. This was taken from a description(13) of Phillips Petroleum Company's plant which produces 16,000 barrels per day of 95% isopentane from a reactor feed of 26,000 barrels per day of 85% normal pentane. The reactor uses a platinum catalyst and can operate in a temperature range between 700oF and 900oF and with a pressure above 200 psig. The feed preparation facility is a distillation column, and the reflux ratio controls the purity of the normal pentane separated from the mixture of normal pentane and other hydrocarbons in the feed. The temperature of the normal pentane stream is increased in the heater to the optimum reactor temperature and pressure, and it is fed to the reactor along with hydrogen. Then the reactor product goes to a separator where the hydrogen is removed and recycled. The purification of the product is completed in two distillation columns where the reflux ratios control the the removal of the other hydrocarbons in the stabilizer column and the separation of isopentane and normal pentane in the pentane splitter column. The unreacted normal pentane is recycled to the heater as shown on the diagram.
Develop the dynamic programming functional diagram from the process flow diagram assuming that economic and process models are available in a convenient form. Define the state and decision variables and explain how the dynamic programming optimization will be performed. To perform this analysis consider that the flowrate and composition to the feed purification distillation column are fixed and that the separation in the column is controlled by the reflux ratio. The conversion of normal pentane to isopentane is controlled by the reactor temperature and pressure as is the amount of other hydrocarbons produced by side reactions. Also the separation in the stabilizer and pentane splitter distillation columns is controlled by the reflux ratio on each column. The isopentane produced must have a purity of at least 95%. The heater and the hydrogen separator can be treated as decisionless stages, and the flow rate of for recycle hydrogen is computed by a material balance and is not a state or decision variable.
Solution:
The dynamic programming functional diagram is shown in Soln 7-14. The two decisionless stages, the heater and separator, are combined with the reactor. The state and decision variables are defined on the diagram for this initial value problem. The following describes the type of dynamic programming partial optimization at each stage. At stage 1, the pentane splitter column, there is a two state, one decision partial optimization. The return is the net of the sale of isopentane and the operating costs for the column. At stage 2, the stabilizer column, there is a two state, one decision partial optimization. At stage 3, the combined heater, reactor and separator, there is a two state, two decision partial optimization. The n-pentane flow rate at this stage is the sum of the flow rate from the feed purification column and the amount recycled from the pentane splitter column. At stage 4 there is a no state, one decision partial optimization where the feed to the feed purification column is known and constant.
7-15. A chemical process uses a piece of equipment that is affected by corrosion which uses deterioration in performance. The net annual profit obtained from operating the equipment is given by the following equation:
where t can have integer values of 0, 1, 2, 3 and 4. For equipment that is more than four years old, the performance has declined to the point where no profit is made, and the equipment has no salvage value. The replacement cost with new equipment is 22. If a decision is to be made annually to keep the current unit or to replace it, determine the optimal policy for the equipment replacement for the next five years with the equipment being one year old at the start.
Solution:
The value of the profit function is given below for each of the years.
time t 0 1 2 3 4 5
P(t) 26 23½ 20 15½ 10 0
This information is used for the partial optimization at each stage.
Stage 1: The dynamic programming algorithm is:
As shown in the table for Stage 1 at the end of this problem, the optimal decisions are to keep for values of the state variable from 1 through 4 and to replace for 5.
Stage 2: The dynamic programming algorithm is:
The values of the keep decision for year 1 through 3 are:
t 1 2 3
P(t) + f1(t+1) 23½ + 20 = 43½ 20 + 15½ = 35½ 15½ + 10 = 25½
These results are incorporated with those of Stage 1 at the end of this problem.
Stage 3: The dynamic programming algorithm is:
The values of the keep decision for years 1 through 3 are:
t 1 2 3
P(t) + f2(t+1) 23½ + 35½ = 59 20 + 27½ = 47½ 15½ + 27½ = 43
These results are incorporated with those of Stages 1 and 2 the end of this problem.
Stage 4: The dynamic programming algorithm is:
The values of the keep decisions for years 1 through 3 are:
t 1 2 3
P(t) + f3(t+1) 23½ + 47½ = 71 20 + 47½ = 67½ 15½ + 47½ = 63
These results are incorporated with those of the previous stages on below.
Stage 5: The dynamic programming algorithm is:
The values of the keep decision for years 1 through 3 are:
t 1 2 3
(t) + f4(t+1) 23½ + 67½ = 91 20 + 63 = 83 15½ + 63 = 78½
These results are incorporated with those of the previous stages below.
The maximum profit is 91 units and the optimal decisions are:
Stages: 5 4 3 2 1
Decisions: k k r k k
7-16. Solve the following four stages, final value, serial dynamic programming problem using decision inversion.
where: Ri = si + 3di return function
si = 2si - 0.2di transition function
si = si-1 incident identity
s1 = 2,400 specified final value,
1
0 < s4 < 200 bounds on initial value, s4
for i = 1, 2, 3, 4
Solution:
The partial optimizations at each stage are as follows:
Stage 1:
Using s1 = 2400 = 2s1 - 0.2d1 or d1 = 10s1 - 12000 and substituting above, gives:
f1(s1) = 31s1 - 36000 There is no partial optimization from decision inversion.
Stage 2:
Substituting for f1(s1) from Stage 1 gives:
Using s1 = 2 = 2s2 - 0.2d2 and substituting above, gives:
To maximize f2(s2), have d2 = 0; and this gives:
f2(s2) = 63s2 - 36000
Stage 3:
Substituting for f2(s2) from Stage 2 gives:
Using s2 = 3 = 2s3 - 0.2d3 and substituting above, gives:
To maximize f3(s3), have d3 = 0; and this gives:
f3(s3) = 127s3 - 36000
Stage 4:
Substituting for f3(s3) from Stage 3 gives:
Using s3 = 4 = 2s4 - 0.2d4 and substituting above, gives:
To maximize f4(s4), have d4 = 0 and s4 = 200; and this gives:
f4 = 255(200) - 36000 = 15000
Now the optimal solution can be determined as shown below.
Stage 4:
f4 = 15,000
s4 = 200
d4 = 0
s4 = 400
Stage 3:
f3 = 14,800 s3 =
s3 = 400 f3 = 127(400) - 36000 = 14800
d3 = 0 s3 = 2s3 - 0.2d3
s3 = 800 s3 = 2(400) - 0.2(0) = 800
Stage 2:
f2 = 14400
s2 = 800 f2 = 63(800) - 36000 = 14400
d2 = 0 s2 = 2s2 - 0.2d2
s2 = 1600 s2 = 2(800) - 0.2(0) = 1600
Stage 1:
f1 = 13600
s1 = 1600 d1 = 10s1 - 12000
d1 = 4000 d1 = 10(1600) - 12000 = 4000
s1 = 24000
7-17. Solve the following cyclic optimization problem by dynamic programming.
where: Ri = si + 3di for i = 1, 2, 3, 4
si-1 = si
s4 = si cyclic optimization
s4 < 100
Solution:
The partial optimizations at each stage are as follows:
Stage 1: Decision inversion is required and s1 is known. The dynamic programming algorithm is:
Using s1 = 2s1 - 0.2d1, d1 = 10s1 - 5s1 and substituting above, gives:
There is no partial optimization with decision inversion.
Stage 2: This stage is combined with stage 1. The dynamic programming algorithm is:
Substituting for f1(s1) from stage 1, gives:
Using s1 = 2
= 2s2 - 0.2d2 and substituting above, gives:
To maximize f2(s2), have d2 = 0; and this gives:
f2(s2) = 63s2 - 15
Stage 3:
Substituting for f2(s2) from stage 2 gives:
Using s2 = s3 = 2s3 - 0.2d3 and substituting above, gives:
f3(s3) = max[127s3 - 9.6d3 - 15
To maximize f3(s3), have d3 = 0; and this gives:
f3(s3) = 127s3 - 15
Stage 4: At this stage, s4 = s1 for cyclic optimization.
Substituting for f3(s3) from stage 3 gives:
Using s3 = s4 = 2s4 - 0.2d4 and substituting above, gives:
To maximize f4(s4) have d4 = 0, and this gives:
f4(s4) = 255s4 - 15s1
Now cyclic optimization requires s4
= 1,
and this gives:
f4(s4) = 255s4 - 15s4 = 240s4
To maximize f4 use the largest value of s4 i.e. s4 = 100, and this gives:
f4 = 24,000
Using the results of the partial optimization at each stage, the state and decision variables can be computed and determined as follows.
Stage 4:
f4 = 24,000
s4 = 100
d4 = 0
Stage 3:
f3 = 23,900 s3 =
s3 = 200 f3 = 127(200) - 15(100) = 23,900
d3 = 0 s3 = 2s3 - 0.2d3 = 400
Stage 2:
f2 = 23,700 s2 =
s2 = 400 f2 = 63(400) - 1500 = 23,700
d2 = 0
Stage 1:
f1 = 23,300 s1 =
s1 = 800 f1 = 31(800) - 1500 = 23,300
d1 = 7500 d1 = 10s1 - 5s1 = 10(800) - 5(100) = 7,500
7-18. For a process the net profit is given in the following table for a ten year period. Also, the sum of the cost of construction of a new process and the salvage value of the old process is given in the table with approximations for the effects of inflation, taxes, etc. Determine the maximum profit and the optimal equipment replacement policy for a five year period for the two cases of starting with a new plant and starting with a five year old plant.
Solution:
Stage 1: The dynamic programming algorithm is:
where: R1(t) = net profit made at the end of the tenth year
R0(0) = net profit from operating a new plant = 23
C(t) = net of the new process construction cost and salvage value
The results of the partial optimization at stage 1 are shown in Soln 7-18.
Stage 2: The dynamic programming algorithm is:
The results of the partial optimization at stage 2 are shown in Soln 7-18.
Stage 3: The dynamic programming algorithm is:
The results of the partial optimization at stage 3 are shown in Soln 7-18.
Stage 4: The dynamic programming algorithm is:
The results of the partial optimization at stage 4 are shown in Soln 7-18.
Stage 5: The dynamic programming algorithm for a new plant is:
Replace is not a decision with a new plant. The optimal decisions are: keep, keep, replace, keep, keep; and maximum profit is $106,000.
The dynamic programming algorithm for a 5 year old plant is:
f5(5) = max R5(5) + f4(6) = 16 + 79 = 95 keep
d5 = k or r R(0) - C(0) + f4(1) =
23 - 5 + 83 = 101 replace
The optimal decisions are: replace, keep, replace, keep, keep; and maximum profit is $101,000.