Forecasting: Time series and trend analysis

Chapter-9.pdf

Home >Business & Finance homework help >Operations Management homework help >Forecasting: Time series and trend analysis

341

1. Structure LP problems for the transportation, trans- shipment, and assignment models.

2. Use the northwest corner and stepping-stone methods.

9.1 Introduction

9.2 The Transportation Problem

9.3 The Assignment Problem

9.4 The Transshipment Problem

9.5 The Transportation Algorithm

9.6 Special Situations with the Transportation Algorithm

9.7 Facility Location Analysis

9.8 The Assignment Algorithm

9.9 Special Situations with the Assignment Algorithm

3. Solve facility location and other application problems with transportation models.

4. Solve assignment problems with the Hungarian (matrix reduction) method.

After completing this chapter, students will be able to:

CHAPTER OUTLINE

LEARNING OBJECTIVES

Transportation and Assignment Models

CHAPTER

Summary • Glossary • Solved Problems • Self-Test • Discussion Questions and Problems • Internet Homework Prob-

lems • Case Study: Andrew–Carter, Inc. • Case Study: Old Oregon Wood Store • Internet Case Studies • Bibliography

Appendix 9.1: Using QM for Windows

Supply Demand

Source Destination

Des Moines (Source 1)

100 300

300 200

Evansville (Source 2)

Albuquerque (Destination 1)

Boston (Destination 2)

Fort Lauderdale (Source 3)

Cleveland (Destination 3)

FIGURE 9.1 Network Representation of a Transportation problem, with Costs, Demands, and Supplies

9.1 Introduction

In this chapter we explore three special types of linear programming problems—the transporta- tion problem (first introduced in Chapter 8), the assignment problem, and the transshipment problem. All these may be modeled as network flow problems, with the use of nodes (points) and arcs (lines). Additional network models will be discussed in Chapter 11.

This first part of this chapter will explain these problems, provide network representations for them, and provide linear programming models for them. The solutions will be found using standard linear programming software. The transportation and assignment problems have a spe- cial structure that enables them to be solved with very efficient algorithms. The latter part of the chapter will present the special algorithms for solving them.

9.2 The Transportation Problem

The transportation problem deals with the distribution of goods from several points of supply (origins or sources) to a number of points of demand (destinations). Usually we are given a ca- pacity (supply) of goods at each source, a requirement (demand) for goods at each destination, and the shipping cost per unit from each source to each destination. An example is shown in Figure 9.1. The objective of such a problem is to schedule shipments so that total transportation costs are minimized. At times, production costs are included also.

Transportation models can also be used when a firm is trying to decide where to locate a new facility. Before opening a new warehouse, factory, or sales office, it is good practice to con- sider a number of alternative sites. Good financial decisions concerning the facility location also attempt to minimize total transportation and production costs for the entire system.

Linear Program for the Transportation Example The Executive Furniture Corporation is faced with the transportation problem shown in Figure 9.1. The company would like to minimize the transportation costs while meeting the demand at each destination and not exceeding the supply at each source. In formulating this as a linear

342 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

9.2 THE TRANSPORTATION PROBLEM 343

program, there are three supply constraints (one for each source) and three demand constraints (one for each destination). The decisions to be made are the number of units to ship on each route, so there is one decision variable for each arc (arrow) in the network. Let

number of units shipped from source i to destination j

where

1, 2, 3, with Des Moines, Evansville, and Fort Lauderdale

1, 2, 3, with Albuquerque, Boston, and Cleveland

The LP formulation is

subject to

(Des Moines supply)

(Evansville supply)

(Fort Lauderdale supply)

(Albuquerque demand)

(Boston demand)

(Cleveland demand)

for all i and j

The solution to this LP problem could be found using Solver in Excel 2010 by putting these con- straints into a spreadsheet, as discussed in Chapter 7. However, the special structure of this prob- lem allows for an easier and more intuitive format, as shown in Program 9.1. Solver is still used, but since all the constraint coefficients are 1 or 0, the left-hand side of each constraint is simply the sum of the variables from a particular source or to a particular destination. In Program 9.1 these are cells E10:E12 and B13:D13.

A General LP Model for Transportation Problems In this example, there were 3 sources and 3 destinations. The LP had variables and

constraints. In general, for a transportation problem with m sources and n destina- tion, the number of variables is mn, and the number of constraints is For example, if there are 5 (i.e., ) constraints and 8 (i.e., ) variables, the linear program would have

variables and constraints. The use of the double subscripts on the variables makes the general form of the linear pro-

gram for a transportation problem with m sources and n destinations easy to express. Let

number of units shipped from source i to destination j

cost one unit from source i to destination j

The linear programming model is

subject to

1, 2,..., m

1, 2,..., n

for all i and jxij Ú 0

j =g m

i=1 xij = dj

i =g n

j=1 xij … si

Minimize cost = g n

j=1 g m

i=1 cijxij

dj = demand at destination j

si = supply at source i

cij = xij =

5 + 8 = 135(8) = 40 n = 8m = 5

m + n. 3 + 3 = 6

3 * 3 = 9

Xij Ú 0

X13 + X23 + X33 = 200

X12 + X22 + X32 = 200

X11 + X21 + X31 = 300

X31 + X32 + X33 … 300

X21 + X22 + X23 … 300

X11 + X12 + X13 … 100

+ 3X23 + 9X31 + 7X32 + 5X33

Minimize total cost = 5X11 + 4X12 + 3X13 + 8X21 + 4X22

3 =2 =1 =j = 3 =2 =1 =i =

Xij =

The number of variables and constraints for a typical transportation problem can be found from the number of sources and destinations.

344 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

9.3 The Assignment Problem

The assignment problem refers to the class of LP problem that involve determining the most efficient assignment of people to projects, sales people to territories, auditors to companies for audits, contracts to bidders, jobs to machines, heavy equipment (such as cranes) to construction jobs, and so on. The objective is most often to minimize total costs or total time of performing the tasks at hand. One important characteristic of assignment problems is that only one job or worker is assigned to one machine or project.

Figure 9.2 provides a network representation of an assignment problem. Notice that this network is very similar to the network for the transportation problem. In fact, an assignment problem may be viewed as a special type of transportation problem in which the supply at each source and the demand at each destination must equal one. Each person may only be assigned to one job or project, and each job only needs one person.

An assignment problem is equivalent to a transportation problem with each supply and demand equal to 1.

PROGRAM 9.1 Executive Furniture Corporation Solution in Excel 2010

Set Objective: B16 By Changing cells: B10:D12 To: Min Subject to the Constraints:

E10:E12 <= F10:F12 B13:D13 = B14:D14

Solving Method: Simplex LP � Make Variables Non-Negative

Solver Parameter Inputs and Selections Key Formulas

Copy B13 to C13:D13

Copy E10 to E11:E12

9.3 THE ASSIGNMENT PROBLEM 345

Supply Demand

Person Project

Adams (Source 1)

1 1

$11

$14

$10

$11

$12

1 1

Brown (Source 2)

Project 1 (Destination 1)

Project 2 (Destination 2)

Cooper (Source 3)

Project 3 (Destination 3)

FIGURE 9.2 Example of an Assignment Problem in a Transportation Network Format

Linear Program for Assignment Example The network in Figure 9.2 represents a problem faced by the Fix-It Shop, which has just received three new repair projects that must be completed quickly: (1) a radio, (2) a toaster oven, and (3) a coffee table. Three repair persons, each with different talents, are available to do the jobs. The shop owner estimates the cost in wages if the workers are assigned to each of the three projects. The costs differ due to the talents of each worker on each of the jobs. The owner wishes to assign the jobs so that total cost is minimized and each job must have one person assigned to it, and each person can only be assigned to one job.

In formulating this as a linear program, the general LP form of the transportation problem can be used. In defining the variables, let

where

1, 2, 3, with Adams, Brown, and Cooper

1, 2, 3, with Project Project 2, and Project 3

The LP formulation is

subject to

or 1 for all i and j

The solution is shown in Program 9.2. From this, so Adams is assigned to project 3; so Brown is assigned to project 2; and so Cooper is assigned to project 1. All

other variables are 0. The total cost is 25. x31 = 1,x22 = 1,

x13 = 1,

xij = 0

X13 + X23 + X33 = 1

X12 + X22 + X32 = 1

X11 + X21 + X31 = 1

X31 + X32 + X33 … 1

X21 + X22 + X23 … 1

X11 + X12 + X13 … 1

+ 11X23 + 9X31 + 12X32 + 7X33

Minimize total cost = 11X11 + 14X12 + 6X13 + 8X21 + 10X22

3 =1, 2 =1 =j = 3 =2 =1 =i =

Xij = e1 if person i is assigned to project j

0 otherwise Special variables 0-1 are used with the assignment model.

346 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

9.4 The Transshipment Problem

In a transportation problem, if the items being transported must go through an intermediate point (called a transshipment point) before reaching a final destination, the problem is called a transshipment problem. For example, a company might be manufacturing a product at several factories to be shipped to a set of regional distribution centers. From these centers, the items are

PROGRAM 9.2 Fix-It Shop Solution in Excel 2010

Set Objective: B16 By Changing cells: B10:D12 To: Min Subject to the Constraints:

E10:E12 <= F10:F12 B13:D13 = B14:D14

Solving Method: Simplex LP � Make Variables Non-Negative

Solver Parameter Inputs and Selections Key Formulas

Copy B13 to C13:D13

Copy E10 to E11:E12

In the assignment problem, the variables are required to be either 0 or 1. Due to the special structure of this problem with the constraint coefficients as 0 or 1 and all the right-hand-side val- ues equal to 1, the problem can be solved as a linear program. The solution to such a problem (if one exists) will always have the variables equal to 0 or 1. There are other types of problems where the use of such 0–1 variables is desired, but the solution to such problems using normal linear programming methods will not necessarily have only zeros and ones. In such cases, spe- cial methods must be used to force the variables to be either 0 or 1, and this will be discussed as a special type of integer programming problem which will be seen in Chapter 10.

shipped to retail outlets that are the final destinations. Figure 9.3 provides a network representa- tion of a transshipment problem. In this example, there are two sources, two transshipment points, and three final destinations.

Linear Program for Transshipment Example Frosty Machines manufactures snow blowers in factories located in Toronto and Detroit. These are shipped to regional distribution centers in Chicago and Buffalo, where they are delivered to the supply houses in New York, Philadelphia, and St. Louis, as illustrated in Figure 9.3.

The available supplies at the factories, the demands at the final destination, and shipping costs are shown in the Table 9.1. Notice that snow blowers may not be shipped directly from Toronto or Detroit to any of the final destinations but must first go to either Chicago or Buffalo. This is why Chicago and Buffalo are listed not only as destinations but also as sources.

Frosty would like to minimize the transportation costs associated with shipping suffi- cient snow blowers to meet the demands at the three destinations while not exceeding the supply at each factory. Thus, we have supply and demand constraints similar to the trans- portation problem, but we also have one constraint for each transshipment point indicating that anything shipped from these to a final destination must have been shipped into that transshipment point from one of the sources. The verbal statement of this problem would be as follows:

9.4 THE TRANSSHIPMENT PROBLEM 347

A transportation problem with intermediate points is a transshipment problem.

Supply

800

450

350

300

700

DemandSource

Toronto (Node 1)

Detroit (Node 2)

Chicago (Node 3)

New York City (Node 5)

Philadelphia (Node 6)

St. Louis (Node 7)

Buffalo (Node 4)

DestinationTransshipment Point FIGURE 9.3 Network Representation of Transshipment Example

TABLE 9.1 Frosty Machine Transshipment Data

NEW YORK FROM CHICAGO BUFFALO CITY PHILADELPHIA ST. LOUIS SUPPLY

Toronto $4 $7 — — — 800

Detroit $5 $7 — — — 700

Chicago — — $6 $4 $5 —

Buffalo — — $2 $3 $4 —

Demand — — 450 350 300

The decision variables should represent the number of units shipped from each source to each transshipment point and the number of units shipped from each transshipment point to each fi- nal destination, as these are the decisions management must make. The decision variables are

number of units shipped from location (node) i to location (node) j

where

1, 2, 3, 4

3, 4, 5, 6, 7

The numbers are the nodes shown in Figure 9.3, and there is one variable for each arc (route) in the figure.

The LP model is

subject to

(Supply at Toronto [node 1])

(Supply at Detroit [node 2])

(Demand at New York City [node 5])

(Demand at Philadelphia [node 6])

(Demand at St. Louis [node 7])

(Shipping through Chicago [node 3])

(Shipping through Buffalo [node 4])

for all i and j

The solution found using Solver in Excel 2010 is shown in Program 9.3. The total cost is $9,550 by shipping 650 units from Toronto to Chicago, 150 unit from Toronto to Buffalo, 300 units from Detroit to Buffalo, 350 units from Chicago to Philadelphia, 300 from Chicago to St. Louis, and 450 units from Buffalo to New York City.

While all of these linear programs can be solved using computer software for linear pro- gramming, some very fast and easy-to-use special-purpose algorithms exist for the transporta- tion and assignment problems. The rest of this chapter is devoted to these special-purpose algorithms.

xij Ú 0

X14 + X24 = X45 + X46 + X47

X13 + X23 = X35 + X36 + X37

X37 + X47 = 300

X36 + X46 = 350

X35 + X45 = 450

X23 + X24 … 700

X13 + X14 … 800

+ 5X37 + 2X45 + 3X46 + 4X47

Minimize total cost = 4X13 + 7X14 + 5X23 + 7X24 + 6X35 + 4X36

j = i =

xij =

348 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

Special transshipment constraints are used in the linear program.

9.5 The Transportation Algorithm

The transportation algorithm is an iterative procedure in which a solution to a transportation problem is found and evaluated using a special procedure to determine whether the solution is optimal. If it is optimal, the process stops. If it is not optimal, a new solution is generated. This new solution is at least as good as the previous one, and it is usually better. This new solution is then evaluated, and if it is not optimal, another solution is generated. The process continues un- til the optimal solution is found.

Minimize cost

subject to

1. The number of units shipped from Toronto is not more than 800

2. The number of units shipped from Detroit is not more than 700

3. The number of units shipped to New York is 450

4. The number of units shipped to Philadelphia is 350

5. The number of units shipped to St. Louis is 300

6. The number of units shipped out of Chicago is equal to the number of units shipped into Chicago

7. The number of units shipped out of Buffalo is equal to the number of units shipped into Buffalo

9.5 THE TRANSPORTATION ALGORITHM 349

PROGRAM 9.3 Solution to Frosty Machines Transshipment Problem

Set Objective: B19 By Changing cells: B12:C13, D14:F15 To: Min Subject to the Constraints:

G12:G13 <= H12:H13 D16:F16 = D17:F17 B16:C16 = G14:G15

Solving Method: Simplex LP � Make Variables Non-Negative

Solver Parameter Inputs and Selections Key Formulas

Copy to G15

Copy to G13

Copy to C16

Copy to E16:F16

350 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

Balanced supply and demand occurs when total demand equals total supply.

We will illustrate this process using the Executive Furniture Corporation example shown in Figure 9.1. This is presented again in a special format in Table 9.2.

We see in Table 9.2 that the total factory supply available is exactly equal to the total ware- house demand. When this situation of equal demand and supply occurs (something that is rather unusual in real life), a balanced problem is said to exist. Later in this chapter we take a look at how to deal with unbalanced problems, namely, those in which destination requirements may be greater than or less than origin capacities.

Developing an Initial Solution: Northwest Corner Rule When the data have been arranged in tabular form, we must establish an initial feasible solution to the problem. One systematic procedure, known as the northwest corner rule, requires that we start in the upper-left-hand cell (or northwest corner) of the table and allocate units to ship- ping routes as follows:

1. Exhaust the supply (factory capacity) at each row before moving down to the next row. 2. Exhaust the (warehouse) requirements of each column before moving to the right to the

next column. 3. Check that all supply and demands are met.

We can now use the northwest corner rule to find an initial feasible solution to the Execu- tive Furniture Corporation problem shown in Table 9.2.

The use of transportation models to minimize the cost of ship- ping from a number of sources to a number of destinations was first proposed in 1941. This study, called “The Distribution of a Product from Several Sources to Numerous Localities,” was written by F. L. Hitchcock. Six years later, T. C. Koopmans independently

produced the second major contribution, a report titled “Opti- mum Utilization of the Transportation System.” In 1953, A. Charnes and W. W. Cooper developed the stepping-stone method, an algorithm discussed in detail in this chapter. The modified-distribution (MODI) method, a quicker computational approach, came about in 1955.

HISTORY How Transportation Methods Started

TABLE 9.2 Transportation Table for Executive Furniture Corporation

FROM

DES MOINES FACTORY

WAREHOUSE AT ALBUQUERQUE

WAREHOUSE AT BOSTON

WAREHOUSE AT CLEVELAND

FACTORY CAPACITY

EVANSVILLE FACTORY

FORT LAUDERDALE FACTORY

WAREHOUSE REQUIREMENTS

$5 $4 $3 100

Cost of shipping 1 unit from Fort Lauderdale factory to Boston warehouse

Cleveland warehouse demand

Total demand and total supply

Cell representing a source-to-destination (Evansville to Cleveland) shipping assignment that could be made

Des Moines capacity constraint

$4 $3 300

$9 $7 $5 300

700200200300

9.5 THE TRANSPORTATION ALGORITHM 351

It takes five steps in this example to make the initial shipping assignments (see Table 9.3):

1. Beginning the upper-left-hand corner, we assign 100 units from Des Moines to Albuquerque. This exhausts the capacity or supply at the Des Moines factory. But it still leaves the warehouse at Albuquerque 200 desks short. Move down to the second row in the same column.

2. Assign 200 units from Evansville to Albuquerque. This meets Albuquerque’s demand for a total of 300 desks. The Evansville factory has 100 units remaining, so we move to the right to the next column of the second row.

3. Assign 100 units from Evansville to Boston. The Evansville supply has now been exhausted, but Boston’s warehouse is still short by 100 desks. At this point, we move down vertically in the Boston column to the next row.

4. Assign 100 units from Fort Lauderdale to Boston. This shipment will fulfill Boston’s demand for a total of 200 units. We note, though, that the Fort Lauderdale factory still has 200 units available that have not been shipped.

5. Assign 200 units from Fort Lauderdale to Cleveland. This final move exhausts Cleveland’s demand and Fort Lauderdale’s supply. This always happens with a balanced problem. The initial shipment schedule is now complete.

We can easily compute the cost of this shipping assignment:

TABLE 9.3 Initial Solution to Executive Furniture Problem Using the Northwest Corner Method

FROM TO

DES MOINES (D)

EVANSVILLE (E)

FORT LAUDERDALE (F)

WAREHOUSE REQUIREMENTS

$5 $4 $3 100

Means that the firm is shipping 100 units along the Fort Lauderdale–Boston route

$4 $3 300

$9 $7 $5 300

700200

200

100

100200

100

300

ALBUQUERQUE (A)

BOSTON (B)

CLEVELAND (C)

FACTORY CAPACITY

ROUTE UNITS PER-UNIT TOTAL FROM TO SHIPPED COST ($) � COST ($)

D A 100 5 500

E A 200 8 1,600

E B 100 4 400

F B 100 7 700

F C 200 5 1,000

Total 4,200

This solution is feasible since demand and supply constraints are all satisfied. It was also very quick and easy to reach. However, we would be very lucky if this solution yielded the optimal transportation cost for the problem, because this route-loading method totally ignored the costs of shipping over each of the routes.

Here is an explanation of the five steps needed to make an initial shipping assignment for Executive Furniture.

A feasible solution is reached when all demand and supply constraints are met.

352 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

After the initial solution has been found, it must be evaluated to see if it is optimal. We com- pute an improvement index for each empty cell using the stepping-stone method. If this indi- cates a better solution is possible, we use the stepping-stone path to move from this solution to improved solutions until we find an optimal solution.

Stepping-Stone Method: Finding a Least-Cost Solution The stepping-stone method is an iterative technique for moving from an initial feasible solu- tion to an optimal feasible solution. This process has two distinct parts: The first involves testing the current solution to determine if improvement is possible, and the second part involves making changes to the current solution in order to obtain an improved solution. This process continues until the optimal solution is reached.

For the stepping-stone method to be applied to a transportation problem, one rule about the number of shipping routes being used must first be observed: The number of occupied routes (or squares) must always be equal to one less than the sum of the number of rows plus the number of columns. In the Executive Furniture problem, this means that the initial solution must have

squares used. Thus

When the number of occupied routes is less than this, the solution is called degenerate. Later in this chapter we talk about what to do if the number of used squares is less than the num- ber of rows plus the number of columns minus 1.

TESTING THE SOLUTION FOR POSSIBLE IMPROVEMENT How does the stepping-stone method work? Its approach is to evaluate the cost-effectiveness of shipping goods via transportation routes not currently in the solution. Each unused shipping route (or square) in the transporta- tion table is tested by asking the following question: “What would happen to total shipping costs if one unit of our product (in our example, one desk) were tentatively shipped on an un- used route?”

This testing of each unused square is conducted using the following five steps:

Five Steps to Test Unused Squares with the Stepping-Stone Method

1. Select an unused square to be evaluated. 2. Beginning at this square, trace a closed path back to the original square via squares that are

currently being used and moving with only horizontal and vertical moves. 3. Beginning with a plus sign at the unused square, place alternate minus signs and

plus signs on each corner square of the closed path just traced. 4. Calculate an improvement index by adding together the unit cost figures found in each

square containing a plus sign and then subtracting the unit costs in each square containing a minus sign.

5. Repeat steps 1 to 4 until an improvement index has been calculated for all unused squares. If all indices computed are greater than or equal to zero, an optimal solution has been reached. If not, it is possible to improve the current solution and decrease total shipping costs.

To see how the stepping-stone method works, let us apply these steps to the Executive Fur- niture Corporation data in Table 9.3 to evaluate unused shipping routes. The four currently unas- signed routes are Des Moines to Boston, Des Moines to Cleveland, Evansville to Cleveland, and Fort Lauderdale to Albuquerque.

Steps 1 and 2. Beginning with the Des Moines–Boston route, we first trace a closed path using only currently occupied squares (see Table 9.4) and then place alternate plus signs and minus signs in the corners of this path. To indicate more clearly the meaning of a closed path, we see that only squares currently used for shipping can be used in turning the corners of the route

(-)(+)

5 = 3 + 3 - 1

Occupied shipping routes (squares) = Number of rows + Number of columns - 1

3 + 3 - 1 = 5

The stepping-stone method involves testing each unused route to see if shipping one unit on that route would increase or decrease total costs.

Note that every row and every column will have either two changes or no changes.

Closed paths are used to trace alternate plus and minus signs.

9.5 THE TRANSPORTATION ALGORITHM 353

Defining the Problem The sugar market has been in a crisis for over a decade. Low sugar prices and decreasing demand have added to an already unstable market. Sugar producers needed to minimize costs. They targeted the largest unit cost in the manufacturing of raw sugar contributor—namely, sugar cane transportation costs.

Developing a Model To solve this problem, researchers developed a linear program with some integer decision variables (e.g., num- ber of trucks) and some continuous (linear) variables and linear decision variables (e.g., tons of sugar cane).

Acquiring Input Data In developing the model, the inputs gathered were the operating demands of the sugar mills involved, the capacities of the intermediary storage facilities, the per-unit transportation costs per route, and the pro- duction capacities of the various sugar cane fields.

Testing the Solution The researchers involved first tested a small version of their mathematical formulation using a spreadsheet. After noting encouraging results, they implemented the full version of their model on large computer. Re- sults were obtained for this very large and complex model (on the order of 40,000 decision variables and 10,000 constraints) in just a few milliseconds.

Analyzing the Results The solution obtained contained information on the quantity of cane delivered to each sugar mill, the field where cane should be collected, and the means of transportation (by truck, by train, etc.), and several other vital operational attributes.

Implementing the Results While solving such large problems with some integer variables might have been impossible only a decade ago, solving these problems now is certainly possible. To implement these results, the researchers worked to develop a more user-friendly interface so that managers would have no problem using this model to help make decisions.

Source: Based on E. L. Milan, S. M. Fernandez, and L. M. Pla Aragones. “Sugar Cane Transportation in Cuba: A Case Study,” European Journal of Operational Research, 174, 1 (2006): 374–386.

MODELING IN THE REAL WORLD Moving Sugar Cane in Cuba

being traced. Hence the path Des Moines–Boston to Des Moines–Albuquerque to Fort Lauderdale–Albuquerque to Fort Lauderdale–Boston to Des Moines–Boston would not be acceptable since the Fort Lauderdale–Albuquerque square is currently empty. It turns out that only one closed route is possible for each square we wish to test.

Step 3. How do we decide which squares are given plus signs and which minus signs? The answer is simple. Since we are testing the cost-effectiveness of the Des Moines–Boston shipping route, we pretend we are shipping one desk from Des Moines to Boston. This is one more unit than we were sending between the two cities, so we place a plus sign in the box. But if we ship one more unit than before from Des Moines to Boston, we end up sending 101 desks out of the Des Moines factory.

That factory’s capacity is only 100 units; hence we must ship one fewer desks from Des Moines–Albuquerque—this change is made to avoid violating the factory capacity constraint. To indicate that the Des Moines–Albuquerque shipment has been reduced, we place a minus sign in its box. Continuing along the closed path, we notice that we are no longer meeting the Albuquerque warehouse requirement for 300 units. In fact, if the Des Moines–Albuquerque shipment is reduced to 99 units, the Evansville–Albuquerque load has to be increased by 1 unit,

How to assign and signs.��

Defining the Problem

Developing a Model

Acquiring Input Data

Testing the Solution

Analyzing the Results

Implementing the Results

354 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

Improvement index computation involves adding costs in squares with plus signs and subtracting costs in squares with minus signs.

is the improvement index on the route from source i to destination j.

Iij

TABLE 9.4 Evaluating the Unused Des Moines–Boston Shipping Route

FROM TO

ALBUQUERQUE

Warehouse A

Factory D

Factory E

BOSTON CLEVELAND FACTORY CAPACITY

DES MOINES

EVANSVILLE

FORT LAUDERDALE

WAREHOUSE REQUIREMENTS

Start

100

Result of Proposed Shift in Allocation

Evaluation of Des Moines–Boston Square

–

– +

+ –

300

700200

200

100

100200

100

300

Warehouse B

$8 $4

200

201

100

= 1 × $4 – 1 × $5 + 1 × $8 – 1 × $4 = + $3

5 4 3

8 4 3

9 7 5

to 201 desks. Therefore, we place a plus sign in that box to indicate the increase. Finally, we note that if the Evansville–Albuquerque route is assigned 201 desks, the Evansville–Boston route must be reduced by 1 unit, to 99 desks, to maintain the Evansville factory capacity con- straint of 300 units. Thus, a minus sign is placed in the Evansville–Boston box. We observe in Table 9.4 that all four routes on the closed path are thereby balanced in terms of demand-and- supply limitations.

Step 4. An improvement index for the Des Moines–Boston route is now computed by adding unit costs in squares with plus signs and subtracting costs in squares with minus signs. Hence

Does Moines–Boston index

This means that for every desk shipped via the Des Moines–Boston route, total transportation costs will increase by $3 over their current level.

Step 5. Let us now examine the Des Moines–Cleveland unused route, which is slightly more difficult to trace with a closed path. Again, you will notice that we turn each corner along the path only at squares that represent existing routes. The path can go through the Evansville–Cleveland box but cannot turn a corner or place a or sign there. Only an occupied square may be used as a stepping stone (Table 9.5).

The closed path we use is

Des Moines—Cleveland improvement index

Thus, opening this route will also not lower our total shipping costs.

= +$4

= +$3 - $5 + $8 - $4 + $7 - $5

= IDC

+DC - DA + EA - EB + FB - FC:

= IDB = +$4 - $5 + $8 - $4 = +$3

(Iij)

A path can go through any box but can only turn at a box or cell that is occupied.

9.5 THE TRANSPORTATION ALGORITHM 355

The other two routes may be evaluated in a similar fashion:

Evansville–Cleveland index

Fort Lauderdale–Albuquerque index

Because this last improvement index is negative, a cost savings may be attained by mak- ing use of the (currently unused) Fort Lauderdale–Albuquerque route.

OBTAINING AN IMPROVED SOLUTION Each negative index computed by the stepping-stone method represents the amount by which total transportation costs could be decreased if 1 unit or product were shipped on that route. We found only one negative index in the Executive Furni- ture problem, that being on the Fort Lauderdale factory–Albuquerque warehouse route. If, however, there were more than one negative improvement index, our strategy would be to choose the route (unused square) with the negative index indicating the largest improvement.

The next step, then, is to ship the maximum allowable number of units (or desks, in our case) on the new route (Fort Lauderdale to Albuquerque). What is the maximum quantity that can be shipped on the money-saving route? That quantity is found by referring to the closed path of plus signs and minus signs drawn for the route and selecting the smallest number found in those squares containing minus signs. To obtain a new solution, that number is added to all squares on the closed path with plus signs and subtracted from all squares on the path assigned minus signs. All other squares are unchanged.

Let us see how this process can help improve Executive Furniture’s solution. We repeat the transportation table (Table 9.6) for the problem. Note that the stepping-stone route for Fort Lauderdale to Albuquerque (F–A) is drawn in. The maximum quantity that can be shipped on the newly opened route (F–A) is the smallest number found in squares containing minus signs— in this case, 100 units. Why 100 units? Since the total cost decreases by $2 per unit shipped, we know we would like to ship the maximum possible number of units. Table 9.6 indicates that each unit shipped over the F–A route results in an increase of 1 unit shipped from E to B and a de- crease of 1 unit in both the amounts shipped from F to B (now 100 units) and from E to A (now 200 units). Hence, the maximum we can ship over the F–A route is 100. This results in 0 units being shipped from F to B.

-$2

(IFA)

(closed path: +FA - FB + EB - EA)

= -$2

= IFA = +$9 - $7 + $4 - $8

(closed path: +EC - EB + FB - FC)

= +$1

= IEC = +$3 - $4 + $7 - $5

To reduce our overall costs, we want to select the route with the negative index indicating the largest improvement.

The maximum we can ship on the new route is found by looking at the closed path’s minus signs. We select the smallest number found in the squares with minus signs.

Changing the shipping route involves adding to squares on the closed path with plus signs and subtracting from squares with minus signs.

TO (A) (B) (C) FACTORY FROM ALBUQUERQUE BOSTON CLEVELAND CAPACITY

(D) $5 $4 $3

DES MOINES � Start

100 + 100

(E) $8 $4 $3

EVANSVILLE + �

200 100 300

(F) $9 $7 $5

FORT LAUDERDALE 100

+ �

100 200 300

WAREHOUSE REQUIREMENTS 300 200 200 700

TABLE 9.5 Evaluating the Des Moines–Cleveland (D–C) Shipping Route

356 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

We add 100 units to the 0 now being shipped on route F–A; then proceed to subtract 100 from route F–B, leaving 0 in that square (but still balancing the row total for F); then add 100 to route E–B, yielding 200; and finally, subtract 100 from route E–A, leaving 100 units shipped. Note that the new numbers still produce the correct row and column totals as required. The new solution is shown in Table 9.7.

Total shipping cost has been reduced by and is now $4,000. This cost figure can, of course, also be derived by multiplying each unit shipping cost times the number of units transported on its route, namely,

The solution shown in Table 9.7 may or may not be optimal. To determine whether further improvement is possible, we return to the first five steps given earlier to test each square that is now unused. The four improvement indices—each representing an available shipping route— are as follows:

Hence, an improvement can be made by shipping the maximum allowable number of units from E to C (see Table 9.8). Only the squares E–A and F–C have minus signs in the closed path; be- cause the smallest number in these two squares is 100, we add 100 units to E–C and F–A and

(closed path: +FB - EB + EA - FA)

F to B = IFB = +$7 - $4 + $8 - $9 = +$2

(closed path: +EC - EA + FA - FC)

E to C = IEC = +$3 - $8 + $9 - $5 = -$1

(closed path: +DC - DA + FA - FC)

D to C = IDC = +$3 - $5 + $9 - $5 = +$2

(closed path: +DB - DA + EA - EB)

D to B = IDB = +$4 - $5 + $8 - $4 = +$3

(200 * $4) + (100 * $9) + (200 * $5) = $4,000. (100 * $5) + (100 * $8) +

(100 units) * ($2 saved per unit) = $200,

Improvement indices for each of the four unused shipping routes must now be tested to see if any are negative.

TO FACTORY FROM A B C CAPACITY

D $5 $4 $3

100 100

E $8 $4 $3

�200 �100 300

F $9 $7 $5

+ �100 200 300

WAREHOUSE REQUIREMENTS 300 200 200 700

TABLE 9.6 Stepping-Stone Path Used to Evaluate Route F–A

TO FACTORY FROM A B C CAPACITY

D $5 $4 $3

100 100

E $8 $4 $3

100 200 300

F $9 $7 $5

100 200 300

WAREHOUSE REQUIREMENTS 300 200 200 700

TABLE 9.7 Second Solution to the Executive Furniture Problem

9.5 THE TRANSPORTATION ALGORITHM 357

subtract 100 units from E–A and F–C. The new cost for this third solution, $3,900, is computed in the following table:

TO FACTORY FROM A B C CAPACITY

D $5 $4 $3

100 100

E $8 $4 $3

100 � 200 Start+ 300

F $9 $7 $5

100 + 200 � 300

WAREHOUSE REQUIREMENTS 300 200 200 700

TABLE 9.8 Path to Evaluate the E–C Route

ROUTE DESKS PER-UNIT TOTAL FROM TO SHIPPED COST ($) COST ($)

D A 100 5 500

E B 200 4 800

E C 100 3 300

F A 200 9 1,800

F C 100 5 500

Total 3,900

�:

Table 9.9 contains the optimal shipping assignments because each improvement index that can be computed at this point is greater than or equal to zero, as shown in the following equa- tions. Improvement indices for the table are

F to B = IFB = +$7 - $5 + $3 - $4 = +$1 (path: +FB - FC + EC - EB)

E to A = IEA = +$8 - $9 + $5 - $3 = +$1 (path: +EA - FA + FC - EC)

D to C = IDC = +$3 - $5 + $9 - $5 = +$2 (path: +DC - DA + FA - FC)

= +$2 (path: +DB - DA + FA - FC + EC - EB)

D to B = IDB = +$4 - $5 + $9 - $5 + $3 - $4Since all four of these improvement indices are greater than or equal to zero, we have reached an optimal solution.

TO FACTORY FROM A B C CAPACITY

D $5 $4 $3

100 100

E $8 $4 $3

200 100 300

F $9 $7 $5

200 100 300

WAREHOUSE REQUIREMENTS 300 200 200 700

TABLE 9.9 Third and Optimal Solution

Total Cost of Third Solution

358 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

Let us summarize the steps in the transportation algorithm:

Summary of Steps in Transportation Algorithm (Minimization)

1. Set up a balanced transportation table. 2. Develop initial solution using the northwest corner method. 3. Calculate an improvement index for each empty cell using the stepping-stone method. If

improvement indices are all nonnegative, stop; the optimal solution has been found. If any index is negative, continue to step 4.

4. Select the cell with the improvement index indicating the greatest decrease in cost. Fill this cell using a stepping-stone path and go to step 3.

Some special situations may occur when using this algorithm. They are presented in the next section.

The transportation algorithm has four basic steps.

9.6 Special Situations with the Transportation Algorithm

When using the transportation algorithm, some special situations may arise, including unbalanced problems, degenerate solutions, multiple optimal solutions, and unacceptable routes. This algo- rithm may be modified to maximize total profit rather than minimize total cost. All of these situa- tions will be addressed, and other modifications of the transportation algorithm will be presented.

Unbalanced Transportation Problems A situation occurring quite frequently in real-life problems is the case in which total demand is not equal to total supply. These unbalanced problems can be handled easily by the preceding so- lution procedures if we first introduce dummy sources or dummy destinations. In the event that total supply is greater than total demand, a dummy destination (warehouse), with demand exactly equal to the surplus, is created. If total demand is greater than total supply, we introduce a dummy source (factory) with a supply equal to the excess of demand over supply. In either case, shipping cost coefficients of zero are assigned to each dummy location or route because no shipments will actually be made from a dummy factory or to a dummy warehouse. Any units as- signed to a dummy destination represent excess capacity, and units assigned to a dummy source represent unmet demand.

Answering Warehousing Questions at San Miguel Corporation

The San Miguel Corporation, based in the Philippines, faces unique distribution challenges. With more than 300 products, in- cluding beer, alcoholic drinks, juices, bottled water, feeds, poul- try, and meats to be distributed to every corner of the Philippine archipelago, shipping and warehousing costs make up a large part of total product cost.

The company grappled with these questions:

� Which products should be produced in each plant and in which warehouse should they be stored?

� Which warehouses should be maintained and where should new ones be located?

� When should warehouses be closed or opened? � Which demand centers should each warehouse serve?

Turning to the transportation model of LP, San Miguel is able to answer these questions. The firm uses these types of ware- houses: company owned and staffed, rented but company staffed, and contracted out (i.e., not company owned or staffed).

San Miguel’s Operations Research Department computed that the firm saves $7.5 million annually with optimal beer warehouse configurations over the existing national configura- tions. In addition, analysis of warehousing for ice cream and other frozen products indicated that the optimal configuration of warehouses, compared with existing setups, produced a $2.17 million savings.

Source: Based on Elise del Rosario. “Logistical Nightmare,” OR/MS Today (April 1999): 44–46.

IN ACTION

Dummy sources or destinations are used to balance problems in which demand is not equal to supply.

9.6 SPECIAL SITUATIONS WITH THE TRANSPORTATION ALGORITHM 359

DEMAND LESS THAN SUPPLY Considering the original Executive Furniture Corporation prob- lem, suppose that the Des Moines factory increases its rate of production to 250 desks. (That factory’s capacity used to be 100 desks per production period.) The firm is now able to supply a total of 850 desks each period. Warehouse requirements, however, remain the same (at 700 desks), so the row and column totals do not balance.

To balance this type of problem, we simply add a dummy column that will represent a fake warehouse requiring 150 desks. This is somewhat analogous to adding a slack variable in solv- ing an LP problem. Just as slack variables were assigned a value of zero dollars in the LP objec- tive function, the shipping costs to this dummy warehouse are all set equal to zero.

The northwest corner rule is used once again, in Table 9.10, to find an initial solution to this modified Executive Furniture problem. To complete this task and find an optimal solution, you would employ the stepping-stone method.

Note that the 150 units from Fort Lauderdale to the dummy warehouse represent 150 units that are not shipped from Fort Lauderdale.

DEMAND GREATER THAN SUPPLY The second type of unbalanced condition occurs when total demand is greater than total supply. This means that customers or warehouses require more of a product than the firm’s factories can provide. In this case we need to add a dummy row repre- senting a fake factory.

The new factory will have a supply exactly equal to the difference between total demand and total real supply. The shipping costs from the dummy factory to each destination will be zero.

Let us set up such an unbalanced problem for the Happy Sound Stereo Company. Happy Sound assembles high-fidelity stereophonic systems at three plants and distributes through three regional warehouses. The production capacities at each plant, demand at each warehouse, and unit shipping costs are presented in Table 9.11.

As can be seen in Table 9.12, a dummy plant adds an extra row, balances the problem, and allows us to apply the northwest corner rule to find the initial solution shown. This initial solu- tion shows 50 units being shipped from the dummy plant to warehouse C. This means that ware- house C will be 50 units short of its requirements. In general, any units shipped from a dummy source represent unmet demand at the respective destination.

Degeneracy in Transportation Problems We briefly mentioned the subject of degeneracy earlier in this chapter. Degeneracy occurs when the number of occupied squares or routes in a transportation table solution is less than the num- ber of rows plus the number of columns minus 1. Such a situation may arise in the initial solu- tion or in any subsequent solution. Degeneracy requires a special procedure to correct the

TABLE 9.10 Initial Solution to an Unbalanced Problem Where Demand is Less than Supply

FROM TO ALBUQUERQUE

(A) BOSTON (B)

CLEVELAND (C)

DUMMY WAREHOUSE

FACTORY CAPACITY

DES MOINES (D)

EVANSVILLE (E)

FORT LAUDERDALE (F)

WAREHOUSE REQUIREMENTS

250 250

50 50200

New Des Moines capacity

300

150 150 300

850

Total cost = 250($5) + 50($8) + 200($4) + 50($3) + 150($5) + 150($0) = $3,350

4 3

9 7 5

150200300 200

Degeneracy arises when the number of occupied squares is less than the number of rows

columns -1.+

360 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

TO WAREHOUSE WAREHOUSE WAREHOUSE PLANT FROM A B C SUPPLY

PLANT W $6 $4 $9

200

PLANT X $10 $5 $8

175

PLANT Y $12 $7 $6

WAREHOUSE 450

DEMAND 250 100 150 500

TABLE 9.11 Unbalanced Transportation Table for Happy Sound Stereo Company

Totals do not balance

TO WAREHOUSE WAREHOUSE WAREHOUSE PLANT FROM A B C SUPPLY

PLANT W 6 4 9

200 200

PLANT X 10 5 8

50 100 25 175

PLANT Y 12 7 6

75 75

DUMMY 0 0 0 PLANT 50 50

WAREHOUSE DEMAND 250 100 150 500

Total cost of initial solution � 200($6) � 50($10) � 100($5) � 25($8) � 75($6) + 50($0) � $2,850

TABLE 9.12 Initial Solution to an Unbalanced Problem in which Demand Is Greater Than Supply

problem. Without enough occupied squares to trace a closed path for each unused route, it would be impossible to apply the stepping-stone method. You might recall that no problem discussed in the chapter thus far has been degenerate.

To handle degenerate problems, we create an artificially occupied cell—that is, we place a zero (representing a fake shipment) in one of the unused squares and then treat that square as if it were occupied. The square chosen must be in such a position as to allow all stepping-stone paths to be closed, although there is usually a good deal of flexibility in selecting the unused square that will receive the zero.

DEGENERACY IN AN INITIAL SOLUTION Degeneracy can occur in our application of the northwest corner rule to find an initial solution, as we see in the case of the Martin Shipping Company. Martin has three warehouses from which to supply its three major retail customers in San Jose. Martin’s hipping costs, warehouse supplies, and customer demands are presented in Table 9.13. Note that origins in this problem are warehouses and destinations are retail stores. Initial shipping assignments are made in the table by application of the northwest corner rule.

This initial solution is degenerate because it violates the rule that the number of used squares must be equal to the number of rows plus the number of columns minus 1 (i.e.,

is greater than the number of occupied boxes). In this particular problem, degeneracy arose because both a column and a row requirement (that being column 1 and row 1) were satisfied simultaneously. This broke the stair-step pattern that we usually see with north- west corner solutions.

To correct the problem, we can place a zero in an unused square. With the northwest corner method, this zero should be placed in one of the cells that is adjacent to the last filled cell so the

3 + 3 - 1 = 5

9.6 SPECIAL SITUATIONS WITH THE TRANSPORTATION ALGORITHM 361

stair-step pattern continues. In this case, those squares representing either the shipping route from warehouse 1 to customer 2 or from warehouse 2 to customer 1 will do. If you treat the new zero square just like any other occupied square, the regular solution method can be used.

DEGENERACY DURING LATER SOLUTION STAGES A transportation problem can become degen- erate after the initial solution stage if the filling of an empty square results in two (or more) filled cells becoming empty simultaneously instead of just one cell becoming empty. Such a problem occurs when two or more squares assigned minus signs on a closed path tie for the lowest quan- tity. To correct this problem, a zero should be put in one (or more) of the previously filled squares so that only one previously filled square becomes empty.

Bagwell Paint Example. After one iteration of the stepping-stone method, cost analysts at Bagwell Paint produced the transportation table shown as Table 9.14. We observe that the solution in Table 9.14 is not degenerate, but it is also not optimal. The improvement indices for the four currently unused squares are

factory A – warehouse 2 index

factory A – warehouse 3 index

factory B – warehouse 3 index

factory C – warehouse 2 index

Hence, an improved solution can be obtained by opening the route from factory B to ware- house 3. Let us go through the stepping-stone procedure for finding the next solution to Bagwell Paint’s problem. We begin by drawing a closed path for the unused square representing factory B–warehouse 3. This is shown in Table 9.15, which is an abbreviated version of Table 9.14 and contains only the factories and warehouses necessary to close the path.

= +11

= -15

= +1

= +2

TO CUSTOMER CUSTOMER CUSTOMER WAREHOUSE FROM 1 2 3 SUPPLY

WAREHOUSE 8 2 6

1 100 100

WAREHOUSE 10 9 9

2 100 20 120

WAREHOUSE 7 10 7

3 80 80

CUSTOMER DEMAND 100 100 100 300

TABLE 9.13 Initial Solution of a Degenerate Problem

TO WAREHOUSE WAREHOUSE WAREHOUSE FACTORY FROM 1 2 3 CAPACITY

FACTORY 8 5 16

A 70 70

FACTORY 15 10 7

B 50 80 130

FACTORY 3 9 10

C 30 50 80

WAREHOUSE REQUIREMENT 150 80 50 280

TABLE 9.14 Bagwell Paint Transportation Table

Total shipping cost � $2,700

Only route with a negative index

362 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

TO WAREHOUSE WAREHOUSE FROM 1 3

FACTORY 15 7

B 50 � �

FACTORY 3 10

C 30 + �� 50

TABLE 9.15 Tracing a Closed Path for the Factory B–Warehouse 3 Route

The smallest quantity in a square containing a minus sign is 50, so we add 50 units to the factory B–warehouse 3 and factory C–warehouse 1 routes, and subtract 50 units from the two squares containing minus signs. However, this act causes two formerly occupied squares to drop to 0. It also means that there are not enough occupied squares in the new solution and that it will be degenerate. We will have to place an artificial zero in one of the previously filled squares (generally, the one with the lowest shipping cost) to handle the degeneracy problem.

More Than One Optimal Solution Just as with LP problems, it is possible for a transportation problem to have multiple optimal so- lutions. Such a situation is indicated when one or more of the improvement indices that we cal- culate for each unused square is zero in the optimal solution. This means that it is possible to design alternative shipping routes with the same total shipping cost. The alternate optimal solu- tion can be found by shipping the most to this unused square using a stepping-stone path. Practi- cally speaking, multiple optimal solutions provide management with greater flexibility in selecting and using resources.

Maximization Transportation Problems If the objective in a transportation problem is to maximize profit, a minor change is required in the transportation algorithm. Since the improvement index for an empty cell indicates how the objective function value will change if one unit is placed in that empty cell, the optimal solution is reached when all the improvement indices are negative or zero. If any index is positive, the cell with the largest positive improvement index is selected to be filled using a stepping-stone path. This new solution is evaluated and the process continues until there are no positive im- provement indices.

Unacceptable or Prohibited Routes At times there are transportation problems in which one of the sources is unable to ship to one or more of the destinations. When this occurs, the problem is said to have an unacceptable or prohibited route. In a minimization problem, such a prohibited route is assigned a very high cost to prevent this route from ever being used in the optimal solution. After this high cost is placed in the transportation table, the problem is solved using the techniques previously discussed. In a maximization problem, the very high cost used in minimization problems is given a negative sign, turning it into a very bad profit.

Other Transportation Methods While the northwest corner method is very easy to use, there are other methods for finding an initial solution to a transportation problem. Two of these are the least-cost method and Vogel’s approximation method. Similarly, the stepping-stone method is used to evaluate empty cells, and there is another technique called the modified distribution (MODI) method that can evaluate empty cells. For very large problems, the MODI method is usually much faster than the step- ping-stone method.

Multiple solutions are possible when one or more improvement indices in the optimal solution stages are equal to zero.

The optimal solution to a maximization problem has been found when all improvement indices are negative or zero.

A prohibited route is assigned a very high cost to prevent it from being used.

9.7 FACILITY LOCATION ANALYSIS 363

9.7 Facility Location Analysis

The transportation method has proved to be especially useful in helping a firm decide where to locate a new factory or warehouse. Since a new location is an issue of major financial impor- tance to a company, several alternative locations must ordinarily be considered and evaluated. Even though a wide variety of subjective factors are considered, including quality of labor sup- ply, presence of labor unions, community attitude and appearance, utilities, and recreational and educational facilities for employees, a final decision also involves minimizing total shipping and production costs. This means that each alternative facility location should be analyzed within the framework of one overall distribution system. The new location that will yield the minimum cost for the entire system will be the one recommended. Let us consider the case of the Hard- grave Machine Company.

Locating a New Factory for Hardgrave Machine Company The Hardgrave Machine Company produces computer components at its plants in Cincinnati, Salt Lake City, and Pittsburgh. These plants have not been able to keep up with demand for or- ders at Hardgrave’s four warehouses in Detroit, Dallas, New York, and Los Angeles. As a result, the firm has decided to build a new plant to expand its productive capacity. The two sites being considered are Seattle and Birmingham; both cities are attractive in terms of labor supply, municipal services, and ease of factory financing.

Table 9.16 presents the production costs and output requirements for each of the three exist- ing plants, demand at each of the four warehouses, and estimated production costs of the new proposed plants. Transportation costs from each plant to each warehouse are summarized in Table 9.17.

Locating a new facility within one overall distribution system is aided by the transportation method.

MONTHLY DEMAND PRODUCTION MONTHLY COST TO PRODUCE

WAREHOUSE (UNITS) PLANT SUPPLY ONE UNIT ($)

Detroit 10,000 Cincinnati 15,000 48

Dallas 12,000 Salt Lake City 6,000 50

New York 15,000 Pittsburgh 14,000 52

Los Angeles 9,000 35,000

46,000

Supply needed from new plant � 46,000 � 35,000 � 11,000 units per month

ESTIMATED PRODUCTION COST PER UNIT AT PROPOSED PLANTS

Seattle $53

Birmingham $49

TABLE 9.16 Hardgrave’s Demand and Supply Data

TO NEW LOS FROM DETROIT DALLAS YORK ANGELES

CINCINNATI $25 $55 $40 $60

SALT LAKE CITY 35 30 50 40

PITTSBURGH 36 45 26 66

SEATTLE 60 38 65 27

BIRMINGHAM 35 30 41 50

TABLE 9.17 Hardgrave’s Shipping Costs

364 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

The important question that Hardgrave now faces is this: Which of the new locations will yield the lowest cost for the firm in combination with the existing plants and warehouses? Note that the cost of each individual plant-to-warehouse route is found by adding the shipping costs (in the body of Table 9.17) to the respective unit production costs (from Table 9.16). Thus, the total production plus shipping cost of one computer component from Cincinnati to Detroit is $73 ($25 for shipping plus $48 for production).

To determine which new plant (Seattle or Birmingham) shows the lowest total systemwide cost of distribution and production, we solve two transportation problems—one for each of the two possible combinations. Tables 9.18 and 9.19 show the resulting two optimum solutions with the total cost for each. It appears that Seattle should be selected as the new plant site: Its total cost of $3,704,000 is less than the $3,741,000 cost at Birmingham.

USING EXCEL QM AS A SOLUTION TOOL We can use Excel QM to solve each of the two Hard- grave Machine Company problems. To do this, select Excel QM from the Add-Ins tab in Excel 2010 and scroll down to select Transportation. When the window opens, enter the number of Origins (sources) and Destinations, specify Minimize, give this a title if desired, and click OK. Then simply enter the costs, supplies, and demands in the table labeled Data, as shown in Prob- lem 9.4. Then select Solver from the Data tab and click Solve. No further input is needed as Ex- cel QM automatically specifies the necessary parameters and selections. Excel also prepares the formulas for the constraints used by Solver. The solution will appear in the table labeled Ship- ments, and the cost will be specified below this table.

TO NEW LOS MONTHLY FROM DETROIT DALLAS YORK ANGELES SUPPLY

CINCINNATI 73 103 88 108

10,000 1,000 4,000 15,000

SALT LAKE CITY 85 80 100 90

1,000 5,000 6,000

PITTSBURGH 88 97 78 118

14,000 14,000

BIRMINGHAM 84 79 90 99

11,000 11,000

MONTHLY DEMAND 10,000 12,000 15,000 9,000 46,000

TABLE 9.18 Birmingham Plant Optimal Solution: Total Hardgrave Cost Is $3,741,000

TO NEW LOS MONTHLY FROM DETROIT DALLAS YORK ANGELES SUPPLY

CINCINNATI 73 103 88 108

10,000 4,000 1,000 15,000

SALT LAKE CITY 85 80 100 90

6,000 6,000

PITTSBURGH 88 97 78 118

14,000 14,000

SEATTLE 113 91 118 80

2,000 9,000 11,000

MONTHLY DEMAND 10,000 12,000 15,000 9,000 46,000

TABLE 9.19 Seattle Plant Optimal Solution: Total Hardgrave Cost Is $3,704,000

We solve two transportation problems to find the new plant with lowest system cost.

9.8 THE ASSIGNMENT ALGORITHM 365

From the Data tab, select Solver and click Solve.

Enter the costs, supplies, and demands in this table.

Solver puts the solution here.

PROGRAM 9.4 Excel QM Solution for Facility Location Example

9.8 The Assignment Algorithm

The second special-purpose LP algorithm discussed in this chapter is the assignment method. Each assignment problem has associated with it a table, or matrix. Generally, the rows contain the objects or people we wish to assign, and the columns comprise the tasks or things we want them assigned to. The numbers in the table are the costs associated with each particular assignment.

An assignment problem can be viewed as a transportation problem in which the capacity from each source (or person to be assigned) is 1 and the demand at each destination (or job to be done) is 1. Such a formulation could be solved using the transportation algorithm, but it would have a severe degeneracy problem. However, this type of problem is very easy to solve using the assignment method.

As an illustration of the assignment method, let us consider the case of the Fix-It Shop, which has just received three new rush projects to repair: (1) a radio, (2) a toaster oven, and (3) a broken coffee table. Three repair persons, each with different talents and abilities, are available to do the jobs. The Fix-It Shop owner estimates what it will cost in wages to assign each of the workers to each of the three projects. The costs, which are shown in Table 9.20, differ because the owner believes that each worker will differ in speed and skill on these quite varied jobs.

The owner’s objective is to assign the three projects to the workers in a way that will result in the lowest total cost to the shop. Note that the assignment of people to projects must be on a one-to-one basis; each project will be assigned exclusively to one worker only. Hence the num- ber of rows must always equal the number of columns in an assignment problem’s cost table.

The goal is to assign projects to people (one project to one person) so that the total costs are minimized.

PROJECT

PERSON 1 2 3

Adams $11 $14 $6

Brown 8 10 11

Cooper 9 12 7

TABLE 9.20 Estimated Project Repair Costs for the Fix-It Shop Assignment Problem

One way to solve (small) problems is to enumerate all possible outcomes.

Matrix reduction reduces the table to a set of opportunity costs. These show the penalty of not making the least-cost (or best) assignment.

*The steps apply if we can assume that the matrix is balanced, that is, the number of rows in the matrix equals the number of columns. In Section 9.9 we discuss how to handle unbalanced problems.

366 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

Because the Fix-It Shop problem only consists of three workers and three projects, one easy way to find the best solution is to list all possible assignments and their respective costs. For ex- ample, if Adams is assigned to project 1, Brown to project 2, and Cooper to project 3, the total cost will be Table 9.21 summarizes all six assignment options. The table also shows that the least-cost solution would be to assign Cooper to project 1, Brown to project 2, and Adams to project 3, at a total cost of $25.

Obtaining solutions by enumeration works well for small problems but quickly becomes in- efficient as assignment problems become larger. For example, a problem involving the assign- ment of four workers to four projects requires that we consider or 24 alternatives. A problem with eight workers and eight tasks, which actually is not that large in a realistic situation, yields or 40,320 possible solu- tions! Since it would clearly be impractical to compare so many alternatives, a more efficient solution method is needed.

The Hungarian Method (Flood’s Technique) The Hungarian method of assignment provides us with an efficient means of finding the opti- mal solution without having to make a direct comparison of every option. It operates on a prin- ciple of matrix reduction, which means that by subtracting and adding appropriate numbers in the cost table or matrix, we can reduce the problem to a matrix of opportunity costs. Opportu- nity costs show the relative penalties associated with assigning any person to a project as opposed to making the best, or least-cost, assignment. We would like to make assignments such that the opportunity cost for each assignment is zero. The Hungarian method will indicate when it is possible to make such assignments.

There are basically three steps in the assignment method*:

Three Steps of the Assignment Method

1. Find the opportunity cost table by (a) Subtracting the smallest number in each row of the original cost table or matrix from

every number in that row. (b) Then subtracting the smallest number in each column of the table obtained in part (a)

from every number in that column.

2. Test the table resulting from step 1 to see whether an optimal assignment can be made. The procedure is to draw the minimum number of vertical and horizontal straight lines necessary to cover all zeros in the table. If the number of lines equals either the number of rows or columns in the table, an optimal assignment can be made. If the number of lines is less than the number of rows or columns, we proceed to step 3.

3. Revise the present opportunity cost table. This is done by subtracting the smallest number not covered by a line from every uncovered number. This same smallest number is also added to any number(s) lying at the intersection of horizontal and vertical lines. We then return to step 2 and continue the cycle until an optimal assignment is possible.

8! (= 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1),

4! (= 4 * 3 * 2 * 1),

$11 + $10 + $7 = $28.

PROJECT ASSIGNMENT

1 2 3 LABOR COSTS ($) TOTAL COSTS ($)

Adams Brown Cooper 11 � 10 � 7 28

Adams Cooper Brown 11 � 12 � 11 34

Brown Adams Cooper 8 � 14 � 7 29

Brown Cooper Adams 8 � 12 � 6 26

Cooper Adams Brown 9 � 14 � 11 34

Cooper Brown Adams 9 � 10 � 6 25

TABLE 9.21 Summary of Fix-It Shop Assignment Alternatives and Costs

Here are the three steps of the assignment method.

9.8 THE ASSIGNMENT ALGORITHM 367

These steps are charted in Figure 9.4. Let us now apply them.

Step 1: Find the Opportunity Cost Table. As mentioned earlier, the opportunity cost of any decision we make in life consists of the opportunities that are sacrificed in making that decision. For example, the opportunity cost of the unpaid time a person spends starting a new business is the salary that person would earn for those hours that he or she could have worked on another job. This important concept in the assignment method is best illustrated by applying it to a problem. For your convenience, the original cost table for the Fix-It Shop problem is repeated in Table 9.22.

Suppose that we decide to assign Cooper to project 2. The table shows that the cost of this assignment is $12. Based on the concept of opportunity costs, this is not the best decision, since Cooper could perform project 3 for only $7. The assignment of Cooper to project 2 then involves an opportunity cost of $5 the amount we are sacrificing by making this assign- ment instead of the least-cost one. Similarly, an assignment of Cooper to project 1 represents an opportunity cost of Finally, because the assignment of Cooper to project 3 is the best assignment, we can say that the opportunity cost of this assignment is zero The results of this operation for each of the rows in Table 9.22 are called the row opportunity costs and are shown in Table 9.23.

($7 - $7). $9 - $7 = $2.

(= $12 - $7),

Revise opportunity cost table in two steps: (a) Subtract the smallest number not covered by a line from itself and every other uncovered number. (b) Add this number at every intersection of any two lines.

Find opportunity cost. (a) Subtract smallest number in each row from every number in that row, then (b) subtract smallest number in each column from every number in that column.

Step 1

Test opportunity cost table to see if optimal assignments are possible by drawing the minimum possible lines on columns and/or rows such that all zeros are covered.

Optimal solution at zero locations. Systematically make final assignments. (a) Check each row and column for a unique zero and make the first assign- ment in that row or column. (b) Eliminate that row and column and search for another unique zero. Make that assignment and proceed in a like manner.

Step 2

Optimal (No. of Lines = No. of Rows or Columns)

Not Optimal (No. of Lines < No. of Rows or Columns)

Step 3

Set up cost table for problem.

FIGURE 9.4 Steps in the Assignment Method

Row and column opportunity costs reflect the cost we are sacrificing by not making the least-cost selection.

368 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

We note at this point that although the assignment of Cooper to project 3 is the cheapest way to make use of Cooper, it is not necessarily the least-expensive approach to completing project 3. Adams can perform the same task for only $6. In other words, if we look at this assignment problem from a project angle instead of a people angle, the column opportunity costs may be completely different.

What we need to complete step 1 of the assignment method is a total opportunity cost table, that is, one that reflects both row and column opportunity costs. This involves following part (b) of step 1 to derive column opportunity costs.* We simply take the costs in Table 9.23 and sub- tract the smallest number in each column from each number in that column. The resulting total opportunity costs are given in Table 9.24.

You might note that the numbers in columns 1 and 3 are the same as those in Table 9.23, since the smallest column entry in each case was zero. Thus, it may turn out that the assignment of Cooper to project 3 is part of the optimal solution because of the relative nature of opportu- nity costs. What we are trying to measure are the relative efficiencies for the entire cost table and to find what assignments are best for the overall solution.

Step 2: Test for an Optimal Assignment. The objective of the Fix-It Shop owner is to assign the three workers to the repair projects in such a way that total labor costs are kept at a minimum. When translated to making assignments using our total opportunity cost table, this means that we would like to have a total assigned opportunity cost of 0. In other words, an optimal solution has zero opportunity costs for all of the assignments.

Looking at Table 9.24, we see that there are four possible zero opportunity cost assign- ments. We could assign Adams to project 3 and Brown to either project 1 or project 2. But this leaves Cooper without a zero opportunity cost assignment. Recall that two workers cannot be given the same task; each must do one and only one repair project, and each project must be as- signed to only one person. Hence, even though four zeros appear in this cost table, it is not yet possible to make an assignment yielding a total opportunity cost of zero.

A simple test has been designed to help us determine whether an optimal assignment can be made. The method consists of finding the minimum number of straight lines (vertical and hori- zontal) necessary to cover all zeros in the cost table. (Each line is drawn so that it covers as many zeros as possible at one time.) If the number of lines equals the number of rows or columns in the table, then an optimal assignment can be made. If, on the other hand, the number of lines is less than the number of rows or columns, an optimal assignment cannot be made. In the latter case, we must proceed to step 3 and develop a new total opportunity cost table.

Table 9.25 illustrates that it is possible to cover all four zero entries in Table 9.24 with only two lines. Because there are three rows, an optimal assignment may not yet be made.

Step 3: Revise the Opportunity-Cost Table. An optimal solution is seldom obtained from the initial opportunity cost table. Often, we need to revise the table in order to shift one (or more) of the zero costs from its present location (covered by lines) to a new uncovered location in the table. Intuitively, we would want this uncovered location to emerge with a new zero opportunity cost.

Total opportunity costs reflect the row and column opportunity cost analyses.

When a zero opportunity cost is found for all of the assignments, an optimal assignment can be made.

This line test is used to see if a solution is optimal.

*Can you think of a situation in which part (b) of step 1 would not be required? See if you can design a cost table in which an optimal solution is possible after part (a) of step 1 is completed.

PROJECT

PERSON 1 2 3

Adams $5 $8 $0

Brown 0 2 3

Cooper 2 5 0

TABLE 9.23 Row Opportunity Cost Table for the Fix-It Shop Step 1, Part (a)

PROJECT

PERSON 1 2 3

Adams $11 $14 $6

Brown 8 10 11

Cooper 9 12 7

TABLE 9.22 Cost of Each Person–Project Assignment for the Fix-It Shop Problem

9.8 THE ASSIGNMENT ALGORITHM 369

This is accomplished by subtracting the smallest number not covered by a line from all numbers not covered by a straight line. This same smallest number is then added to every num- ber (including zeros) lying at the intersection of any two lines.

The smallest uncovered number in Table 9.25 is 2, so this value is subtracted from each of the four uncovered numbers. A 2 is also added to the number that is covered by the intersecting horizontal and vertical lines. The results of step 3 are shown in Table 9.26.

To test now for an optimal assignment, we return to step 2 and find the minimum number of lines necessary to cover all zeros in the revised opportunity cost table. Because it requires three lines to cover the zeros (see Table 9.27), an optimal assignment can be made.

Making the Final Assignment It is apparent that the Fix-It Shop problem’s optimal assignment is Adams to project 3, Brown to project 2, and Cooper to project 1. In solving larger problems, however, it is best to rely on a more systematic approach to making valid assignments. One such way is first to select a row or column that contains only one zero cell. Such a situation is found in the first row, Adams’s row, in which the only zero is in the project 3 column. An assignment can be made to that cell, and then lines drawn through its row and column (see Table 9.28). From the uncovered rows and columns, we again choose a row or column in which there is only one zero cell. We make that assignment and continue the procedure until each person is assigned to one task.

The total labor costs of this assignment are computed from the original cost table (see Table 9.22). They are as follows:

PROJECT

PERSON 1 2 3

Adams $5 $6 $0

Brown 0 0 3

Cooper 2 3 0

TABLE 9.24 Total Opportunity Cost Table for the Fix-It Shop Step 1, Part (b)

PROJECT

PERSON 1 2 3

Adams $5 $6 $0

Brown 0 0 3 Covering line 1

Cooper 2 3 0

Covering line 2

TABLE 9.25 Test for Optimal Solution to Fix-It Shop Problem

PROJECT

PERSON 1 2 3

Adams $3 $4 $0

Brown 0 0 5

Cooper 0 1 0

TABLE 9.26 Revised Opportunity Cost Table for the Fix-It Shop Problem

PROJECT

PERSON 1 2 3

Adams $3 $4 $0

Brown 0 0 5 Covering line 2

Cooper 0 1 0

Covering line 1 Covering line 3

TABLE 9.27 Optimality Test on the Revised Fix-It Shop Opportunity Cost Table

ASSIGNMENT COST ($)

Adams to project 3 6

Brown to project 2 10

Cooper to project 1 9

Total cost 25

Making an optimal assignment involves first checking the rows and columns where there is only one zero cell.

370 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

USING EXCEL QM FOR THE FIX-IT SHOP ASSIGNMENT PROBLEM Excel QM’s Assignment mod- ule can be used to solve the Fix-It problem. Simply select Excel QM from the Add-Ins tab in Excel 2010 and then select Assignment. When the window opens, give the problem a title, enter the number of assignments (row or columns), and specify Minimize. Excel QM will initialize the spreadsheet, and the costs are then entered, as shown in Program 9.5. Then select Solver from the Data tab and click Solve. The solution will be placed in the Assignments area of the spreadsheet, as shown in Program 9.5. Adams will be assigned job 3, Brown will be assigned job 2, and Cooper will be assigned job 1. The total cost is $25.

(A) FIRST (B) SECOND (C) THIRD ASSIGNMENT ASSIGNMENT ASSIGNMENT

1 2 3 1 2 3 1 2 3

Adams 3 4 0 Adams 3 4 0 Adams 3 4 0

Brown 0 0 5 Brown 0 0 5 Brown 0 0 5

Cooper 0 1 0 Cooper 0 1 0 Cooper 0 1 0

TABLE 9.28 Making the Final Fix-It Shop Assignments

From the Data tab, select Solver and click Solve.

Solver puts the optimal assignments here.

Enter the costs.

PROGRAM 9.5 Excel QM Solution for Fix-It Shop Assignment Problem

9.9 SPECIAL SITUATIONS WITH THE ASSIGNMENT ALGORITHM 371

9.9 Special Situations with the Assignment Algorithm

There are two special situations that require special procedures when using the Hungarian algorithm for assignment problems. The first involves problems that are not balanced, and the second involves solving a maximization problem instead of a minimization problem.

Unbalanced Assignment Problems The solution procedure to assignment problems just discussed requires that the number of rows in the table equal the number of columns. Such a problem is called a balanced assignment problem. Often, however, the number of people or objects to be assigned does not equal the number of tasks or clients or machines listed in the columns, and the problem is unbalanced. When this occurs, and we have more rows than columns, we simply add a dummy column or task (similar to how we handled unbalanced transportation problems earlier in this chapter). If the number of tasks that need to be done exceeds the number of people available, we add a dummy row. This creates a table of equal dimensions and allows us to solve the problem as before. Since the dummy task or person is really nonexistent, it is reasonable to enter zeros in its row or column as the cost or time estimate.

Suppose the owner of the Fix-It Shop realizes that a fourth worker, Davis, is also available to work on one of the three rush jobs that just came in. Davis can do the first project for $10, the second for $13, and the third project for $8. The shop’s owner still faces the same basic problem, that is, which worker to assign to which project to minimize total labor costs. We do not have a fourth project, however, so we simply add a dummy column or dummy project. The initial cost table is shown in Table 9.29. One of the four workers, you should realize, will be assigned to the dummy project; in other words, the worker will not really be assigned any of the tasks.

Maximization Assignment Problems Some assignment problems are phrased in terms of maximizing the payoff, profit, or effec- tiveness of an assignment instead of minimizing costs. It is easy to obtain an equivalent min- imization problem by converting all numbers in the table to opportunity costs. This is brought about by subtracting every number in the original payoff table from the largest sin- gle number in that table. The transformed entries represent opportunity costs; it turns out that minimizing opportunity costs produces the same assignment as the original maximization problem. Once the optimal assignment for this transformed problem has been computed, the total payoff or profit is found by adding the original payoffs of those cells that are in the op- timal assignment.

Let us consider the following example. The British navy wishes to assign four ships to pa- trol four sectors of the North Sea. In some areas ships are to be on the outlook for illegal fish- ing boats, and in other sectors to watch for enemy submarines, so the commander rates each ship in terms of its probable efficiency in each sector. These relative efficiencies are illustrated in Table 9.30. On the basis of the ratings shown, the commander wants to determine the patrol assignments producing the greatest overall efficiencies.

A balanced assignment problem is one in which the number of rows equals the number of columns.

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

PROJECT

PERSON 1 2 3 DUMMY

Adams $11 $14 $6 $0

Brown 8 10 11 0

Cooper 9 12 7 0

Davis 10 13 8 0

TABLE 9.29 Estimated Project Repair Costs for Fix-It Shop with Davis Included

372 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

Step by step, the solution procedure is as follows. We first convert the maximizing effi- ciency table into a minimizing opportunity cost table. This is done by subtracting each rating from 100, the largest rating in the whole table. The resulting opportunity costs are given in Table 9.31.

We now follow steps 1 and 2 of the assignment algorithm. The smallest number in each row is subtracted from every number in that row (see Table 9.32); and then the smallest number in each column is subtracted from every number in that column (as shown in Table 9.33).

The minimum number of straight lines needed to cover all zeros in this total opportunity cost table is four. Hence an optimal assignment can be made already. You should be able by now to spot the best solution, namely, ship 1 to sector D, ship 2 to sector C, ship 3 to sector B, and ship 4 to sector A.

The overall efficiency, computed from the original efficiency data in Table 9.30, can now be shown:

Row subtractions: the smallest number in each row is subtracted from every number in that row.

Column subtractions: the smallest number in each column is subtracted from every number in that column.

SECTOR

SHIP A B C D

1 20 60 50 55

2 60 30 80 75

3 80 100 90 80

4 65 80 75 70

TABLE 9.30 Efficiencies of British Ships in Patrol Sectors

SECTOR

SHIP A B C D

1 80 40 50 45

2 40 70 20 25

3 20 0 10 20

4 35 20 25 30

TABLE 9.31 Opportunity Costs of British Ships

SECTOR

SHIP A B C D

1 25 0 10 0

2 5 50 0 0

3 5 0 10 15

4 0 0 5 5

TABLE 9.33 Total Opportunity Costs for the British Navy Problem

SECTOR

SHIP A B C D

1 40 0 10 5

2 20 50 0 5

3 20 0 10 20

4 15 0 5 10

TABLE 9.32 Row Opportunity Costs for the British Navy Problem

ASSIGNMENT EFFICIENCY

Ship 1 to sector D 55

Ship 2 to sector C 80

Ship 3 to sector B 100

Ship 4 to sector A 65

Total efficiency 300

GLOSSARY 373

Facility Location Leads to Improved Supply-Chain Reliability

Supply chains are, at their physical level, an interconnected net- work of delivery routes (roads, bridges, shipping lanes, etc.) that lead from multiple sources (warehouse, factories, refineries, etc.) to multiple destinations (stores, outlets, other warehouses, etc.) along which products and commodities travel. In most cases, the allocation of particular destinations to particular sources is known and fairly constant.

Researchers, in trying to help companies plan for emergen- cies, have investigated the problem of supply-chain disruption. What would happen if one of the sources were to catastrophically fail due to an earthquake, a tornado, or worse? The answer lies

in the area of the facility location problem: Which warehouses should deliver to which stores addresses this issue. Analyzing the transportation problem with current sources eliminated one by one, the analysts were able to measure the impact of such disrup- tion. The researchers concluded that “backup assignments” of warehouses to stores should be planned ahead of time to help mitigate the impact of possible catastrophes. It always pays to plan ahead!

Source: Based on L. Snyder and M. Daskin, “Reliability Models for Facility Location: The Expected Failure Cost Case,” Transportation Science 39, 3 (2005): 400–416.

IN ACTION

Summary

In this chapter we explored the transportation model and the assignment model. We saw how to develop an initial solution to the transportation problem with the northwest corner method. The stepping-stone path method was used to calculate improvement indices for the empty cells. Improved solutions were developed using a stepping-stone path. The special cases of the transportation problem included degeneracy, unbalanced problems, and multiple optimal solutions. We demonstrated

how to use the transportation model for facility location analysis.

We saw how the assignment problem may be viewed as a special case of the transportation problem. The Hungarian method for solving assignment problems was presented. When assignment problems are unbalanced, dummy rows or columns are used to balance the problem. Assignment problems with maximization objectives were also presented.

Glossary

Balanced Assignment Problem. An assignment problem in which the number of rows is equal to the number of columns.

Balanced Transportation Problem. The condition under which total demand (at all destinations) is equal to total supply (at all sources).

Degeneracy. A condition that occurs when the number of occupied squares in any solution is less than the number of rows plus the number of columns minus 1 in a transportation table.

Destination. A demand location in a transportation problem. Dummy Destination. An artificial destination added to a

transportation table when total supply is greater than total demand. The demand at the dummy destination is set so that total supply and demand are equal. The transportation cost for dummy destination cells is zero.

Dummy Rows or Columns. Extra rows or columns added in order to “balance” an assignment problem so that the number of rows equals the number of columns.

Dummy Source. An artificial source added to a transporta- tion table when total demand is greater than total supply. The supply at the dummy source is set so that total demand and supply are equal. The transportation cost for dummy source cells is zero.

Facility Location Analysis. An application of the transportation method to help a firm decide where to locate a new factory, warehouse, or other facility.

Flood’s Technique. Another name for the Hungarian method. Hungarian Method. A matrix reduction approach to solving

the assignment problem. Improvement Index. The net cost of shipping one unit on a

route not used in the current transportation problem solution. Matrix Reduction. The approach of the assignment method

that reduces the original assignment costs to a table of opportunity costs.

Northwest Corner Rule. A systematic procedure for establishing an initial feasible solution to the transportation problem.

374 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

Opportunity Costs. In an assignment problem, this is the additional cost incurred when the assignment with the lowest possible cost in a row or column is not selected.

Source. An origin or supply location in a transportation problem.

Stepping-Stone Method. An iterative technique for moving from an initial feasible solution to an optimal solution in transportation problems.

Transportation Problems. A specific case of LP concerned with scheduling shipments from sources to destinations so that total transportation costs are minimized.

Transportation Table. A table summarizing all transporta- tion data to help keep track of all algorithm computations. It stores information on demands, supplies, shipping costs, units shipped, origins, and destinations.

Solved Problems

Solved Problem 9-1 Don Yale, president of Hardrock Concrete Company, has plants in three locations and is currently work- ing on three major construction projects, located at different sites. The shipping cost per truckload of concrete, plant capacities, and project requirements are provided in the accompanying table.

a. Formulate an initial feasible solution to Hardrock’s transportation problem using the northwest cor- ner rule.

b. Then evaluate each unused shipping route (each empty cell) by applying the stepping-stone method and computing all improvement indices. Remember to do the following:

1. Check that supply and demand are equal.

2. Load the table via the northwest corner method.

3. Check that there are the proper number of occupied cells for a “normal” solution, namely,

4. Find a closed path to each empty cell.

5. Determine the improvement index for each unused cell.

6. Move as many units as possible to the cell that provides the most improvement (if there is one).

7. Repeat steps 3 through 6 until no further improvement can be found.

Number of rows + Number of columns - 1 = Number of occupied cells.

TO PROJECT PROJECT PROJECT PLANT FROM A B C CAPACITIES

PLANT 1 $10 $4 $11 70

PLANT 2 $12 $5 $8 50

PLANT 3 $9 $7 $6 30

PROJECT REQUIREMENTS 40 50 60 150

Solution a. Northwest corner solution:

Initial cost = 40($10) + 30($4) + 20($5) + 30($8) + 30($6) = $1,040

SOLVED PROBLEMS 375

TO PROJECT PROJECT PROJECT PLANT FROM A B C CAPACITIES

PLANT 1 $10 $4 $11

40 30 70

PLANT 2 $12 $5 $8

20 30 50

PLANT 3 $9 $7 $6

30 30

PROJECT REQUIREMENTS 40 50 60 150

b. Using the stepping-stone method, the following improvement indices are computed:

Path: plant 1 to project

(closed path: 1C to 1B to 2B to 2C)

C = $11 - $4 + $5 - $8 = +$4

FROM

PLANT 1

PLANT 2

PLANT 3

PROJECT REQUIREMENTS 40

7040 30

50 60 150

3030

503020

PROJECT A

PROJECT B

PROJECT C

PLANT CAPACITIES

10 4

5 8

–

11 Path: plant 1 to project C

376 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

Path: plant 2 to project

(closed path: 2A to 2B to 1B to 1A)

A = $12 - $5 + $4 - $10 = +$1

FROM TO

PLANT 1

PLANT 2

PLANT 3

PROJECT REQUIREMENTS 40

50 60 150

3020

3040

PROJECT A

PROJECT B

PROJECT C

PLANT CAPACITIES

10 4

5 8

–

11 Path: plant 2 to project A

9 7

Path: plant 3 to project

(closed path: 3A to 3C to 2C to 2B to 1B to 1A)

A = $9 - $6 + $8 - $5 + $4 - $10 = $0

FROM TO

PLANT 1 40 30

20 PLANT 2

PLANT 3

PROJECT REQUIREMENTS 40

50 60 150

PROJECT A

PROJECT B

PROJECT C

PLANT CAPACITIES

10 4

5 8

–

Path: plant 3 to project A

9 7

SOLVED PROBLEMS 377

Path: plant 3 to project

(closed path: 3B to 3C to 2C to 2B)

B = $7 - $6 + $8 - $5 = +$4

FROM TO

PLANT 1

PLANT 2

PLANT 3

PROJECT REQUIREMENTS

40 30 70

50 60 150

50 20 30

PROJECT A

PROJECT B

PROJECT C

PLANT CAPACITIES

10 4

5 8

–

Path: plant 3 to project B

Since all indices are greater than or equal to zero (all are positive or zero), this initial solution provides the optimal transportation schedule, namely, 40 units from 1 to A, 30 units from 1 to B, 20 units from 2 to B, 30 units from 2 to C, and 30 units from 3 to C.

Had we found a path that allowed improvement, we would move all units possible to that cell and then check every empty cell again. Because the plant 3 to project A improvement index was equal to zero, we note that multiple optimal solutions exist.

Solved Problem 9-2 The initial solution found in Solved Problem 9-1 was optimal, but the improvement index for one of the empty cells was zero, indicating another optimal solution. Use a stepping-stone path to develop this other optimal solution.

Solution Using the stepping-stone path, we see that the lowest number of units in a cell where a subtraction is to be made is 20 units from plant 2 to project B. Therefore, 20 units will be subtracted from each cell with a minus sign and added to each cell with a plus sign. The result is shown here:

TO PROJECT PROJECT PROJECT PLANT FROM A B C CAPACITIES

PLANT 1 10 4 11

20 50 70

PLANT 2 12 5 8

50 50

PLANT 3 9 7 6

20 10 30

PROJECT REQUIREMENTS 40 50 60 150

378 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

Solved Problem 9-3 Solve the Hardgrave Machine Company facility location problem shown in Table 9.19 on page 366 with an LP formulation.

Solution First we shall formulate this transportation problem as an LP model by introducing double-subscripted decision variables. We let denote the number of units shipped from origin 1 (Cincinnati) to destination 1 (Detroit), denote shipments from origin 1 (Cincinnati) to destination 2 (Dallas), and so on. In general, the decision variables for a transportation problem having m origins and n destinations are written as

where

Because the objective of the transportation model is to minimize total transportation costs, we develop the following cost expression:

Now we establish supply constraints for each of the four plants:

(Cincinnati supply)

(Salt Lake supply)

(Pittsburgh supply)

(Seattle supply)

With four warehouses as the destinations, we need the following four demand constraints:

(Detroit demand)

(Dallas demand)

(New York demand)

(Los Angeles demand)

A computer solution will confirm that total shipping costs will be $3,704,000. Although LP codes can indeed be used on transportation problems, the special transportation module for Excel QM (shown ear- lier) and QM for Windows (shown in Appendix 9.1) tend to be easier to input, run, and interpret.

Solved Problem 9-4 Prentice Hall, Inc., a publisher headquartered in New Jersey, wants to assign three recently hired college graduates, Jones, Smith, and Wilson to regional sales districts in Omaha, Dallas, and Miami. But the firm also has an opening in New York and would send one of the three there if it were more economical than a move to Omaha, Dallas, or Miami. It will cost $1,000 to relocate Jones to New York, $800 to relocate Smith there, and $1,500 to move Wilson. What is the optimal assignment of personnel to offices?

X14 + X24 + X34 + X44 = 9,000

X13 + X23 + X33 + X43 = 15,000

X12 + X22 + X32 + X42 = 12,000

X11 + X21 + X31 + X41 = 10,000

X41 + X42 + X43 + X44 … 11,000

X31 + X32 + X33 + X34 … 14,000

X21 + X22 + X23 + X24 … 6,000

X11 + X12 + X13 + X14 … 15,000

+ 113X41 + 91X42 + 118X43 + 80X44

+ 88X31 + 97X32 + 78X33 + 118X34

+ 85X21 + 80X22 + 100X23 + 90X24

Minimize = 73X11 + 103X12 + 88X13 + 108X14

j = 1, 2, Á , n

i = 1, 2, Á , m

Xij = Number of units shipped from origin i to destination j

X12

X11

OFFICE HIREE OMAHA MIAMI DALLAS

JONES $800 $1,100 $1,200

SMITH $500 $1,600 $1,300

WILSON $500 $1,000 $2,300

SOLVED PROBLEMS 379

Solution

a. The cost table has a fourth column to represent New York. To balance the problem, we add a dummy row (person) with a zero relocation cost to each city.

OFFICE HIREE OMAHA MIAMI DALLAS NEW YORK

JONES $800 $1,100 $1,200 $1,000

SMITH $500 $1,600 $1,300 $800

WILSON $500 $1,000 $2,300 $1,500

DUMMY 0 0 0 0

OFFICE HIREE OMAHA MIAMI DALLAS NEW YORK

JONES 0 100 200 0

SMITH 0 900 600 100

WILSON 0 300 1,600 800

DUMMY 200 0 0 0

OFFICE HIREE OMAHA MIAMI DALLAS NEW YORK

JONES 0 300 400 200

SMITH 0 1,100 800 300

WILSON 0 500 1,800 1,000

DUMMY 0 0 0 0

b. Subtract smallest number in each row and cover zeros (column subtraction will give the same num- bers and therefore is not necessary).

c. Subtract smallest uncovered number (200), add it to each square where two lines intersect, and cover all zeros.

d. Subtract smallest uncovered number (100), add it to each square where two lines intersect, and cover all zeros.

OFFICE HIREE OMAHA MIAMI DALLAS NEW YORK

JONES 0 0 100 0

SMITH 0 800 500 100

WILSON 0 200 1,500 800

DUMMY 300 0 0 100

380 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

e. Subtract smallest uncovered number (100), add it to squares where two lines intersect, and cover all zeros.

OFFICE HIREE OMAHA MIAMI DALLAS NEW YORK

JONES 100 0 100 0

SMITH 0 700 400 0

WILSON 0 100 1,400 700

DUMMY 400 0 0 100

f. Since it takes four lines to cover all zeros, an optimal assignment can be made at zero squares. We assign

Dummy (no one) to Dallas

Wilson to Omaha

Smith to New York

Jones to Miami

Cost = $0 + $500 + $800 + $1,100 = $2,400

Self-Test

� Before taking the self-test, refer to the learning objectives at the beginning of the chapter, the notes in the margins, and the glossary at the end of the chapter.

� Use the key at the back of the book to correct your answers. � Restudy pages that correspond to any questions that you answered incorrectly or material you feel uncertain about.

1. If the total demand equals the total supply in a transportation problem, the problem is a. degenerate. b. balanced. c. unbalanced. d. infeasible.

2. If a transportation problem has 4 sources and 5 destinations, the linear program for this will have a. 4 variables and 5 constraints. b. 5 variable and 4 constraints. c. 9 variables and 20 constraints. d. 20 variables and 9 constraints.

3. In a transportation problem, what indicates that the mini- mum cost solution has been found? a. all improvement indices are negative or zero b. all improvement indices are positive or zero c. all improvement indices are equal to zero d. all cells in the dummy row are empty

4. An assignment problem may be viewed as a transportation problem with a. a cost of $1 for all shipping routes. b. all supplies and demands equal to 1.

c. only demand constraints. d. only supply constraints.

5. If the number of filled cells in a transportation table does not equal the number of rows plus the number of columns minus 1, then the problem is said to be a. unbalanced. b. degenerate. c. optimal. d. maximization problem.

6. If a solution to a transportation problem is degenerate, then a. it will be impossible to evaluate all empty cells without

removing the degeneracy. b. a dummy row or column must be added. c. there will be more than one optimal solution. d. the problem has no feasible solution.

7. If the total demand is greater than the total capacity in a transportation problem, then a. the optimal solution will be degenerate. b. a dummy source must be added. c. a dummy destination must be added. d. both a dummy source and a dummy destination must

be added.

DISCUSSION QUESTIONS AND PROBLEMS 381

8. In solving a facility location problem in which there are two possible locations being considered, the transportation algorithm may be used. In doing this, a. two rows (sources) would be added to the existing

rows and the enlarged problem would be solved. b. two separate transportation problems would be solved. c. costs of zero would be used for each of the new facilities. d. the problem would be a transshipment problem.

9. The Hungarian method is a. a way to develop an initial solution to a transportation

problem. b. used to solve assignment problems. c. also called Vogel’s approximation method. d. only used for problems in which the objective is to

maximize profit.

10. In an assignment problem, it may be necessary to add more than one row to the table. a. True b. False

11. When using the Hungarian method, an optimal assignment can always be made when every row and every column has at least one zero. a. True b. False

12. An assignment problem can be viewed as a special type of transportation problem with which of the following features? a. the capacity for each source and the demand for each

destination is equal to one b. the number of rows is equal to the number of columns c. the cost for each shipping route is equal to one d. all of the above

Discussion Questions and Problems

Discussion Questions 9-1 Is the transportation model an example of decision

making under certainty or decision making under uncertainty? Why?

9-2 Explain how to determine the number of variables and constraints that would be in a transportation problem simply by knowing the number of sources and the number of destinations.

9-3 What is a balanced transportation problem? Describe the approach you would use to solve an unbalanced problem.

9-4 The stepping-stone method is being used to solve a transportation problem. The smallest quantity in a cell with a minus sign is 35, but two different cells with minus signs have 35 units in them. What prob- lem will this cause, and how should this difficulty be resolved?

9-5 The stepping-stone method is being used to solve a transportation problem. There is only one empty cell having a negative improvement index, and this index is The stepping-stone path for this cell indicates that the smallest quantity for the cells with minus signs is 80 units. If the total cost for the current solution is $900, what will the total cost be for the im- proved solution? What can you conclude about how much the total cost will decrease when developing each new solution for any transportation problem?

9-6 Explain what happens when the solution to a trans- portation problem does not have occu- pied squares (where number of rows in the table and number of columns in the table).

9-7 What is the enumeration approach to solving assign- ment problems? Is it a practical way to solve a 5 row 5 column problem? a problem? Why?7 * 7

n = m =

m + n - 1

-2.

9-8 How could an assignment problem be solved using the transportation approach? What condition will make the solution of this problem difficult?

9-9 You are the plant supervisor and are responsible for scheduling workers to jobs on hand. After estimat- ing the cost of assigning each of five available work- ers in your plant to five projects that must be completed immediately, you solve the problem us- ing the Hungarian method. The following solution is reached and you post these job assignments:

Jones to project A

Smith to project B

Thomas to project C

Gibbs to project D

Heldman to project E

The optimal cost was found to be $492 for these as- signments. The plant general manager inspects your original cost estimates and informs you that in- creased employee benefits mean that each of the 25 numbers in your cost table is too low by $5. He suggests that you immediately rework the problem and post the new assignments. Is this necessary? Why? What will the new optimal cost be?

9-10 Sue Simmons’s marketing research firm has local representatives in all but five states. She decides to expand to cover the whole United States by transfer- ring five experienced volunteers from their current locations to new offices in each of the five states. Simmons’s goal is to relocate the five representa- tives at the least total cost. Consequently, she sets up a relocation cost table and prepares to solve it for the best assignments by use of the Hungarian

5 * 5

382 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

method. At the last moment, Simmons recalls that although the first four volunteers did not pose any objections to being placed in any of the five new cities, the fifth volunteer did make one restriction. That person absolutely refused to be assigned to the new office in Tallahassee, Florida—fear of southern roaches, the representative claimed! How should Sue alter the cost matrix to ensure that this assign- ment is not included in the optimal solution?

Problems* 9-11 The management of the Executive Furniture Corpo-

ration decided to expand the production capacity at its Des Moines factory and to cut back production at its other factories. It also recognizes a shifting mar- ket for its desks and revises the requirements at its three warehouses. (a) Use the northwest corner rule to establish an ini-

tial feasible shipping schedule and calculate its cost.

(b) Use the stepping-stone method to test whether an improved solution is possible.

(c) Explain the meaning and implications of an improvement index that is equal to 0. What deci- sions might management make with this informa- tion? Exactly how is the final solution affected?

9-12 Formulate the transportation problem in Problem 9-11 as a linear program and solve using computer soft- ware.

9-13 The Hardrock Concrete Company has plants in three locations and is currently working on three major construction projects, each located at a different site. The shipping cost per truckload of concrete, daily plant capacities, and daily project requirements are provided in the table below. (a) Formulate an initial feasible solution to Hard-

rock’s transportation problem using the north- west corner rule. Then evaluate each unused shipping route by computing all improvement indices. Is this solution optimal? Why?

(b) Is there more than one optimal solution to this problem? Why?

NEW WAREHOUSE REQUIREMENTS NEW FACTORY CAPACITIES

Albuquerque (A) 200 desks Des Moines (D) 300 desks

Boston (B) 200 desks Evansville (E) 150 desks

Cleveland (C) 300 desks Fort Lauderdale (F) 250 desks

Data for Problem 9-11

TO FROM ALBUQUERQUE BOSTON CLEVELAND

DES MOINES 5 4 3

EVANSVILLE 8 4 3

FORT LAUDERDALE 9 7 5

Table for Problem 9-11

TO FROM PROJECT A PROJECT B PROJECT C PLANT CAPACITIES

PLANT 1 $10 $4 $11 70

PLANT 2 12 5 8 50

PLANT 3 9 7 6 30

PROJECT REQUIREMENTS 40 50 60 150

Data for Problem 9-13

Note: means the problem may be solved with QM for Windows; means the problem may be

solved with Excel QM; and means the problem may be solved with QM for Windows and/or Excel QM.

DISCUSSION QUESTIONS AND PROBLEMS 383

9-14 Hardrock Concrete’s owner has decided to increase the capacity at his smallest plant (see Problem 9-13). In- stead of producing 30 loads of concrete per day at plant 3, that plant’s capacity is doubled to 60 loads. Find the new optimal solution using the northwest corner rule and stepping-stone method. How has changing the third plant’s capacity altered the optimal shipping as- signment? Discuss the concepts of degeneracy and multiple optimal solutions with regard to this problem.

9-15 Formulate the Hardrock Concrete Company trans- portation problem in Problem 9-13 as a linear pro- gram and solve using computer software. What would change in the linear program if the change in Problem 9-14 were implemented?

9-16 The Saussy Lumber Company ships pine flooring to three building supply houses from its mills in Pineville, Oak Ridge, and Mapletown. Determine the best transportation schedule for the data given in the table. Use the northwest corner rule and the step- ping-stone method.

9-17 The Krampf Lines Railway Company specializes in coal handling. On Friday, April 13, Krampf had empty cars at the following towns in the quantities indicated:

TOWN SUPPLY OF CARS

Morgantown 35

Youngstown 60

Pittsburgh 25

TO SUPPLY SUPPLY SUPPLY MILL FROM HOUSE 1 HOUSE 2 HOUSE 3 CAPACITY (TONS)

PINEVILLE $3 $3 $2

OAK RIDGE 4 2 3

MAPLETOWN 3 2 3

SUPPLY HOUSE DEMAND (TONS) 30 30 35 95

Table for Problem 9-16

TOWN DEMAND FOR CARS

Coal Valley 30

Coaltown 45

Coal Junction 25

Coalsburg 20

By Monday, April 16, the following towns will need coal cars as follows:

TO FROM COAL VALLEY COALTOWN COAL JUNCTION COALSBURG

MORGANTOWN 50 30 60 70

YOUNGSTOWN 20 80 10 90

PITTSBURGH 100 40 80 30

Table for Problem 9-17

Using a railway city-to-city distance chart, the dis- patcher constructs a mileage table for the preceding towns. The result is shown in the table below. Mini- mizing total miles over which cars are moved to new locations, compute the best shipment of coal cars.

9-18 Formulate the Krampf Lines Railway Company sit- uation (Problem 9-17) as a linear program and solve using computer software.

9-19 An air conditioning manufacturer produces room air conditioners at plants in Houston, Phoenix, and Memphis. These are sent to regional distributors in Dallas, Atlanta, and Denver. The shipping costs vary, and the company would like to find the least-cost way to meet the demands at each of the distribution centers. Dallas needs to receive 800 air conditioners per month, Atlanta needs 600, and Denver needs 200. Houston has 850 air conditioners available each month, Phoenix has 650, and Memphis has 300. The shipping cost per unit from Houston to Dallas is $8,

384 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

to Atlanta is $12, and to Denver is $10. The cost per unit from Phoenix to Dallas is $10, to Atlanta is $14, and to Denver is $9. The cost per unit from Memphis to Dallas is $11, to Atlanta is $8, and to Denver is $12. How many units should be shipped from each plant to each regional distribution center? What is the total cost for this?

9-20 Formulate the air conditioning situation present in Problem 9-18 as a linear program and solve using computer software.

9-21 Finnish Furniture manufactures tables in facilities located in three cities—Reno, Denver, and Pitts- burgh. The tables are then shipped to three retail stores located in Phoenix, Cleveland, and Chicago. Management wishes to develop a distribution sched- ule that will meet the demands at the lowest possible cost. The shipping cost per unit from each of the sources to each of the destinations is shown in the following table:

TO FROM PHOENIX CLEVELAND CHICAGO

RENO 10 16 19

DENVER 12 14 13

PITTSBURGH 18 12 12

The available supplies are 120 units from Reno, 200 from Denver, and 160 from Pittsburgh. Phoenix has a demand of 140 units, Cleveland has a demand of 160 units, and Chicago has a demand of 180 units. How many units should be shipped from each man- ufacturing facility to each of the retail stores if cost is to be minimized? What is the total cost?

9-22 Finnish Furniture has experienced a decrease in the demand for tables in Chicago; the demand has fallen

TO EXCESS FROM W X Y Z SUPPLY

A 12¢ 4¢ 9¢ 5¢ 55

B 8¢ 1¢ 6¢ 6¢ 45

C 1¢ 12¢ 4¢ 7¢ 30

UNFILLED POWER DEMAND 40 20 50 20

Find an initial transmission assignment of the excess power supply. Then find the least-cost distribution system.

9-25 Consider the transportation table given below. Find an initial solution using the northwest corner rule. What special condition exists? Explain how you will proceed to solve the problem.

TO DESTINATION DESTINATION DESTINATION FROM A B C SUPPLY

SOURCE 1 $8 $9 $4

SOURCE 2 5 6 8

SOURCE 3 7 9 6

SOURCE 4 5 3 7

DEMAND 110 34 31 175

Table for Problem 9-25

to 150 units (see Problem 9-21). What special condition would exist? What is the minimum-cost solution? Will there be any units remaining at any of the manufacturing facilities?

9-23 Formulate the Finnish Furniture situation (Problem 9-21) as a linear program and solve using computer software.

9-24 The state of Missouri has three major power-generating companies (A, B, and C). During the months of peak demand, the Missouri Power Authority authorizes these companies to pool their excess supply and to distribute it to smaller independent power companies that do not have generators large enough to handle the demand. Excess supply is distributed on the ba- sis of cost per kilowatt hour transmitted. The follow- ing table shows the demand and supply in millions of kilowatt hours and the cost per kilowatt hour of transmitting electric power to four small companies in cities W, X, Y, and Z:

DISCUSSION QUESTIONS AND PROBLEMS 385

TO HOSPITAL HOSPITAL HOSPITAL HOSPITAL FROM 1 2 3 4 SUPPLY

BANK 1 $8 $9 $11 $16

BANK 2 12 7 5 8

BANK 3 14 10 6 7

120

DEMAND 90 70 40 50 250

Table for Problem 9-26

DEMAND FOR MONTH STAINLESS STEEL SINKS

1 120

2 160

3 240

4 100

PROPERTY (INTEREST RATES) (%)

SAVINGS AND DRURY MAXIMUM LOAN COMPANY HILL ST. BANKS ST. PARK AVE. LANE CREDIT LINE ($)

FIRST HOMESTEAD 8 8 10 11 80,000

COMMONWEALTH 9 10 12 10 100,000

WASHINGTON FEDERAL 9 11 10 9 120,000

LOAN REQUIRED TO PURCHASE BUILDING $60,000 $40,000 $130,000 $70,000

Table for Problem 9-28

9-26 The three blood banks in Franklin County are coordi- nated through a central office that facilitates blood de- livery to four hospitals in the region. The cost to ship a standard container of blood from each bank to each hospital is shown in the table below. Also given are the biweekly number of containers available at each bank and the biweekly number of containers of blood needed at each hospital. How many shipments should be made biweekly from each blood bank to each hos- pital so that total shipment costs are minimized?

9-27 Formulate the Franklin County Blood Bank situation (Problem 9-26) as a linear program and solve using computer software.

9-28 The B. Hall Real Estate Investment Corporation has identified four small apartment buildings in which it would like to invest. Mrs. Hall has approached three savings and loan companies regarding financing. Because Hall has been a good client in the past and has maintained a high credit rating in the commu- nity, each savings and loan company is willing to consider providing all or part of the mortgage loan needed on each property. Each loan officer has set differing interest rates on each property (rates are af- fected by the neighborhood of the apartment build- ing, condition of the property, and desire by the individual savings and loan to finance various-size buildings), and each loan company has placed a

maximum credit ceiling on how much it will lend Hall in total. This information is summarized in the table on this page.

Each apartment building is equally attractive as an investment to Hall, so she has decided to pur- chase all buildings possible at the lowest total pay- ment of interest. From which savings and loan companies should she borrow to purchase which buildings? More than one savings and loan can fi- nance the same property.

9-29 Formulate the B. Hall Real Estate Investment Cor- poration problem (Problem 9-28) as a linear pro- gram and solve using computer software.

9-30 The J. Mehta Company’s production manager is planning for a series of 1-month production periods for stainless steel sinks. The demand for the next 4 months is as follows:

386 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

The Mehta firm can normally produce 100 stainless steel sinks in a month. This is done during regular production hours at a cost of $100 per sink. If de- mand in any 1 month cannot be satisfied by regular production, the production manager has three other choices: (1) He can produce up to 50 more sinks per month in overtime but at a cost of $130 per sink; (2) he can purchase a limited number of sinks from a friendly competitor for resale (the maximum num- ber of outside purchases over the 4-month period is 450 sinks, at a cost of $150 each); or (3) he can fill the demand from his on-hand inventory. The inven- tory carrying cost is $10 per sink per month. Back orders are not permitted. Inventory on hand at the beginning of month 1 is 40 sinks. Set up this “pro- duction smoothing” problem as a transportation problem to minimize cost. Use the northwest corner rule to find an initial level for production and outside purchases over the 4-month period.

9-31 Formulate the J. Mehta production problem (See Problem 9-30) as a linear program and solve using computer software.

9-32 Ashley’s Auto Top Carriers currently maintains plants in Atlanta and Tulsa that supply major distri- bution centers in Los Angeles and New York. Be- cause of an expanding demand, Ashley has decided to open a third plant and has narrowed the choice to one of two cities—New Orleans or Houston. The pertinent production and distribution costs, as well as the plant capacities and distribution demands, are shown in the table below.

Which of the new possible plants should be opened?

9-33 Formulate and solve linear programs to help Ashley’s Auto Top Carriers (See Problem 9-32) determine

where to open the new plant. How much difference in the costs for the two locations?

9-34 Marc Smith, vice president for operations of HHN, Inc., a manufacturer of cabinets for telephone switches, is constrained from meeting the 5-year forecast by limited capacity at the existing three plants. These three plants are Waterloo, Pusan, and Bogota. You, as his able assistant, have been told that because of existing capacity constraints and the expanding world market for HHN cabinets, a new plant is to be added to the existing three plants. The real estate department has advised Marc that two sites seem particularly good because of a stable po- litical situation and tolerable exchange rate: Dublin, Ireland, and Fontainebleau, France. Marc suggests that you should be able to take the data on the next page and determine where the fourth plant should be located on the basis of production costs and trans- portation costs. Which location is better?

9-35 Don Levine Corporation is considering adding an additional plant to its three existing facilities in Decatur, Minneapolis, and Carbondale. Both St. Louis and East St. Louis are being considered. Evaluating only the transportation costs per unit as shown in the tables below and on the next page, which site is best?

Indicates distribution cost (shipping, handling, storage) will be $6 per carrier if sent from Houston to New York

TO DISTRIBUTION CENTERS

FROM PLANTS

ATLANTA

TULSA

NEW ORLEANS

HOUSTON

FORECAST DEMAND

LOS ANGELES

NEW YORK

NORMAL PRODUCTION

UNIT PRODUCTION

COST ($)

800

1,200

2,000

500

900

600 6

Existing plants

Proposed locations

(anticipated)

Data for Problem 9-32

FROM EXISTING PLANTS

TO DECATUR MINNEAPOLIS CARBONDALE DEMAND

Blue Earth $20 $17 $21 250

Ciro 25 27 20 200

Des Moines 22 25 22 350

Capacity 300 200 150

DISCUSSION QUESTIONS AND PROBLEMS 387

9-36 Using the data from Problem 9-35 plus the unit pro- duction costs shown in the following table, which lo- cations yield the lowest cost?

9-38 Four automobiles have entered Bubba’s Repair Shop for various types of work, ranging from a transmis- sion overhaul to a brake job. The experience level of the mechanics is quite varied, and Bubba would like to minimize the time required to complete all of the jobs. He has estimated the time in minutes for each mechanic to complete each job. Billy can complete job 1 in 400 minutes, job 2 in 90 minutes, job 3 in 60 minutes, and job 4 in 120 minutes. Taylor will finish job 1 in 650 minutes, job 2 in 120 minutes, job 3 in 90 minutes, and job 4 in 180 minutes. Mark will finish job 1 in 480 minutes, job 2 in 120 minutes, job 3 in 80 minutes, and job 4 in 180 minutes. John will complete job 1 in 500 minutes, job 2 in 110 minutes, job 3 in 90 minutes, and job 4 in 150 minutes. Each mechanic should be assigned to just one of these jobs. What is the minimum total time required to finish the four jobs? Who should be assigned to each job?

PLANT LOCATION

MARKET AREA WATERLOO PUSAN BOGOTA FONTAINEBLEAU DUBLIN

Canada

Demand 4,000

Production cost $50 $30 $40 $50 $45

Transportation cost 10 25 20 25 25

South America

Demand 5,000

Production cost 50 30 40 50 45

Transportation cost 20 25 10 30 30

Pacific Rim

Demand 10,000

Production cost 50 30 40 50 45

Transportation cost 25 10 25 40 40

Europe

Demand 5,000

Production cost 50 30 40 50 45

Transportation cost 25 40 30 10 20

Capacity 8,000 2,000 5,000 9,000 9,000

Data for Problem 9-34

FROM PROPOSED PLANTS

TO EAST ST. LOUIS ST. LOUIS

Blue Earth $29 $27

Ciro 30 28

Des Moines 30 31

Capacity 150 150

LOCATION PRODUCTION COSTS

Decatur $50

Minneapolis 60

Carbondale 70

East St. Louis 40

St. Louis 50

9-37 In a job shop operation, four jobs may be performed on any of four machines. The hours required for each job on each machine are presented in the fol- lowing table. The plant supervisor would like to as- sign jobs so that total time is minimized. Find the best solution.

MACHINE

JOB W X Y Z

A12 10 14 16 13

A15 12 13 15 12

B2 9 12 12 11

B9 14 16 18 16

388 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

9-39 Baseball umpiring crews are currently in four cities where three-game series are beginning. When these are finished, the crews are needed to work games in four different cities. The distances (miles) from each of the cities where the crews are currently working to the cities where the new games will begin are shown in the following table:

Bardot, and Hoolihan. Believing in the quantitative analysis approach to problem solving, the adminis- trator has interviewed each nurse, considered his or her background, personality, and talents, and devel- oped a cost scale ranging from 0 to 100 to be used in the assignment. A 0 for Nurse Bardot being assigned to the cardiology unit implies that she would be per- fectly suited to that task. A value close to 100, on the other hand, would imply that she is not at all suited to head that unit. The accompanying table gives the complete set of cost figures that the hospital admin- istrator felt represented all possible assignments. Which nurse should be assigned to which unit?

9-43 The Gleaming Company has just developed a new dishwashing liquid and is preparing for a national tel- evision promotional campaign. The firm has decided to schedule a series of 1-minute commercials during the peak homemaker audience viewing hours of 1 to 5 p.m. To reach the widest possible audience, Gleam- ing wants to schedule one commercial on each of four networks and to have one commercial appear during each of the four 1-hour time blocks. The exposure rat- ings for each hour, which represent the number of viewers per $1,000 spent, are presented in the follow- ing table. Which network should be scheduled each hour to provide the maximum audience exposure?

FROM KANSAS CITY CHICAGO DETROIT TORONTO

Seattle 1,500 1,730 1,940 2,070

Arlington 460 810 1,020 1,270

Oakland 1,500 1,850 2,080 X

Baltimore 960 610 400 330

COURSE

PROFESSOR STATISTICS MANAGEMENT FINANCE ECONOMICS

Anderson 90 65 95 40

Sweeney 70 60 80 75

Williams 85 40 80 60

McKinney 55 80 65 55

DEPARTMENT

NURSE UROLOGY CARDIOLOGY ORTHOPEDICS OBSTETRICS

Hawkins 28 18 15 75

Condriac 32 48 23 38

Bardot 51 36 24 36

Hoolihan 25 38 55 12

The X indicates that the crew in Oakland cannot be sent to Toronto. Determine which crew should be sent to each city to minimize the total distance traveled. How many miles will be traveled if these assignments are made?

9-40 In Problem 9-39, the minimum travel distance was found. To see how much better this solution is than the assignments that might have been made, find the assignments that would give the maximum distance traveled. Compare this total distance with the dis- tance found in Problem 9-39.

9-41 Roscoe Davis, chairman of a college’s business department, has decided to apply a new method in assigning professors to courses next semester. As a criterion for judging who should teach each course, Professor Davis reviews the past two years’ teaching evaluations (which were filled out by students). Since each of the four professors taught each of the four courses at one time or another during the two- year period, Davis is able to record a course rating for each instructor. These ratings are shown in the table. Find the best assignment of professors to courses to maximize the overall teaching rating.

9-42 The hospital administrator at St. Charles General must appoint head nurses to four newly established departments: urology, cardiology, orthopedics, and obstetrics. In anticipation of this staffing problem, she had hired four nurses: Hawkins, Condriac,

NETWORK

VIEWING HOURS A B C INDEPENDENT

1–2 P.M. 27.1 18.1 11.3 9.5

2–3 P.M. 18.9 15.5 17.1 10.6

3–4 P.M. 19.2 18.5 9.9 7.7

4–5 P.M. 11.5 21.4 16.8 12.8

PROJECT

WORKER 1 2 3

Adams $11 $14 $6

Brown 8 10 11

Cooper 9 12 7

Davis 10 13 8

9-44 The Fix-It Shop (see Section 9.8) has added a fourth repairman, Davis. Solve the accompanying cost table for the new optimal assignment of workers to projects. Why did this solution occur?

DISCUSSION QUESTIONS AND PROBLEMS 389

9-45 The Patricia Garcia Company is producing seven new medical products. Each of Garcia’s eight plants can add one more product to its current line of med- ical devices. The unit manufacturing costs for pro- ducing the different parts at the eight plants are shown in the table above. How should Garcia assign the new products to the plants to minimize manufac- turing costs?

9-46 Haifa Instruments, an Israeli producer of portable kidney dialysis units and other medical products, develops an 8-month aggregate plan. Demand and capacity (in units) are forecast as shown in the table below.

The cost of producing each dialysis unit is $1,000 on regular time, $1,300 on overtime, and $1,500 on a subcontract. Inventory carrying cost is $100 per unit per month. There is no beginning or ending in- ventory in stock. (a) Set up a production plan, using the transporta-

tion model, that minimizes cost. What is this plan’s cost?

(b) Through better planning, regular time produc- tion can be set at exactly the same value, 275 per month. Does this alter the solution?

9-47 NASA’s astronaut crew currently includes 10 mis- sion specialists who hold a doctoral degree in either astrophysics or astromedicine. One of these special- ists will be assigned to each of the 10 flights sched- uled for the upcoming nine months. Mission specialists are responsible for carrying out scientific and medical experiments in space or for launching, retrieving, or repairing satellites. The chief of astro- naut personnel, himself a former crew member with three missions under his belt, must decide who should be assigned and trained for each of the very different missions. Clearly, astronauts with medical educations are more suited to missions involving bi- ological or medical experiments, whereas those with engineering- or physics-oriented degrees are best suited to other types of missions. The chief assigns each astronaut a rating on a scale of 1 to 10 for each possible mission, with a 10 being a perfect match for the task at hand and a 1 being a mismatch. Only one specialist is assigned to each flight, and none is reas- signed until all others have flown at least once. (a) Who should be assigned to which flight? (b) NASA has just been notified that Anderson is

getting married in February and has been granted a highly sought publicity tour in Europe that month. (He intends to take his wife and let

CAPACITY SOURCE JAN. FEB. MAR. APR. MAY JUNE JULY AUG.

Labor

Regular time 235 255 290 300 300 290 300 290

Overtime 20 24 26 24 30 28 30 30

Subcontract 12 15 15 17 17 19 19 20

Demand 255 294 321 301 330 320 345 340

Data for Problem 9-46

ELECTRONIC PLANT

COMPONENT 1 2 3 4 5 6 7 8

C53 $0.10 $0.12 $0.13 $0.11 $0.10 $0.06 $0.16 $0.12

C81 0.05 0.06 0.04 0.08 0.04 0.09 0.06 0.06

D5 0.32 0.40 0.31 0.30 0.42 0.35 0.36 0.49

D44 0.17 0.14 0.19 0.15 0.10 0.16 0.19 0.12

E2 0.06 0.07 0.10 0.05 0.08 0.10 0.11 0.05

E35 0.08 0.10 0.12 0.08 0.09 0.10 0.09 0.06

G99 0.55 0.62 0.61 0.70 0.62 0.63 0.65 0.59

Data for Problem 9-45

390 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

the trip double as a honeymoon.) How does this change the final schedule?

(c) Certo has complained that he was misrated on his January missions. Both ratings should be 10s, he claims to the chief, who agrees and re- computes the schedule. Do any changes occur over the schedule set in part (b)?

(d) What are the strengths and weaknesses of this approach to scheduling?

9-48 The XYZ Corporation is expanding its market to include Texas. Each salesperson is assigned to

potential distributors in one of five different areas. It is anticipated that the salesperson will spend about three to four weeks in each area. A statewide mar- keting campaign will begin once the product has been delivered to the distributors. The five sales peo- ple who will be assigned to these areas (one person for each area) have rated the areas on the desirability of the assignment as shown in the following table. The scale is 1 (least desirable) to 5 (most desirable). Which assignments should be made if the total of the ratings is to be maximized?

MISSION

JAN. JAN. FEB. FEB. MAR. APR. MAY JUN. AUG. SEP. ASTRONAUT 12 27 5 26 26 12 1 9 20 19

Vincze 9 7 2 1 10 9 8 9 2 6

Veit 8 8 3 4 7 9 7 7 4 4

Anderson 2 1 10 10 1 4 7 6 6 7

Herbert 4 4 10 9 9 9 1 2 3 4

Schatz 10 10 9 9 8 9 1 1 1 1

Plane 1 3 5 7 9 7 10 10 9 2

Certo 9 9 8 8 9 1 1 2 2 9

Moses 3 2 7 6 4 3 9 7 7 9

Brandon 5 4 5 9 10 10 5 4 9 8

Drtina 10 10 9 7 6 7 5 4 8 8

Data for Problem 9-47

AUSTIN/SAN ANTONIO

DALLAS/FT. WORTH

EL PASO/WEST TEXAS

HOUSTON/ GALVESTON

CORPUS CHRISTI/RIO GRANDE VALLEY

Erica 5 3 2 3 4

Louis 3 4 4 2 2

Maria 4 5 4 3 3

Paul 2 4 3 4 3

Orlando 4 5 3 5 4

See our Internet home page, at www.pearsonhighered.com/render, for additional problems, Problems 9-49 through 9-55.

Internet Homework Problems

www.pearsonhighered.com/render

CASE STUDY 391

Case Study

Andrew–Carter, Inc.

Andrew–Carter, Inc. (A–C), is a major Canadian producer and distributor of outdoor lighting fixtures. Its fixture is distributed throughout North America and has been in high demand for several years. The company operates three plants that manufac- ture the fixture and distribute it to five distribution centers (warehouses).

During the present recession, A–C has seen a major drop in demand for its fixture as the housing market has declined. Based on the forecast of interest rates, the head of operations feels that demand for housing and thus for its product will re- main depressed for the foreseeable future. A–C is considering closing one of its plants, as it is now operating with a forecasted excess capacity of 34,000 units per week. The forecasted weekly demands for the coming year are

Warehouse 1 9,000 units

Warehouse 2 13,000 units

Warehouse 3 11,000 units

Warehouse 4 15,000 units

Warehouse 5 8,000 units

The plant capacities in units per week are

Plant 1, regular time 27,000 units

Plant 1, on overtime 7,000 units

Plant 2, regular time 20,000 units

Plant 2, on overtime 5,000 units

Plant 3, regular time 25,000 units

Plant 3, on overtime 6,000 units

If A–C shuts down any plants, its weekly costs will change, as fixed costs are lower for a nonoperating plant. Table 9.34 shows production costs at each plant, both variable at regular time and overtime, and fixed when operating and shut down. Table 9.35 shows distribution costs from each plant to each warehouse (distribution center).

Discussion Questions 1. Evaluate the various configurations of operating and

closed plants that will meet weekly demand. Determine which configuration minimizes total costs.

2. Discuss the implications of closing a plant.

Source: Professor Michael Ballot, University of the Pacific.

FIXED COST PER WEEK

PLANT VARIABLE COST OPERATING NOT OPERATING

No. 1, regular time $2.80/unit $14,000 $6,000

No. 1, overtime 3.52

No. 2, regular time 2.78 12,000 5,000

No. 2, overtime 3.48

No. 3, regular time 2.72 15,000 7,500

No. 3, overtime 3.42

TABLE 9.34 Andrew–Carter, Inc., Variable Costs and Fixed Production Costs per Week

TO DISTRIBUTION CENTER

FROM PLANT W1 W2 W3 W4 W5

No. 1 $0.50 $0.44 $0.49 $0.46 $0.56

No. 2 0.40 0.52 0.50 0.56 0.57

No. 3 0.56 0.53 0.51 0.54 0.35

TABLE 9.35 Andrew–Carter, Inc., Distribution Costs per Unit

392 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

Case Study

Old Oregon Wood Store

In 1992, George Brown started the Old Oregon Wood Store to manufacture Old Oregon tables. Each table is carefully con- structed by hand using the highest-quality oak. Old Oregon tables can support more than 500 pounds, and since the start of the Old Oregon Wood Store, not one table has been returned because of faulty workmanship or structural problems. In addi- tion to being rugged, each table is beautifully finished using a urethane varnish that George developed over 20 years of work- ing with wood-finishing materials.

The manufacturing process consists of four steps: prepara- tion, assembly, finishing, and packaging. Each step is per- formed by one person. In addition to overseeing the entire operation, George does all of the finishing. Tom Surowski per- forms the preparation step, which involves cutting and forming the basic components of the tables. Leon Davis is in charge of the assembly, and Cathy Stark performs the packaging.

Although each person is responsible for only one step in the manufacturing process, everyone can perform any one of the steps. It is George’s policy that occasionally everyone should complete several tables on his or her own without any help or assistance. A small competition is used to see who can complete an entire table in the least amount of time. George maintains average total and intermediate completion times. The data are shown in Figure 9.5.

It takes Cathy longer than the other employees to construct an Old Oregon table. In addition to being slower than the other employees, Cathy is also unhappy about her current responsi- bility of packaging, which leaves her idle most of the day. Her first preference is finishing, and her second preference is preparation.

In addition to quality, George is concerned with costs and efficiency. When one of the employees misses a day, it causes major scheduling problems. In some cases, George assigns an- other employee overtime to complete the necessary work. At other times, George simply waits until the employee returns to work to complete his or her step in the manufacturing process. Both solutions cause problems. Overtime is expensive, and waiting causes delays and sometimes stops the entire manufac- turing process.

To overcome some of these problems, Randy Lane was hired. Randy’s major duties are to perform miscellaneous jobs and to help out if one of the employees is absent. George has given Randy training in all phases of the manufacturing process, and he is pleased with the speed at which Randy has been able to learn how to completely assemble Old Oregon tables. Total and intermediate completion times are given in Figure 9.6.

Preparation Assembly Finishing Packaging

100 160 250 275

(Tom)

Preparation Assembly Finishing Packaging

80 160 220 230

(George)

Preparation Assembly Finishing Packaging

110 200 290

(Leon)

Preparation Assembly Finishing Packaging

120 190 290 315

(Cathy)

FIGURE 9.5 Manufacturing Time in Minutes

Preparation Assembly Finishing Packaging

110 190 290 300 FIGURE 9.6 Randy’s Completion Times in Minutes

APPENDIX 9.1: USING QM FOR WINDOWS 393

Discussion Questions 1. What is the fastest way to manufacture Old Oregon tables

using the original crew? How many could be made per day? 2. Would production rates and quantities change signifi-

cantly if George would allow Randy to perform one of the four functions and make one of the original crew the backup person?

3. What is the fastest time to manufacture a table with the original crew if Cathy is moved to either preparation or finishing?

4. Whoever performs the packaging function is severely un- derutilized. Can you find a better way of utilizing the four- or five-person crew than either giving each a single job or allowing each to manufacture an entire table? How many tables could be manufactured per day with this scheme?

See our Internet home page, at www.pearsonhighered.com/render, for these additional case studies:

(1) Northwest General Hospital: This case involves improving the food distribution system in a hospital to reduce the chances of food getting cold before it is delivered to the patients.

(2) Custom Vans, Inc: This case involves finding the best location for a plant that will manu- facture showers used in customized vans.

Internet Case Studies

Bibliography

Adlakha, V., and K. Kowalski. “Simple Algorithm for the Source-Induced Fixed-Charge Transportation Problem,” Journal of the Operational Research Society 55, 12 (2004): 1275–1280.

Awad, Rania M., and John W. Chinneck. “Proctor Assignment at Carleton University,” Interfaces 28, 2 (March–April 1998): 58–71.

Bowman, E. “Production Scheduling by the Transportation Method of Linear Programming,” Operations Research 4 (1956).

Dawid, Herbert, Johannes Konig, and Christine Strauss. “An Enhanced Ros- tering Model for Airline Crews,” Computers and Operations Research 28, 7 (June 2001): 671–688.

Domich, P. D., K. L. Hoffman, R. H. F. Jackson, and M. A. McClain. “Locat- ing Tax Facilities: A Graphics-Based Microcomputer Optimization Model,” Management Science 37 (August 1991): 960–979.

Hezarkhani, Behzad, and Wieslaw Kubiak. “A Coordinating Contract for Transshipment In a Two-Company Supply Chain,” European Journal of Operational Research 207, 1 (2010): 232–237.

Koksalan, Murat, and Haldun Sural. “Efes Beverage Group Makes Location and Distribution Decisions for Its Malt Plants,” Interfaces 29, 2 (March–April, 1999): 89–103.

Liu, Shiang-Tai. “The Total Cost Bounds of the Transportation Problem with Varying Demand and Supply,” Omega 31, 4 (2003): 247–251.

Martello, Silvano. “Jeno Egervary: From the Origins of the Hungarian Algo- rithm to Satellite Communication,” Central European Journal of Opera- tions Research 18, 1 (2010): 47–58.

McKeown, P., and B. Workman. “A Study in Using Linear Programming to Assign Students to Schools,” Interfaces 6, 4 (August 1976).

Pooley, J. “Integrated Production and Distribution Facility Planning at Ault Foods,” Interfaces 24, 4 (July–August 1994): 113–121.

Render, B., and R. M. Stair. Introduction to Management Science. Boston: Allyn & Bacon, Inc., 1992.

Appendix 9.1: Using QM for Windows

QM for Windows has both a transportation module and an as- signment module in its menu. Both are easy to use in terms of data entry and easy to interpret in terms of output. Program 9.6A shows the input screen for the Executive Furniture transportation example. The starting solution technique may be specified. The

results are shown in Figure 9.6B. By clicking Window, you have the option of seeing the iterations that are performed to reach the final solution. Program 9.7A provides the input screen for the Fix-It Shop assignment example. Simply enter the costs and then click Solve. Program 9.7B gives the solution to this.

www.pearsonhighered.com/render

394 CHAPTER 9 • TRANSPORTATION AND ASSIGNMENT MODELS

PROGRAM 9.6A QM for Windows Input for Executive Furniture Transportation Example

PROGRAM 9.6B QM for Windows Solution for Executive Furniture Transportation Example

PROGRAM 9.7A QM for Windows Input for the Fix-It Shop Assignment Example

PROGRAM 9.7B QM for Windows Solution for the Fix-It Shop Assignment Example

CHAPTER 9 Transportation and Assignment Models

9.1 Introduction
9.2 The Transportation Problem

Linear Program for the Transportation Example
A General LP Model for Transportation Problems

9.3 The Assignment Problem

Linear Program for Assignment Example

9.4 The Transshipment Problem

Linear Program for Transshipment Example

9.5 The Transportation Algorithm

Developing an Initial Solution: Northwest Corner Rule
Stepping-Stone Method: Finding a Least-Cost Solution

9.6 Special Situations with the Transportation Algorithm

Unbalanced Transportation Problems
Degeneracy in Transportation Problems
More Than One Optimal Solution
Maximization Transportation Problems
Unacceptable or Prohibited Routes
Other Transportation Methods

9.7 Facility Location Analysis

Locating a New Factory for Hardgrave Machine Company

9.8 The Assignment Algorithm

The Hungarian Method (Flood’s Technique)
Making the Final Assignment

9.9 Special Situations with the Assignment Algorithm

Unbalanced Assignment Problems
Maximization Assignment Problems

Summary
Glossary
Solved Problems
Self-Test
Discussion Questions and Problems
Case Study: Andrew–Carter, Inc.
Case Study: Old Oregon Wood Store
Bibliography
Appendix 9.1 Using QM for Windows