Degenerating

Degeneracy in the Transportation Problem

In the context of transportation problems, degeneracy occurs when the number of positive allocations (occupied cells) in the basic feasible solution is fewer than m+n−1, where mmm is the number of origins and n is the number of destinations. Degeneracy can complicate the solving process, particularly when applying methods like the Modified Distribution Method (MODI) to test for optimality.

Understanding Degeneracy

• Basic Feasible Solution:
  • A feasible solution satisfies all supply and demand constraints. For a transportation problem with mmm origins and n destinations, the number of basic feasible solutions must be m+n−1. This ensures that all constraints are met without redundancy.
• Degeneracy Criteria:
  • If the initial basic feasible solution or the solution obtained during the testing phase has fewer than m+n−1 positive allocations, the solution is considered degenerate.

Stages of Degeneracy

• Degeneracy at the Initial Solution:
  • When the initial feasible solution is obtained using methods like North-West Corner, Least Cost, or Vogel’s Approximation, it might result in fewer than m+n−1 positive allocations. This occurs due to the specific method used or the problem's constraints, resulting in a degenerate solution.
• Degeneracy During Optimality Testing:
  • During the process of optimizing the solution (e.g., using the MODI method), degeneracy may appear if the number of positive allocations is insufficient for accurate calculations. In such cases, it is challenging to compute the necessary parameters (dual variables) for testing optimality.

Example of Degeneracy

Consider a transportation problem with 3 origins and 4 destinations. According to the formula m+n−1:

• m=3m = 3m=3 (origins)
• n=4n = 4n=4 (destinations)
• m+n−1 = 3+4−1 = 6

If the initial feasible solution has only 5 positive allocations instead of 6, the solution is degenerate.

Handling Degeneracy

• Identifying Degeneracy:
  • Check if the number of positive allocations is less than m+n−1. If so, degeneracy is present.
• Resolving Degeneracy:
  • Artificial Allocation: Introduce a small positive allocation (often called a "dummy allocation") to make up for the deficit. This helps in completing the feasible solution set.
  • Adjustments During Optimization: When using the MODI method, if degeneracy is detected, special techniques like perturbation (slightly adjusting values to break ties) can be used to handle the issue.
• Revising the Solution:
  • After introducing artificial allocations or adjustments, recompute the solution to ensure that it meets all constraints and is optimal.

Important Facts

• Redundancy in Constraints: Degeneracy often indicates redundant constraints or insufficient basic feasible solutions.
• Impact on Algorithms: Degeneracy can affect the performance and accuracy of algorithms used for solving transportation problems, necessitating additional steps or modifications to handle it properly.

By understanding and addressing degeneracy, one can ensure that the transportation problem is solved effectively and accurately.