Deck 23: Transportation, Assignment, and Network Algorithms

Question 1

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.

Answer 1

True

Question 2

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.

Answer 2

False

Question 3

In a transportation problem,a single source may supply something to all destinations.

Answer 3

True

Question 4

The Hungarian method is designed to solve transportation problems efficiently.

Question 5

The maximal-flow technique would be helpful to city planners in determining how freeways should be expanded.

Question 6

A solution to the transportation problem can become degenerate at any iteration.

Question 7

Maximization assignment problems can easily be converted to minimization problems by subtracting each rating from the largest rating in the table.

Question 8

It is possible to find an optimal solution to a transportation problem that is degenerate.

Question 9

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.

Question 10

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.

Question 11

The transportation algorithm can be used to solve both minimization problems and maximization problems.

Question 12

Busy highways are often analyzed with the maximal-flow technique.

Question 13

The objective of a transportation problem solution is to schedule shipments from sources to destinations while minimizing total transportation and production costs.

Question 14

Transportation models may be used when a firm is trying to decide where to locate a new facility.

Question 15

In using the stepping-stone method,the path can turn at any box or cell that is unoccupied.

Question 16

The objective of an assignment problem solution most often is to minimize the total costs or time of performing the assigned tasks.

Question 17

A typical transportation problem may ask the question,"How many of X should be shipped to point E from source A?"

Question 18

Assignment problems involve determining the most efficient assignment of people to projects,salesmen to territories,contracts to bidders,and so on.

Question 19

Using the stepping-stone method to solve a maximization problem,we would choose the route with the largest positive improvement index.

Question 20

In a transportation problem,each destination must be supplied by one and only one source.

Question 21

The shortest-route technique might be used by someone planning a vacation in order to minimize the required amount of driving.

Question 22

The maximal-flow model might be of use to an engineer looking for spare capacity in an oil pipeline system.

Question 23

Table M8-2
In Table M8-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

Question 24

Table M8-1
What is the value of the improvement index for cell B1 shown in Table M8-1?

A)-50
B)+3
C)+2
D)+1
E)None of the above

Question 25

The shortest-route model assumes that one is trying to connect two end points in the shortest manner possible,rather than attempting to connect all the nodes in the model.

Question 26

In the maximal-flow technique,a zero (0)means no flow or a one-way arc.

Question 27

A traveling salesperson might use the shortest route technique to minimize the distance traveled to reach one of his/her customers.

Question 28

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

Question 29

In Table M8-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

Question 30

The maximal-flow model assumes that there is a net flow from "source" to "sink."

Question 31

Table M8-3 The following improvements are proved for Table M8-3:
The cell improvement indices for Table M8-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

Question 32

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.

Question 33

The maximal-flow technique might be used by the U.S.Army Corps of Engineers to study water run-off in an attempt to minimize the danger from floods.

Question 34

Table M8-1
What is the total cost represented by the solution shown in Table M8-1?

A)60
B)2500
C)2600
D)500
E)None of the above

Question 35

Table M8-6
In Table M8-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

Question 36

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.

Question 37

We may begin the maximal-flow technique by picking an arbitrary path through the network.

Question 38

Table M8-4 the next tableau will be:
A) B) C) D) E)None of the above
Answer: B
Diff: 3
Topic: THE TRANSPORTATION ALGORITHM
AACSB: Analytic Skills
Table M8-5
Table M8-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

Question 39

Transportation companies would definitely be interested in the shortest-route technique to optimize travel.

Question 40

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.

Question 41

Which of the following accurately describes steps of the northwest corner rule,after making the initial allocation of units in the northwest cell?

A)Move down first,and then move right.
B)Move right first,and then move down.
C)Move right or down first,depending on whether the demand requirement or the supply capacity,respectively,is exhausted first.
D)Move right or down first,depending on whether the supply capacity or the demand requirement,respectively,is exhausted first.
E)Move diagonally first.

Question 42

Table M8-7
Table M8-7 illustrates a(n)

A)optimal solution.
B)degenerate solution.
C)unbounded solution.
D)infeasible solution.
E)None of the above

Question 43

In the transportation problem,using the stepping-stone method,

A)you may not skip over an empty cell.
B)you may not skip over a used cell.
C)your path may not cross over itself.
D)if you have an optimal solution and get an improvement index of zero,there is another optimal solution.
E)None of the above

Question 44

An artificial source added to a transportation table when total demand is greater than total supply is called

A)excess source.
B)filler source.
C)dummy source.
D)demand source.
E)supply source.

Question 45

After testing each unused cell by the stepping-stone method in the transportation problem and finding only one cell with a negative improvement index,

A)once you make that improvement,you would definitely have an optimal solution.
B)you would make that improvement and then check all unused cells again.
C)you could stop because you already had the optimal solution.
D)you should check to be sure that you don't have to add a dummy source or dummy destination.
E)None of the above

Question 46

Which of the following techniques can be used for moving from an initial feasible solution to an optimal solution in a transportation problem?

A)Hungarian method
B)stepping-stone method
C)northwest corner rule
D)Vogel's approximation method
E)All of the above

Question 47

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

Question 48

If the total supply from the sources does not equal the total demand from the destinations in the transportation problem,

A)and if supply is greater than demand,add a dummy source or factory.
B)the amount put in a dummy source or destination should make supply and demand equal.
C)and if demand is greater than supply,add a dummy destination or warehouse.
D)All of the above
E)None of the above

Question 49

When using the stepping-stone method,what is the maximum amount that can be shipped on the new route?

A)the smallest number found in the squares with minus signs
B)the smallest number found in the squares with plus signs
C)the smallest number along the closed path
D)the minimum of the demand requirement for that column and the supply capacity for that row
E)the largest number found on the squares with minus signs

Question 50

Table M8-11
A company must assign mechanics to each of four jobs.The time involved varies according to individual abilities.Table M8-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

Question 51

Table M8-14
The solution shown in Table M8-14 is

A)infeasible.
B)one of a number of alternate solutions.
C)unbounded.
D)optimal.
E)None of the above

Question 52

Table M8-13
Table M8-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

Question 53

Table M8-10
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.

Question 54

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

Question 55

Table M8-12
Given Table M8-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

Question 56

Which of the following is an applicable characteristic in using the stepping-stone method?

A)Only an unoccupied square may be used as a "stepping-stone."
B)Only an occupied square may be used as a "stepping-stone."
C)Only the column and row with the highest factory capacity may be used as a "stepping-stone."
D)All of the above
E)None of the above

Question 57

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

Question 58

Table M8-10
What is wrong with Table M8-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.

Question 59

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

Question 60

If we want to quickly arrive at a "feasible," but not necessarily "optimal" solution to the transportation problem,we will use the

A)stepping-stone method.
B)northwest corner rule.
C)Vogel's approximation method.
D)MODI method.
E)Any of the above

Question 61

The final node or destination in a network is called a(n)

A)arc.
B)branch.
C)source.
D)mouth.
E)sink.

Question 62

The maximal-flow technique would best be used

A)to assign workers to jobs in the cheapest manner.
B)to determine the number of units to ship from each source to each destination.
C)to determine LAN network wiring within a building.
D)to maximize traffic flow on a busy highway.
E)by a trucking company making frequent but repeatable drops.

Question 63

In an assignment problem

A)the number of rows and columns must be equal.
B)the number of rows must exceed the number of columns.
C)the number of rows must equal or exceed the number of columns.
D)the number of columns must equal or exceed the number of rows.
E)None of the above

Question 64

When using the shortest-route technique,the first step is to

A)connect the nearest node that minimizes the total distance to the origin.
B)trace the path from the warehouse to the plant.
C)determine the average distance traveled from source to end.
D)find the nearest node to the origin and put a distance box by the node.
E)None of the above

Question 65

The origin or beginning node in a network is called

A)home.
B)delta.
C)source.
D)mouth.
E)sink.

Question 66

Which of the following problems can be solved as a linear program using binary decision variables?

A)maximal-flow problem
B)shortest-route problem
C)minimal-spanning tree problem
D)A and B
E)A,B,and C

Question 67

In a transportation problem,degeneracy occurs when

A)the number of used (or full)cells does not equal the number of rows plus columns minus one.
B)in an initial solution,both a row total and a column total are satisfied simultaneously.
C)during an improvement,two negative cells contain the same smallest amount.
D)All of the above
E)None of the above

Question 68

Which of the following methods is used only with the assignment problem?

A)the Hungarian method
B)stepping-stone method
C)MODI method
D)Vogel's approximation method
E)the simplex method

Question 69

The maximal-flow technique might be used

A)to help design the moving sidewalks transporting passengers from one terminal to another in a busy airport.
B)by someone designing the traffic approaches to an airport.
C)by someone attempting to design roads that would limit the flow of traffic through an area.
D)All of the above
E)None of the above

Question 70

Which of the following is not considered a special situation with the transportation algorithm?

A)unbalanced transportation problems
B)degeneracy
C)unconstrained transportation problems
D)more than one optimal solution
E)maximization transportation problems

Question 71

Practically speaking,multiple optimal solutions

A)are infeasible.
B)are unbounded.
C)are degenerate.
D)are unbalanced.
E)provide management with greater flexibility in selecting and using resources.

Question 72

In revising the opportunity cost table of the assignment problem,after drawing lines through all of the zeros,

A)the smallest uncovered number is added to all zeros.
B)the smallest uncovered number is added to all uncovered numbers.
C)the largest uncovered number is added to all uncovered numbers.
D)the smallest uncovered number is added to all numbers at the intersection of lines.
E)the largest uncovered number is added to all numbers at the intersection of lines.

Question 73

The second step in the maximal-flow technique is to

A)pick the node with the maximum flow.
B)pick any path with some flow.
C)decrease the flow as much as possible.
D)add capacity to the path with minimum flow.
E)find the arc on the previously chosen path with the smallest flow capacity available.

Question 74

Objectives of the assignment problem can include

A)minimize total costs.
B)minimize total time to perform the tasks at hand.
C)minimize opportunity costs.
D)maximize profit.
E)All of the above

Question 75

Which of the following problems can be solved as a linear program using integer decision variables?

A)maximal-flow problem
B)shortest-route problem
C)minimal-spanning tree problem
D)A and B
E)A,B,and C

Question 76

Which of the following is not a step in the Hungarian method of assignment?

A)find the opportunity-cost table
B)test for an optimal assignment
C)enumerate all possible solutions
D)revise the opportunity-cost table
E)None of the above

Question 77

The first step in the maximal-flow technique is to

A)pick the node with the maximum flow.
B)pick any path with some flow.
C)eliminate any node that has a zero flow.
D)add a dummy flow from the start to the finish.
E)None of the above

Question 78

The shortest-route technique would best be used to

A)plan the routes for a vacation driving tour.
B)plan the route for a school bus.
C)determine the path for a truck making frequent runs from a factory to a warehouse.
D)All of the above
E)None of the above

Question 79

Why don't we want to use the transportation algorithm to solve the assignment problem?

A)It would likely lead to an unbounded solution.
B)It would likely lead to a degenerate solution.
C)It would likely lead to an infeasible solution.
D)It would likely lead to multiple optima.
E)It would likely lead to an unbalanced solution.

Question 80

The shortest-route technique would best be used to

A)assign workers to jobs in the cheapest manner.
B)determine the number of units to ship from each source to each destination.
C)determine the amount of LAN network wiring within a building.
D)minimize the amount of traffic flow on a busy highway.
E)determine the path for a truck making frequent but repeatable drops.