Deck 17: Dynamic Programming

Question 1

The arrow labeled S₂ in Figure M2.1 represents the output from stage 1.

Answer 1

True

Question 2

Both dynamic programming and linear programming take a multi-stage approach to solving problems.

Answer 2

False

Question 3

The arrow labeled D₂ in Figure M2.1 represents a disturbance.

Answer 3

False

Question 4

Linear programming is typically applied to problems wherein one must make a decision at a specified point (or points)in time.Dynamic programming is typically applied to problems wherein one must make a sequence of decisions.

Question 5

Subproblems in a dynamic programming problem are called stages.

Question 6

In a shortest-route problem, the nodes represent the destinations.

Question 7

Dynamic programming can be applied to a professional tennis player's serving strategy.

Question 8

In dynamic programming, there is a state variable defined for every stage.

Question 9

The problem that NASA has in determining what types of cargo may be loaded on the space shuttle is an example of a knapsack problem.

Question 10

A transformation changes the identities of the state variables.

Question 11

The formula s_n = t_n(s_n-1,d_n,r_n)allows us to go from one stage to the next in Figure M2.1.

Question 12

In dynamic programming, the decision rules defining an optimal policy give optimal decisions for any entering condition at any stage.

Question 13

Each item in a knapsack problem will be a stage of the dynamic programming problem.

Question 14

In a shortest-route problem, the limit on the number of allowable decision variables from one node to another is the number of possible nodes to which one might yet travel.

Question 15

The second step in solving a dynamic programming problem is to solve the last stage of the problem for all conditions or states.

Question 16

Your local paper carrier could make use of the shortest-route technique.

Question 17

The arrow labeled S₁ in Figure M2.1 represents an output.

Question 18

Dynamic programming can only be used to solve network-based problems.

Question 19

For knapsack problems, s_n-1 = a_n × s_n + b_n × d_n + c_n is a typical transformation expression.

Question 20

In Figure M2.1 there is a function t₂ that is not depicted, that converts s₂ and d₂ to s₁.

Question 21

The data below is a dynamic programming solution for a shortest route problem.

Using the data in Table M2-1, determine the distance of stage 1 for the optimal route.

A)0
B)8
C)12
D)16

Question 22

The following information describes a shortest-route problem with the distance in miles.What is the shortest possible route from node 1 to node 8?

A)100
B)130
C)157
D)181

Question 23

The data below is a dynamic programming solution for a shortest route problem.

According to Table M2-2, which gives a solution to a shortest route problem solved with dynamic programming, which cities would be included in the best route?

A)1, 2, 3, 4, 5, 6
B)1, 4, 6, 7
C)1, 2, 5, 6, 7
D)6, 7

Question 24

The following information describes a shortest-route problem with the distance in miles.How many stages will this dynamic problem have?

A)8
B)4
C)3
D)2

Question 25

The data below is a dynamic programming solution for a shortest route problem.

Using the data in Table M2-1, determine the minimum distance from point 1 to point 7.

A)21
B)22
C)23
D)24

Question 26

The following information describes a shortest-route problem with the distance in miles.Which nodes are involved in the shortest route?

A)1-3-7-8
B)1-2-6-8
C)1-4-7-8
D)1-4-6-8

Question 27

The data below is a dynamic programming solution for a shortest route problem.

Using the data in Table M2-1, determine the optimal arc of stage 1.

A)6
B)7
C)6 - 7
D)5 - 7

Question 28

The data below is a dynamic programming solution for a shortest route problem.

According to Table M2-2, which gives a solution to a shortest route problem solved with dynamic programming, the total distance from City 1 to City 7 is 14.What is the shortest distance from City 3 to City 7?

A)7
B)10
C)13
D)25

Question 29

There are three items (A, B, and C) that are to be shipped by air. The weights of these are 4, 5, and 3 tons, respectively. The profits (in thousands of dollars) generated by these are 3 for A, 4 for B, and 2 for C. There are four units of each available for shipment. Only 12 tons may be loaded on the plane. The maximum possible profit for this would be

A) 7.
B) 8.
C) 9.
D) 10.

Question 30

The data below is a dynamic programming solution for a shortest route problem.

Using the data in Table M2-1, what is the optimal travel path from point 1 to 7?

A)5, 7
B)6, 7
C)1, 2, 6, 7
D)1, 2, 5, 7

Question 31

If dynamic programming were used to solve for the minimum distance from City 1 to City 6 above, how many stages would there be?

A)6
B)5
C)4
D)3

Question 32

The data below is a dynamic programming solution for a shortest route problem.

Using the data in Table M2-1, determine the distance of stage 3 for the optimal route.

A)22
B)23
C)7
D)10

Question 33

The data below is a dynamic programming solution for a shortest route problem.

Using the data in Table M2-1, what is the optimal arc of stage 3?

A)1
B)1 - 4
C)1 - 3
D)1 - 2

Question 34

There are three items (A, B, and C) that are to be shipped by air. The weights of these are 4, 5, and 3 tons, respectively, and the plane can carry 13 tons. The profits (in thousands of dollars) generated by these are 3 for A, 4 for B, and 2 for C. There are four units of each available for shipment. If this were to be solved as a dynamic programming problem, how many stages would there be?

A) 1
B) 2
C) 3
D) 4

Question 35

The data below is a dynamic programming solution for a shortest route problem.

Using the data in Table M2-1, determine the optimal arc of stage 2.

A)3 - 6
B)3 - 5
C)2 - 6
D)2 - 5

Question 36

For the bus line problem above, what are the stages that provide the minimum distance?

A)1-2, 2-4, 4-6
B)1-2, 2-5, 5-6
C)1-3, 3-4, 4-6
D)1-3, 3-5, 5-6

Question 37

For the bus line problem above, what is the minimum possible distance to travel from City 1 to City 6?

A)26
B)20
C)18
D)22

Question 38

The data below is a dynamic programming solution for a shortest route problem.

Using the data in Table M2-1, determine the distance of stage 2 for the optimal route.

A)0
B)4
C)8
D)12

Question 39

There are six cities (City 1-City 6) serviced by a particular airline. Limited routes are available, and the distances for each of these routes are presented in the table below.

What is the minimum distance that must be traveled to get from City 1 to City 6?

A)46
B)47
C)48
D)49

Question 40

There are three items (A, B, and C) that are to be shipped by air. The weights of these are 4, 5, and 3 tons, respectively. The profits (in thousands of dollars) generated by these are 6 for A, 7 for B, and 5 for C. A total of 14 tons may be carried by the plane. There are four units of each available for shipment. What is the maximum possible profit for this situation?

A) 14
B) 20
C) 21
D) 22

Question 41

For the shortest route problem described in Table M2-4, what is the length of the shortest route?

A)205 miles
B)94 miles
C)241 miles
D)108 miles

Question 42

A transformation describes

A)the relationship between stages.
B)the initial condition of the system.
C)a stage.
D)a state variable.

Question 43

There are six cities (City 1-City 6) serviced by a particular airline. Limited routes are available, and the distances for each of these routes are presented in the table below.

Which nodes are involved in the shortest distance between City 1 and City 6?

A)1-2-4-6
B)1-2-5-6
C)1-3-4-6
D)1-3-5-6

Question 44

A stage is a(n)

A)alternative.
B)policy.
C)condition at the end of the problem.
D)subproblem.

Question 45

Figure M2.1
In Figure M2.1, arrow S₂ represents a(n)

A)signal.
B)source.
C)stage.
D)output.

Question 46

There are seven cities (City 1-City 7) served by Acme Trucking. Route availability is limited. The distances, in hundreds of miles, are given in the table below for each route.

What is the minimum distance a load being moved from City 1 to City 7 must travel?

A)3000 miles
B)2900 miles
C)1500 miles
D)2700 miles

Question 47

There are six cities (City 1-City 6) serviced by a particular airline. Limited routes are available, and the distances for each of these routes are presented in the table below.

What is the shortest route between City 1 and City 5?

A)29
B)30
C)31
D)32

Question 48

The above information describes a shortest-route problem with the distance in miles.How many stages will this dynamic programming problem have?

A)8
B)4
C)3
D)2

Question 49

GATRA, the Greater Attleboro-Taunton Regional Transit Authority, serves six cities (City 1-City 6). While there are many restrictions (primarily roads on which they may not travel), they do have some choice of routes. The distances between cities, along permitted routes, are presented below.

What is the minimum distance that must be traveled to get from City 1 to City 6?

A)26
B)9
C)11
D)3

Question 50

There are seven cities (City 1-City 7) served by Acme Trucking. Route availability is limited. The distances, in hundreds of miles, are given in the table below for each route.

If the truck were required to take the route from City 4 to City 5, what would be the overall route?

A)1-3, 3-4, 4-5, 5-6, 6-7
B)1-2, 2-4, 4-5, 5-7
C)1-2, 2-3, 3-4, 4-5, 5-6, 6-7
D)1-3, 3-5, 5-6, 6-7

Question 51

For the shortest route problem described in Table M2-3, which arcs comprise the shortest route?

A)1-2, 2-6, 6-8
B)1-5, 5-8
C)1-2, 2-5, 5-8
D)1-3, 3-5, 5-8

Question 52

GATRA, the Greater Attleboro-Taunton Regional Transit Authority, serves six cities (City 1-City 6). While there are many restrictions (primarily roads on which they may not travel), they do have some choice of routes. The distances between cities, along permitted routes, are presented below.

What is the shortest route?

A)1-3, 3-5, 5-6
B)1-2, 2-3, 3-4, 4-5, 5-6
C)1-3, 3-4, 4-5, 5-6
D)1-2, 2-3, 3-5, 5-6

Question 53

For the shortest route problem described in Table M2-3, what is the distance for the shortest route?

A)155 miles
B)66 miles
C)59 miles
D)114 miles

Question 54

Figure M2.1
In Figure M2.1, arrow S₁ represents a(n)

A)signal.
B)input.
C)stage.
D)source.

Question 55

There are six cities (City 1-City 6) serviced by a particular airline. Limited routes are available, and the distances for each of these routes are presented in the table below.

Which nodes are involved in the shortest distance between City 1 and City 5?

A)1-2-5
B)1-3-5
C)1-2-3-5
D)1-2-4-5

Question 56

There are seven cities (City 1-City 7) served by Acme Trucking. Route availability is limited. The distances, in hundreds of miles, are given in the table below for each route.

What route should the truck from City 1 to City 7 take?

A)1-2, 2-5, 5-7
B)1-3, 3-4, 4-6, 6-7
C)1-2, 2-4, 4-5, 5-6, 6-7
D)1-3, 3-5, 5-6, 6-7

Question 57

Figure M2.1
In Figure M2.1, arrow d₂ represents a

A)decision
B)disturbance
C)d-transformation
D)dynamic node

Question 58

There are four items (A, B, C, and D) that are to be shipped by truck. The weights of these are 3, 7, 4, and 5 tons, respectively, and the plane can carry 13 tons. The profits (in thousands of dollars) generated by these are 3 for A, 4 for B, 2 for C, and 5 for D. There are three units of each available for shipment. The maximum possible profit for this would be

A) $9.
B) $11.
C) $13.
D) $15.

Question 59

There are four items (A, B, C, and D) that are to be shipped by truck. The weights of these are 3, 7, 4, and 5 tons, respectively, and the plane can carry 13 tons. The profits (in thousands of dollars) generated by these are 3 for A, 4 for B, 2 for C, and 5 for D. There are four units of each available for shipment. If this were to be solved as a dynamic programming problem, how many stages would there be?

A) 1
B) 2
C) 3
D) 4

Question 60

There are seven cities (City 1-City 7) served by Acme Trucking. Route availability is limited. The distances, in hundreds of miles, are given in the table below for each route.

If the truck were required to take the route from City 4 to City 5, what would be the shortest distance from City 1 to City 7?

A)2900 miles
B)3200 miles
C)3700 miles
D)3400 miles

Question 61

Develop the shortest-route network for the problem below, and determine the minimum distance from node 1 to node 7.

Question 62

Using the data in Table M2-5, determine the optimal travel path from point 1 to point 7.

A)1 - 2, 2 - 4, 4 - 5, 5 - 7
B)1 - 2, 2 - 5, 5 - 7
C)1 - 3, 3 - 4, 4 - 5, 5 - 7
D)1 - 2, 2 - 4, 4 - 6, 6 - 7

Question 63

There are four items (A, B, C, and D)that are to be shipped by air.The weights of these are 5, 7, 8, and 11 tons, respectively.The profits (in thousands of dollars)generated by these are 5 for A, 8 for B, 7 for C, and 10 for D.There are 3 units of A, 4 unit of B, 6 units of C, and 5 units of D available to be shipped.The maximum weight is 44 tons.Use dynamic programming to determine the maximum possible profits that may be generated.

Question 64

Using the data in Table M2-5, determine the minimum distance from point 1 to point 7.

A)18
B)17
C)23
D)14

Question 65

Hard D.Head has decided that he wants to climb one of the world's tallest mountains.He has mapped out a number of routes between various points on the mountain, and rated each route as to difficulty.His rating scale considers a 1 as being particularly easy, and a 10 as being almost impossible.
(a)Given the information below, identify the route that would provide the easiest climb.
(b)What would be the average rating of the route?
(c)What is wrong with this approach to Mr.Head's problem?

Question 66

Using the data in Table M2-5, determine the optimal arc of stage 1.

A)3 - 7
B)6 - 7
C)5 - 7
D)4 - 7

Question 67

GATRA, the Greater Attleboro-Taunton Regional Transit Authority, serves six cities (City 1-City 6). While there are many restrictions (primarily roads on which they may not travel), they do have some choice of routes. The distances between cities, along permitted routes, are presented below.

Which routes should be traveled?

A)1-2, 2-3, 3-5, 5-6
B)1-2, 2-3, 3-4, 4-6
C)1-2, 2-5, 5-6
D)1-4, 4-6

Question 68

Using the data in Table M2-5, determine the optimal arc of stage 4.

A)1 - 2
B)2 - 4
C)1 - 3
D)3 - 4

Question 69

The data below details the distances that a delivery service must travel.Use dynamic programming to solve for the shortest route from City 1 to City 8.

Question 70

Using the data in Table M2-5, determine the optimal distance of stage 3.

A)22
B)17
C)24
D)7

Question 71

Using the data in Table M2-5, determine the optimal arc of stage 2.

A)4 - 6
B)5 - 6
C)4 - 5
D)2 - 5

Question 72

Using the data in Table M2-5, determine the optimal distance of stage 2.

A)10
B)7
C)8
D)11

Question 73

GATRA, the Greater Attleboro-Taunton Regional Transit Authority, serves six cities (City 1-City 6). While there are many restrictions (primarily roads on which they may not travel), they do have some choice of routes. The distances between cities, along permitted routes, are presented below.

What is the minimum distance that must be traveled to get from City 1 to City 6?

A)1100 miles
B)900 miles
C)1,300 miles
D)1,400 miles

Question 74

What is the decision criterion for a knapsack problem?

Question 75

What is meant by a decision variable in a shortest-route problem?

Question 76

Develop the shortest-route network for the problem below, and determine the minimum distance from node 1 to node 8.

Question 77

What is the decision criterion for a shortest route problem?

Question 78

Using the data in Table M2-5, determine the optimal distance of stage 1.

A)0
B)8
C)7
D)14

Question 79

What are the four steps in dynamic programming?

Question 80

For the shortest route problem described in Table M2-4, which arcs comprise the shortest route?

A)1-2, 2-6, 6-8
B)1-3, 3-5, 5-8
C)1-5, 5-8
D)1-2, 2-4, 4-7, 7-8