Chapter 19 – Solution Procedures for Transportation and Assignment Problems
True / False
1. The transportation simplex method can be used to solve the assignment problem.
a.
True
b.
False
2. The transportation simplex method is limited to minimization problems.
a.
True
b.
False
3. For an assignment problem with 3 agents and 4 tasks, the assignment matrix will have 3 rows and 4 columns.
a.
True
b.
False
4. If a transportation problem has four origins and five destinations, one of the destinations will not be fully supplied.
a.
True
b.
False
5. When an assignment problem involves an unacceptable assignment, a dummy agent or task must be introduced.
a.
True
b.
False
6. In assignment problems, dummy agents or tasks are created when the number of agents and tasks is not equal.
a.
True
b.
False
7. The transportation simplex method is more efficient than general-purpose linear programming for solving large-sized
transportation problems.
a.
True
b.
False
8. A dummy origin in a transportation problem is used when supply exceeds demand.
a.
True
b.
False
9. The net evaluation index for occupied cells in the transportation simplex method is 0.
a.
True
b.
False
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
10. Optimal assignments are made in the Hungarian method to cells in the reduced matrix that contain a 0.
a.
True
b.
False
11. Using the Hungarian method, the optimal solution to an assignment problem is found when the minimum number of
lines required to cover the zero cells in the reduced matrix equals the number of agents.
a.
True
b.
False
12. To handle unacceptable routes in a transportation problem where cost is to be minimized, infeasible arcs must be
assigned negative cost values.
a.
True
b.
False
Multiple Choice
13. A solution to a transportation problem that has less than m + n − 1 cells with positive allocations in the transportation
tableau is
a.
an optimal solution.
b.
an initial feasible solution.
c.
a minimum-cost solution.
d.
a degenerate solution.
14. The optimal solution is found in an assignment matrix when the minimum number of straight lines needed to cover all
the zeros equals
a.
(the number of agents) − 1.
b.
(the number of agents).
c.
(the number of agents) + 1.
d.
(the number of agents) + (the number of tasks).
15. The stepping-stone method requires that one or more artificially occupied cells with a flow of zero be created in the
transportation tableau when the number of occupied cells is fewer than
a.
m + n − 2
b.
m + n − 1
c.
m + n
d.
m + n + 1
16. The per-unit change in the objective function associated with assigning flow to an unused arc in the transportation
simplex method is called the
a.
net evaluation index.
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
b.
degenerate value.
c.
opportunity loss.
d.
simplex multiplier.
17. The difference between the transportation and assignment problems is that
a.
total supply must equal total demand in the transportation problem
b.
the number of origins must equal the number of destinations in the transportation problem
c.
each supply and demand value is 1 in the assignment problem
d.
there are many differences between the transportation and assignment problems
18. An example of a heuristic is the
a.
minimum-cost method.
b.
stepping-stone method.
c.
Hungarian method.
d.
MODI method.
19. Using the transportation simplex method, the optimal solution to the transportation problem has been found when
a.
there is a shipment in every cell.
b.
more than one stepping-stone path is available.
c.
there is a tie for outgoing cell.
d.
the net evaluation index for each unoccupied cell is ≥ 0.
20. Identifying the outgoing arc in Phase II of the transportation simplex method is performed using the
a.
minimum cost method.
b.
MODI method.
c.
stepping-stone method.
d.
matrix reduction method.
21. The MODI method is used to
a.
identify an outgoing arc.
b.
identify an incoming arc.
c.
identify unoccupied cells.
d.
identify an initial feasible solution.
22. To use the transportation simplex method, a transportation problem that is unbalanced requires the use of
a.
artificial variables.
b.
one or more transshipment nodes.
c.
a dummy origin or destination.
d.
matrix reduction.
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
23. To use the Hungarian method, a profit-maximization assignment problem requires
a.
converting all profits to opportunity losses.
b.
a dummy agent or task.
c.
matrix expansion.
d.
finding the maximum number of lines to cover all the zeros in the reduced matrix.
24. To use the transportation simplex method,
a.
there can be no unacceptable routes.
b.
the initial feasible solution cannot be degenerate.
c.
a minimization objective function must be the case.
d.
total supply must equal total demand.
Subjective Short Answer
25. Develop the transportation tableau for this transportation problem.
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
26. Solve the following transportation problem using the transportation simplex method. State the minimum total shipping
cost.
Origin
Supply
Destination
Demand
A
500
X
300
B
400
Y
300
Z
300
Shipping costs are:
Destination
Source
X
Y
Z
A
2
3
5
B
9
12
10
27. Canning Transport is to move goods from three factories (origins) to three distribution centers (destinations).
Information about the move is given below. Solve the problem using the transportation simplex method and compute the
total shipping cost.
Origin
Supply
Destination
Demand
A
200
X
50
B
100
Y
125
C
150
Z
125
Shipping costs are:
Destination
Origin
X
Y
Z
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
A
3
2
5
B
9
10
—
C
5
6
4
(Source B cannot ship to destination Z)
Supply
Demand
250
125
125
Total shipping cost = $2,000.
28. The following table shows the unit shipping cost between cities, the supply at each origin city, and the demand at each
destination city. Solve this minimization problem using the transportation simplex method and compute the optimal total
cost.
Destination
Origin
Terre Haute
Indianapolis
Ft. Wayne
South Bend
Supply
St. Louis
8
6
12
9
100
Evansville
5
5
10
8
100
Bloomington
3
2
9
10
100
Demand
150
60
45
45
South Bend
150
45
45
Ship 10 from St. Louis to Indianapolis, 45 from St. Louis to Ft. Wayne, 45 from St. Louis to South Bend,
Indianapolis. The total cost is 1755.
29. After some special presentations, the employees of the AV Center have to move overhead projectors back to
classrooms. The table below indicates the buildings where the projectors are now (the origins), where they need to go (the
destinations), and a measure of the distance between sites. Determine the transport arrangement that minimizes the total
transport distance.
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
Destination
Origin
Business
Education
Parsons Hall
Holmstedt Hall
Supply
Baker Hall
10
9
5
2
35
Tirey Hall
12
11
1
6
10
Arena
15
14
7
6
20
Demand
12
20
10
10
Distance
12
120
20
180
3
6
10
10
7
42
13
0
358
30. Solve the following assignment problem using the Hungarian method. No agent can be assigned to more than one
task. Total cost is to be minimized.
Task
Agent
A
B
C
D
1
9
5
4
2
2
12
6
3
5
3
11
6
5
7
1
2
3
Total Cost
31. Use the Hungarian method to obtain the optimal solution to the following assignment problem in which total cost is to
be minimized. All tasks must be assigned and no agent can be assigned to more than one task.
Task
Agent
A
B
C
D
1
10
12
15
25
2
11
14
19
32
3
18
21
23
29
4
15
20
26
28
1
2
3
4
Total Cost
32. A professor has been contacted by four not-for-profit agencies that are willing to work with student consulting teams.
The agencies need help with such things as budgeting, information systems, coordinating volunteers, and forecasting.
Although each of the four student teams could work with any of the agencies, the professor feels that there is a difference
in the amount of time it would take each group to solve each problem. The professor’s estimate of the time, in days, is
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
given in the table below. Use the Hungarian method to determine which team works with which project. All projects must
be assigned and no team can be assigned to more than one project.
Project
Team
Budgeting
Information
Volunteers
Forecasting
A
32
35
15
27
B
38
40
18
35
C
41
42
25
38
D
45
45
30
42
works with information. The total time is 131.
33. A manufacturer of electrical consumer products, with its headquarters in Burlington, Iowa, produces electric irons at
Manufacturing Plants 1, 2, and 3. The irons are shipped to Warehouses A, B, C, and D. The shipping cost per iron, the
monthly warehouse requirements, and the monthly plant production levels are:
Warehouse
Monthly Plant
Production (units)
A
B
C
D
Plant 1
$.20
$.25
$.15
$.20
10,000
Plant 2
.15
.30
.20
.15
20,000
Plant 3
.15
.20
.20
.25
10,000
Monthly Warehouse
Requirements (units)
12,000
8,000
15,000
5,000
How many electric irons should be shipped per month from each plant to each warehouse to minimize monthly shipping
costs?
a.
Use the minimum cost method to find an initial feasible solution.
b.
Can the initial solution be improved?
c.
Compute the optimal total shipping cost per month.
c. Total monthly shipping cost = $6,650.
34. Al Bergman, staff traffic analyst at the corporate headquarters of Computer Products Corporation (CPC), is
developing a monthly shipping plan for the El Paso and Atlanta manufacturing plants to follow next year. These plants
manufacture specialized computer workstations that are shipped to five regional warehouses. Al has developed these
estimated requirements and costs:
Warehouse
Monthly Plant
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
Plant
Chicago
Dallas
Denver
New York
San Jose
Production (units)
Atlanta
$35
$40
$60
$45
$90
200
El Paso
50
30
35
95
40
300
Monthly Warehouse
Requirements (units)
75
100
25
150
150
Determine how many workstations should be shipped per month from each plant to each warehouse to minimize monthly
shipping costs, and compute the total shipping cost.
a.
Use the minimum cost method to find an initial feasible solution.
b.
Use the transportation simplex method to find an optimal solution.
c.
Compute the optimal total shipping cost.
c. Total monthly shipping cost = $19,625.
35. Consider the transportation problem below.
Destination
Supply
Origin
1
2
3
A
$ .50
$ .90
$ .50
100
B
.80
1.00
.40
500
C
.90
.70
.80
900
Demand
300
800
400
a.
Use the minimum cost method to find an initial feasible solution.
b.
Can the initial solution be improved?
c.
Compute the optimal total shipping cost.
a.
The minimum cost method provided the solution shown below.
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
36. Five customers needing their tax returns prepared must be assigned to five tax accountants. The estimated profits for
all possible assignments are shown below. Only one accountant can be assigned to a customer, and all customers’ tax
returns must be prepared. What should the customer-accountant assignments be so that estimated total profit is
maximized? What is the resulting total profit?
Accountant
Customer
1
2
3
4
5
A
$500
$525
$550
$600
$700
B
625
575
700
550
800
C
825
650
450
750
775
D
590
650
525
690
750
E
450
750
660
390
550
$ 700
37. Four jobs must be assigned to four work centers. Only one job can be assigned to each work center, and all jobs must
be processed. The cost of processing each job at each work center is shown below. Determine which jobs should be
assigned to which work center to minimize total processing cost. Compute the total processing cost.
Work Center
Job
1
2
3
4
A
$50
$45
$50
$65
B
25
40
35
20
C
65
60
55
65
E
55
65
75
85
38. Four employees must be assigned to four projects. Only one employee can be assigned to each project, and all projects
must be completed. The cost of each employee completing each project is shown below. Determine which employee
The solution cannot be improved. It is optimal.
Total shipping cost = $940.
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
should be assigned to which project to minimize total project completion cost. Be sure to compute the total project
completion cost.
Project
Employee
1
2
3
4
Al
$300
$325
$500
$350
Ben
400
525
575
600
Cal
350
400
600
500
Dan
400
350
450
450
$ 350
39.
A
large screen printer is faced with six jobs due on Tuesday. The plan is to do the jobs on Monday so they will be ready on
time. The shop has six worker-machine pairs that can work on any of the six jobs. Because of differing experience levels
and machine capabilities, processing times differ. The processing times presented in the table below are in minutes. What
is the optimal assignment of jobs to worker-machine pairs that minimizes total processing time?
Worker-Machine Pair
Job
1
2
3
4
5
6
A
250
375
175
425
225
350
B
350
310
375
410
275
225
C
410
450
325
275
315
275
D
380
245
350
375
210
350
E
395
250
280
390
410
375
F
250
285
410
385
300
295
40. A company ships products from four factories to four warehouses. The factory capacities, warehouse requirements,
and per-unit shipping costs are shown below:
Warehouse
Monthly Factory
Capacity (units)
1
2
3
4
Factory A
$11
$13
$ 9
$ 6
5,000
Factory B
12
10
7
9
10,000
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
Factory C
19
16
15
21
10,000
Factory D
7
6
4
9
5,000
Monthly Warehouse
Min. Requirement (units)
3,000
8,000
12,000
5,000
How many products should the company ship from each factory to each warehouse to minimize monthly shipping costs?
What will the monthly shipping cost be if the shipping plan is followed? (Use the minimum cost method to find an initial
feasible solution and the transportation simplex method to find an optimal solution.)
41.
The Des Moines plant of Tri-B Corp. has three fabrication departments with each producing a single unique product with
equipment that is dedicated solely to its product. The three products are moved to four assembly departments where they
are assembled.
Although any of the three products can be processed in any of the assembly departments, the materials-handling and
assembly costs are different because of the varying distances between departments and because of different equipment.
Each fabrication and assembly department has a different monthly capacity, and it is desirable that each department
operate at capacity. The variable costs and capacity for each department is shown below.
Assembly Department
Monthly Fabrication
Dept. Capacity (units)
1
2
3
4
Fabrication Dept. A
$1.20
$0.70
$0.50
$0.60
9,000
Fabrication Dept. B
0.70
0.50
0.50
0.60
17,000
Fabrication Dept. C
0.50
0.70
0.80
1.20
14,000
Monthly Assembly
Dept. Capacity (units)
3,000
10,000
15,000
12,000
How many units of each product should be moved from each fabrication department to each assembly department to
minimize total monthly costs? (Use the minimum cost method to find an initial feasible solution and the transportation
simplex method to find an optimal solution.) Compute the optimal total monthly cost?
Essay
42. For an assignment problem where the number of agents does not equal the number of tasks, what adjustments must be
made to allow the problem to be solved using the Hungarian method?
43. Explain how the transportation simplex method can be used to solve a transportation problem that has a maximization
Chapter 19 – Solution Procedures for Transportation and Assignment Problems
objective.
44. Explain what adjustments are made to the transportation tableau when there are unacceptable routes.
45. Explain what adjustments are made to the transportation tableau when total supply and total demand are not equal.
46. Explain how the Hungarian method can be used to solve an assignment problem that has a maximization objective.