Solving Degenaracy in Transportation Problem

Very easy way to solve degeracy in Transpiortaion Problem

1. Solve Degeneracy in Transportation Problem LDC INSTITUTE OF TECHNICAL STDIES, SORAON PRAYAGRAJ BY Dr. Mrinal Kanti Manik Director LDC Institute of Technical studies Soraon , Allahabad, India [email protected]

2. Degeneracy in Transportation Problem Here I will solve the degeneracy of transportation problem with one example. I have taken the transportation problem having four different source and five destinations .

3. Solution: Step-1 This problem is balanced transportation problem as total supply is equal to total demand.

4. Least cost method has been applied to find the initial basic feasible solution. One can also use any other method to find the initial basic feasible solution. The following solution is obtained.

5. Optimization of the solution using U-V Method: Step-3 Check whether m + n – 1 = total number of allocated cells. In this case m + n – 1 = 4 + 5 – 1 = 8 where as total number of allocated cells are 7, hence this is the case of degeneracy in transportation problem. Step-4 So in this case we convert the necessary number (in this case it is m + n – 1 – total number of allocated cells i.e. 8 – 7 = 1 ) of unallocated cells into allocated cells to satisfy the above condition.

6. Step-5 To convert unallocated cells into allocated cells: Start from the least value of the unallocated cell. Check the loop formation one by one. There should be no closed-loop formation. Select that loop as a new allocated cell and assign a value ‘ Є ’. The closed loop can be in any form but all the turning point should be only at allocated cell or at the cell from the loop is started.

7. In this problem there are 13 unallocated cells. Select the least value (i.e. 5 in this case) from unallocated cells. There are two 5s here so you can select randomly any one. Lets select the cell with Є marked 20+ Є

8. Look if there is any closed-loop formation starting from this cell. Step-6 If a closed-loop is drawn from this cell as shown earlier then it cannot consider for allocation. But here it does not form any close loop. So this cell will be selected and assigned a random value ‘ Є ’.

9.  If the closed loop would have been formed from that cell then we would try another cell with least value and do the same procedure and check whether closed loop is possible or not. Considering with Є value of one allocated cell count total number of allocated cells, that should be 8. here m + n – 1 = 4 + 5 – 1 = 8. Then degeneracy of transportation problem is solved Calculate cost of the solution as ( 20x2+15x3+10x2+30x4+20x15+25x13+5x8=890 For calculation purpose Є location is taken as zero Step-7 Now this solution can be optimized using  U-V method . We get the below solution after performing optimization using U-V method. Find Ui + Vj = Cij for all allocated cell And find penalty Pij = Ui + Vj - Cij for all unallocated cell

10. Initially we assume U1=0 there after from the formula Ui + Vj = Cij we calculate all value of Ui + Vj

11. Step-8 Here penalty for all unoccupied cell Pij = Ui + Vj - Cij are shown below C11= 0+12 -10 =2 C14= 0-4 -15 =-19 C15= 0-2 -9 =-11 C21= 6+12 -5 =13 Highest (+) ve value here C22= 6+2 -10 =-2 C23= 6+3 -15 =-6 C33= 3+3 -14 =-8 C34= 3-4 -7 =-8 C35= 3-2-15 =-14 C41=1 0+12 -20 =2 C42=1 0+2 -15 =-3 C44=1 0-4 -25 =-19 For optimality all values of Pij ≤ 0, So again we repeat the step 6 and that start will be from cell C21

12. After Selecting an occupied cell complete loop and placed alternative (+) ve and (-) ve value as shown in the figure. Find out the most minimum vale out of all negative locations. Subtract most minimum value from all (-) ve location and add most minimum value at every (+) ve location of all turning point of loop

13. Again /Find Ui + Vj = Cij for all allocated cell and Pij = Ui + Vj - Cij for all unallocated cell For optimality all values of Pij ≤ 0, Otherwise repeat from step 6 as follows **Finally Calculate cost value35x3+20x5+10x2+10x4+20x5+5x13+25x8=630

14. Thank you