Which of the following is a valid reason for causing degeneracy in a…
2017
Which of the following is a valid reason for causing degeneracy in a transportation problem ? Here m is no. of rows and n is no. of columns in transportation table.
- A.
When the number of allocations is m + n − 1.
- B.
When two or more occupied cells become unoccupied simultaneously.
- C.
When the number of allocations is less than m + n − 1.
- D.
When a loop cannot be drawn without using unoccupied cells, except the starting cell of the loop.
Attempted by 8 students.
Show answer & explanation
Correct answer: C
Answer: A transportation problem is degenerate when the number of basic (allocated) cells is less than m + n − 1.
Why:
A basic feasible solution for an m by n transportation table requires exactly m + n − 1 independent allocations (basic variables).
If there are fewer than m + n − 1 allocations, some basic variables are effectively zero, which is called degeneracy.
Notes on the other statements:
Having exactly m + n − 1 allocations is the normal (non-degenerate) case.
Two or more occupied cells becoming unoccupied simultaneously is an operational event during adjustments, not the definition of degeneracy.
Difficulty drawing a loop without using unoccupied cells can be a symptom of degeneracy, but the formal criterion remains the count of allocations.
How to detect and fix degeneracy:
Detect: Count the number of allocated cells. If it is less than m + n − 1, the solution is degenerate.
Fix: Introduce a very small artificial allocation (epsilon) in one or more unallocated cells to bring the count to m + n − 1; treat those epsilons as zero for cost calculations but keep them to preserve feasibility and allow loop formation.