Page 118 - DCOM303_DMGT504_OPERATION_RESEARCH

Unit 5: Transportation Problem

5.8 Degeneracy in Transportation Problems Notes

Degeneracy involves two steps:
1. Check for degeneracy: The solution that satisfies the above said conditions N = m + n – 1 is
a non-degenerate basic feasible solution otherwise, it is a degenerate solution. Degeneracy
may occur either at the initial stage or at subsequent iterations.
If number of allocations, N = m + n – 1, then degeneracy does not exist, one has to go to the
next step.
If number of allocations, N = m + n – 1, then degeneracy does exist, and has to be resolved
before going to the next step.
2. Resolving Degeneracy: To resolve degeneracy at the initial solution, allocate a small positive
quantity e to one or more unoccupied cell that have lowest transportation costs, so as to
make m + n – 1 allocations (i.e., to satisfy the condition N = m + n – 1). The cell chosen for
allocating e must be of an independent position. In other words, the allocation of e should
avoid a closed loop and should not have a path.
The following Table 5.21 shows independent allocations.

Table 5.21: Independent Allocations

* *

* * * *

* * *

The following Tables 5.22 (a), (b) and (c) show non-independent allocations.

Table 5.22: (a) Independent Allocations, (b) and (c)

* *

* *

* * * *

(a) (b)

* * * *
* * *

* * * *

* *
(c)

LOVELY PROFESSIONAL UNIVERSITY 113