Transportation Problem

Transportation Problem in OR

1. By : Group 2 Aayush Agrawal (Slide 2 – 8) Adil Hussain (Slide 9 –16) Seema Thappa (Slide 17–26) Vibhor Aggarwal (Slide 27- 39) Abhishek Kumar (Slide 40- 77)

2. TRANSPORTATION PROBLEM   The transportation problem is  a special type of linear programming problem ( It's a sub class of LPP ) where the objective consists in minimizing transportation cost of a given commodity from a number of sources or origins  (e.g. factory, manufacturing facility) to a number of destinations (e.g. warehouse, store) 1 2 3 …..........n 1 C11          X11           C12          X12           C13          X13            C1n          X1n           a1 2 C21          X21            C22          X22            C23          X23             C2n        X2n          a2 3 C31          X31           C32          X32            C33          X33           C3n          X3n           a3 ….......m Cm1        Xm1        Cm2        Xm2           Cm3      Xm3       Cmn      Xmn        …..a m b1 b2 b3 …....b n DESTINATION ORIGIN DEMAND SUPPLY Cij – It's the cost of transporting one unit of the product from i th  origin to j th destination. Xij – It's the quantity transported from i th  origin to j th  destination.

3. WHY TRANSPORTATION PROBLME CAN’T BE FORMULATE IN LPP OBJECTIVE FUNCTION :- Minimize Z = c11*x11 + c12*x12+ c13*x13+ c21*x21 ……………. c1n*1n+ c2n*2n+c3n*3n +cm1*m1+ cm2*m2+ cm3*m3 ( multiplying all cost with quantity) x11+x12+x13+x1n <_a1 x21+x22+x23+x2n <_a2 (Supply constraints) x31+x32+x33+x3n <_a3 x11+x21+x31+xm1 = b1 x12+x22+x32+xm2 = b2 (Demand Constraints) x13+x23+x33+xm3 = b3 x14+x24+x34+xm4 = b4

4. Real Life Application – Scheduling Appointments at Australian Trade Events The Australian Tourist Commission (ATC) organizes trade events around the world to provide a forum for Australian sellers to meet international buyers of tourism products. During these events, sellers are stationed in booths and are visited by buyers according to scheduled appointments. Because of the limited number of time slots available in each event and the fact that the number of buyers and sellers can be quite large . ATC attempts to schedule the seller- buyer appointments in advance of the event in a manner that maximizes preferences. The model has resulted in greater satisfaction for both the buyers and sellers. 

5. TRANSPORTATION PROBLEM - A) UNBALANCED TRANSPORTATION PROBLEM           (i) DEMAND > SUPPLY   ( Σbj>Σai)          (ii) DEMAND < SUPPLY  ( Σbj<Σai) B) BALANCED TRANSPORTATION PROBLEM               DEMAND = SUPPLY ( Σai=Σbj) BALANCING PART -  In unbalanced transportation problem for balancing in the case of demand > supply we add a dummy row with a cost 0 and supply equals to ( demand – supply) In case of supply > demand we add a dummy column with cost 0 and demand equals to (supply – demand) .

6. Balancing the unbalanced transportation table  D1 D2 D3 D4 SUPPLY O1 5 4 2 6 30 O2 8 3 5 7 40 O3 10 11 3 1 20 O4 9 12 6 3 10 DEMAND 10 50 30 20 D1 D2 D3 D4 SUPPLY O1 5 4 2 6 30 O2 8 3 5 7 40 O3 10 11 3 1 20 O4 9 12 6 3 10 O5 10 DEMAND 10 50 30 20 110 Converting unbalanced transportation into balanced one where Demand > Supply   DEMAND = 110 ;  SUPPLY = 100

7. Balancing the unbalanced transportation table  D1 D2 D3 D4 SUPPLY O1 1 9 14 8 50 O2 13 2 7 12 20 O3 15 6 3 11 10 O4 5 10 16 4 30 DEMAND 10 20 30 40 D1 D2 D3 D4 D5 SUPPLY O1 1 9 14 8 50 O2 13 2 7 12 20 O3 15 6 3 11 10 O4 5 10 16 4 30 DEMAND 10 20 30 40 10 110 DEMAND = 100 ;  SUPPLY = 110 Converting unbalanced transportation into balanced one where Demand > Supply 

8. TRANSPORTATION PROBLEM SOLUTION The solution of transportation problem can be obtained in two stages:- A) INITIAL SOLUTION B) OPTIMAL SOLUTION            Initial solution can be obtained by using any of the three :-               I) NORTH-WEST CORNER RULE ( NWCR)      II) LEAST COST METHOD OR MATRIX MINIMA METHOD     III) VOGEL'S  APPROXIMATION METHOD (VAM)           Optimal solution can be obtained by using any one of the following :-        I) MODI MEHTOD ( MODIFIED DISTRIBUTION MEHTOD)   II) STEPPING STONE METHOD.

9. The North-West Corner Method The  North-West Corner Rule  is a method adopted to compute the initial feasible solution of the transportation problem. The name North-west corner is given to this method because the basic variables are selected from the extreme left corner. D1 D2 D3 Supply S1 5 1 7 10 S2 6 4 6 80 S3 3 2 5 50 Demand 75 20 50 - We take an example of situation, were the demand is greater than the supply available.

10. D1 D2 D3 Supply S1 5 1 7 10 S2 6 4 6 80 S3 3 2 5 50 S4 5 Demand 75 20 50 - The prerequisite condition for solving the transportation problem is that demand should be equal to the supply. In case the demand is more than supply, then dummy row is added to the table. The supply of dummy row will be equal to the difference between the total supply and total demand. The cost associated with the dummy origin will be zero. Here, Total Demand = 145 Total Supply = 140

11. D1 D2 D3 Supply S1 5 1 7 10 0 S2 6 4 6 80 S3 3 2 5 50 S4 5 Demand 75 65 20 50 - 10

12. D1 D2 D3 Supply S1 5 1 7 10 0 S2 6 4 6 80 15 S3 3 2 5 50 S4 5 Demand 75 65 0 20 50 - 10 65

13. D1 D2 D3 Supply S1 5 1 7 10 S2 6 4 6 80 15 0 S3 3 2 5 50 S4 5 Demand 75 65 0 20 5 50 - 15 10 65

14. D1 D2 D3 Supply S1 5 1 7 10 0 S2 6 4 6 80 15 0 S3 3 2 5 50 45 S4 5 Demand 75 65 0 20 5 0 50 - 5 10 65 15

15. D1 D2 D3 Supply S1 5 1 7 10 0 S2 6 4 6 80 15 0 S3 3 2 5 50 45 0 S4 5 Demand 75 65 0 20 5 0 50 5 - 45 10 65 15 5

16. D1 D2 D3 Supply S1 5 1 7 10 0 S2 6 4 6 80 15 0 S3 3 2 5 50 45 0 S4 5 0 Demand 75 65 0 20 5 0 50 5 0 - 5 45 5 15 65 10 The Total cost can be computed by multiplying the units assigned to each cell with the concerned transportation cost. Total Cost = 5*10 + 6*65 + 4*15 + 2*5 + 5*45 + 0*5 = $ 735

17. Least Cost Method The Least Cost Method is another method used to obtain the initial feasible solution for the transportation problem. Here, the allocation begins with the cell which has the minimum cost. The lower cost cells are chosen over the higher cost cells with the objective to have the least cost of transportation.

18. Steps under Least Cost Method: First we need to check if the problem is balanced or not i.e., S=D. Select the lowest cost from the entire matrix and allocate the minimum of supply and demand. Remove the row or column whose supply or demand is fulfilled and prepare a new matrix. Repeat the procedure until all the allocations are over. After all the allocations are over, write the allocations and calculate the transportation cost.

19. To D1 D2 D3 D4 Supply O1 6 4 1 5 14 O2 8 9 2 7 16 O3 4 3 6 2 5 Demand 6 10 15 4 35 From Total Supply= 14+16+5= 35 Total Demand= 6+10+15+4= 35 The table is Balanced.

20. To D1 D2 D3 D4 Supply O1 6 4 1 5 14 0 O2 8 9 2 7 16 O3 4 3 6 2 5 Demand 6 10 15 1 4 35 From 14

21. To D1 D2 D3 D4 Supply O1 6 4 1 5 14 0 O2 8 9 2 7 16 15 O3 4 3 6 2 5 Demand 6 10 15 1 0 4 35 From 14 1

22. To D1 D2 D3 D4 Supply O1 6 4 1 5 14 0 O2 8 9 2 7 16 15 O3 4 3 6 2 5 1 Demand 6 10 15 1 0 4 0 35 From 14 1 4

23. To D1 D2 D3 D4 Supply O1 6 4 1 5 14 0 O2 8 9 2 7 16 15 O3 4 3 6 2 5 1 0 Demand 6 10 9 15 1 0 4 0 35 From 14 1 4 1

24. To D1 D2 D3 D4 Supply O1 6 4 1 5 14 0 O2 8 9 2 7 16 15 9 O3 4 3 6 2 5 1 0 Demand 6 0 10 9 15 1 0 4 0 35 From 14 1 4 1 6

25. To D1 D2 D3 D4 Supply O1 6 4 1 5 14 0 O2 8 9 2 7 16 15 9 0 O3 4 3 6 2 5 1 0 Demand 6 0 10 9 0 15 1 0 4 0 35 From 14 1 4 1 6 9

26. Now, we’ll multiply the cost of cells with their respective allocated values and add all of them. (1*14)+(2*1)+(2*4)+(3*1)+(8*6)+(9*9)= rs.156

27. Vogel’s Approximation Method The Vogel’s Approximation method, commonly known as VAM, is a cost-based method used for obtaining initial solution to a transportation problem select the appropriate cells to make allocations. VAM is considered to be the most effective method of calculating least cost because initial solution obtained from this method is either the optimal solution or is very close to the optimal solution. Why it is considered effective This method works on the principle of Opportunity cost or the Penalty cost i.e. it helps to ascertain & avoid the loss that a firm could incur by procuring material from supplier which could result in higher cost.

28. Example Using Vogel’s Approximation Method, calculate the least cost of transporting different quantities from different origins to destinations, given the supply, demand and cost function. TO From P Q R S Supply A 12 10 12 13 500 B 7 11 8 14 300 C 6 16 11 7 200 Demand 180 150 350 320 1000

29. Steps under Vogel’s Approximation Method Firstly it is essential to check whether the problem is balanced or not i.e. D=S. Calculate the Iterations (Penalties) for each row and column. Iteration (Penalty) = 2 nd Lowest value – Lowest value Choose the penalty with the highest value among the values corresponding to rows and columns found in step 2 and put an arrow besides it. Now focus on the cell with the smallest cost in the row or column so chosen and make the allocation in that. The number of units to be allocated would be lower of the corresponding demand and supply values. In case of a tie in the largest cost difference, either of them might be chosen.

30. To From P Q R S Supply Iteration I A 12 10 12 13 500 2 B 7 11 8 14 300 1 C 6 16 11 7 200 1 Demand 180 150 350 320 1000 I 1 1 3 6 Table 1

31. To From P Q R S Supply Iteration I II III A 12 10 12 13 500 2 2 B 7 11 8 14 300 1 1 C 6 16 11 7 200 200 1 - Demand 180 150 350 320 120 1000 I 1 1 3 6 II 5 1 4 1 III

32. To From P Q R S Supply Iteration I II III A 12 10 12 13 500 2 2 2 B 7 180 11 8 14 300 (120) 1 1 3 C 6 16 11 7 200 200 1 - - Demand 180 150 350 320 120 1000 I 1 1 3 6 II 5 1 4 1 III - 1 4 1

33. To From P Q R S Supply Iteration I II III IV A 12 10 12 13 500 2 2 2 2 B 7 180 11 8 120 14 300 (120) 1 1 3 - C 6 16 11 7 200 200 1 - - - Demand 180 150 350 230 320 120 1000 I 1 1 3 6 II 5 1 4 1 III - 1 4 1 IV - 10 12 13

34. The least total cost will be (10x150)+(12x230)+(13x120)+(7x180)+ (8x120)+(7x200) = 9,440 The same could also be found by using MS-Excel with the application of Solver. To From P Q R S Supply A 12 10 150 12 230 13 120 500 B 7 180 11 8 120 14 300 C 6 16 11 7 200 200 Demand 180 150 350 320 1000 Final Table

35. The same problem could also be solved by using MS-Excel with the application of Solver by following LPP Model There are 2 tables in the file given, one being cost table and other being quantity table. S olver will be solving the problem in second table and will produce the result. Our final solution depends on the allocation of the quantities in quantity table, so we can say we have 12 (3*4) decision variables on which our actual solution depends. In cell Q5, Q6, Q7, we need to apply sum formula such that sum of supplies from O1, O2 and O3 is ≤ 500, 300 and 200 respectively. Similarly in cell M8, M9, M10 and M11, we need to apply sum formula such that sum of demand from D1 , D2 and D3 and D4 is = 180, 150, 350, 320 respectively. As Solver applies LPP model to solve transportation problem there are supply constraints, Demand constraints an objective function.

36. Supply constraints would be O1D1+ O1D2+ O1D3+ O1D4 ≤ 500 O2D1+ O2D2+ O2D3+ O2D4 ≤ 300 O3D1 + O3D2+ O3D3+ O3D4 ≤ 200 Demand constraints would be O1D1+ O2D1+ O3D1 = 180 O1D2+ O2D2+ O3D2 = 150 O1D3+ O2D3+ O3D3 = 350 O1D4+ O2D4+ O3D4 = 320 Here our objective function will be sum-product of cost and quantity which is represented in cell M13 which is to be kept at minimum. Now by applying Solver from Data tab, using Simplex LP method under select a solving method we can obtain our solution. If we want to get iterations at each stage, we may go on option under solver and may select iterations option.

37. Practice question covering all the 3 methods and application of R. Problem SunRay Transport Company ships truckloads of grain from three silos to four mills. The supply  (in truckloads) and the demand (also in truckloads) together with the unit transportation costs per truckload on the different routes are summarized. The unit transportation costs, cij (shown in the northeast corner of each box), are in hundreds of dollars. The model seeks the minimum cost shipping schedule between the silos and the mills.

38. North-West Method  10 5 5 10

39. North-West Method  10 5 5 10 20 5

40. North-West Method  10 5 5 10 20 5 15 5

41. North-West Method  10 5

42. North-West Method  10 5 5 10 20 5 15 5 5 10

43. North-West Method  10 5 5 10 20 5 15 5 5 10 10

44. North-West Method  10 5 5 10 20 5 15 5 5 10 10

45. The starting basic solution is x11 = 5, x12 = 10, x22 = 5, x23 = 15, x24 = 5, x34 = 10. 10 5 5 10 5 15 5 5 10 10 The associated cost of the schedule is: z = 5 * 10 + 10 * 2 + 5 * 7 + 15 * 9 + 5 * 20 + 10 * 18 = $520. 20

46. 15 Least Cost Method

47. 15 5 Least Cost Method 5

48. 15 5 15 15 Least Cost Method 5 10

49. 15 5 15 15 Least Cost Method 5 10

50. 15 5 5 10 15 15 5 10 Least Cost Method

51. 15 5 5 10 15 15 5 10 10 Least Cost Method

52. 15 5 5 10 15 15 5 10 10 Least Cost Method

53. 15 5 5 10 15 15 5 10 10 The starting solution (consisting of six basic variables)  is x12 = 15, x14 = 0, x23 = 15, x24 = 10, x31 = 5, x34 = 5. The associated objective value is z = 15 * 2 + 0 * 11 + 15 * 9 + 10 * 20 + 5 * 4 + 5 * 18 = $475

54. Vogel’s Approximation Method

55. z = 15 * 2 + 0 * 11 + 15 * 9 + 10 * 20 + 5 * 4 + 5 * 18 = $475.

56. The same problem could also be solved by using R with the lpSolve package by lp.transport function through LPP Model.

57. Conclusion With NWC method we will get $520 as cost. With Least Cost Method we will get $475 as cost. With Vogel’s Approximation Method we will get $475 as cost. By forming LLP model and through R We will get $435 as cost which optimized cost and minimal cost among all. In conclusion all method will give different results, we can use different methods as per our need and availability of resources.

58. Thank You