Quantitative Analysis for Management, 11e (Render)
Chapter 9 Transportation and Assignment Models
1) Transportation and assignment problems are really linear programming techniques called network flow
problems.
2) Transportation models may be used when a firm is trying to decide where to locate a new facility.
3) A typical transportation problem may ask the question, “How many of X should be shipped to point E from
source A?”
4) The objective of a transportation problem solution is to schedule shipments from sources to destinations while
minimizing total transportation and production costs.
5) In a transportation problem, each destination must be supplied by one and only one source.
6) In a transportation problem, a single source may supply something to all destinations.
7) In finding the maximum quantity that can be shipped on the least costly route using the stepping–stone
method, one examines the closed path of plus and minus signs drawn and selects the smallest number found in
those squares containing minus signs.
8) In using the stepping–stone method, the path can turn at any box or cell that is unoccupied.
9) Using the stepping–stone method to solve a maximization problem, we would choose the route with the largest
positive improvement index.
10) One of the advantages of the stepping–stone method is that if, at a particular iteration, we accidentally choose
a route that is not the best, the only penalty is to perform additional iterations.
11) A “balanced problem” exists in a transportation model when the optimal solution has the same amount being
shipped over all paths that have any positive shipment.
12) It is possible to find an optimal solution to a transportation problem that is degenerate.
13) A solution to the transportation problem can become degenerate at any iteration.
14) The transportation algorithm can be used to solve both minimization problems and maximization problems.
15) Assignment problems involve determining the most efficient assignment of people to projects, salesmen to
territories, contracts to bidders, and so on.
16) The objective of an assignment problem solution most often is to minimize the total costs or time of
performing the assigned tasks.
17) In the assignment problem, the costs for a dummy row will be equal to the lowest cost of the column for each
respective cell in that row.
Topic: THE ASSIGNMENT ALGORITHM
18) The Hungarian method is designed to solve transportation problems efficiently.
19) Maximization assignment problems can easily be converted to minimization problems by subtracting each
rating from the largest rating in the table.
20) In a transportation problem, a dummy source is given a zero cost, while in an assignment problem, a dummy
source is given a very high cost.
Table 9–1
21) What is the total cost represented by the solution shown in Table 9–1?
A) 60
B) 2500
C) 2600
D) 500
E) None of the above
22) What is the value of the improvement index for cell B1 shown in Table 9–1?
A) –50
B) +3
C) +2
D) +1
E) None of the above
Table 9–2
23) In Table 9–2, cell A3 should be selected to be filled in the next solution. If this was selected as the cell to be
filled, and the next solution was found using the appropriate stepping–stone path, how many units would be
assigned to this cell?
A) 10
B) 15
C) 20
D) 30
E) None of the above
Table 9–3
The following improvements are proved for Table 9–3:
Cell
Improvement Index
A1
+2
A3
+6
B2
+1
B–Dummy
+2
C1
+2
C2
+1
24) The cell improvement indices for Table 9–3 suggest that the optimal solution has been found. Based on this
solution, how many units would actually be sent from source C?
A) 10
B) 170
C) 180
D) 250
E) None of the above
25) In Table 9–3, suppose shipping cost from source C to point 2 was 8, which below would be true?
A) There would be multiple optimal solutions.
B) The minimum possible total cost would decrease.
C) The minimum possible total cost would increase.
D) Another dummy column would be needed.
E) None of the above
26) Both transportation and assignment problems are members of a category of LP techniques called ________.
A) transshipment problems
B) Hungarian problems
C) source–destination problems
D) supply and demand problems
E) network flow problems
27) Transportation models can be used for which of the following decisions?
A) facility location
B) production mix
C) media selection
D) portfolio selection
E) employee shift scheduling
28) When using a general LP model for transportation problems, if there are 4 sources and 3 destinations, which
of the following statements is true?
A) There are typically 4 decision variables and 3 constraints.
B) There are typically 12 decision variables and 7 constraints.
C) There are typically 7 decision variables and 7 constraints.
D) There are typically 12 decision variables and 12 constraints.
E) There are typically 12 decision variables and 3 constraints.
29) The two most common objectives for the assignment problem are the minimization of ________.
A) uncertainty or inexperience
B) total costs or inexperience
C) total costs or total time
D) total time or inexperience
E) total costs or uncertainty
7
30) Assuming that Table 9–4 represents the results of an iteration of a transportation model,
Table 9–4
The next tableau will be:
A)
B)
C)
D)
E) None of the above
Table 9–5
31) Table 9–5 represents a solution that is
A) clearly optimal for a minimization objective.
B) degenerate.
C) infeasible.
D) All of the above
E) None of the above
Table 9–6
32) In Table 9–6, if cell A3 is filled on the next iteration, what is the improvement in the objective function?
A) 60
B) 30
C) 530
D) 590
E) None of the above
33) A transportation problem
A) is a special case of the linear programming problem.
B) can be solved by linear programming, but is solved more efficiently by a special–purpose algorithm.
C) may give an initial feasible solution rather than the optimal solution.
D) requires the same assumptions that are required for linear programming problems.
E) All of the above
Table 9–7
34) Table 9–7 illustrates a(n)
A) optimal solution.
B) degenerate solution.
C) unbounded solution.
D) infeasible solution.
E) None of the above
35) The only restriction we place on the initial solution of a transportation problem is that
A) we must have nonzero quantities in a majority of the boxes.
B) all constraints must be satisfied.
C) demand must be less than supply.
D) we must have a number (equal to the number of rows plus the number of columns minus one) of boxes that
contain nonzero quantities.
E) None of the above
36) Which of the following is used to summarize conveniently and concisely all relevant data and to keep track of
algorithm computations?
A) source–destination matrix
B) Hungarian table
C) stepping–stone grid
D) transportation table
E) tabulation report
37) In Table 9–8, which cell should be filled on the next iteration?
Table 9–8
A) A1
B) ADummy
C) B2
D) C1
E) C2
Table 9–9
38) The solution presented in Table 9–9 is
A) infeasible.
B) degenerate.
C) unbounded.
D) optimal.
E) None of the above
Table 9–10
39) What is wrong with Table 9–10?
A) The solution is infeasible.
B) The solution is degenerate.
C) The solution is unbounded.
D) Nothing is wrong.
E) There are too many filled cells.
40) Which of the following statements concerning the transshipment problem are false?
A) The number of units shipped into a transshipment point should be equal to the number of units shipped out.
B) There can be constraints on the number of units shipped out of an origin point.
C) There can be constraints on the number of units shipped into a destination point.
D) The transshipment problem can be solved with linear programming.
E) Any units shipped from one origin point must all go to the same destination point.
41) What is said to exist when total demand equals total supply in a transportation problem?
A) an equalized problem
B) an equilibrialized problem
C) a harmonized problem
D) a balanced problem
E) This situation can never occur.
Table 9–11
42) A company must assign mechanics to each of four jobs. The time involved varies according to individual
abilities. Table 9–11 shows how many minutes it takes each mechanic to perform each job. If the optimal
assignments are made, how many total minutes would be required for completing the jobs?
A) 0
B) 4
C) 17
D) 16
E) None of the above
Table 9–12
43) Given Table 9–12, the final table for an assignment problem, who should be assigned to job 2?
A) worker A
B) worker C
C) either worker A or worker C
D) neither worker A nor worker C
E) worker D
Table 9–13
44) Table 9–13 provides information about a transportation problem. This problem is
A) unbounded.
B) unbalanced.
C) infeasible.
D) All of the above
E) None of the above
45) Which of the following statements concerning transportation and assignment models is false?
A) The transportation, transshipment, and assignment problems can all be solved using linear programming.
B) A common objective is cost minimization.
C) Both transportation and assignment models involve the distribution of goods from sources to destinations.
D) The assignment problem can have a maximization objective.
E) The transshipment problem is a special class of transportation problems.
46) Which of the following is not part of the transportation algorithm?
A) northwest corner rule
B) stepping–stone method
C) balanced transportation table
D) portfolio selection
E) Hungarian method
47) Which technique requires that we start in the upper–left–hand cell of the table and allocate units to shipping
routes in a “stair step” fashion?
A) upper–left rule
B) stair step method
C) northwest corner rule
D) Vogel’s approximation method
E) MODI
48) If items being transported must go through an intermediate point before reaching a final destination, then this
situation is known as a(n) ________.
A) transshipment problem
B) assignment problem
C) transportation problem
D) intermediate point problem
E) None of the above