Transportation and Assignment Problems

1 1L. Ntaimo (c) 2005 INEN420 TAMUT ransportation and Assignment Problems Based onChapter 7 introduction to Mathematical Programming: operations research , Volume 14th edition, by Wayne L. Winston and Munirpallam VenkataramananLewis Ntaimo2L. Ntaimo (c) 2005 INEN420 a Transportation a basic feasible Transportation simplex algorithm3L. Ntaimo (c) 2005 INEN420 Powerco ProblemPowerco has 3 electric power plants that supply the needs of 4 cities. Each power plant can supply the following numbers of kilowatt-hours (kwh) of electricity: plant 1 35 million; plant 2 50 million; plant 3 40 million (see Table 1). The peak power demands in these cities, which occur at the same time (2pm), are as follows (in kwh): city 1 45 million; city 2 20 million; city 3 30 million; city 4 -30 million. The costs of sending 1 million kwh of electricity from plant to city depend on the distance the electricity must travel.

2 Formulate an LP to minimize the cost of meeting each city s peak power demand. Table 1: Shipping Costs, Supply, and Demand for PowercoToSupplyFromCity 1 City 2 City 3 City 4(million kwh)Plant 1$8 $6 $10 $9 $35 Plant 2$9 $12 $13 $7 $50 Plant 3$14 $9 $16 $5 $40 Demand45 20 30 30 (million kwh)4L. Ntaimo (c) 2005 INEN420 Graphical RepresentationDemand PointsPlant 1 Plant 3 City 1 City 2 City 3 City 4 Supply Pointsd1= 45 Plant 2xijs1= 35d2= 20s2= 50d3= 30s3= 40d4= 30 Decision Variables:xij# of (million) kwh produced at plant iand sent to city jConstraints: Supply (Capacity) constraintsDemand constraints5L. Ntaimo (c) 2005 INEN420 Powerco problem Formulation)4,3,2,1;3,2,1( 0 30 30 20 45 40 50 35 713129 9106 8 Min 3424143323133222121321113433323124232221 14131211343332312423222114131211== ++ ++ ++ ++ +++ +++ ++++++++++++++jixxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxijSupply ConstraintsDemand ConstraintsMinimize total shipping costs0.

3 Toequal ablesother vari ,30,10,5,45,10,10,1020 :solution Optimal343223211312allxxxxxxz=======6L. Ntaimo (c) 2005 INEN420 Graphical RepresentationDemand PointsPlant 1 Plant 3 City 1 City 2 City 3 City 4 Supply Pointsd1= 45 Plant 2x21= 45x12= 10x34= 30x13=25x23= 5x32= 10s1= 35d2= 20s2= 50d3= 30s3= 40d4= 307L. Ntaimo (c) 2005 INEN420 General Formulation of a Transportation problem ),..,2,1;,..,2,1( 0 s)constraint (demand ),..,2,1( s)constraint(supply ),..,2,1( 1111njmixnjdxmisxxcijjniijinjijminjijij= = = = ====8L. Ntaimo (c) 2005 INEN420 A Balanced Transportation problem ===njjmiids11In a balanced Transportation problem , the total supply is equal to the total demand: All constraints must be binding It becomes relatively easy to find a basic feasible solution Simplex pivots do not involve multiplication, they reduce to additions and subtractions Therefore, it is desirable to formulate a Transportation problemas a balanced Transportation problem9L.

4 Ntaimo (c) 2005 INEN420 A Balanced Transportation problem ),..,2,1;,..,2,1( 0 s)constraint (demand ),..,2,1( s)constraint(supply ),..,2,1( 1111njmixnjdxmisxxcijjniijinjijminjijij= = ==== ====10L. Ntaimo (c) 2005 INEN420 Balancing a Transportation problem if Total Supply Exceeds Total DemandCreate a dummy demand point that has demand equal to the amount of excess supplyShipments to the dummy demand point:(1)Are assigned a cost of zero because they are not real shipments(2)Indicate unused supply capacity11L. Ntaimo (c) 2005 INEN420 TAMUD emand Balancing a Transportation problem if Total Supply Exceeds Total DemandPlant 1 Plant 3 City 1 City 2 City 3 City 4 Supply Pointsd1= 35 Plant 2xijDummy5s1= 35d2= 2011541= =jjd12531= =iiss2= 50d3= 30s3= 40d4= 30d5 = 10c15= c25=c35= 012L.

5 Ntaimo (c) 2005 INEN420 Balancing a Transportation problem if Total Supply is Less than Total DemandIn this case the problem has no feasible solution: demand cannotbe satisfiedHowever, it is sometimes desirable to allow the possibility of leaving some demand unmet:(1)A penalty (cost) is often associated with the unmet demand(2)To balance the problem , add a dummy (or shortage) supply point 13L. Ntaimo (c) 2005 INEN420 Transportation TableauA Transportation problem is specified by supply, the demand, and the shipping costs, so the relevant data can be summarized in a Transportation tableau :j ..i1s12s2 Cell: (row i, col j)smmd2dnd114L. Ntaimo (c) 2005 INEN420 Powerco Transportation Tableau If xijis a bv, its value is placed in the lower left-hand corner of the ijthcell86910103525912137504551491654010 304520303015L. Ntaimo (c) 2005 INEN420 Finding BFS s for Transportation ProblemsConsider a Transportation with msupply points and ndemand points-Such a problem contains m + nequality constraints-Recall:In the Big Mmethod and Two-phasesimplex method it is difficult to find a bfs if all of the LP s constraints are equalities-Fortunately, the structure of the Transportation Problems makesit easy to find a bfsImportant ObservationIf a set of values for the xij s satisfies all but one of the constraints of a balanced Transportation problem , then the values for the xij s will automatically satisfy the other Ntaimo (c) 2005 INEN420 Powerco problem Formulation)4,3,2,1.

6 3,2,1( 0 30 30 20 45 40 50 35 713129 9106 8 Min 3424143323133222123121113433323124232221 14131211343332312423222114131211== =++=++=++=++=+++=+++=++++++++++++++jixxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxijSupp ly ConstraintsDemand ConstraintsMinimize total shipping costsOmit this constraint0. toequal ablesother vari ,30,10,5,45,10,10,1020 :solution Optimal343223211312allxxxxxxz=======17L. Ntaimo (c) 2005 INEN420 Powerco ExampleRecall:s1= 35, s2= 50, s3= 40,d1= 45, d2= 20, d3= 30, d4= 30 Let a set of xij s satisfy all constraints except the first supply this set of xij s must supply d1+ d2+ d3+ d4= 125 million kwh to cities 1 to 4 and supply s2+ s3= 125 s1= 90 million kwh from plants 2 and plant 1 must supply 125 (125 s1) = 35 million kwh, So the xij s must satisfy the first supply constraint!)

7 Therefore, we arbitrarily assume that the first constraint is omittedfrom Ntaimo (c) 2005 INEN420 LoopDefinition: An ordered sequence of at least 4 different cells is called a 2 consecutive cells lie in either the same row or same 3 consecutive cells lie in the same row or last cell in the sequence has a row or column in common withthe first cell in the sequencePath:(1,1)-(1,2)-(2,3)-(2,1)Loop or Path?Loop:(2,1)-(2,4)-(4,4)-(4,1)Loop:(1 ,1)-(1,2)-(2,2)-(2,3)-(4,3)-(4,5)-(3,5)- (3,1)Path:(1,1)-(1,2)-(1,3)-(2,3)-(2,1)1 9L. Ntaimo (c) 2005 INEN420 TheoremIn a balanced Transportation problem with msupply points and ndemand points, the cells corresponding to a set of (m+ n 1) variables contain no loop iff the (m+ n 1) variables yield a basic solutionThis follows from the fact that a set of (m + n 1)cells contains no loop iff the (m + n 1)columns corresponding to these cells are linearly : Loop:(1,1)-(1,2)-(2,2)-(2,1)45324 Because (1,1)-(1,2)-(2,2)-(2,1) is a loop, the Theorem tells us that {x11, x12, x22, x21} cannotyield a bfs for this Transportation Ntaimo (c) 2005 INEN420 The Northwest Corner Method for Finding a BFS for a Balanced Transportation problem Begin in the upper left (or northwest) corner of the Transportation tableau Set x11as large as possible.

8 Clearly x11= min{s1, d1}. If x11= s1, cross out row 1 of the Transportation tableau; no more bv s will come from row 1. Also set d1= d1-s1. If x11= d1, cross out the column 1 of the Transportation tableau; no more bv s will come from column 1. Also set s1= s1-d1. If x11= s1 = d1, cross out eitherrow 1 or column 1 (but NOTboth). If you cross out row 1, set d1= 0. If you cross out column 1, set s1= 0. Continue applying this procedure to the most northwest corner cell in the tableau that does not lie in a crossed-out row or column. Eventually, will come to a point where there is only one cell that can be assigned a value. Assign this cell a value equal to its row or column demand, andcross out both the cell s row and column. A BFS has now been Ntaimo (c) 2005 INEN420 Powerco Example: Finding a BFS8691035 -3535912137501491654045-3520303086910x35 50912137401491651020303022L.

9 Ntaimo (c) 2005 INEN420 Powerco Example: Finding a BFS86910X359121371050-101491654010-10203 03086910x35912137401014916540X20303023L. Ntaimo (c) 2005 INEN420 Powerco Example: Finding a BFS86910X359121371040-202014916540X320-2 030086910x3591213720102014916540X3X30024 L. Ntaimo (c) 2005 INEN420 Powerco Example: Finding a BFS86910X3591213710202020-2014916540X3X3 0-20086910x35912137X10202014916540X3X100 25L. Ntaimo (c) 2005 INEN420 TAMUP owerco Example: Finding a BFS86910X35912137X1020201491651040-10X3X 10-10086910x35912137X1020201491653010X3X X026L. Ntaimo (c) 2005 INEN420 Powerco Example: Finding a BFS86910X35912137X10202014916530-301030X 3XX0-308691035X912137X102020149165X1030 XXXX27L. Ntaimo (c) 2005 INEN420 Powerco Example: Basic Feasible Solution86910353591213710502020149165103 04045203030 BFS:x11 = 35x22= 10x22= 20x23 = 20x33 = 10x34 = 30 NOTE: The BFS does NOT form a LOOP28L.

10 Ntaimo (c) 2005 INEN420 The Transportation Simplex MethodPricing Out Nonbasic VariablesRecall:.variablesbasic ofset dropped)been has constraintsupply first that the(assuming LP, original in the for column ,for t coefficien objective where,, by given is cost) (reduced 0 Row s tableau'in the variable theoft coefficien The1=== = are variablesnonbasic theallfor s' theif optimal be willbfscurrent theproblem, ONMINIMIZATI a solving are weSinceijc. POSITIVE most with the variablenonbasic thebasis theinto ENTER weOtherwise,ijc29L. Ntaimo (c) 2005 INEN420 The Transportation Simplex Method demand the toingcorrespond of elements theare ,..,, s;constraintsupply 1 the toingcorrespond of elements theare ,.. , where ,].