what is degeneracy in transportation problem

In a transportation problem, degeneracy means that the basic feasible solution has fewer positive (occupied) cells than required, which makes the usual optimization steps break down.

Core idea in one line

For an m×nm\times nm×n transportation table, a non-degenerate basic feasible solution must have exactly m+n−1m+n-1m+n−1 occupied cells; if it has fewer, the solution is called degenerate.

Formal definition

• In a balanced transportation problem (total supply = total demand), any basic feasible solution should contain exactly m+n−1m+n-1m+n−1 basic variables (i.e., cells with allocations, including zeros if treated as basic).

• When the number of occupied cells is less than m+n−1m+n-1m+n−1, the solution is said to exhibit degeneracy.

• This causes difficulties in computing the usual potentials ui,vju_i,v_jui​,vj​ and constructing closed loops for improvement (for methods like MODI or stepping-stone).

Example:

• Suppose there are 3 sources and 4 destinations (m=3,n=4m=3,n=4m=3,n=4).
• Required number of basic cells: 3+4−1=63+4-1=63+4−1=6.
• If your initial solution (say by Northwest corner or Vogel’s method) has only 5 positive allocations, the solution is degenerate.

When and why degeneracy occurs

Degeneracy can appear in two main stages:

1. At the initial solution
   • After finding an initial feasible solution, you count occupied cells and find fewer than m+n−1m+n-1m+n−1.
   • This often happens because one row or column gets exhausted “too early,” limiting the number of distinct routes used.
2. During improvement/iterations
   • While moving from one basic feasible solution to another (e.g., when adjusting along a loop), two or more basic variables can simultaneously become zero.
   • The new solution then ends up with fewer than m+n−1m+n-1m+n−1 basic variables.

The practical issue: without exactly m+n−1m+n-1m+n−1 basic variables, the system of equations used to compute uiu_iui​ and vjv_jvj​ is underdetermined, and you cannot uniquely evaluate all opportunity costs.

How degeneracy is handled (conceptual)

Although your question only asked “what is degeneracy,” in textbooks the definition is often paired with its standard fix:

• Introduce a very small quantity ε\varepsilon ε (epsilon) into one or more empty cells carefully chosen so that:
  • They are treated as basic cells,
  • The total number of basic cells becomes m+n−1m+n-1m+n−1,
  • Supply, demand, and total cost are effectively unchanged.
• These ε\varepsilon ε allocations are only a mathematical device so that algorithms like MODI can proceed normally; they are dropped once an optimal solution is found.

In short:

Degeneracy in a transportation problem is the situation where the number of occupied cells in a basic feasible solution is less than m+n−1m+n-1m+n−1, which disrupts the usual optimization procedure and requires using artificial tiny allocations (ε\varepsilon ε) to restore a proper basic structure.

Information gathered from public forums or data available on the internet and portrayed here.