PROCESS OPTIMIZATION

DYNAMIC PROGRAMMING
DYNAMIC PROGRAMMING
The use of dynamic programming is a very convenient way to
optimize large systems that would be too complicated for their study by
direct optimization methods.
More than an optimization technique itself, dynamic programming consists of
an organization of the information structure of a system that allows its
decomposition into smaller and easier-to-analyze subsystems and
optimize.
Each subsystem may require a specific optimization method, in a
At a given moment, the advantage can be seen as the decomposition of a problem of
multivariable optimization to a series of optimization problems of a
single variable (or the number of variables less than the original problem).
This method has the appeal of being able to handle nonlinear or non
analytics effectively.
In general, it can be said that dynamic programming yields a
optimal sequence of decisions. For industrial processes, this technique can
provide the set of design variables that optimizes the behavior of
a complete system according to a specific objective function.
BELLMAN'S OPTIMALITY PRINCIPLE
Dynamic programming is based on Bellman's principle of optimality and is
applies to systems that do not have cycles in their information flow, that is, to
systems whose calculations flow directly from the first to the last variable without
need for recycling in the problem-solving process. In this way, the changes of
Any design variable of a unit only affects the units.
subsequent.
The Bellman optimality principle can be established as follows:
Given an acyclic system, it is optimized if each component or unit is
it also optimizes for the entire set of possible values of the variables that
they come from the previous stages.
According to this principle, a system is optimized when for each possible
the input from the previous subsystem takes the best decision which is
possible at that level, for what could be required of some optimization method
explicit. Therefore, the order of application of dynamic programming is the
opposite to the flow of materials of the process.
The important point is that a decision made about a stage of a process,
it only affects the subsequent units; the acyclic structure causes that the
Units prior to the one being analyzed are not affected by the decisions.
made at this level.
In this way, the application of this technique implies analyzing the last stage.
first for the set of values of the input variables it can receive.

Material flow

Order of solution

The solutions that were taken on the last stage are used directly in
function of the output obtained in the penultimate stage (calculated to solve the
penultimate unit for each possible value of the input current to that unit.
The analysis process is repeated until reaching the first stage of the flowchart.
what is the last to be analyzed. Once this numerical process is completed, the solution
optimal is easily obtained by recovering each suboptimal according to the flow of
information about the original problem.
TYPES OF APPLICATIONS
Let's consider the general case of an optimization problem of various
variables, whose solution requires a multivariable optimization algorithm.
The figure below shows the diagram of a system of this type for the
dynamic programming application.
 dn of d2 d1

Yes S3 S2 S1
F n Sn Sn-i i 2 1

d= design variable s = state variable

For convenience, the stages are listed in reverse order of the flow of information.
in such a way that the first stage for the analysis is the last one of the diagram of
flow.
For each stage we distinguish a group of state variables, S, which are
they obtain from the solution of the system of equations of that unit.
We also distinguish another group of design variables.
Due to the decomposition of the problem, the individual analysis of each stage in
As for its degrees of freedom, it would be equal to the state variables that come from
the previous stage plus the design stage. The degrees of freedom associated with the first type

variables are satisfied by assuming values (anticipating the whole interval that these
they can take), according to Bellman's principle of optimality; when assuming these
the effective degrees of freedom for each stage are those associated with the
design variables, d, on which a search must be conducted
optimization for each assumed value of the input variables.
To analyze the dynamic programming application technique to the system of the
In the previous figure, let's initially consider the last stage of the diagram.
The suboptimization of this stage implies the consideration of all possible
values that come from the previous stage according to the flow of information:

∗
max [f 1 (2 , 1= )] ( 21)( 1 )

The degrees of freedom for this stage are those associated with S2 and d1, the degrees of
freedom associated with S2 is consumed by assuming some value that this variable
can take, while the degrees of freedom associated with d1 allow the use
of some optimization technique to find its optimal value.
Therefore, each suboptimal implies the best value that the state variable S2,
comes from the previous stage. This solution process is shown in the following
figure:
Analysis Stage 1 SOLUTION STRATEGY
STRUCTURE
Assume S2

Optimize to find the

best value of d1

OPTIMIZATION SUBPROBLEM
Have all been considered?
the possible values that S2,
Can you take? NO

YES
End of the analysis of stage 1

TABULATION OF RESULTS

S2 d1* f1*

The following two stages are considered together.

For a given value of the input current S3 and some value of the variable of
design d2, the solution of the system's equations must provide the value
corresponding output of unit 2, S2 and for any value of S2 has already been
obtained what is the best design variable of unit 1.
Thus the problem:
∗
max [f 2 (3 , 2+ ) 21, ( 1= )]( 3 )(2 2 , 1)

It transforms into:
max [f 2 )]
(3 , 2+ ) ∗1 2(, 2
This search must be repeated for all possible values that S3 can take.
and each suboptimal must be properly tabulated and graphed, as shown in
the figure below.
Analysis Stage 1 and 2 SOLUTION STRATEGY
STRUCTURE
Assuming S3

Optimize d2. For each

search point. The
solution of the equations of
stage 2 provides the
value of S2 of which is
SUBPROBLEM OF OPTIMIZATION
obtains f1 (S2) from the analysis of
stage 1

YES
Have all been considered?
the possible values that S3,
Can you take? NO

TABULATION OF RESULTS
End of the analysis of stage 2
S3 d2* S2 f2*

This procedure extends similarly to other units that represent

the original process.
In general, for any stage i, the subproblem to solve is:
max [f 1 ()]+1 , )
+ +1∗ ( ,
At this level, all subsequent stages have already been analyzed, so the
The complement to the optimal structure depends only on the value obtained in Si.
Finally, when i=N, the first stage of the information flow, we have the last one.
suboptimization, from which the global optimal plan is recovered.
At this level, the degrees of freedom of the system are equivalent to the number of
design variables of the last stage dN, for which a single process is required
search to optimize this unit.
The global solution is recovered by following the reverse path of the solution.
numerical that has been raised through this technique.
Although the optimization process has been outlined for a variable of
design for each stage, the extension to multivariable optimization problems
for each stage is direct; in that case, the optimization method must be chosen
appropriately, but the use of dynamic programming is equivalent.
In summary, dynamic programming determines an optimal sequence of
decisions. We can conceptualize two main cases for this type of
problems:
1. When it comes to a sequence of decisions without the need to use
no explicit optimization method; in this case it should simply
arranging the best order of implementation of a series of events
discrete.
2. When the mathematical model of each analysis stage contains degrees of
freedom, which must be satisfied through the application of some
optimization method.