Scribd
Upload
2 views

Dynamic programming_0

The document discusses Dynamic Programming (DP) as a method for solving optimization problems by breaking them into stages and using recursive equations. It outlines two strategies, forward and backward, for solving problems such as the Shortest Path Problem and the Knapsack Problem, detailing how to define stages, states, and recursive equations for each. Examples illustrate the application of DP in finding optimal solutions for manufacturing sequences and maximizing returns in a knapsack scenario.

Uploaded by

karenmutio808
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views

Dynamic programming_0

The document discusses Dynamic Programming (DP) as a method for solving optimization problems by breaking them into stages and using recursive equations. It outlines two strategies, forward and backward, for solving problems such as the Shortest Path Problem and the Knapsack Problem, detailing how to define stages, states, and recursive equations for each. Examples illustrate the application of DP in finding optimal solutions for manufacturing sequences and maximizing returns in a knapsack scenario.

Uploaded by

karenmutio808
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

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

You might also like