9/18/2013
Operations Analysis II
IE 322
Dynamic Programming
Dynamic Programming (DP) determines the
optimum solution of a problem by decomposing it
into stages.
1‐Each Stage includes a simple variable sub problem.
2‐Recursive equation linking the different stages.
3‐Guarantees that each stage’s optimal solution is
also optimal for the entire problem.
1
9/18/2013
Recursive Nature of Computations in DP is done in
the sense that the optimum solution of one sub
problem is used as an input to the next sub problem.
By the time the last sub problem is solved, the
optimum solution for the entire problem is at hand.
The manner in which the recursive computations are
carried out depends on how we decompose.
Forward Strategy
1‐ Divide the original problem into sub problems
called stages.
2‐Solve the first stage of the problem for all possible
conditions or states.
3‐Working forward from that first stage, solve each
intermediate stage.
4‐Obtain the optimal solution for the original
problem by solving all stages sequentially.
2
9/18/2013
Backward Strategy
1‐ Divide the original problem into sub problems
called stages.
2‐Solve the last stage of the problem for all possible
conditions or states.
3‐Working backward from that last stage, solve
each intermediate stage.
4‐Obtain the optimal solution for the original
problem by solving all stages sequentially.
Shortest Path Problem
An industrial engineer is planning the production of a single
product. The product can be manufactured in several ways and
by several departments. The industrial engineer needs to find the
least time to manufacture the product. The sequences of the
operations are shown in the figure.
The arcs represent the operations.
The product has to pass through 3 operations.
3
9/18/2013
This problem can be solved as finding the shortest route
from
node 1 to node 7.
The problem can be decomposed into stages, where each
stage represents an operation.
Decomposition is performed so that the shortest time to
all the terminal nodes of a stage are used in the following
stage.
The terminal nodes of the first stage are 2, 3, and 4.
The shortest time of the terminal does to node 1 are:
Shortest time from 1 to 2 = 7
Shortest time from 1 to 3 = 8
Shortest 1 to 4 = 5
The terminal nodes of the second stage are 5 and 6.
Using the shortest times from the previous stage, the
shortest times to the terminal nodes are:
Shortest time from 1 to 5 = min{15+7, 8+8, 7+5} = 12
Shortest time from 1 to 6 = min{8+9, 5+13} = 17
The third stage has only one terminal node, node 7.
Shortest time from 1 to 7 = min{12+9, 17+6} = 21
Since node 7 is the last node, the solution has been
determined, which is, the shortest time to manufacture
the product is 21 minutes and the operations are (1,4),
(4,5), and(5,7).
4
9/18/2013
Forward Equations
To define the recursive equation for this manufacturing
sequence problem, define ft(i) be the shortest time from
node 1 to node i at stage t.
Define cji as the time from node j to node i.
Then, ft is computed from ft‐1 using the recursive formula:
ft(i) =min {cji + ft‐1(j)}
f0(1) =0
In dynamic programming, ‘i’ is referred to as the state of
the system at stage t.
In general, a state is the information that is needed at
any stage to make an optimal decision.
Backward Equations
To define the recursive equation for this manufacturing
sequence problem, define ft(i) be the shortest time from
node 7 to node i at stage t.
Define cij as the time from node j to node i.
Then, ft is computed from ft‐1 using the recursive formula:
ft(i) =min {cij + ft+1(i)}
f4(7) =0
In dynamic programming, ‘i’ is referred to as the state of
the system at stage t.
In general, a state is the information that is needed at
any stage to make an optimal decision.
5
9/18/2013
Solve Example 10.1‐1, assuming that the
following routes are used:
d(1,2) = 5, d(1,3) = 9, d(1,4) = 8
d(2,5) = 10, d(2,6) = 17
d(3,5) = 4, d(3,6) = 10
d(4,5) = 9, d(4,6) = 9
d(5,7) = 8
d(6,7) = 9
How to define stages and states in the Shortest
Path Problem
In the shortest path problem we decompose the graph into stages. Each
stage includes two sets of nodes (starting nodes and arrival nodes) such
that the arrival nodes can be reached only from the starting nodes.
The arrival nodes of the current stage represent the different states of the
current stage
The starting nodes of the current stage represent the states of the
previous stage.
The set of starting nodes in the first stage includes only the source node (s)
The set of arrival nodes in the last stage includes only the sink node (t)
6
9/18/2013
Knap Sack Problem
This classical problem deals with the situation in which a
hiker must decide on the most valuable items to carry in a
backpack.
There are n items 1,2….n.
There are mi unit of items i. The weight per unit of
item i is wi and ri is the revenue per unit of item i.
The hiker can carry a weight of at most W.
Maximize z =r1m1 + r2m2 + … + rnmn
Subject to
w1m1 + w2m2 + … + wnmn <= W
m1 , m2 ,…, mn >= 0 and Integer.
The three elements of the model are
1‐ stages, each stage is represented by item i, , i=1,2…n.
2‐The alternatives at stage i are represented by the number mi of item i
included in the knapsack. The associated return is rimi.
(Note that mi can take values 0,1,….[W/wi])
3‐The State at stage I is represented by xi, the total weight assigned to
stages i, i+1, … n.
Define : fi(xi) = maximum return of stages i, i+1, … n at state xi.
The recursive equation is
7
9/18/2013
8
9/18/2013
9
9/18/2013
10
9/18/2013
11
9/18/2013
12
9/18/2013
13
9/18/2013
3
1 8
1 6 6
4 2
10 t
4 1
s
15
3 10 4
7
2
5 11
9
14
