At which of the following stage(s), the degeneracy do not occur in…
2017
At which of the following stage(s), the degeneracy do not occur in transportation problem ? (m, n represents number of sources and destinations respectively)
(a) While the values of dual variables ui and vj cannot be computed.
(b) While obtaining an initial solution, we may have less than m + n – 1 allocations.
(c) At any stage while moving towards optimal solution, when two or more occupied cells with the same minimum allocation become unoccupied simultaneously.
(d) At a stage when the no. of +ve allocation is exactly m + n – 1.
- A.
(a), (b) and (c)
- B.
(a), (c) and (d)
- C.
(a) and (d)
- D.
(a), (b), (c) and (d)
Attempted by 6 students.
Show answer & explanation
Correct answer: C
Answer: Degeneracy does not occur only when the number of positive allocations is exactly m + n − 1.
Case describing inability to compute the dual variables u_i and v_j: This is a sign of degeneracy. When there are fewer than m + n − 1 independent occupied cells, the potentials cannot be uniquely determined, so degeneracy is present.
Case where an initial solution has fewer than m + n − 1 allocations: This is degeneracy by definition. A basic feasible solution is degenerate when the number of basic (positive) allocations is less than m + n − 1.
Case where two or more occupied cells with the same minimum allocation become unoccupied simultaneously during optimization: This can produce degeneracy. Such simultaneous loss of occupied cells can reduce the count of basic allocations below m + n − 1.
Case when the number of positive allocations is exactly m + n − 1: This is the non-degenerate situation. The basic feasible solution has the required number of independent allocations, so degeneracy does not occur.
Therefore the only stage where degeneracy does not occur is the stage when the number of positive allocations equals m + n − 1.
Practical note: If degeneracy occurs, introduce a very small allocation (epsilon) to an empty cell to restore m + n − 1 basic allocations and continue computations.