Scribd
Upload
113 views

10 DynamicProgramming

The document discusses dynamic programming and its applications. It provides examples of using dynamic programming to solve optimization problems like allocating salespeople across regions, finding the shortest route, and determining the best configuration of system components. It also outlines the key characteristics of dynamic programming problems and solutions.

Uploaded by

Ron Caleb Heras
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
113 views

10 DynamicProgramming

The document discusses dynamic programming and its applications. It provides examples of using dynamic programming to solve optimization problems like allocating salespeople across regions, finding the shortest route, and determining the best configuration of system components. It also outlines the key characteristics of dynamic programming problems and solutions.

Uploaded by

Ron Caleb Heras
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/ 1

DYNAMIC PROGRAMMING

1. (Hillier, 9ed) The Sales Manager for a publisher of a college


textbook has 6 travelling salespeople to assign to three
different regions of the country. She has decided that each
region should be assigned at least one salesperson and that
each individual salesperson should be restricted to one of the
regions, but now she wants to determine how many
salespeople should be assigned to the respective regions in
order to maximize sales. The table gives the estimated
increase in sales in appropriate units, si(b), in each region i if
it were allocated b salespeople.

2. (Winston, 4ed) Use dynamic programming to 3. (modified from Hillier, 9ed) Find the shortest
solve a knapsack problem in which the knapsack route from O to T using dynamic programming.
can hold up to 13 lb.

4. (Taha, 7ed) Luxor Travel arranges 1-week tours to southern Egypt. The agency is contracted to provide tourist
groups with 7, 4, 7, and 8 rental cars over the next four weeks, respectively [An assumption here is that
requirement must be met.] Luxor Travel subcontracts with a local car dealer to supply rental needs. The dealer
charges a rental fee of $220 per car per week, plus a flat fee of $500 for any rental transaction. Luxor, however,
may elect not to return the rental cars at the end of the week, in which case the agency will be responsible only
for the $220-weekly rental. What is the best way for Luxor Travel to handle the rental situation?

5. (modified from Hillier, 9ed) Consider an electronic system consisting of four components, all of which must work
for the system to function. The reliability of the system can be improved by installing several parallel units in one
or more components. The following table gives the probability, Pi that component i (i = 1, 2, 3, 4) will function if
they consist of one, two, or three parallel units. The table also presents the respective configuration costs (in $).
Because of budget limitations, a maximum of $1,000 can be expended. Determine the best configuration using DP.
Parallel Units Component 1 Component 2 Component 3 Component 4
P1 Cost P2 Cost P3 Cost P4 Cost
1 0.5 100 0.6 200 0.7 100 0.5 200
2 0.6 200 0.7 400 0.8 300 0.7 300
3 0.8 300 0.8 500 0.9 400 0.9 400

Characteristics of Dynamic Programming (Winston, 4ed)


1. The problem can be subdivided into stages with a decision required at each stage.
2. Each stage has a number of states associated with it. By a state, we mean the information that is needed at any
stage to make an optimal decision.
3. The decision chosen at any stage describes how the state at the current stage is transformed into the state at the
next stage.
4. Principle of Optimality. Given the current state, the optimal decision for each of the remaining stages must not
depend on previously reached states or previously chosen decisions.
5. (modified) There is a recursion or a recursive formula that relates the reward/cost of the states in a current stage
to that of a previously-solved stage.
Forward Recursion. Given Stages 1, 2, ... N, the approach in solving the DP advances from Stage 1, Stage 2, ... to
Stage N.
Backward Recursion. Given Stages 1, 2, ... N, the approach in solving the DP starts with Stage N, Stage N-1, ... to
Stage 1.

You might also like