9.8 Linear Programming as a Case of Dynamic Programming 571whereβ 1 ,β 2 , andβ 3 are the resources available for allocation at stage 1, andx 1 is a
nonnegative value that satisfies the side constraints 10x 1 ≤β 1 , 4x 1 ≤β 2 , andx 1 ≤β 3.
Hereβ 1 = 5002 − 5 x 2 ,β 2 = 0002 − 10 x 2 , andβ 3 = 504 − 1. 5 x 2 , and hence the max-
imum valueβthatx 1 can assume is given by
β=x∗ 1 = inm[
2500 − 5 x 2
10,
2000 − 10 x 2
4, 450 − 1. 5 x 2]
(E 1 )
Thus
f 1 ∗(
2500 − 5 x 2
10,
2000 − 10 x 2
4, 450 − 1. 5 x 2)
= 50 x 1 ∗= 0 min 5(
2500 − 5 x 2
10,
2000 − 10 x 2
4, 450 − 1. 5 x 2)
The second-stage problem is to find the maximum value off 2 :
maxf 2 (β 1 , β 2 , β 3 ) = max
0 ≤x 2 ≤β[
100 x 2 +f 1 ∗(
2500 − 5 x 2
10,
2000 − 10 x 2
4, 450 − 1. 5 x 2)]
(E 2 )
whereβ 1 ,β 2 , andβ 3 are the resources available for allocation at stage 2, which are
equal to 2500, 2000, and 450, respectively. The maximum value thatx 2 can assume
without violating any constraint is given by
β=min(
2500
5
,
2000
10
,
450
1. 5
)
= 200
Thus the recurrence relation, Eq. (E 2 ) can be restated as,
maxf 2 ( 5002 , 2000 , 450 )= max
0 ≤x 2 ≤ 002{
100 x 2 + 0 min 5(
2500 − 5 x 2
10,
2000 − 10 x 2
4, 450 − 1. 5 x 2)}
Since
min(
2500 − 5 x 2
10,
2000 − 10 x 2
4, 450 − 1. 5 x 2)
=
2500 − 5 x 2
10if 0≤x 2 ≤ 2512000 − 10 x 2
4if 125≤x 2 ≤ 002