Module 4: Transportation Problem d Assignment problem ©) Transportation Problem: (Vogel’s Approximation Method) The North-West Corner method and the Least Cost Cell method has been discussed in the ion. In this session, the Vogel’s Approximation method will be discussed D3 »4 Supply 300 7] 4 = 400 5| 9 osf|_ 8] 3] al 2 Solution: * For each row find the least value and then the second least'value and take the absolute difference of these two least values and write it in the corresponding Yow difference as shown in the image below. In row OI, 1 is the least value and’3 is the secbnd least value and their absolute difference is 2. Similarly, for row 02 and/O3, the absélute differences are 3 and 1 respectively. + For each column find the least value and thempthe second least value and take the absolute difference of these two least values then write it in the corresponding column difference as shown in the figure. In column D1, 2 isthe least value and 3 is the second least value and their absolute difference is, Similatly, for column D2, D3and D3, the absolute differences are 2, 2 and 2 respectively. p12 ps a__—«SUP PY Row Difference Column Difference: Prasad A Y, Dept of CSE, ACSCE, B'lore-74 Page 8Module 4: Transportation Problem and Assignment problem + These value of row difference and column difference are also called as penalty. Now select the maximum penalty. The maximum penalty is 3 i.e. row 02. Now find the cell with the least cost in row O2 and allocate the minimum among the supply of the respective row and the demand of the respective column. Demand is smaller than the supply so allocate the column’s demand i.e, 250 to the cell. Then cancel the column D1. Row Difference Dema Column Difference; + From the remaining cells, find out the row difference 4nd column difference. Column Differencs + Again select the maximum penalty which is 3 corresponding to row O1. The least-cost cell in row O1 is (01, D2) with cost 1, Allocate the minimum among supply and demand from the Prasad A Y, Dept of CSE, ACSCE, B'lore-74 Page 9Module ‘ransportation Problem and Assignment problem respective row and column to the cell. Cancel the row or column with zero value. Row Difference Demand: Column Difference;, ‘* Now find the row difference and column di Destinatior rence from the remaining cells. DI op2 «D3 pa Supply Row Difference Column Differenc + Now select the maximum penalty which is 7 corresponding to column D4. The least cost cell in column D4 is (03, D4) with cost 2, The demand is smaller than the supply for cell (03, D4). Allocate 200 to the cell and cancel the column, Prasad A Y, Dept of CSE, ACSCE, B'lore-74 Page 10Module ‘ransportation Problem and Assignment problem supply Row Difference Column Differenos + Find the row difference and the column differénee from th€ remaining cells. Destin: Row Difference Column Difference + NoWpthe maximum penalty is 3 corresponding to the column D2. The cell with the least value in D2 is (03, D2). Allocate the minimum of supply and demand and cancel the column. Prasad A Y, Dept of CSE, ACSCE, B'lore-74 Page 11jodule 4: Transportation Problem d Assignment problem Supply Row Difference source Demand: Column Difference: + Now there is only one column so select thé cell with the least cost and allocate the value. Column Difference, Prasad A Y, Dept of CSE, ACSC! Page 12,Module ‘ransportation Problem and Assignment problem + Now there is only one cell so allocate the remaining demand or supply to the cell Destination blob? pa Supply Row Difference Source Demand: Column Differences + No balance remains, So multiply the allocated value of the céllS with their corresponding cell cost and add all to get the final cost i.e. (300 * 1) + (250 *\2) + (50 * 3) + (250 * 3) + (200 * 2) + (150 * 5) = 2850 Prasad A Y, Dept of CSE, ACSCE, B'lore-74 Page 13,