Engineering Optimization: Theory and Practice, Fourth Edition

570 Dynamic Programming

such that

∑n

j= 1

aijxj≤bi, i= 1 , 2 ,... , m (9.29)

xj≥ 0 , j= 1 , 2 ,... , n (9.30)

The recurrence relationship (9.16), when applied to this problem yields

f 1 ∗(β 1 , β 2 ,... , βm) = max

0 ≤xi≤β

[cixi+fi∗− 1 (β 1 −a 1 ixi,

β 2 −a 2 ixi,... , βm−amixi) ], i= 2 , 3 ,... , n (9.31)

whereβ 1 , β 2 ,... , βmare the resources available for allocation at stagei;a 1 ixi,... ,

amixiare the resources allocated to the activityxi,β 1 −a 1 ixi, β 2 −a 2 ixi,... , βm−

amixiare the resources available for allocation to the activityi− 1 , andβindicates

the maximum value thatxican take without violating any of the constraints stated in

Eqs.(9.29). The value ofβis given by

β=min

(

β 1

a 1 i

,

β 2

a 2 i

,... ,

βm

ami

)

(9.32)

since any value larger thanβwould violate at least one constraint. Thus at theith

stage, the optimal valuesxi∗andfi∗can be determined as functions ofβ 1 , β 2 ,... , βm.

Finally, at thenth stage, since the values ofβ 1 ,β 2 ,. .. ,βmare known to be

b 1 , b 2 ,... , bm, respectively, we can determine x∗n andfn∗. Oncexn∗is known, the

remainingvalues,x∗n− 1 , x∗n− 2 ,... , x∗ 1 can be determined by retracing the suboptimiza-

tion steps.

Example 9.5†

Maximizef(x 1 , x 2 ) = 50 x 1 + 001 x 2

subject to

10 x 1 + 5 x 2 ≤ 5002

4 x 1 + 01 x 2 ≤ 0002

x 1 + 1. 5 x 2 ≤ 504

x 1 ≥ 0 , x 2 ≥ 0

SOLUTION Sincen=2 andm=3, this problem can be considered as a two-stage

dynamic programming problem with three state parameters. The first-stage problem is

to find the maximum value off 1 :

maxf 1 (β 1 , β 2 , β 3 , x 1 ) = max

0 ≤x 1 ≤β

( 05 x 1 )

†This problem is the same as the one stated in Example 3.2.