Chapter 21 – Dynamic Programming
True / False
1. Dynamic programming requires that its subproblems be independent of one another.
a.
True
b.
False
2. Dynamic programming, when used for the shortest route problem, requires complete enumeration of paths from the
beginning to ending node.
a.
True
b.
False
3. The solution of stage k of a dynamic programming problem is dependent upon the solution of stage k−1.
a.
True
b.
False
4. The output of stage k is the input for stage k−1.
a.
True
b.
False
5. State variables are a function of a state variable and a decision.
a.
True
b.
False
6. The return function for a shortest route problem refers to two directional arcs between nodes.
a.
True
b.
False
7. In solving a shortest route problem using dynamic programming the stages represent how many arcs you are from the
terminal node.
a.
True
b.
False
8. Dynamic programming is a general approach rather than a specific technique.
a.
True
b.
False
9. Dynamic programming must only involve a finite number of decision alternatives and a finite number of stages.
a.
True
b.
False
Chapter 21 – Dynamic Programming
10. Dynamic programming is a general approach with stage decision problems differing substantially from application to
application.
a.
True
b.
False
11. In a production and inventory control problem, the states can correspond to the amount of inventory on hand at the
beginning of each period.
a.
True
b.
False
12. In a knapsack problem, if one adds another item, one must completely resolve the problem in order to find a new
optimal solution.
a.
True
b.
False
13. The subscripts used in dynamic programming notation refer to states.
a.
True
b.
False
14. In order to use dynamic programming, one must be able to view the problem as a multistage decision problem.
a.
True
b.
False
15. Finding the optimal solution to each stage of a dynamic programming problem will always lead to an optimal solution
to the total problem.
a.
True
b.
False
16. The stage transformation function identifies which state one reaches at the next stage for a given decision.
a.
True
b.
False
Multiple Choice
17. Stages of a dynamic programming solution procedure
a.
represent parts of a large mathematical model.
b.
often represent a sequence of decisions made over time.
c.
are usually not independent of each other.
Chapter 21 – Dynamic Programming
d.
All of the alternatives are true.
18. State variables in a shortest route problem represent
a.
decisions.
b.
locations in the network.
c.
the minimum distance between nodes.
d.
None of the alternatives is true.
19. The stage transformation function
a.
transforms the input into the output.
b.
transforms a stage into a state.
c.
is a different function for each stage.
d.
None of the alternatives is true.
20. Stage transformation functions
a.
are linear.
b.
calculate the return.
c.
determine the output of the stage.
d.
All of the alternatives are true.
21. A return function is a value such as profit or loss associated with making decision dn at:
a.
stage n for specific value of output variable xn.
b.
stage n for a specific value of input variable xn.
c.
stage n for a specific value of stage m.
d.
input n for a specific value of output variable xn.
22. If x3 = t4 (x4,d4) = x4 − 2d4 and r4(x4,d4) = 16d4 the state variable is
a.
t
b.
x
c.
r
d.
d
23. If x3 = t4(x4,d4) = x4 − 2d4 and r4(x4,d4) = 16d4, the stage transformation function is
a.
t
b.
x
c.
r
d.
d
Chapter 21 – Dynamic Programming
24. If x3 = t4(x4,d4) = x4 − 2d4 and r4(x4,d4) = 16d4, the subscripts refer to
a.
state.
b.
stage.
c.
transformation.
d.
return.
25. The knapsack problem is to determine how many units of each item to place in the knapsack to:
a.
minimize total value.
b.
maximize total value.
c.
minimize the number of items in the knapsack.
d.
maximize the number of items in the knapsack.
26. Solutions in dynamic programming
a.
are not optimal.
b.
are unique.
c.
represent each stage.
d.
All of the alternatives are true.
Subjective Short Answer
27. Find the shortest path through the following network using dynamic programming.
STAGE 1
Input node
Decision arc
Shortest distance
8
8−10
4
9
9−10
3
STAGE 2
Input node
Decision arc
Shortest distance
5
5−9
6
7
7−8
11
STAGE 3
Input node
Decision arc
Shortest distance
Chapter 21 – Dynamic Programming
28. Audio Disks will be opening outlets in the greater Phoenix area. The estimated sales at each store are dependent not
only on the store location, but on the number of sales personnel, as presented in the table below ($000/year). Each store
requires at least 2 sales people, and a pool of 9 salespeople is available.
Staff Size
2
3
4
5
Store 1
60
85
90
100
Store 2
105
120
130
150
Store 3
120
145
160
175
a.
What would the states be in the dynamic programming formulation?
b.
Draw the network that represents the dynamic programming formulation.
c.
Given the above network, solve the sales personnel allocation problem by finding the longest
path.
a.
The states represent the number of salesmen available at each stage (store).
c.
Alternate optimal solutions:
Total Sales
29. Consider the following integer linear program
Max
5x1 + 7x2 + 9x3
s.t.
2x1 + 3x2 + 4x3 ≤ 8
x1 ≤ 3
x2 ≤ 2
x1, x2, x3 ≥ 0, integer
2
2−5
16
3
3−5
13
4
4−6
17
STAGE 4
Input node
Decision arc
Shortest distance
1
1−4
19
Chapter 21 – Dynamic Programming
a.
Set up the network that represents the dynamic programming formulation.
b.
Solve the problem using dynamic programming.
30. A driver wants to make a trip from city 1 to city 7. The road mileage between cities is given below. Find the shortest
route.
To City:
From City
1
2
3
4
5
6
7
1
−
2
2
4
−
−
−
2
−
−
−
−
4
10
−
3
−
−
−
−
12
6
−
4
−
−
−
−
10
−
−
5
−
−
−
−
−
−
14
6
−
−
−
−
−
−
2
7
−
−
−
−
−
−
−
1-3-6-7; 13 miles
31. The owner of a small construction firm is excavating at three sites. He wishes to assign his 5 additional trucks in such
a way as to minimize his total costs. Each site can use 0 to 3 additional trucks; no site can use more than 3 trucks
efficiently. The following site total costs are known.
Number Cost of Excavating
of Trucks
Site 1
Site 2
Site 3
0
$10000
$15000
$20000
1
10000
14000
18000
2
9200
13250
17500
3
8500
12750
17250
a.
Use dynamic programming to find the assignment of the additional trucks that minimizes
total cost.
b.
If the owner had only 4 trucks to assign, what would be the optimal assignment and total
cost?
a.
The minimal cost truck assignments are:
0 trucks to site 1
3 trucks to site 2
Chapter 21 – Dynamic Programming
32. We have a number of types of items to be shipped as cargo. The total available weight in the truck is ten tons. We
wish to determine the number of units of items to be shipped to maximize profit.
Item
Weight (Tons)
Profit (1000s dollars)
A
3
5
B
4
7
C
2
3
Total profit 17.
33. A cargo company has a set of delivery patterns for its goods from its locations at city1 to a series of cities 2,3,4,5, and
6. The delivery times between cities are given I hours below. Find the shortest route.
To City:
From City:
1
2
3
4
5
6
7
1
−
6
10
7
−
−
−
2
6
−
4
−
5
−
−
3
10
4
−
4
2
4
−
4
7
−
5
−
−
8
−
5
−
5
3
−
−
−
7
6
−
−
4
8
−
−
5
7
−
−
−
−
7
5
−
34. Ajax Sound is in the business of fabricating printer connection cables. They purchase 30 foot spools of wire from
National Electric at $3.00 per spool and cut the wire into various lengths.
Each length of wire is fitted with printer connector jacks at both ends and then packaged. The printer connector jacks
cost $.40 per pair (one pair is used in each cable package). Packaging and labor together cost $.20 per package.
Because of Ajax’s superior marketing skills they are in the enviable position of being able to sell all the printer connection
cables they produce. They are currently contemplating offering four different sized cable packages:
Size Wholesale Package Price
5′ $1.30
8′ $1.80
12′ $2.50
16′ $3.30
If unused wire from a spool can be sold for scrap at $.03 per foot, how many packages of each size cable should Ajax
make from a 30-foot spool?
Produce one package of 16 ft. wire.
2 trucks to site 3
There are two optimal assignments:
0 trucks 0 trucks
3 trucks or 2 trucks
1 truck 2 trucks
Chapter 21 – Dynamic Programming
35. Unidyde Corporation is currently planning the production of red dye number 56 for the next four months. Production
and handling costs, as well as production and storage capacity, vary from month to month. This data is given in the table
below.
Production and holding costs are in ($1,000’s per batch) and production levels and storage capacities are in batches.
Holding costs are based on inventory on hand at the end of the month. The number of orders for batches the sales
department has received over the four-month period are also given.
Month
Production
Cost
Maximum
Production
Holding
Cost
Storage
Capacity
Orders
Received
February
11
3
3
4
2
March
15
4
2
3
4
April
16
3
2
5
2
May
9
2
1
2
3
Unidyne does not wish to have any inventory of the dye at the end of May. Its current inventory is 2 batches. Determine
a production schedule for the next four months.
36. Marvelous Marvin is planning his annual “Almost Everything Must Go” inventory clearance sale. Marvin has decided
to allocate 18 shelf feet to the cooking section. He is considering offering up to five items for sale in this category:
Item
Shelf Feet Required
Expected Profit
A
1
$ 10
B
2
$ 25
C
3
$ 40
D
5
$ 70
E
7
$100
If Marvin wants at least one item A and one item B on sale, what stock should he have on sale and what is the total
expected profit?
37.
Franklin Plate Company is in the business of manufacturing commemorative plates for holidays. The company is
currently planning its production schedule for this year’s Thanksgiving plate.
Discussions with the sales manager have indicated that sales of the plate will run from August through November. The
production manager has determined the manufacturing cost per plate for each of these months as well as the sales demand
(in 1000’s) and manufacturing capacity (in 1000’s). The data is as follows:
Manufacturing
Maximum
Chapter 21 – Dynamic Programming
Month
Demand
Cost Per Plate
Production
August
2
2
6
September
4
3
6
October
6
3
4
November
3
4
3
It is also known that the maximum inventory level possible at the end of any month is 5,000 plates. The storage cost per
plate for each plate in inventory at the end of the month is $.50.
Franklin has no inventory on hand at the beginning of August and wishes to have no inventory left after November. Use
dynamic programming to determine an optimal production schedule.
Month
August
6
6
6
September
2
3
5
October
4
4
4
November
3
2
0
38.
Walt’s Custom Boats manufactures luxury yachts. Walt is phasing out production of his 42-foot Sportfisher that he plans
to replace with a 44-foot Sportfisher. Walt currently has orders for the next four months for the 42-foot model after which
he will cease production. The following data (with costs in $1,000’s) is given for the next four months:
Month
Production
Cost Per Boat
Maximum
Production
Level
Holding Cost Per
Boat in Inventory at
End of Month
Maximum
Storage
Capacity
Number of Boats to
be Delivered in
Month
May
25
4
1
6
1
June
27
3
1
5
3
July
30
2
2
3
3
August
29
3
1
4
4
If Walt’s current inventory of 42-foot Sportfishers is 1 boat, how should Walt schedule production of the 42-foot
Sportfisher over the next four months to minimize the total production and inventory holding costs?
Total Cost = $278,000.
39.
Mission Bay Development Corporation is engaged in developing an exclusive 25 acre parcel of property. They have
received bids from five builders to purchase construction lots. Because of the different nature of the builders, they desire
different sized lots. The data are as follows:
Builder
Lot Size
Requested
Offered Price
Per Lot
Maximum Number
Of Lots Desired
1
3 acre
$ 50,000
6
2
1 acre
$ 15,000
5
3
6 acre
$105,000
8
4
20 acre
$350,000
1
5
5 acre
$ 91,000
2
How should Mission Bay sell their land to maximize total sales revenue?
Chapter 21 – Dynamic Programming
Builder 1: 1 lot; Builder 3: 2 lots; Builder 5: 2lots; Total revenue = $442,000
40.
Given the following shortest path problem in which travel is only permitted from left to right. Use dynamic programming
to determine the shortest path from node 1 to:
a. Node 15.
b. Node 14.
b. 1-4-9-13–14: Distance = 37
Essay
41. What is the Principle of Optimality, and what is its relationship to dynamic programming?
Answer not provided.
42. Define the following terms as they relate to dynamic programming.
a.
Stage
b.
State variable
c.
Stage transformation function
Answer not provided.
43. A stage in a dynamic programming problem is defined when 2 variables and 2 functions related to that stage are
defined. Identify and define the 2 variables and 2 functions and illustrate them with an example of your choice.
Answer not provided.
Chapter 21 – Dynamic Programming
44. Explain the divide-and-conquer solution strategy of dynamic programming.