Transportation Problem Solve TP by Greedy Heuristic:sub-optimal The total cost= Min(78,120) 45×250+35×,1280+ Min(45,80) .=S304,900, Factories Warehouse (Sinks) Amarillo Teaneck Chicago Sioux Falls (sources) 250 420 380 280 Sunnyvale 45 45 1,280 990 1,440 1,520 Dublin 55 帮 120 1,550 1,420 1660 1,730 Bangkok 40 55 95 80 78 47 55 Mim(80-45,120-78) Min(120-35-78,47) Min(47-7,95)
Solve TP by Greedy Heuristic: sub-optimal Transportation Problem Amarillo Teaneck Chicago Sioux Falls Warehouse (Sinks) Factories (sources) Sunnyvale Dublin Bangkok 250 420 380 280 1,280 990 1,440 1,520 1,550 1,420 1,660 1,730 45 120 95 80 78 47 55 55 45 Min (45, 80) 78 Min (78, 120) 35 Min (80-45, 120-78) 7 Min (120-35-78, 47) 40 Min(47-7, 95) The total cost= 45250+35,1280+ …=$304,900
Transportation Problem Solve TP by LP Let m (=3)be the number of sources and n (=4)be the number of sinks; xi=the flow from the source i to sink j for 1s ism and 1<jsn; ci=the cost of shipping one unit from source i to sink j; m Min ∑∑cx i=1 i=1 Subject to Demand:∑y=a,or1≤i≤m Results: j=l X12=45,X21=42,X22=78,X31=38, Swpply:∑x,=b,forl≤j≤m, x33=47,andx34=10; i=l The cost is Nonegtive:x,≥0，for1≤i≤nand1≤j≤m $297,000<$304,900
Solve TP by LP • Let m (=3) be the number of sources and n (=4) be the number of sinks; • xij=the flow from the source i to sink j for 1 im and 1jn; • cij =the cost of shipping one unit from source i to sink j; Transportation Problem 1 1 n m ij ij i j Min c x Subject to 1 1 : , 1 ; : , 1 ; : 0 , 1 1 m ij i j n ij j i ij Demand x a for i n Supply x b for j m Nonegtive x for i n and j m Results: x12=45, x21=42, x22=78, x31=38, x33=47, and x34=10; The cost is $297,000<$304,900
Transportation Problem A B H M N 0 Solution of Example 6.1 (Pear's Transportation Problem) 2 3 Variables ×11×12×13×14×21 ×22 ×23×24 ×31×32×33 X34 Operator Value RHS 4 5 Values 0 0 0 45 42 78 0 38 47 10 6 7 Objective Coeff 250420 3802801280 990144015201550142016601730 Min 297800 8 s 9 Constraint 1 45 45 10 Constraint 2 = 120 120 11 Constraint 3 95 95 12 Constraint 4 80 80 13 Constraint 5 78 78 14 Constraint 6 47 47 15 Constraint 7 1 55 55 16 17 18 Notes:Formula for Cell 9:=SUMPRODUCT [B9:M9,SBS5:SMS5).Copied to 10 to 15 19 Changing cells for Solver ore $BS5:SMS5 20 Fig 6-3 Solution of Pear's Transportation Problem Using Excel Solver
Transportation Problem Fig 6-3 Solution of Pear’s Transportation Problem Using Excel Solver
Generalizations of the Transportation Infeasible Routes Eliminate routes from some sources to some sinks=Set the costs of these routes very high; Traditionally M is used to denote the very high cost.However, in practice,costs of these routes are assigned numbers much larger than the costs of other feasible routes,so that optimal solution will never assign flow to these routes. Unbalanced Problems The total amount shipped from the sources is not equal to the total amount required at the sinks. Occurs when the demand exceeds the supply or vice versa. √Two measures either add a dummy row or a dummy column to absorb the excess supply or demand; Alter the appropriate set of constraints to either or form
Generalizations of the Transportation • Infeasible Routes Eliminate routes from some sources to some sinks=Set the costs of these routes very high; Traditionally M is used to denote the very high cost. However, in practice, costs of these routes are assigned numbers much larger than the costs of other feasible routes, so that optimal solution will never assign flow to these routes. • Unbalanced Problems The total amount shipped from the sources is not equal to the total amount required at the sinks. Occurs when the demand exceeds the supply or vice versa. Two measures either add a dummy row or a dummy column to absorb the excess supply or demand; Alter the appropriate set of constraints to either or form
Generalizations of the Transportation 。 Suppose that the demand for the drives was higher than anticipated. vThe anticipated demand for the four sinks: 80784755 (the anticipated total demand is 260) √The actual demands: 90 78 5555 (the actual total demand is 278) Treatments to turn into balanced problem in Greedy Heuristic >Add an additional fictitious factory to account for this 18-unit shortfall:add a dummy row in the transportation tableau and all entries for this row are assigned an arbitrarily large unit cost
• Suppose that the demand for the drives was higher than anticipated. The anticipated demand for the four sinks: 80 78 47 55 (the anticipated total demand is 260) The actual demands: 90 78 55 55 (the actual total demand is 278) • Treatments to turn into balanced problem in Greedy Heuristic Add an additional fictitious factory to account for this 18-unit shortfall: add a dummy row in the transportation tableau and all entries for this row are assigned an arbitrarily large unit cost. Generalizations of the Transportation