Deck 21: Dynamic Programming

Question 1

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

Answer 1

False

Question 2

​Finding the optimal solution to each stage of a dynamic programming problem will always lead to an optimal solution to the total problem.

Answer 2

True

Question 3

​In a production and inventory control problem, the states can correspond to the amount of inventory on hand at the beginning of each period.

Answer 3

True

Question 4

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

Question 5

​The stage transformation function identifies which state one reaches at the next stage for a given decision.

Question 6

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 7

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

Question 8

​In a knapsack problem, if one adds another item, one must completely resolve the problem in order to find a new optimal solution.

Question 9

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 10

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

Question 11

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

Question 12

​The subscripts used in dynamic programming notation refer to states.

Question 13

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 14

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

Question 15

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

Question 16

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

Question 17

In order to use dynamic programming, one must be able to view the problem as a multistage decision problem.

Question 18

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 19

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

Question 20

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

Question 21

​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:
​ 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?

Question 22

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 23

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

Question 24

​What is the Principle of Optimality, and what is its relationship to dynamic programming?

Question 25

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 26

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

Question 27

​Explain the divide-and-conquer solution strategy of dynamic programming.

Question 28

Solutions in dynamic programming

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

Question 29

​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 30

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 31

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

Question 32

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 33

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 34

​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:
​ ​
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?

Question 35

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 36

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 37

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

Question 38

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.