Transportation, Transshipment, and Assignment Problems

Chapter 6Transportation, Transshipment, and Assignment ProblemsPart 2 Deterministic Decision ModelsLearning ObjectivesDescribe the nature of transportation, transshipment, and assignment problems.Formulate a transportation problem as a linear programming model.Use the transportation method to solve problems with Excel.Solve maximization transportation problems, unbalanced problems, and problems with prohibited routes.Solve aggregate planning problems using the transportation model.After completing this chapter, you should be able to:2Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Learning Objectives (cont’d)Formulate a transshipment problem as a linear programming model.Solve transshipment problems with Excel.Formulate an assignment problem as a linear programming model.Use the assignment method to solve problems with Excel.After completing this chapter, you should be able to:3Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Transportation ProblemsTransportation ProblemA distribution-type problem in which supplies of goods that are held at various locations are to be distributed to other receiving locations.The solution of a transportation problem will indicate to a manager the quantities and costs of various routes and the resulting minimum cost.Used to compare location alternatives in deciding where to locate factories and warehouses to achieve the minimum cost distribution configuration.4Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Formulating the ModelA transportation problemTypically involves a set of sending locations, which are referred to as origins, and a set of receiving locations, which are referred to as destinations. To develop a model of a transportation problem, it is necessary to have the following information:Supply quantity (capacity) of each origin.Demand quantity of each destination.Unit transportation cost for each origin-destination route.5Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Transshipment ProblemsTransshipment ProblemsA transportation problem in which some locations are used as intermediate shipping points, thereby serving both as origins and as destinations.Involve the distribution of goods from intermediate nodes in addition to multiple sources and multiple destinations.6Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Assignment ProblemsThe Assignment-type ProblemsInvolve the matching or pairing of two sets of items such as jobs and machines, secretaries and reports, lawyers and cases, and so forth.Have different cost or time requirements for different pairings.7Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 6–1 Schematic of a Transportation Problem8Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 6–1 Transportation Table for Harley’s Sand and Gravel9Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Special Cases of Transportation ProblemsMaximizationTransportation-type problems that concern profits or revenues rather than costs with the objective to maximize profits rather than to minimize costs.Unacceptable RoutesCertain origin-destination combinations may be unacceptable due to weather factors, equipment breakdowns, labor problems, or skill requirements that either prohibit, or make undesirable, certain combinations (routes).10Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Special Cases of Transportation Problems (cont’d)Unequal Supply and DemandSituations in which supply and demand are not equal such that it is necessary to modify the original problem so that supply and demand are equalized.Quantities in dummy routes in the optimal solution are not shipped and serve to indicate which supplier will hold the excess supply, and how much, or which destination will not receive its total demand, and how much it will be short.11Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6-1 Input and Output Worksheet for the Transportation (topsoil) Problem12Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6-2 Parameter Specification Screen for the Topsoil Transportation Problem13Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–3 Solver Options Screen14Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–4 Solver Results15Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–5 Answer Report for the Topsoil Transportation Problem16Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–6 Sensitivity Report for the Topsoil Transportation Problem17Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–7 Input and Output Sheet for the Revised Transportation (topsoil) Problem When the Shipping Route between Farm B and Project 1 Is Prohibited18Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 6–2 A Network Diagram of a Transshipment Problem19Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 6-2Transshipment ProblemThe manager of Harley’s Sand and Gravel Pit has decided to utilize two intermediate nodes as transshipment points for temporary storage of topsoil. The revised diagram of the transshipment problem is given in Figure 6-3.Table 6–2 Cost of Shipping One Unit from the Farms to WarehousesTable 6–2 Cost of Shipping One Unit from the Warehouses to Projects20Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 6–3 A Network Diagram of Harley’s Sand and Gravel PitTransshipment Example21Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–8 Excel Input and Output Screen for the Transshipment Problem22Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–9 Parameter Specifications Screen for the Transshipment Problem23Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Using the Transportation Problem to Solve Aggregate Planning ProblemsAggregate PlanningInvolves creating a long-term production plan for achieving a demand-supply balance. Aggregate planners usually avoid in terms of thinking of individual products. Planners are concerned about the quantity and timing of production to meet the expected demand.Aggregate planners attempt to minimize the production cost over the planning horizon.24Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 6–4 Transportation Table for Aggregate Planning Purposes25Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 6-326Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 6–5 Transportation Table for the Aggregate Planning Problem of Example 6-327Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Using the Transportation Problem to Solve Location Planning ProblemsLocation AnalysisComparing transportation costs for alternative locations for new facilities to minimize total cost.Provides planners an opportunity to assess the impact of each warehouse location on the total distribution costs for the system.28Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 6–6 System with Chicago WarehouseTable 6–7 System with Detroit Warehouse29Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 6-4A manager has prepared a table that shows the cost of performing each of five jobs by each of five employees (see Table 6-8). According to this table, job I will cost $15 if done by Al. $20 if it is done by Bill, and so on. The manager has stated that his goal is to develop a set of job assignments that will minimize the total cost of getting all four jobs done. It is further required that the jobs be performed simultaneously, thus requiring one job being assigned to each employee. In the past, to find the minimum-cost set of assignments, the manager has resorted to listing all of the different possible assignments (i.e., complete enumeration) for small problems such as this one. But for larger problems, the manager simply guesses because there are too many possibilities to try to list them. For example, with a 5X5 table, there are 5! = 120 different possibilities; but with, say, a 7X7 table, there are 7! = 5,040 possibilities.30Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 6–8 Numerical Example for the Assignment Problem31Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–10 Excel Input and Output Worksheet for the Assignment Problem32Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–11 Parameter Specifications Screen for the Assignment Problem33Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–12 Excel Worksheet for the Transportation Problem in Solved Problem 134Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–13 Parameter Specification Screen for Solved Problem 135Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–14 Excel Worksheet for the Assignment Problem in Solved Problem 236Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–15 Parameter Specification Screen for Solved Problem 237Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–16 Excel Worksheet for the Transportation Problem in Solved Problem 338Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 6–17 Parameter Specification Screen for Solved Problem 339Copyright © 2007 The McGraw-Hill Companies. All rights reserved.