Dynamic Programming

1
TLO 6: Illustrate the algorithm for solving simple applications of dynamic programming and
goal programming
DYNAMIC PROGRAMMING
Dynamic programming is a quantitative technique used to make a series of

interrelated decisions. It is concerned with finding a combination of decisions which
will maximize overall effectiveness.
For example, a company may wish to make a series of marketing decisions

over time which will provide it with the highest possible sales volume.
Another organization may wish to find that series of interrelated production

decisions over time which will minimize production cost or minimize hiring and
layoff to achieve some specified production goal.
The dynamic programming approach divides the problem into a number of

subproblems, or stages. The decision we make at each stage influences not only
the next stage but also every stage to the end of the problem.
Dynamic programming starts with the last stage of the problem and works
backward toward the first stage, making optimal decisions at each stage of the
problem.
Whereas linear programming has standard ways to formulate the problems

and solve them, there is no such “standard approach” in dynamic programming. It
is, instead, sort of a general way of solving large, complex problems by breaking
them down into a series of smaller problems which are more easily solved.
DYNAMIC PROGRAMMING APPLIED TO THE SHORTEST-ROUTE PROBLEM
Kooch Kottas is the truck dispatcher for an Atlanta transportation company.

His firm has been awarded a contract to pick up a number of loads of woven
material in Atlanta and transport them to St. Louis. Kooch has looked at the map of
alternative routes between those two points and constructed the highway network
below:
The circles (nodes) represent the origin, destination, and other cities where
routes intersect. The arrows (or branches) represent the highways connecting the
nodes, each with its mileage indicated.
2
Kooch’s problem is to find the shortest route from Atlanta to St. Louis.
Stage 1. There is one route each from input node 8 and 9 going to node 10, with
the following distances:
Input node Output node Route Shortest distance

To Saint Louis
8 10 8-10 150
9 10 9-10 100
The solution is the shortest distance from each of stage 1 input nodes to Saint
Louis.
Stage 2. Analysis of stage 2 distances from input and output nodes are as follows:

To Saint Louis
7 8 7-8 275
6 9 6-9 300
5 8 5-8 400
3
Note that there are two output nodes for node 5: 8 and 9. The choice of an optimal
route from node 5 is either 500 miles or 400 miles. Route 5-8-10 is the optimal
one.
Stage 3. We begin with node 2. Using the optimal answers for nodes 6 and 5 from
stage 2, we evaluate routes 2-6 and 2-5 and choose route 2-6 (300 + 300 < 275 +
400).
Looking at node 4, we see that we have three choices: we use the optimal answers
for nodes 6, 5 and 7 from stage 2 (300, 400, 275). We evaluate routes 4-6, 4-5
and 4-7 and choose 4-6 (500 < 575 or 550).
For node 3, there are two choices: routes 3-5 and 3-7. Using the optimal answers
for nodes 5 and 7 from stage 2, we choose route 3-5 (600 < 625).
Stage 3 results are:

To Saint Louis
4
2 6 2-6 600
4 6 4-6 500
3 5 3-5 600
Stage 4. There is only one input in stage 4, node 1, and so we have 3 choices: 1-2,
1-4 or 1-3. Using the output of stage 3, we evaluate the 3 routes and choose 1-4
(650 < 700 or 775).
Stage 4 results are:

To Saint Louis
1 4 1-4 650
THE SHORTEST ROUTE
Now that we have solved the four individual problems, let us go through the
network from stage 4 to stage 1 and pick the route at each stage which leads us to
the optimal decision. The table below illustrates this process. We can see now that
the shortest route between Atlanta and Saint Louis is
1-4-6-9-10, with a total distance of 650 miles.
Picking the best decision at each stage:
Input node Output node Route Shortest distance to

Saint Louis
Stage 4 1 4 1-4 650
Stage 3 2 6 2-6 600
4 6 4-6 500
3 5 3-5 600
Stage 2 7 8 7-8 275
6 9 6-9 300
5 8 5-8 400
Stage 1 8 10 8-10 150
9 10 9-10 100
5

Dynamic Programming

Uploaded by

Copyright:

Available Formats

Dynamic Programming

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dynamic Programming

Uploaded by

Copyright:

Available Formats

1

Dynamic programming is a quantitative technique used to make a series of

For example, a company may wish to make a series of marketing decisions

Another organization may wish to find that series of interrelated production

The dynamic programming approach divides the problem into a number of

Whereas linear programming has standard ways to formulate the problems

DYNAMIC PROGRAMMING APPLIED TO THE SHORTEST-ROUTE PROBLEM

Kooch Kottas is the truck dispatcher for an Atlanta transportation company.

Input node Output node Route Shortest distance

Input node Output node Route Shortest distance

Stage 3 results are:

Input node Output node Route Shortest distance

Stage 4 results are:

Input node Output node Route Shortest distance

THE SHORTEST ROUTE

Picking the best decision at each stage:

Input node Output node Route Shortest distance to

You might also like