Engineering Optimization: Theory and Practice, Fourth Edition

566 Dynamic Programming

Now, we retrace the steps to collect the optimum values ofx∗ 3 ,x∗ 2 , andx∗ 1 and obtain

x 3 ∗= ype (c) tankt , s 3 = 251 ,000 kgf

x 2 ∗= ype (a) columnst , s 2 = 701 ,000 kgf

x 1 ∗= ype (c) foundationt , s 1 = 811 ,000 kgf

and the total minimum cost of the water tank is $12,625. Thus the minimum cost water

tank consists of a rectangular RCC tank, RCC columns, and a steel pile foundation.

9.7 Conversion of a Final Value Problem into an Initial Value Problem

In previous sections the dynamic programming technique has been described with

reference to an initial value problem. If the problem is a final value problem as shown

in Fig. 9.15a, it can be solved by converting it into an equivalent initial value problem.

Let the stage transformation (design) equation be given by

si=ti(si+ 1 , xi), i= 1 , 2 ,... , n (9.22)

Assuming that the inverse relations exist, we can write Eqs. (9.22) as

si+ 1 =ti(si, xi), i= 1 , 2 ,... , n (9.23)

where the input state to stageiis expressed as a function of its output state and the

decision variable. It can be noticed that the roles of input and output state variables

are interchanged in Eqs. (9.22) and (9.23). The procedure of obtaining Eq. (9.23) from

Eq. (9.22) is calledstate inversion. If the return (objective) function of stagei is

originally expressed as

Ri=ri(si+ 1 , xi), i= 1 , 2 ,... , n (9.24)

Eq. (9.23) can be used to express it in terms of the output state and the decision

variable as

Ri=ri[ti(si, xi), xi]=ri(si, xi), i= 1 , 2 ,... , n (9.25)

The optimization problem can now be stated as follows:

Findx 1 , x 2 ,... , xnso that

f(x 1 , x 2 ,... , xn)=

∑n

i= 1

Ri=

∑n

i= 1

ri(si, xi) (9.26)

will be optimum where thesiare related by Eq. (9.23).

The use of Eq. (9.23) amounts to reversing the direction of the flow of information

through the state variables. Thus the optimization process can be started at stagenand

stagesn− 1 , n− 2 ,... ,1 can be reached in a sequential manner. Sinces 1 is specified

(fixed)in the original problem, the problem stated in Eq. (9.26) will be equivalent to