9 Dynamic Programming
9.1 Introduction
In most practical problems, decisions have to be made sequentially at different points
in time, at different points in space, and at different levels, say, for a component, for
a subsystem, and/or for a system. The problems in which the decisions are to be made
sequentially are calledsequential decision problems. Since these decisions are to be
made at a number of stages, they are also referred to asmultistage decision problems.
Dynamic programming is a mathematical technique well suited for the optimization of
multistage decision problems. This technique was developed by Richard Bellman in
the early 1950s [9.2, 9.6].
The dynamic programming technique, when applicable, represents or decomposes
a multistage decision problem as a sequence of single-stage decision problems. Thus
anN-variable problem is represented as a sequence ofNsingle-variable problems that
are solved successively. In most cases, theseNsubproblems are easier to solve than
the original problem. The decomposition toNsubproblems is done in such a manner
that the optimal solution of the originalN-variable problem can be obtained from
the optimal solutions of theNone-dimensional problems. It is important to note that
the particular optimization technique used for the optimization of theNsingle-variable
problems is irrelevant. It may range from a simple enumeration process to a differential
calculus or a nonlinear programming technique.
Multistage decision problems can also be solved by direct application of the clas-
sical optimization techniques. However, this requires the number of variables to be
small, the functions involved to be continuous and continuously differentiable, and the
optimum points not to lie at the boundary points. Further, the problem has to be rela-
tively simple so that the set of resultant equations can be solved either analytically or
numerically. The nonlinear programming techniques can be used to solve slightly more
complicated multistage decision problems. But their application requires the variables
to be continuous and prior knowledge about the region of the global minimum or max-
imum. In all these cases, the introduction of stochastic variability makes the problem
extremely complex and renders the problem unsolvable except by using some sort of an
approximation such as chance constrained programming.†Dynamic programming, on
the other hand, can deal with discrete variables, nonconvex, noncontinuous, and nondif-
ferentiable functions. In general, it can also take into account the stochastic variability
by a simple modification of the deterministic procedure. The dynamic programming†The chance constrained programming is discussed in Chapter 11.544 Engineering Optimization: Theory and Practice, Fourth Edition Singiresu S. Rao
Copyright © 2009 by John Wiley & Sons, Inc.