There are six cities (City 1-City 6) serviced by a particular bus line. Limited routes are available, and the distance for each of these routes is presented in the table below.
From
City
To
City
Distance
(100s miles)
1
2
8
1
3
4
2
4
12
2
5
8
3
4
8
3
5
14
4
6
6
5
6
4
16) 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
E) 2
17) 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
E) None of the above
Answer: C
Diff: 2
Topic: SHORTEST-ROUTE PROBLEM SOLVED BY DYNAMIC PROGRAMMING
AACSB: Analytic Skill
18) 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
E) None of the above
19) 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
E) None of these
20) 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.
E) None of these
21) 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
E) None of these
22) The following information describes a shortest-route problem with the distance in miles. How many stages will this dynamic problem have?
From
To
Distance
From
To
Distance
1
2
40
3
7
20
1
3
22
4
6
43
1
4
66
4
7
33
1
5
39
5
7
66
2
6
18
6
8
72
2
7
24
7
8
58
3
6
23
A) 8
B) 4
C) 3
D) 2
E) 1
Table M2-1
The data below is a dynamic programming solution for a shortest route problem.
.jpg”>
23) 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
E) 75
24) 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
E) 24