572 Dynamic Programming
we obtainmax
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)]
=max
100 x 2 + 05(
2500 − 5 x 2
10)
if 0≤x 2 ≤ 251100 x 2 + 05(
2000 − 10 x 2
4)
if 125≤x 2 ≤ 002=max
75 x 2 + 21 ,500 if 0≤x 2 ≤ 25125 , 000 − 25 x 2 if 125≤x 2 ≤ 002Now,max( 75 x 2 + 21 , 500 )= 21 ,875 atx 2 = 251max( 25 , 000 − 25 x 2 ) = 21 ,875 atx 2 = 251Hence
f 2 ∗ 500 ( 2 , 2000 , 450 )= 21 ,875 at x 2 ∗= 251. 0From Eq. (E 1 ) e havewx∗ 1 = inm(
2500 − 5 x 2 ∗
10,
2000 − 10 x∗ 2
4, 450 − 1. 5 x 2 ∗)
=min( 187. 5 , 187. 5 , 262. 5 )= 187. 5Thus the optimum solution of the problem is given byx∗ 1 = 871 .5,x 2 ∗= 251 .0, and
fmax= 12 , 875 .0, which can be seen to be identical with the one obtained earlier.Problem of Dimensionality in Dynamic Programming. The application of dynamic
programming for the solution of a linear programming problem has a serious limitation
due to the dimensionality restriction. The number of calculations needed will increase
very rapidly as the number of decision variables and state parameters increases. As an
example, consider a linear programming problem with 100 constraints. This means that
there are 100 state variables. By the procedure outlined in Section 9.4, if a table offi∗
is to be constructed in which 100 discrete values (settings) are given to each parameter,
the table contains 100^100 entries. This is a gigantic number, and if the calculations are
to be performed on a high-speed digital computer, it would require 100^96 seconds or
about 100^92 years†merely to compute one table offi∗. Like this, 100 tables have
to be prepared, one for each decision variable. Thus it is totally out of the question
to solve a general linear programming problem of any reasonable size‡by dynamic
programming.†The computer is assumed to be capable of computing 10 (^8) values offi∗per second.
‡As stated in Section 4.7, LP problems with 150,000 variables and 12,000 constraints have been solved in
a matter of a few hours using some special techniques.