Transportation, Assignment and Transshipment problems

1 Chapter 7 Transportation, Assignment & Transshipment ProblemsPart 2 Prof. Dr. Arslan M. Assignment ProblemsSpecial type of LP, in fact a special type of Transportation (workers, processors, machines, vehicles, plants, time slots) are being assigned to tasks(jobs, classrooms, people).Example: Machineco has four jobs to be completed. Each machine must be assigned to complete one job. The time required to setup each machine for completingeach job is given. Machineco wants to minimize the total setup time needed to complete the four jobs.(Also called the cost matrix)The ModelAssignment problem : A balanced transportation problem where all supplies and demands are equal to the supplies and demands for the Machineco problem (and for any assignmentproblem) are integers, so all variables in Machineco soptimal solution must be integers.

2 Solve with Transportation simplex is often inefficient. For this reason The Hungarian Methodis used for solving Assignment problems . Assignment ProblemsThe steps of The Hungarian a bfs. Find the minimum element in each row of the mxmcost matrix. Construct a new matrix by subtracting from each cost the minimum cost in its row. For this new matrix, find the minimum cost in each column. Construct a new matrix (reduced cost matrix) by subtracting from each cost the minimum cost in its the minimum number of lines (horizontal and/or vertical) that are needed to cover all zeros in the reduced cost matrix. If m lines are required, an optimal solution is available among the covered zeros in the fewer than m lines are required, proceed to step the smallest nonzero element (call its value k) in the reduced cost matrix that is uncovered by the lines drawn in step 2.

3 Now subtract kfrom each uncovered element of the reduced cost matrix and add kto each element that is covered by two lines. Return to Solution with Hungarian MethodMachineco Solution (cont.)Machineco Solution (cont.)Machineco Solution (cont.)The smallest uncovered element equals 1, so we now subtract 1 from each uncoveredelement in the reduced cost matrix and add 1 to each twice-covered Solution (cont.)To find an optimal Assignment , observe that the only covered 0 incolumn 3 is x33, so we must have x33=1. Also, the only available covered zero in column2 is x12, so we set x12= the only available covered zero in column 4 is x24. Thus, we choose x24=1.

4 Finally, we choose x41= Model ExampleProblem Definition and DataProblem: Assign four teams of officials to four games in a way that will minimize total distance traveled by the officials. Supply is always one team of officials, demand is for only one team of officials at each 1 if i is assigned to j, 0 otherwise. i= A, B, C, D, j=R, A, C, DMinimize Z =210xAR+ 90xAA+ 180xAD+ 160xAC+ 100xBR+70xBA+ 130xBD+ 200xBC + 175xCR+ 105xCA+140xCD+ 170xCC+ 80xDR+ 65xDA+ 105xDD+ 120xDCsubject to: xAR+ xAA+ xAD+ xAC= 1xij 0xBR+ xBA+ xBD+ xBC= 1xCR+ xCA+ xCD+ xCC= 1xDR+ xDA+ xDD+ xDC= 1xAR+ xBR+ xCR+ xDR= 1xAA+ xBA+ xCA+ xDA= 1xAD+ xBD+ xCD+ xDD= 1xAC+ xBC+ xCC+ xDC= 1 Assignment Model ExampleModel Formulation14 Assignment Model ExampleAssignment Network Solution15 Assignment ModelThe Hungarian Method Develop the reduced cost the minimum value in each row from every row element in the.

5 Subtract the minimum value in each column from every column element in the can be made in the matrix where a 0 is ModelThe Hungarian Method 17 Draw the minimum number of horizontal or vertical lines necessary to cross out all zeros throughthe rows and columns of the reduced cost ModelThe Hungarian Method The three lines indicate that there are only three unique assignments, whereas four arerequired for an optimal solution. 18 Next, subtract the minimum value that is not crossed out from all values not crossed out. Add this minimumvalue to those cells where two lines ModelThe Hungarian Method 19No matter how the lines are drawnnow, at least four are required to cross outall the zeros.

6 This indicates that four unique assignments can be made and that an optimalsolution has been reached: Team A Atlanta, Team B Raleigh, Team C Durham, Team D Clemsonwith 450 miles total distance. ORTeam A Clemson, Team B Atlanta, Team C Durham, Team D Raleigh with 450 miles total ModelThe Hungarian Method 20An Assignment problem is unbalancedwhen supply exceeds demand or demand exceeds example, assume that, instead of fourteams of officials, there are five teams to be assigned to the four games. In this casea dummy column is added to the Assignment tableau to balance the ModelThe Hungarian Method 21 In solving this model, one team of officials would be assigned to the dummy column.

7 Ifthere were five games and only four teams of officials, a dummy row would be addedinstead of a dummy column. The addition of a dummy row or column does not affect thesolution ModelThe Hungarian Method 22 Prohibited assignments are possible in an Assignment problem . In the Assignment model, a Big Mvalue isassigned as a large cost for the cell representing the prohibited Assignment . MAssignment ModelThe Hungarian Method Transshipment ProblemsA transportation problem allows only shipments that go directly from supply points to demand many situations, shipments are allowed between supply points or between demand points. Sometimes there may also be points (called Transshipment points) through which goods can be transshipped on their journey from a supply point to a demand point.

8 The optimal solution to a Transshipment problem can be found by solving a transportation Transshipment ProblemsDefine a supply point to be a point that can send goods to anotherpoint but cannot receive goods from any other point. Similarly, a demand point is a pointthat can receive goods from other points but cannot send goods to any other point. Atransshipment point is a point that can both receive goods from other points and sendgoods to other points. Transshipment ProblemsExample: factoriesinMemphis and Denver, with supplies 150 per day, and 200 per day. Customers inLos Angeles and Boston, with a demand 130 per believes that it may be cheaper to first ship somewidgets to New York or Chicago and then ship them to their final destinations.

9 The costsof shipping a widget are given. Widgetco wants to minimize the total cost ofshipping the required widgets to its Transshipment Transshipment ProblemsFollow these steps in solving a Transshipment necessary, add a dummy demand point (demand equal to the problem s excess supply) to balance the problem . Shipments to the dummy and from a point to itself will cost zero. Step2. Construct a transportation tableau as follows: A row in the tableau will be needed for each supply point and Transshipment point, and a column will be needed for each demand point and Transshipment Transshipment ProblemsEach supply point will have a supply equal to it s original supply, and each demand point will have a demand to its original demand.

10 Let s= total available supply. Then each Transshipment point will have a supply equal to (point s original supply)+s and a demand equal to (point s original demand)+s. Although we don t know how much will be shipped through each Transshipment point, we can be sure that the total amount will not exceed Transshipment Transshipment ProblemsExample: factoriesinMemphis and Denver, with supplies 150 per day, and 200 per day. Customers inLos Angeles and Boston, with a demand 130 per believes that it may be cheaper to first ship somewidgets to New York or Chicago and then ship them to their final destinations. The costsof shipping a widget are given.