DrHanyAbdelhakeem-transportation PDF

## Chapter 19: Solution Procedures for Transportation and Assignment Problems ### Contents - **19.1 Transportation Simplex Method: A Special-Purpose Solution Procedure** - Phase I: Finding an Initial Feasible Solution - Phase II: Iterating to the Optimal Solution - Summary of the Transportat...

## Chapter 19: Solution Procedures for Transportation and Assignment Problems ### Contents - **19.1 Transportation Simplex Method: A Special-Purpose Solution Procedure** - Phase I: Finding an Initial Feasible Solution - Phase II: Iterating to the Optimal Solution - Summary of the Transportation Simplex Method - Problem Variations - **19.2 Assignment Problem: A Special-Purpose Solution Procedure** - Finding the Minimum Number of Lines - Problem Variations ### 19.1 Transportation Simplex Method: A Special-Purpose Solution Procedure Solving transportation problems with a general-purpose linear programming code is fine for small to medium-sized problems. However, these problems often grow very large (a problem with 100 origins and 1000 destinations would have 100,000 variables), and more efficient solution procedures may be needed. The network structure of the transportation problem has enabled management scientists to develop special-purpose solution procedures that greatly simplify the computations. In Section 6.1 we introduced the Foster Generators transportation problem and showed how to formulate and solve it as a linear program. The linear programming formulation involved 12 variables and 7 constraints. In this section we describe a special-purpose solution procedure, called the transportation simplex method that takes advantage of the network structure of the transportation problem and makes possible the solution of large transportation problems efficiently on a computer and small transportation problems by hand. The transportation simplex method, like the simplex method for linear programs, is a two-phase procedure; It involves first finding an initial feasible solution and then proceeding iteratively to make improvements in the solution until an optimal solution is reached. To summarize the data conveniently and to keep track of the calculations, we utilize a transportation tableau. The transportation tableau for the Foster Generators problem is presented in Table 19.1. Note that the 12 cells in the tableau correspond to the 12 routes from one origin to one destination. Thus, each cell in the transportation tableau corresponds to a variable in the linear programming formulation. The entries in the right-hand margin of the tableau indicate the supply at each origin, and the entries in the bottom margin indicate the demand at each destination. Each row corresponds to a supply node, and each column corresponds to a demand node in the network model of the problem. The number of rows plus the number of columns equals the number of constraints in the linear programming formulation of the problem. The entries in the upper right-hand corner of each cell show the transportation cost per unit shipped over the corresponding route. Note also that for the Foster Generators problem total supply equals total demand. The transportation simplex method can be applied only to a balanced problem (total supply = total demand); If a problem is not balanced, a dummy origin or dummy destination must be added. The use of dummy origins and destinations will be discussed later in this section. #### Phase I: Finding an Initial Feasible Solution The first phase of the transportation simplex method involves finding an initial feasible solution. Such a solution provides arc flows that satisfy each demand constraint without shipping more from any origin node than the supply available. The procedures most often used to find an initial feasible solution to a transportation problem are called heuristics. A heuristic is a commonsense procedure for quickly finding a solution to a problem. Several heuristics have been developed to find an initial feasible solution to a transportation problem. Although some heuristics can find an initial feasible solution quickly, often the solution they find is not especially good in terms of minimizing total cost. Other heuristics may not find an initial feasible solution as quickly, but the solution they find is often good in terms of minimizing total cost. The heuristic we describe for finding an initial feasible solution to a transportation problem is called the minimum cost method. This heuristic strikes a compromise between finding a feasible solution quickly and finding a feasible solution that is close to the optimal solution. #### Phase II: Iterating to the Optimal Solution Phase II of the transportation simplex method is a procedure for iterating from the initial feasible solution identified in phase I to the optimal solution. Recall that each cell in the transportation tableau corresponds to an arc (route) in the network model of the transportation problem. The first step at each iteration of phase II is to identify an incoming arc. The incoming arc is the currently unused route (unoccupied cell) where making a flow allocation will cause the largest per-unit reduction in total cost. Flow is then assigned to the incoming arc, and the amounts being shipped over all other arcs to which flow had previously been assigned (occupied cells) are adjusted as necessary to maintain a feasible solution. In the process of adjusting the flow assigned to the occupied cells, we identify and drop an outgoing arc from the solution. Thus, at each iteration in phase II, we bring a currently unused arc (unoccupied cell) into the solution, and remove an arc to which flow had previously been assigned (occupied cell) from the solution. #### Summary of the Minimum Cost Method Before applying Phase II of the transportation simplex method, let us summarize the steps for obtaining an initial feasible solution using the minimum cost method. 1. Identify the cell in the transportation tableau with the lowest cost, and allocate as much flow as possible to this cell. In case of a tie, choose the cell corresponding to the arc over which the most units can be shipped. If ties still exist, choose any of the tied cells. 2. Reduce the row supply and the column demand by the amount of flow allocated to the cell identified in step 1. 3. If all row supplies and column demands have been exhausted, then stop; The allocations made will provide an initial feasible solution. Otherwise, continue with step 4. 4. If the row supply is now zero, eliminate the row from further consideration by drawing a line through it. If the column demand is now zero, eliminate the column by drawing a line through it. 5. Continue with step 1 for all unlined rows and columns. #### Problem Variations The following problem variations can be handled, with slight adaptations, by the transportation simplex method: 1. Total supply not equal to total demand 2. Maximization objective function 3. Unacceptable routes ### 19.2 Assignment Problem: A Special-Purpose Solution Procedure As mentioned previously, the assignment problem is a special case of the transportation problem. Thus, the transportation simplex method can be used to solve the assignment problem. However, the assignment problem has an even more special structure: All supplies and demands equal 1. Because of this additional special structure, special-purpose solution procedures have been specifically designed to solve the assignment problem; one such procedure is called the Hungarian method. In this section we will show how the Hungarian method can be used to solve the Fowle Marketing Research problem. #### Finding the Minimum Number of Lines Sometimes it is not obvious how the lines should be drawn through rows and columns of the matrix in order to cover all the zeros with the smallest number of lines. In these cases, the following heuristic works well. Choose any row or column with a single zero. If it is a row, draw a line through the column the zero is in; If it is a column, draw a line through the row the zero is in. Continue in this fashion until you cover all the zeros. If you make the mistake of drawing too many lines to cover the zeros in the reduced matrix and thus conclude incorrectly that you have reached an optimal solution, you will be unable to identify a zero-value assignment. Thus, if you think you have reached the optimal solution, but cannot find a set of zero-value assignments, go back to the preceding step and check to see whether you can cover all the zeros with fewer lines. #### Problem Variations We now discuss how to handle the following problem variations with the Hungarian method: 1. Number of agents not equal to number of tasks 2. Maximization objective function 3. Unacceptable assignments #### Notes and Comments - Research devoted to developing efficient special-purpose solution procedures for network problems has shown that the transportation simplex method is one of the best. It is used in the transportation and assignment modules of The Management Scientist software package. A simple extension of this method also can be used to solve transshipment problems. - As we previously noted, each cell in the transportation tableau corresponds to an arc (route) in the network model of the problem and a variable in the linear programming formulation. Phase II of the transportation simplex method is thus the same as phase II of the simplex method for linear programming. At each iteration, one variable is brought into solution and another variable is dropped from solution. The reason the method works so much better for transportation problems is that the special mathematical structure of the constraint equations means that only addition and subtraction operations are necessary. We can implement the entire procedure in a transportation tableau that has one row for each origin and one column for each destination. A simplex tableau for such a problem would require a row for each origin, a row for each destination, and a column for each arc; thus, the simplex tableau would be much larger. ### Problems 1. Consider the following transportation tableau with four origins and four destinations. | Origin | D₁ | D₂ | D₃ | D₄ | Supply | |---|---|---|---|---|---| | O₁ | 5 | 7 | 10 | 5 | 75 | | O₂ | 25 | 50 | 6 | 5 | 75 | | O₃ | 6 | 6 | 12 | 7 | 100 | | O₄ | 100 | 100 | 75 | 175 | | O₄ | 6 | 6 | 12 | 7 | 100 | | O₄ | 8 | 5 | 14 | 4 | 100 | | Demand | 125 | 100 | 150 | 125 | 150 | a. Use the MODI method to determine whether this solution provides the minimum transportation cost. If it is not the minimum cost solution, find that solution. If it is the minimum cost solution, what is the total transportation cost? b. Does an alternative optimal solution exit? Explain. If so, find the alternative optimal solution. What is the total transportation cost associated with this solution? 2. Consider the following minimum cost transportation problem. | Origin | Los Angeles | San Francisco | San Diego | Supply | |---|---|---|---|---| | San Jose | 4 | 10 | 6 | 100 | | Las Vegas | 8 | 16 | 6 | 300 | | Tucson | 14 | 18 | 10 | 300 | | Demand | 200 | 300 | 200 | 700 | a. Use the minimum cost method to find an initial feasible solution. b. Use the transportation simplex method to find an optimal solution. c. How would the optimal solution change if you must ship 100 units on the Tucson-San Diego route? d. Because of road construction, the Las Vegas-San Diego route is now unacceptable. Re-solve the initial problem. 3. Consider the following network representation of a transportation problem. The supplies, demands, and transportation costs per unit are shown on the network: <img src="" alt="Network for Transportation Problem"> a. Set up the transportation tableau for the problem. b. Use the minimum cost method to find an initial feasible solution. 4. A product is produced at three plants and shipped to three warehouses. The transportation costs per unit are shown in the following table. | Plant | W₁ | W₂ | W₃ | Plant Capacity | |---|---|---|---|---| | P₁ | 20 | 16 | 24 | 300 | | P₂ | 10 | 10 | 8 | 500 | | P₃ | 12 | 18 | 10 | 100 | | Warehouse demand | 200 | 400 | 300 | Use the transportation simplex method to find an optimal solution. 5. Consider the following minimum-cost transportation problem. | Origin | D₁ | D₂ | D₃ | Supply | |---|---|---|---|---| | O₁ | 6 | 8 | 8 | 250 | | O₂ | 18 | 12 | 14 | 150 | | O₃ | 8 | 12 | 10 | 100 | | Demand | 150 | 200 | 150 | | a. Use the minimum cost method to find an initial feasible solution. b. Use the transportation simplex method to find an optimal solution. 6. Scott and Associates, Inc., is an accounting firm that has three new clients. Project leaders will be assigned to the three clients. Based on the different backgrounds and experiences of the leaders, the various leader-client assignments differ in terms of projected completion times. The possible assignments and the estimated completion times in days are: | Project Leader | Client | |---|---| | Jackson | 10 | 16 | 32 | | Ellis | 14 | 22 | 40 | | Smith | 22 | 24 | 34 | Use the Hungarian method to obtain the optimal solution. 7. CarpetPlus sells and installs floor covering for commercial buildings. Brad Sweeney, a CarpetPlus account executive, was just awarded the contract for five jobs. Brad must now assign a CarpetPlus installation crew to each of the five jobs. Because the commission Brad will earn depends on the profit CarpetPlus makes, Brad would like to determine an assignment that will minimize total installation costs. Currently, five installation crews are available for assignment. Each crew is identified by a color code, which aids in tracking of job progress on a large white board. The following table shows the costs (in hundreds of dollars) for each crew to complete each of the five jobs. | Crew | Job | |---|---| | | 1 | 2 | 3 | 4 | 5 | | Red | 30 | 44 | 38 | 47 | 31 | | White | 25 | 32 | 45 | 44 | 25 | | Blue | 23 | 40 | 37 | 39 | 29 | | Green | 26 | 38 | 37 | 45 | 28 | | Brown | 26 | 34 | 44 | 43 | 28 | Use the Hungarian method to obtain the optimal solution. 8. Fowle Marketing Research has four project leaders available for assignment to three clients. Find the assignment of project leaders to clients that will minimize the total time to complete all projects. The estimated project completion times in days are as follows: | Project Leader | Client | |---|---| | Terry | 10 | 15 | 9 | | Carle | 9 | 18 | 5 | | McClymonds | 6 | 14 | 3 | | Higley | 8 | 16 | 6 | Use the Hungarian method to obtain the optimal solution. 9. Use the Hungarian method to solve the Salisbury Discount, Inc., problem using the profit data in Table 19.23. 10. Use the Hungarian method to solve the Salisbury Discount, Inc., problem using the profit data in Table 19.26.