Test Bank For An Introduction to Management Science A Quantitative Approach to Decision Making 12th Edition By David Anderson Dennis Sweeney Thomas Williams Kipp Martin

21

Dynamic Programming

MULTIPLE CHOICE


1. 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.
d. All of the alternatives are true.
ANSWER: d
TOPIC: Introduction

2. 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.
ANSWER: b
TOPIC: Shortest route problem

3. 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.
ANSWER: a
TOPIC: Dynamic programming notation

4. Stage transformation functions
a. are linear.
b. calculate the return.
c. determine the output of the stage.
d. All of the alternatives are true.
ANSWER: c
TOPIC: Dynamic programming notation

5. 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.
ANSWER: b
TOPIC: Introduction

,Chapter 21 Dynamic Programming 2




6. If x3 = t4 (x4,d4) = x4 - 2d4 and r4(x4,d4) = 16d4 the state variable is
a. t
b. x
c. r
d. d
ANSWER: b
TOPIC: Dynamic programming notation

7. 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
ANSWER: a
TOPIC: Dynamic programming notation

8. If x3 = t4(x4,d4) = x4 - 2d4 and r4(x4,d4) = 16d4, the subscripts refer to
a. state.
b. stage.
c. transformation.
d. return.
ANSWER: b
TOPIC: Dynamic programming notation

9. 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.
ANSWER: b
TOPIC: The knapsack problem

10. Solutions in dynamic programming
a. are not optimal.
b. are unique.
c. represent each stage.
d. All of the alternatives are true.
ANSWER: c
TOPIC: The knapsack problem


TRUE/FALSE

1. Dynamic programming requires that its subproblems be independent of one another.
ANSWER: False
TOPIC: Introduction

2. Dynamic programming, when used for the shortest route problem, requires complete enumeration of paths
from the beginning to ending node.
ANSWER: False
TOPIC: Shortest route problem

3. The solution of stage k of a dynamic programming problem is dependent upon the solution of stage k-1.

,Chapter 21 Dynamic Programming 3




ANSWER: True
TOPIC: Dynamic programming notation

4. The output of stage k is the input for stage k-1.
ANSWER: True
TOPIC: Dynamic programming notation

5. State variables are a function of a state variable and a decision.
ANSWER: True
TOPIC: Dynamic programming notation

6. The return function for a shortest route problem refers to two directional arcs between nodes.
ANSWER: False
TOPIC: Shortest route problem

7. In solving a shortest route problem using dynamic programming the stages represent how many arcs you
are from the terminal node.
ANSWER: True
TOPIC: Shortest route problem

8. Dynamic programming is a general approach rather than a specific technique.
ANSWER: True
TOPIC: Notes and comments

9. Dynamic programming must only involve a finite number of decision alternatives and a finite number of
stages.
ANSWER: False
TOPIC: Introduction

10. Dynamic programming is a general approach with stage decision problems differing substantially from
application to application.
ANSWER: True
TOPIC: Introduction



SHORT ANSWER
1. What is the Principle of Optimality, and what is its relationship to Dynamic Programming?

TOPIC: Introduction

2. Define the following terms as they relate to dynamic programming.
a. Stage.
b. State variable.
c. Stage transformation function.

TOPIC: Dynamic programming notation

3. 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.

TOPIC: Dynamic programming notation

, Chapter 21 Dynamic Programming 4




PROBLEMS
1. Find the shortest path through the following network using dynamic programming.

10
2 5 3
8
4 8 3 8
7 4
6
7 11
1 3 6 10
9 9
7 3
2
12 7
9
9
7
4 7

TOPIC: Shortest route problem

2. 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.

TOPIC: Solving a dynamic programming problem

3. 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

a. Set up the network that represents the dynamic programming formulation.
b. Solve the problem using dynamic programming.

TOPIC: Dynamic programming