Deck 23: Transportation, Assignment, and Network Algorithms

Question 1

Once one improvement is made to a transportation network using the stepping-stone method, the solution is optimal.

Answer 1

False

Question 2

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

Answer 2

False

Question 3

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

Answer 3

True

Question 4

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.

Question 5

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.

Question 6

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

Question 7

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

Question 8

A closed route in the stepping-stone method that sums to zero means that an equivalent cost solution exists.

Question 9

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 10

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

Question 11

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

Question 12

The maximal-flow technique would be a useful tool when we are maximizing the cost of shipping items from a series of supply depots to regional distribution centers.

Question 13

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

Question 14

The Hungarian method is designed to solve transportation problems efficiently.

Question 15

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

Question 16

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

Question 17

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

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

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

Question 20

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

Question 21

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

Question 22

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

Question 23

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 24

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

Question 25

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.

Question 26

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

Question 27

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

Question 28

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

Question 29

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.

Question 30

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

Question 31

A chemical engineer might use the shortest route technique to determine the amount of a solution that can be delivered between two points in a soap factory.

Question 32

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 33

Table M8-3 The following improvements are proved for Table M8-3:

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.

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

Question 35

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.

Question 36

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

Question 37

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

Question 38

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

Question 39

Transportation models can be used for which of the following decisions?

A)facility location
B)production mix
C)media selection
D)portfolio selection

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

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)the amount put in a dummy source or destination can be considered a slack variable.

Question 42

The origin or beginning node in a network is called

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

Question 43

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.

Question 44

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.

Question 45

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.

Question 46

In a transportation problem, degeneracy occurs when

A)the number of used (or full)cells equals 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 positive cells contain the same smallest amount.
D)the number of rows exceeds the number of columns.

Question 47

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

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

Question 48

Objectives of the assignment problem would be most likely to include

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

Question 49

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.

Question 50

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

Question 51

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

Question 52

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.

Question 53

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.

Question 54

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)Only r + c-1 squares can be used as a "stepping-stone."

Question 55

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.

Question 56

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

Question 57

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

Question 58

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.

Question 59

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

Question 60

Practically speaking, multiple optimal solutions

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

Question 61

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)Yehudi's dilemma

Question 62

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.

Question 63

Find the shortest route from Node 1 to Node 4.

A)750
B)500
C)550
D)600

Question 64

Given the following traffic flows, in hundreds of cars per hour, what is the maximum traffic flow from City 1 to City 7?

A)1200
B)1400
C)900
D)800

Question 65

Find the shortest route from Node 1 to Node 4 using the shortest-route technique.

A)650
B)450
C)550
D)500

Question 66

Pipeline fluid flows are indicated below.Determine the maximum flow from Node 1 to Node 3.

A)100
B)400
C)500
D)700

Question 67

The shortest-route technique would best be used to

A)plan the routes for a cycling tour of North Cornwall.
B)wire a burglar alarm in a building.
C)cut patterns out of a bolt of cloth to minimize waste.
D)determine which team of referees should call each game in a professional league.

Question 68

Find the shortest route from Node 1 to Node 5.

A)200
B)350
C)250
D)450

Question 69

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)minimum cut problem

Question 70

Find the shortest route from Node 1 to Node 5 using the shortest-route technique.

A)350
B)400
C)450
D)600

Question 71

Pipeline fluid flows are indicated below.Determine the maximum flow from Node 1 to Node 5.

A)300
B)400
C)600
D)500

Question 72

The second step in the maximal-flow technique is to

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

Question 73

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

A)find the next-nearest node to the origin and put the distance in a box by the node.
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.

Question 74

Find the shortest route from Node 1 to Node 6.

A)300
B)450
C)550
D)650

Question 75

Find the shortest route from Node 1 to Node 6.

A)total distance = 350
B)total distance = 410
C)total distance = 270
D)total distance = 520

Question 76

The maximal-flow technique might be used

A)to help design the least expensive blend of grains to prepare a run of chicken feed at a mill.
B)by someone designing the traffic approaches to an airport.
C)by someone attempting to design roads that minimize the cubic feet of asphalt required.
D)to maximize the profit of the fall line of handbags.

Question 77

Pipeline fluid flows are indicated below.Determine the maximum flow from Node 1 to Node 4.

A)200
B)300
C)600
D)700

Question 78

Pipeline fluid flows are indicated below.Determine the maximum flow from Node 1 to Node 4.

A)100
B)150
C)200
D)50

Question 79

The shortest-route technique would best be used to

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

Question 80

Find the shortest route from Node 1 to Node 6.

A)300
B)450
C)550
D)650