Deck 21: Dynamic Programming

Question 1

Dynamic programming requires that its subproblems be independent of one another.

Answer 1

False

Question 2

State variables are a function of a state variable and a decision.

Answer 2

True

Question 3

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

Answer 3

True

Question 4

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.

Question 5

Stage transformation functions

A)are linear.
B)calculate the return.
C)determine the output of the stage.
D)All of the alternatives are true.

Question 6

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.

Question 7

Solutions in dynamic programming

A)are not optimal.
B)are unique.
C)represent each stage.
D)All of the alternatives are true.

Question 8

Dynamic programming, when used for the shortest route problem, requires complete enumeration of paths from the beginning to ending node.

Question 9

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.

Question 10

Dynamic programming is a general approach rather than a specific technique.

Question 11

In solving a shortest route problem using dynamic programming the stages represent how many arcs you are from the terminal node.

Question 12

If x₃ = t₄ (x₄,d₄) = x₄ -2d₄ and r₄(x₄,d₄) = 16d₄ the state variable is

A)t
B)x
C)r
D)d

Question 13

The output of stage k is the input for stage k-1.

Question 14

If x₃ = t₄(x₄,d₄) = x₄ - 2d₄ and r₄(x₄,d₄) = 16d₄, the subscripts refer to

A)state.
B)stage.
C)transformation.
D)return.

Question 15

The return function for a shortest route problem refers to two directional arcs between nodes.

Question 16

If x₃ = t₄(x₄,d₄) = x₄ -2d₄ and r₄(x₄,d₄) = 16d₄, the stage transformation function is

A)t
B)x
C)r
D)d

Question 17

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.

Question 18

A return function is a value such as profit or loss associated with making decision d_n at:

A)stage n for specific value of output variable x_n.
B)stage n for a specific value of input variable x_n.
C)stage n for a specific value of stage m.
D)input n for a specific value of output variable x_n.

Question 19

Dynamic programming must only involve a finite number of decision alternatives and a finite number of stages.

Question 20

Dynamic programming is a general approach with stage decision problems differing substantially from application to application.

Question 21

What is the Principle of Optimality, and what is its relationship to Dynamic Programming?

Question 22

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.

Question 23

Consider the following integer linear program
Max
5x₁ + 7x₂ + 9x₃
s.t.
2x₁ + 3x₂ + 4x₃ $\le$ 8
x₁ $\le$ 3
x₂ $\le$ 2
x₁, x₂, x₃ $\ge$ 0, integer
a.Set up the network that represents the dynamic programming formulation.
b.Solve the problem using dynamic programming.

Question 24

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.

Question 25

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

Question 26

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.

Question 27

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.

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

Question 29

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

Question 30

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