Transportation, Assignment, and Transshipment Problems

1 Transportation, Assignment, andTransshipment ProblemsIn this chapter, we discuss three special types of linear programming Problems : transporta-tion, assignment, and Transshipment . Each of these can be solved by the simplex algorithm,but specialized algorithms for each type of problem are much more 1 Formulating Transportation ProblemsWe begin our discussion of transportation Problems by formulating a linear programmingmodel of the following has three electric power plants that supply the needs of four cities. Each powerplant 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 de-mands in these cities, which occur at the same time (2 ), are as follows (in kwh): city1 45 million; city 2 20 million; city 3 30 million; city 4 30 million.

2 The costs ofsending 1 million kwh of electricity from plant to city depend on the distance the elec-tricity must travel. Formulate an LP to minimize the cost of meeting each city s peakpower formulate Powerco s problem as an LP, we begin by defining a variable for each deci-sion that Powerco must make. Because Powerco must determine how much power is sentfrom each plant to each city, we define (for i 1, 2, 3 and j 1, 2, 3, 4)xij number of (million) kwh produced at plant iand sent to city jIn terms of these variables, the total cost of supplying the peak power demands to cities1 4 may be written as 8x11 6x12 10x13 9x14(Cost of shipping power from plant 1) 9x21 12x22 13x23 7x24(Cost of shipping power from plant 2) 14x31 9x32 16x33 5x34(Cost of shipping power from plant 3)Powerco faces two types of constraints.

3 First, the total power supplied by each plantcannot exceed the plant s capacity. For example, the total amount of power sent from plantPowerco FormulationEXAMPLE 1 This example is based on Aarvik and Randolph (1975).7. 1 Formulating Transportation Problems3611 to the four cities cannot exceed 35 million kwh. Each variable with first subscript 1 rep-resents a shipment of power from plant 1, so we may express this restriction by the LPconstraintx11 x12 x13 x14 35In a similar fashion, we can find constraints that reflect plant 2 s and plant 3 s power is supplied by the power plants, each is a supply , aconstraint that ensures that the total quantity shipped from a plant does not exceed plantcapacity is a supply LP formulation of Powerco s problem contains thefollowing three supply constraints.

4 X11 x12 x13 x14 35(Plant 1 supply constraint)x21 x22 x23 x24 50(Plant 2 supply constraint)x31 x32 x33 x34 40(Plant 3 supply constraint)Second, we need constraints that ensure that each city will receive sufficient power tomeet its peak demand. Each city demands power, so each is a demand exam-ple, city 1 must receive at least 45 million kwh. Each variable with second subscript 1represents a shipment of power to city 1, so we obtain the following constraint:x11 x21 x31 45 Similarly, we obtain a constraint for each of cities 2, 3, and 4. A constraint that ensuresthat a location receives its demand is a demand must satisfy the fol-lowing four demand constraints:x11 x21 x31 45(City 1 demand constraint)x12 x22 x32 20(City 2 demand constraint)x13 x23 x33 30(City 3 demand constraint)x14 x24 x34 30(City 4 demand constraint)Because all the xij s must be nonnegative, we add the sign restrictions xij 0 (i 1, 2,3; j 1, 2, 3, 4).

5 Combining the objective function, supply constraints, demand constraints, and sign re-strictions yields the following LP formulation of Powerco s problem:min z 8x11 6x12 10x13 9x14 9x21 12x22 13x23 7x24 14x31 9x32 16x33 x12 x13 x14 35(Supply constraints) x22 x23 x24 x32 x33 x34 40 TABLE 1 Shipping Costs, Supply, and Demand for PowercoToSupplyFromCity 1 City 2 City 3 City 4(million kwh)Plant 1$8$6$10$935 Plant 2$9$12$13$750 Plant 3$14$9$16$540 Demand45203030(million kwh)362 CHAPTER7 Transportation, Assignment, and Transshipment x21 x31 x34 45(Demand constraints) x22 x32 x34 x23 x33 x34 x24 x34 x34 30xij 0(i 1, 2, 3; j 1, 2, 3, 4)In Section , we will find that the optimal solution to this LP is z 1020, x12 10,x13 25, x21 45, x23 5, x32 10, x34 30.

6 Figure 1 is a graphical representationof the Powerco problem and its optimal solution. The variable xijis represented by a line,or arc, joining the ith supply point (plant i) and the jth demand point (city j).General Description of a Transportation ProblemIn general, a transportation problem is specified by the following information:1A set of m supply pointsfrom which a good is shipped. Supply point ican supply atmost siunits. In the Powerco example, m 3, s1 35, s2 50, and s3 set of n demand pointsto which the good is shipped. Demand point jmust receiveat least djunits of the shipped good. In the Powerco example, n 4, d1 45, d2 20,d3 30, and d4 unit produced at supply point iand shipped to demand point jincurs a variablecostof cij.

7 In the Powerco example, c12 number of units shipped from supply point ito demand point jthen the general formulation of a transportation problem ismin i mi 1 j nj 1cijxijPlant 1 Supply pointsDemand pointss1 = 35x11 = 0x12 = 10x13 = 25x14 = 0x21 = 45x31 = 0x32 = 10x33 = 0x34 = 30x24 = 0x23 = 5x22 = 0 City 1d1 = 45 City 2d2 = 20 City 3d3 = 30 City 4d4 = 30 Plant 2s1 = 50 Plant 3s1 = 40 FIGURE 1 GraphicalRepresentation ofPowerco Problem andIts Optimal Solution7. 1 Formulating Transportation j nj 1xij si(i 1, 2, .. , m)(Supply constraints)(1) i mi 1xij dj(j 1, 2, .. , n)(Demand constraints)xij 0(i 1, 2, .. , m; j 1, 2, .. , n)If a problem has the constraints given in (1) and is a maximizationproblem, then it is stilla transportation problem (see Problem 7 at the end of this section).

8 If i mi 1si j nj 1djthen total supply equals total demand, and the problem is said to be a balanced trans-portation the Powerco problem, total supply and total demand both equal 125, so this is abalanced transportation problem. In a balanced transportation problem, all the constraintsmust be binding. For example, in the Powerco problem, if any supply constraint were non-binding, then the remaining available power would not be sufficient to meet the needs ofall four cities. For a balanced transportation problem, (1) may be written asmin i mi 1 j nj j nj 1xij si(i 1, 2, .. , m)(Supply constraints)(2) i mi 1xij dj(j 1, 2, .. , n)(Demand constraints)xij 0(i 1, 2, .. , m; j 1, 2, .. , n)Later in this chapter, we will see that it is relatively simple to find a basic feasible solu-tion for a balanced transportation problem.

9 Also, simplex pivots for these Problems do notinvolve multiplication and reduce to additions and subtractions. For these reasons, it is de-sirable to formulate a transportation problem as a balanced transportation a Transportation Problem If Total Supply Exceeds Total DemandIf total supply exceeds total demand, we can balance a transportation problem by creat-ing a dummy demand pointthat has a demand equal to the amount of excess shipments to the dummy demand point are not real shipments, they are assigneda cost of zero. Shipments to the dummy demand point indicate unused supply understand the use of a dummy demand point, suppose that in the Powerco problem,the demand for city 1 were reduced to 40 million kwh.

10 To balance the Powerco problem,we would add a dummy demand point (point 5) with a demand of 125 120 5 mil-lion kwh. From each plant, the cost of shipping 1 million kwh to the dummy is 0. The op-timal solution to this balanced transportation problem is z 975, x13 20, x12 15, x21 40, x23 10, x32 5, x34 30, and x35 5. Because x35 5, 5 million kwh ofplant 3 capacity will be unused (see Figure 2).A transportation problem is specified by the supply, the demand, and the shippingcosts, so the relevant data can be summarized in a transportation tableau(see Table 2).The square, or cell,in row iand column jof a transportation tableau corresponds to the364 CHAPTER7 Transportation, Assignment, and Transshipment ProblemsPlant 1 Supply pointsDemand pointss1 = 35x11 = 0x32 = 5x12 = 15x14 = 0x21 = 40x33 = 0x23 = 10x13 = 20x31 = 0x34 = 30x15 = 0x35 = 5x24 = 0x25 = 0x22 = 0 City 1d1 = 40 City 2d2 = 20 City 3d3 = 30 City 4d4 = 30 DummyCity 5d5 = 5 Plant 2s2 = 50 Plant 3s3 = 40 FIGURE 2 GraphicalRepresentation ofUnbalanced PowercoProblem and ItsOptimal Solution (withDummy Demand Point)