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

7-1. For Example 7-1, determine the shortest distance between the East and West Coasts.

Solution

7-2. Solve Example 7-5 as a network problem.

Solution

7-3. In Figure 7-29 a partially completed functional diagram of a process is given that involves a diverging branch and a feed-back loop. Complete the functional diagram by labeling it with the appropriate subscripts on the state and decision variables. Then give the dynamic programming algorithm. transitions functions and incident identities for each stage. Also, give the type of partial optimization at each stage, and describe how the feed-back loop and diverging branch are evaluated and included in the main branch.

Solution

7-4. In Figure 7-30 a partially completed functional diagram of a process is given that involves a converging branch and a feed-forward loop. complete the functional diagram by labeling it with the appropriate subscripts on the state and decision variables. Then give the dynamic programming algorithm, transitions functions and incident identities for each stage. Also, give the type of partial optimization at each stage, and describe how the feed-forward loop and converging branch are evaluated and included in the main branch.

Solution

7-5. The flow diagram shown in Figure 7-31 is a simplified version of a catalytic cracking unit and associated separation facilities. Develop the dynamic programming functional equations and diagram for this process flow diagram. Define each state and decision variable, transition function and incident identity. Describe how to calculate the return at each stage. Simplify the functional diagram where required by applying Wilde's rules, and indicate the steps to obtain the optional return and policy.

Solution

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

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 that maximize the profit from the alkylation process. Because 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 algorithm at each stage, and with this information determine the optimal reactor feed rates, sulfuric acid catalyst concentrations and the maximum profit.

Solution

7-8(10). Solve the following initial value problem by dynamic programming.

where

R_i (s_i,d_i) = s_i +3d_i            for i = 1,2,...,5

s_i-1 = s_i = 2s_i - 0.2d_i

0 < d_i < s_i

and the initial state variable s₅ = 100

Solution

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:

R_i(x_i) = 8x_i - ix_i² and x_i has integer values of 0,1,2,3

Solution

7-10. Consider the three stage, dynamic programming functional diagram shown in Figure 7-4. The functional diagram represents the transition functions, incident identities and dynamic programming algorithm.

The total profit from the process is:

P = R₁ (s₁,d₁) + R₂(s₂,d₂) + R₃(s₃,d₃)

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 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

7-11(10). Find the shortest and longest path from O to P in Figure 7-33. No backward movement (toward 0) is allowed.

Solution

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

7-13 

a. 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 start with a process that is now two years old.

Solution

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 700F and 900F 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 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 removal of the other hydrocarbons in the stabilizer column and the separation of isopentane and 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 isopetane 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 recycled hydrogen is computed by a material balance and is not a state or decision variable.

Solution

7-15. A chemical process uses a piece of equipment that is affected by corrosion which caused a 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 make, 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 equipment replacement for the next five years with the equipment being one year old at the start.

Solution

7-16. Solve the following four stage, final-value, serial dynamic programming problem using decision inversion.

where:

R_i = s_i + 3d_i            return function

_i = 2s_i - 0.2d_i       transition function

_i = s_i - 1                incident identity

₁ = 2,400             specified final value, ₁

0 < s₄ < 200           bounds on initial value, s₄

for i = 1, 2, 3, 4

Solution

7-17. Solve the following cyclic optimization problem by dynamic programming.

where:  

R_i   = s_i + 3d_i           for i = 1, 2, 3, 4

_i   = 2s_i - 0.2d_i

s_i-1 = _i

s₄    = _i                   cyclic optimization

s₄    < 100

Solution

7-18. For a process the following table gives the net profit 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 are given with approximations for the effects on 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

7-19 (15). Consider the following problem

Minimize:    x₁² + x₂² + x₃²

Subject to:  x₁ + x₂ + x₃ > 10

                  x_j > 0        for j =1,2,3.

To solve this problem by dynamic programming, a stage structure must be formulated with state and decision variables.

a. Let d_j = x_j, (j=1,2,3), be the decision variables at three stages and let R_j = d_j² be the return function at these stages. Show that defining state variables as follows will satisfy the constraint equation.

           s₃ > 10

           s₂ = s₃ - d₃

           s₁ = s₂ - d₂

           s_o = s₁ - d₁

where  s_o = 0

b. Show that the following must hold.

Stage 1      s₁ = d₁

Stage 2      0 < d₂ < s₂

Stage 3      0 < d₃ < s₃

c. Show that the partial optimization at three stages using the dynamic programming algorithm gives:

f₁(s₁) = s₁²              f₂(s₂) - (s₂²)/2                  f₃ = 100/3

d. Give the dynamic programming functional diagram for this problem with the return and transition functions at each stage and the values of the state and decision variables.

This procedure can be generalized to N stages with a set of constraints that are in the form of summations and products(15).

top