9.8 Linear Programming as a Case of Dynamic Programming 569
9.8 Linear Programming as a Case of Dynamic Programming
A linear programming problem with ndecision variables and m constraints can
be considered as an n-stage dynamic programming problem with m state vari-
ables. In fact, a linear programming problem can be formulated as a dynamic
programming problem. To illustrate the conversion of a linear programming problem
into a dynamic programming problem, consider the following linear programming
problem:
Maximizef (x 1 , x 2 ,... , xn)=
∑n
j= 1
cjxj
subject to
∑n
j= 1
aijxj≤bi, i= 1 , 2 ,... , m
xj≥ 0 , j= 1 , 2 ,... , n
(9.27)
This problem can be considered as ann-stage decision problem where the value of
the decision variablexj must be determined at stagej.The right-hand sides of the
constraints,bi, i= 1 , 2 ,... , m, can be treated asmtypes of resources to be allocated
among different kinds of activitiesxj. For example,b 1 may represent the available
machines,b 2 the available time, and so on, in a workshop. The variablex 1 may denote
the number of castings produced,x 2 the number of forgings produced,x 3 the number
of machined components produced, and so on, in the workshop. The constantcjmay
represent the profit per unit ofxj. The coefficientsaij represent the amount ofith
resourcebineeded for 1 unit ofjth activityxj (e.g., the amount of material required
to produce one casting). Hence when the value of the decision variablexjat the jth
stage is determined,a 1 jxjunits of resource 1,a 2 jxj units of resource 2,... , amjxj
units of resourcemwill be allocated tojth activity if sufficient unused resources exist.
Thus the amounts of the available resources must be determined before allocating
them to any particular activity. For example, when the value of the first activityx 1 is
determined at stage 1, there must be sufficient amounts of resourcesbifor allocation
to activity 1. The resources remaining after allocation to activity 1 must be determined
before the value ofx 2 is found at stage 2, and so on. In other words, the state of the
system (i.e., the amounts of resources remaining for allocation) must be known before
making a decision (about allocation) at any stage of then-stage system. In this problem
there aremstate parameters constituting the state vector.
By denoting the optimal value of the composite objective function overnstages
asfn∗, we can state the problem as
Find
fn∗=fn∗(b 1 , b 2 ,... , bm) = max
x 1 ,x 2 ,...,xn
∑n
j= 1
cjxj
(9.28)
