Engineering Optimization: Theory and Practice, Fourth Edition

9.2 Multistage Decision Processes 547

Figure 9.3 Multistage decision problem (initial value problem).

wherexidenotes the vector of decision variables at stagei.The state transformation
equations (9.3) are also calleddesign equations.
The objective of a multistage decision problem is to findx 1 ,x 2 ,... ,xnso as
to optimize some function of the individual statge returns, say,f (R 1 , R 2 ,... , Rn)
and satisfy Eqs. (9.3) and (9.4). The nature of then-stage return function,f, deter-
mines whether a given multistage problem can be solved by dynamic programming.
Since the method works as a decomposition technique, it requires the separability
and monotonicity of the objective function. To have separability of the objective
function, we must be able to represent the objective function as the composition
of the individual stage returns. This requirement is satisfied for additive objective
functions:

f=

∑n

i= 1

Ri=

∑n

i= 1

Ri(xi,si+ 1 ) (9.5)

wherexiare real, and for multiplicative objective functions,

f=

∏n

i= 1

Ri=

∏n

i= 1

Ri(xi,si+ 1 ) (9.6)

wherexiare real and nonnegative. On the other hand, the following obj ective function
is not separable:

f=[R 1 (x 1 ,s 2 )+R 2 (x 2 ,s 3 ) []R 3 (x 3 ,s 4 )+R 4 (x 4 ,s 5 )] (9.7)

Fortunately, there are many practical problems that satisfy the separability condition.
The objective function is said to bemonotonic if for all values ofa andbthat
make
Ri(xi=a,si+ 1 )≥Ri(xi=b,si+ 1 )

the following inequality is satisfied:

f (xn,xn− 1 ,... ,xi+ 1 ,xi=a,xi− 1 ,... ,x 1 ,sn+ 1 )

≥f(xn,xn− 1 ,... ,xi+ 1 ,xi=b,xi− 1 ,... ,x 1 ,sn+ 1 ), i= 1 , 2 ,... , n (9.8)