Chapter 7

DYNAMIC PROGRAMMING

• Introduction
  • Variables, Transforms, and Stages
• Serial System Optimization
  • Initial Value Problem
  • Final Value Problem
  • Two-Point Boundary Value Problem
  • Cyclic Optimization
• Branched Systems
• Diverging Branches and Feed Forward Loops
• Converging Branches and Feed Back Loops
• Procedures and Simplifying Rules
• Application to the Contact Process - A Case Study
• Brief Description of the Process
• Dynamic Programming Analysis
• Results
• Optimal Equipment Replacement - Time as a Stage
• Optimal Allocation by Dynamic Programming
• Closure
• References
• Problems

An important optimization problem is the planning required to obtain the maximum profit from a plant over its life. A new plant must recover the construction costs and provide a competitive return on investment through the years that it operates. As the plant ages, maintenance costs increase, new technology brings on obsolescence, tax structure changes, and the cost of raw materials and the sales prices of products change. These and other related factors affect the decision about investing in a new plant or continuing to operate an existing plant.

     Dynamic programming provides an excellent framework to structure the decisions about a plant to maximize the total profit over time. The concepts required to use this method are the same regardless of the time span or the complexity of the economic model used to predict the profitability of the plant through time. Also, if uncertainties about future prices, costs interest rates, etc. can be estimated, then a stochastic version of the optimization algorithm can be used, as described by Roberts(3).

      The following example illustrated using a span of time as a dynamic programming stage. Decisions about whether to continue to operate the plant or replace it with a new plant will be based on an annual evaluation of a simple linear economic model. and a five year period will be used as the total time to determine the maximum profit. With this simple model and annual evaluation, the concepts can be emphasized. The economic model can be evaluated readily, and the time span does not require excessive computations and is not restrictive. Depending on need and available information, the economic model can contain all of the factors mentioned in the previous paragraph and others as well. Also, the time between evaluations, the dynamic programming stage, can be selected to be appropriate for the analysis as can the total time for the evaluation. In addition, once the optimization analysis has been formulated, ti could be up-dated as new information becomes available to provide a better set of future decisions. Finally, the procedure is not limited to a plant; it applies equally well to a process or equipment used in a plant.

Example 7-6

Information about the annual net profit from the operation of a process over a 12 year is shown in Figure 7-25 where the process operates at break-even in year ten and the following years. For convenience, the cost to replace the process with a new one using modern technology is taken to be equal to the net profit made in the first year of operation of the new process, i.e., $10,000. At the beginning of each year an annual review is held, and a decision is made to either continue to operate the process or replace it with a new modern one to have a maximum profit over a five year period. The process is currently four years old, and it is necessary to determine the best decision now and for each of the following four years to maximize the profit, i.e., determine the optimal replacement policy.

     The procedure begins by considering the possible decisions to be made at the start of the fifth year (end of the fourth year), i.e., either to keep or replace the process. Stage one is the time period from the beginning to the end of the fifth year. The dynamic programming algorithm at stage one can be written as:

where the decision, d₁, is to keep or replace the process to maximize the profit, R₁(s₁,d₁). Also the profit depends on the age of the process, the state variable s₁. The optimum decisions are listed in Figure 7-26 for stage one as a function of the state variable, and they are to keep the process operating. The range of state variables goes from a process one year old to having a process ten years old at the start of the fifth year. In the case of a ten year old process there is a tie between keeping the process and replacing it with a new one, and the decision made here is the one that is easier, i.e., keep the process operating. The values shown in Figure 7-26 were obtained from Figure 7-25. The output state variable from stage one s₀ is the age of the process at the end of the year.

     At stage two the optimal decisions are made that maximize the sum of the return at stage 2 and the optimal return from stage one for a range of values of the state variable at stage two. The dynamic programming algorithm at stage two is:

If the decision is to keep the process, the optimal return, f₂(t), is the sum of, R₂(t), the return during the fourth year for a process t years old and f₁(t+1), the optimal return from stage one for a process whose age is in t+1. If the decision is to replace the process the optimal return f₂(t) is the sum of the cost of a new process, -10, the profit from operating a new process for a year, R(0) = 10 and the optimal return from stage one for a process one year old, f₁(1). The optimal decisions are shown in Figure 7-26 at stage 2 for a process whose age can be from one to seven years, s₂. As seen in the figure, the optimal decisions are to continue to operate the process if its age is from one to five years old. However, if the process is six years old or older, the profit will be larger for the fourth and fifth years if the process is replaced with a new one.

     The same procedure is used at stage 3 to determine the maximum profit for the third, fourth, and fifth years. The dynamic programming algorithm is

The optimal decisions for stage 3 are shown in Figure 7-26. At this stage the optimal decisions are to continue to operate the process if its age is from one to three years old; and if it is older, the maximum profit over the three year period will be obtained by replacing the process with a new one.

     Continuing to stage four the procedure is repeated to determine the maximum profit for the four year period. the dynamic programming algorithm to determine the optimal decisions for various age processes (the state variable) is:

     Based on Figure 7-26, the optimal decisions are to continue to operate the process if it is from one to three years older and to replace it with a new one if it is older.

     The results for the final, fifth stage are obtained the same way as previously. However, it is necessary to consider only one value of the state variable, the existing four year old process. The dynamic programming algorithm is as follows:

     As shown in Figure 7-26 the maximum profit for the five year period is $30,000 for a four year old process and the optimal decisions are to keep the process for the first year, to replace it with a new one at the start of the second year and to operate this new process for the remaining three years. Also shown in the table are other cases that were obtained using the dynamic programming algorithm for processes that are one, two, three and five years old. For example for a one year old process the maximum profit would be $35,000, and the optimal decisions would be to continue to operate it for the five year period. However, had the process been five years old the maximum profit would be $30,000; and the optimal decisions would be to replace the existing process with a new one and operate it for the five year period. Consequently, the dynamic programming algorithm generated other possibly useful information without significant additional computational effort.

     In summary, a time span can be used as a stage for the dynamic programming algorithm to establish an optimal set of decisions that maximize the profit over a specified length of time. The previous example illustrated the computational algorithm, and the methodology is the same for more elaborate economic models and different time spans for a state and number of stages. Also, having once been performed, the optimization is readily modified as additional information becomes available. The discussion will continue for a related type of dynamic programming optimization, the optimum allocation problem.

A problem frequently encountered is to determine the best way to distribute a limited amount of resources among competing, profitable processes. These resources are frequently raw materials or money to purchase raw materials used to manufacture products. Also, at the process level, the problem may take the form of the best way to distribute raw material among processes to produce the range of products manufactured at the plant. Linear programming provided one method of making these distributions to maximize the profit when all of the equations were linear. This is not a restriction for dynamic programming.

     The optimal allocation problem requires the specifying the total amount of the resource to be distributed and an expression that gives the profit (or cost) at each stage. A stage might be a plant, a process or a part of a process. A diagram is given in Figure 7-27 to describe the procedure, and the key to the solution of optimal allocation problems is the definition of the state variables. At stage one the state variable is the amount of the resource allocated to this stage, and it has to range from using all of the resource in the stage to using none of it here. The decision variable is the same as the state variable at stage 1. However, from stage 2 through stage N the state and decision variables are different. The decision variable d_i is the amount of the resource allocated to stage i, but the state variable is the amount of the resource allocated to stage i plus the amount remaining to be optimally distributed over the previous stages from i-1 to 1. The state variable s_i varies from allocating all of the resource to the i stages to allocating none to these stages. At stage N the state variable is equal to the total amount of the resource to be allocated to the N stage, and the decision variable is the amount of the resource allocated to stage N to maximize the profit from all N stages. It is necessary to perform only the partial optimization with the dynamic programming algorithm, using the value of the state variable s_N equal to the total amount of the resource available for the N stages (an initial value problem).

     Optimum resource allocation by dynamic programming optimization is illustrated in the following example where a limited amount of feed is to be distributed among three chemical reactors. Also, a more detailed discussion is given by Roberts (3), and Problem 7-9 is a mathematical form of the optimal allocation problem.

Example 7-7

The total feed to be distributed among three chemical reactors operating in parallel is 700 lb per hour. Each reactor has a different catalyst, and the operating conditions of temperature and pressure vary to be able to produce a required set of products. The profit for each reactor is determined by the feed rate, and the parameters in the return function for each reactor are determined by the catalyst and operating conditions as shown below.

R₁ = 0.08F₁ - (F₁/100)²

R₂ = 0.08F₁ - 2(f₂/100)²

R₃ = 0.08F₁ - 3(f₃/100)²

     The problem is one of determining the best distribution of the feed among three reactors to maximize the profit. The process flow diagram, the dynamic programming functional diagram and the stage partial optimizations are shown in Figure 7-28.

     Beginning at stage one the optimal decision is the amount of feed to be allocated to chemical reactor one that maximizes the profit at stage one. It turns out that the state variable is the same as the decision variable, but all possible values of the state variable have to be considered. These range from allocating all of the feed to stage one to none of the feed to stage one. The dynamic programming algorithm is:

and there is no partial optimization at this stage as such. The values of f₁(F₁) were computed in increments of 100 and are shown in Figure 7-28.

     There is a partial optimization at stage two, and the dynamic programming algorithm is:

At stage two the state variable is the sum of the feed to be distributed optimally between reactors one and two. All possible values have to be considered from allocating all of the feed to these two stages to none of the feed to these two stages. The decision variable is the feed to stage two, and it is selected to maximize the profit from chemical reactors one and two for a specified value of the sum of feed to the two reactors. the amount of feed to reactor one, F₁, is the difference between the state variable s₂ = F₁ + F₂ and the decision variable d₂ = F₂. The values of f₂(F₁ + F₂) were computed in increments of 100 and then results are shown in Figure 7-28 along with optimal values of F₂.

     The key to using dynamic programming for optimal allocation is recognizing that the state variable represents the amount of the resource, feed in this case, to be optimally distributed over the remaining stages. Also for stages other than the last stage, the range of possible values must be considered from distributing all to distributing none to the remaining stages. However, at the final stage it is necessary to consider only one value, the total amount to be distributed. This is shown in Figure 7-28 for the total feed rate of 700 lb per hour, and the dynamic programming algorithm at stage three is:

     The results of the partial optimizations at stage three, as shown in Figure 7-28, have an optimal return of 29 and an optimal feed rate, F₃, of 100 lb per hour to reactor three. This means that 600 lb per hour is to be optimally distributed to the other two reactors. From the partial optimizations at stages two and one the optimal value of F₂ is 200 and F₁ is 400. The optimal policy is underlined in Figure 7-28.

     Optimal allocation problems are solved using the same approach as illustrated in Example 7-7. The state variable at each stage is the sum of the amount of the resource to be allocated to that stage and the previous ones. The decision variable is the amount of the resource allocated at that stage. The optimal values of the decision are determined for the range of values on the state variable to maximize the sum of the return at that state and the optimal returns from the previous stages, having the remaining resource distributed optimally. At each stage except the last stage, the possible values of the state variable must range from considering all the resources to be allocated to that and previous stages. At the last stage it is necessary to consider only the one value of the state variable, the total amount of the resource. At the last stage the bounds on the decision variable for the amount allocated to the stage range from having all to having none of the resource used at the stage. This is a no-state, one decision partial optimization. From stage (N-1) to stage 2, there were one-state, one-decision partial optimizations. Frequently, at stage 1 the state and decision variables are the same; and in this case, as in the example, partial optimization is not required.

     In summary, optimal allocation problems can now be solved using either linear or dynamic programming. Dynamic programming offers the advantage of not being limited to linear equations. Usually, the most difficult part of the dynamic programming analysis is formulating the problem and assembling the economic model and constraint equations. The partial optimizations at each stage requires some computational effort that is frequently done using a computer. Selecting the optimal policy may require interpolation of information developed at each stage.

In this chapter the objective has been to develop an understanding of the dynamic programming algorithm and illustrate its application to a number of types of optimization problems. The key is to be able to convert the process flow diagram to a dynamic programming functional diagram. This procedure was illustrated for network problems, serial and branched problems, equipment replacement problems and allocation problems.

     The theory of dynamic programming was given for large problems with loops and branches along with rules for applying this theory to large processes to obtain the functional equations and diagram for the information flow for the dynamic programming optimization. A case study of the contact process for sulfuric acid manufacture illustrated the capabilities and limitations of the methodology for an industrial process.

     The main advantage of dynamic programming is to convert a large optimization problem to a series of partial optimization problems. The techniques of the previous chapter on multivariable search methods were applicable to the partial optimizations. At this point there is methodology to solve large, constrained optimization problems. If the problem is too large for multivariable search methods, then the techniques of dynamic programming can be applied to give a series of smaller partial optimization problems. The texts by Cooper and Cooper(11) and Denardo(12) are recommended for further reading on the subject of deterministic dynamic programming and the text by Ross(14) is recommended for stochastic dynamic programming.

1. Bellman, R.E., Dynamic Programming, Princeton University Press. Princeton, N.J. (1957).

2. Bellman, R.E., and S. Dreyfus, Applied Dynamic Programming, Princeton University Press, Princeton, N.J. (1962).

3. Roberts, S.M., Dynamic Programming in Chemical Engineering and Process Control, Academic Press, New York (1964).

4. Aris, R., The Optimal Design of Chemical Reactors, Academic Press, New York (1961).

5. Mitten, L.G. and G.L. Nemhauser, "Multistage Optimization", Chemical Engineering Process, 54, (1), 53 (Jan 1963).

6. Wilde, D.J., Private communication, 1964.

7. Aris, R., G.L. Nemhauser and D.J. Wilde, "Optimization of Multistage Cyclic and Branching Systems by Serial Procedures", A.I.Ch.E. Journal, 10, (3), 913 (Nov. 1964)

8. Wilde, D.J., "Strategies for Optimization Macrosystems", Chemical Engineering Progress, 61 (3), 86 (March 1965)

9. Lowry, Ivan, A Dynamic Programming Study of the Contact Process, M.S. Thesis, Louisiana State University, Baton Rouge, Louisiana (1965).

10. Wilde, D.J. and C.S. Beightler, Foundations of Optimizations, Prentice-Hall, Inc., Englewood Cliffs, N.J. (1967)

11. Cooper, L. and M.W. Cooper, Introduction to Dynamic Programming, Pergamon Press, New York (1981)

12. Denardo, E.V., Dynamic Programming: Models and Applications, Prentice-Hall, Inc., Englewood Cliffs, N.J. (1982)

13. Anonymous, Manual of 124 Process Flowsheets, McGraw-Hill Publishing Company, New York (1964).

14. Ross, Sheldon, Introduction to Stochastic Dynamic Programming, Academic Press, New York (1983).

15. Nemhauser, G.L., Introduction to Dynamic Programming, John Wiley and Sons, Inc., New York (1966).

top