|
Chapter 7 | 
|
DYNAMIC PROGRAMMING
Problems 7.1 to 7.5 | Problems 7.6 to 7.10 | Problems 7.11 to 7.18
problem7.6 | problem7.7 | problem7.8 | problem7.9 | problem7.10
7-6(3). The optimum equipment replacement policy for a 12 year period is to be determined for a process with the following annual net profit listed below. Also given is the effect of inflation on the construction of a new process and the salvage value.
Solution:
The dynamic programming optimization is shown in Soln 7-6. In this case, a stage is the time period of one year. The optimal policy for the 12 year period is also shown in Soln 7-6 which gives the optimal decision each year and the maximum profit for the 12 years.
The following describes the partial optimization to obtain fi at several stages.
Stage 1 : 12th year
The dynamic programming algorithm is:
R1(s1) = R1(t) = net profit for operating a plant s1 = t years old for one year is the keep decision. The net profit is given in the table
as a function of time.
R1(0) - C + S = net profit for operating a new plant
15 - 16 + 0 = 1 R1(0) less the construction cost, C, plus the salvage value, S, at the start of the 12th year is the replace decision.
The partial optimization is given in Soln
7-6 where the decision is to keep the existing plant and operate it
for one more year until the profit is less than 0 units.
Stage 2 : 11th year
The dynamic programming algorithm is:
R2(s2) + f1(s1)- = net profit for operating a plant s2=t years old for one more year plus the optimal return from the following year
f1(s1) = f1(t+1).
R2(0) - C + S + f1(1) = net profit for operating a new plant R2(0) less
15 - 16 + 0 + 14 = 13 the construction cost, C, plus the salvage value, S, plus the optimal return from the following year for a one
year old plant f1(1).
The partial optimization at stage 2 is given in the table in Soln 7-6. At this stage the optimal decision is to keep the existing plant for one more year until the profit is less than 13 units.
The same procedure is used to obtain the partial optimizations for stages 3 through 11 as shown in Soln 7-6.
At stage 12 the dynamic programming algorithm has to be applied for one value of the state variable s12 = t = 0, a new plant. Then the optimal solution can be obtained by using the tabulated partial optimizations as shown by the underlines in the table.
The optimal decisions and maximum profit are shown in Soln 7-6.
7-7. The refinery process for alkylation employs identical stirred reactors in series. A feed of isobutane and butene are catalytically reacted to produce a main product of iso-octane. The fresh catalyst, 98% sulfuric acid, enters the first reactor and flows through the other reactors. As it passes through each reactor, it is degraded, and the concentration decreases. The concentration in the last reactor in the series must be at least 88%, to prevent polymerization rather than alkylation. A refinery has three stirred alkylation reactors as shown in Figure 7-32. The optimal feed rates to each reactor are needed which maximize the profit from the alkylation process. Since the reactors are identical, the profit (return) function for each reactor is the same. This profit function is shown in the figure along with the catalyst degradation function which gives the decrease in catalyst concentration across each reactor as a function of reactor feed rate.
Apply the dynamic programming algorithem at each stage, and with this information determine the optimal reactor feed rates, sulfuric acid catalyst concentrations and the maximum profit.
Solution:
Using the information given in Figure 7-32, the functional diagram and tables from the dynamic programming partial optimization can be developed.
The following information summarizes the calculations at each stage.
Stage 1: The dynamic programming algorithm is:
where d1 is the feed rate and s1 is the catalyst concentration leaving the reactor.
s1 = s1 - DC
where DC is obtained from the graph given in Figure 7-32. Values of the state variable s1 were selected to vary from 98% to 90% H2SO4. As shown in the following table, an optimal decision for the feed rate d1 was selected to maximize the profit. Results are given for s1=98, and the other values in the tables were computed the same way.
Stage 2: The dynamic programming algorithm is:
The values of the state variable s2 were selected to vary from 98% to 92% H2SO4. As shown in the following table, an optimal decision for the feed rate was selected which maximizes the return from stages 1 and 2. Results are given for s2 = 98, and the other values in the table were computed the same way.
Stage 3: The dynamic programming algorithm is:
The state variable s3 has only one value, 98% H2SO4, at this stage. The results of the partial optimization are shown below and in the table above.
To determine the optimal values at stage 1 and 2, it is necessary to interpolate between the values given in the tables to determine the optimal policy.
7-8(10). Solve the following initial value problem by dynamic programming.
where Ri(si,di) = si + 3di for i = 1, 2, ..., 5
si-1 = si = 2si - 0.2di
0 < di < si
and the initial state variable s5 = 100.
Solution:
For this problem, an analytical equation can be obtained at each stage for fi(si). Then reaching stage 5, the value of f5 can be calculated. Beginning at stage 1, the dynamic programming algorithm is:
Stage 1:
and
so =
1 = 2s1 - 0.2s1 = 1.8s1
Stage 2:
using
s1 =
gives
f1(s1) = 4s1 = 4(2s2 - 0.2d2) = 8s2 - 0.8d2
or
Stage 3:
using
s2 =
gives
f2(s2) = 11.2(2s3 - 0.2d3) = 22.4s3 - 2.24d3
and
Stage 4:
using
s3 =
gives
f3(s3) = 24.16(2s4 - 0.2d4) = 48.32s4 - 4.832d4
and
Stage 5:
using
s4 =
gives
f4(s4) = 49.32(2s5 - 0.2d5) = 98.64s5 - 9.864d5
and
The results of the above can be summarized as follows:
f1(s1) = 4s1 s1 = 1.8s2 d1 = s1
f2(s2) = 11.2s2 s2 = 1.8s3 d2 = s2
f3(s3) = 24.16s3 s3 = 2.0s4 d3 = s3
f4(s4) = 49.32s4 s4 = 2.0s5 d4 = 0
f5(s5) = 99.64s5 s5 = 100 d5 = 0
Then, using s5 = 100 the following results are obtained.
Stage 5: s5 = 100 d5 = 0
f5(s5) = 99.64s5 = 9964
Stage 4: s4 = 2s5 = 200 d4 = 0
f4(s4) = 49.32s4 = 9864
Stage 3: s3 = 2s4 = 400 d3 = s3 = 400
f3(s3) = 24.16s3 = 9664
Stage 2: s2 = 1.8s3 = 720 d2 = s2 = 720
f2(s2) - 11.2s2 = 8064
Stage 1: s1 = 1.8s2 = 1296 d1 = s1 = 1296
f1(s1) = 4s1 = 5184
7-9(10). It is desired to optimally allocate a total of 7.0 units of a resource to four stages of a dynamic programming serial system. The return function at each stage is given by the following equations and the problem can be stated as:
Ri(xi) = 8xi - ixi2 and xi has integer values of 0, 1, 2, 3.
Solution:
The functional diagram and tables from the dynamic programming partial optimization are given in Soln 7-9. The calculations to obtain the results in the table are as follows.
Stage 1:
s1 = d1 = x1 0 < s1 < 3
R1 = (8x1 - x12)
There is no partial optimization at this stage since the state and decision variable are the same.
f1(x1) : 0 7 12 15
x1 : 0 1 2 3
Stage 2:
s2 = x1 + x2 0 < s2 < 6
d2 = x2 0 < d2 < 3
R2 = 8x2 - 2x22
R2 : 0 6 8 6
x2 : 0 1 2 3
Stage 3:
s3 = x1 + x2 + x3 0 < s3 < 7
d3 = x3 0 < d3 < 3
s2 = x2 + x3 0 < s2 < 6
R3 = 8x3 - 3x3²
R3 : 0 5 4 -3
x3 : 0 1 2 3
s3 d3 s2
Stage 4:
s4 = x1 + x2 + x3 + x4 = 7
d4 = x4 0 < d4 < 3
s3 = x1 + x2 + x3 0 < s3 < 7
R4 = 8x4 - 4x4²
R4 : 0 4 0 -8
x4 : 0 1 2 3
s4 d4 s3
Tthe optimal solution is:
x1* = 3, x2* = 2, x3* = 1, x4* = 1, P* = 32
7-10. Consider the three stage, dynamic programming functional diagram shown in Figure 7-4. The functional diagram represents the transition function, incident identities and dynamic programming algorithm. The total profit from the process is:
P = R1(s1,d1) + R2(s2,d2) + R3(s3,d3)
a. Formulate the profit function, P, as a function of the decision variables illustrating the technique of direct substitution from the classical theory of maxima and minima, and state how the optimum is to be found.
b. Formulate the Lagrangian function illustrating the technique of Lagrange multipliers, and state how the optimum is to be found.
c. Give the dynamic programming algorithm at each stage, and discuss how the optimum policy is found.
d. Discuss the merits and difficulties in implementing each of the above three methods as applied to an industrial problem.
Solution:
The functional diagram for a three stage process is shown in Figure 7-4.
Profit function P = R1(s1,d1) + R2(s2,d2) + R3(s3,d3)
a. Formulate the profit function as a function of the decision variables illustrating direct substitution. The transitional functions and incident identities are:
Combining s1 = T2(s2,d2) and s2 = T3(s3,d3) gives:
s1 = T2[T3(s3,d3),d2]
Substituting into the profit function gives:
P = R1 { T2[T3(s3,d3),d2],d1 } + R2[T3(s3,d3),d2] + R3(s3,d3)
The partial derivatives of P with respect to d1, d2, d3 and s3 are set equal to zero and the resulting set of equations are solved for the stationary points. Then sufficiency conditions are used to determine the character of the stationary points, maxima, minima or saddle points.
b. The constraint equations are
s2 = T3(s3,d3)
s1 = T2(s2,d2)
The Lagrangian function is:
L(d1, d2, d3, s1, s2, s3, l1, l2) = R1(s1,d1) + R2(s2,d2) + R3(s3,d3) + l1[s2 - T3(s3,d3)] + l2[s1 - T2(s2,d2)]
Note: 1
= T1(s1,d1) is not a constraint equation
unless s1 is a specified constant or is bounded.
To obtain the optimum, the Lagrangian function L is differentiated with respect to d1, d2, d3, s1, s2, s3, l1 and l2; and the resulting set of equations are set equal to zero to locate the stationary points.
c. The dynamic programming algorithm at each stage is:
The values f1(s1), f2(s2) and f3(s3) are computed at each stage. At stage three, the maximum value of f3(s3) is selected. The optimum policy is the computed using the transition functions.
d. Analytical Methods: If economic and process models are simple and analytical, the necessary algebraic manipulations can be performed. If this is not the case, the method cannot be used, but a search technique can be used.
Lagrange Multipliers: If the economic and process models are analytical and differentiatiable, the Lagrangian function can be formed, derivatives set to zero, and the resulting equation solved. If this is feasible, the method can be used. If not, then a search technique may be used.
Dynamic Programming: If the economic and process models can be formulated into a stage structure, then the dynamic programming algorithm can be used. It is not necessary for the function to be analytic or differentiable. Also, single or multivariable search techniques can be used at each stage.