USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Degeneracy in T.P.

A BFS of a T.P. is said to be degenerate if one or more basic variables assume a zero value. This degeneracy may occur in initial BFS or in the subsequent iterations of uv-method. An initial BFS could become degenerate when the supply and demand in the intermediate stages of any one method (NWC/LCM/VAM ) are equal corresponding to a selected cell for allocation. In uv-method it is identified only when more than one comer points in a loop vanishes due to minimum value of θ.

 

For the degeneracy in initial BFS, arbitrarily we can delete the row due to supply adjusting the demand to zero or delete the column due to demand adjusting the supply to zero whenever there is a tie in demand and supply.

 

For the degeneracy in uv-method, arbitrarily we can make one comer as non-basic cell and put zero in the other comer.

 

Example 6. Find the optimal solution to the following T.P :Solution. Let us find the initial BFS using YAM :

Select (3, 3) cell for allocation and allocate min (40, 20) = 20 in that cell. Cross-off the third column as the requirement is met and adjust the availability to 20. The reduced table is given below :

Select (3, 2) cell for allocation. Now there is a tie in allocation. Let us allocate 20 in (3, 2) cell andcross-off the second column and adjust the availability to zero. The reduced table is given below :

On continuation we obtain the remaining allocations as 0 in (3, 1) cell, 30 in (2, 1) cell and 10 in ( 1, 1) cell. The complete initial BFS is given below and let us apply the first iteration of uv - method:

 

Iteration 1.

For non-basic cells :

 

Since all cij < 0, the current solution is optimal Hence the optimal solution is

 

x11 = 10, x21 = 30, x31 = 0, x32 = 20, x33 = 20.

The transportation cost

=50 * 10 + 80 * 30 + 0 + 180 * 20 + 50 * 20 = $ 7500.