Degeneracy In Transportation Model
Introduction:
Earlier, it is mentioned that the basic feasible solution of a transportation problem must have (m n – 1) basis variables or allocations. This means to say that the number of occupied cells or loaded cells in a given transportation problem is 1 less than the sum of number of rows and columns in the transportation matrix. Whenever the number of occupied cells is less than (m n – 1) , the transportation problem is said to be degenerate.
Degeneracy:
a) degenerate when the initial programme is designed by northwest corner or inspection or VAM, i.e. at the stage of initial allocation only.
b) To solve degeneracy at this stage, allocate extremely small amount of goods (very close to zero) to one or more of the empty cells depending on the shortage, so that the total occupied cells becomes m n – 1.
c) The cell to which small element (load) is allocated is considered to be an occupied cell. In transportation problems, Greek letter ‘∈’ represents the small amount.
d) One must be careful enough to see that the smallest element epsilon is added to such an empty cell, which will enable us to write row number ‘ui’ and column number ‘vj’ without any difficulty while giving optimality test to the basic feasible solution by MODI method.
e) That is care must be taken to see that the epsilon is added to such a cell, which will not make a closed loop, when move horizontally and vertically from loaded cell to loaded cell.
f) (Note: Epsilon is so small so that if it is added or subtracted from any number, it does not change the numerical value of the number for which it added or from which it is subtracted.).
g) Secondly, the transportation problem may become degenerate during the solution stages.
h) This happens when the inclusion of a most favorable empty cell i.e. cell having highest opportunity cost results in simultaneous vacating of two or more of the currently occupied cells.
i) to solve degeneracy, add epsilon to one or more of the empty cells to make the number of occupied cells equals to (m n – 1). To understand the procedure let us solve one problem.
Example: Solve the transportation problem given below:
