Engineering Optimization: Theory and Practice, Fourth Edition

546 Dynamic Programming

seen to be in series and the system has to be treated as a multistage decision problem.

Finally, consider the problem of loading a vessel with stocks ofNitems. Each unit

of itemihas a weightwiand a monetary valueci. The maximum permissible cargo

weight isW. It is required to determine the cargo load that corresponds to maximum

monetary value without exceeding the limitation of the total cargo weight. Although the

multistage nature of this problem is not directly evident, it can be posed as a multistage

decision problem by considering each item of the cargo as a separate stage.

9.2.2 Representation of a Multistage Decision Process

A single-stage decision process (which is a component of the multistage problem) can

be represented as a rectangular block (Fig. 9.2). A decision process can be character-

ized by certain input parameters,S(or data), certain decision variables (X), and certain

output parameters (T) representing the outcome obtained as a result of making the

decision. The input parameters are calledinput state variables, and the output param-

eters are calledoutput state variables. Finally, there is a return or objective function

R, which measures the effectiveness of the decisions made and the output that results

from these decisions. For a single-stage decision process shown in Fig. 9.2, the output

is related to the input through a stage transformation function denoted by

T=t(X,S) (9.1)

Since the input state of the system influences the decisions we make, the return function

can be represented as

R=r(X,S) (9.2)

A serial multistage decision process can be represented schematically as shown

in Fig. 9.3. Because of some convenience, which will be seen later, the stagesn,

n− 1 ,... , i,... , 2 ,1 are labeled in decreasing order. For theith stage, the input state

vector is denoted bysi+ 1 and the output state vector assi. Since the system is a serial

one, the output from stagei+1 must be equal to the input to stagei. Hence the state

transformation and return functions can be represented as

si=ti(si+ 1 ,xi) (9.3)

Ri=ri(si+ 1 ,xi) (9.4)

Figure 9.2 Single-stage decision problem.