Degeneracy in Transportation Problem (With Examples) | Operations Research

Degeneracy in transportation problem occurs in two ways: 1. Resolution of Degeneracy During the Initial Stage 2. Degeneracy at Subsequent Interactions.

1. Resolution of Degeneracy During the Initial Stage:

To resolve degeneracy, we proceed by allocating a small quantity close to zero to one or more (if needed) unoccupied cells so as to get m + n – 1. The cell containing this extremely small quantity is considered to be an occupied cell.

Rule:

This extremely small quantity is denoted by a Greek letter e (epsilon) or A (delta). In a minimization problem it is better to allocate Δ to unoccupied cells that have lowest transportation cost, whereas in maximization problem it should be allocated to a cell that has a high payoff value. The quantity Δ is considered so small that if it is transferred to an occupied cell it does not change the quantity of allocation.

(1) Δ < x_ij for all x_ij > O

(2) x_ij + Δ = x_ij – Δ, x_ij > O

(3) Δ + O = Δ

4. It there are more than one Δ’s in the solution, Δ < Δ’ whenever Δ is above Δ’

Following example make the procedure clear:

Example 1:

A company wants to ship 22 loads of his product shown below. The matrix gives the kilometers from sources of supply to the destination.

Shipping cost is Rs. 10/Load per km. what shipping schedule should be used to minimize total transportation cost?

Solution:

Since total destination requirement of 25 units more than the total resources capacity of 22 by J units. This excess requirement is handled by adding dumny plant S_excees with a capacity equal to 3 unit. We use zero transportation cost to the dummy plant.

Then modified total is shown below:

To obtain initial solution:

We use Vogel’s approximation method and get a following solution:

This solution includes occupied cells but in a rule there will be m + n – 1 = 5 + – 4 = 8 occupied cell.

.^.. The initial solution is degenerate.

In order to remove degeneracy we assign Δ to unoccupied cell (S₂, D₅) which has minimum cost among unoccupied cells as shown in table 2.

To check optionality:

We use MODI method and therefore first we have to find u_i, v_j & Δ_ij with following relation.

c_ij = u_i + v_j for occupied cell

Δ_ij = c_ij – (u_i + v_j) for unoccupied cell.

Here some Δ_ij is not greater or equal to zero. This is not an optimal solution. Then we have to improve this solution for this we have to choose (S_excess D₃) cell because it has largest negative cost it must enter the bases

Then we choose a closed path for cell (S_excess D₃) which is (S_excess, D₃)→(S_excess,D₄)→(S₂D₄)→(S₂,D₅) →(S₁D₅)→(S₁D₃)→ (D₄S_excess)and, min. (Δ,3,5) = Δ

The new solution is shown in following table 4:

To click its optimality again we have to calculate c_i, v_j and Δ_ij.

This is shown in following Table 5:

Here again some Δ_ij, is not greater or equal to zero. Then this is not an optimal solution. Then again we choose (S₃D₄) cell which is largest negative, it must enter the basis and choose a closed path as (S₃ D₄)→(S₃D₅)→(S₁D₅)→(S₁D₃)→(S_excessD₃)→(S_excessD₄)→(S₃D₄). Here min (3, 5) = 3 and find a solution which is shown in following Table 6.

Again we check optimality & calculate u_i v_j & Δ_ij as follows:

Again (S₃D₃) < 0 therefore this is not optimal solution again we choose (S₃D₃) cell enter into basis and mark a closed path as (S₃D₃)→(S₃D₅)→(S₁D₅)→(S₁,D₃)→(S₃D₃) and modified this table as shown below as Table 8.

Again we check optimality for this we calculate µ_i, v_j & Δ_ij as follows:

Since all Δ_ij ≤ 0, this is an optimal solution which is shown as follows:

The minimum total transportation cost associated with this solution is

= (4×4)+(4×4)+(2×6)+ (3×0)+(3×6)+(1×6)+(8×3)]x10

= (16+16+12+0+18+6 +24)10

= Rs. 920

2. Degeneracy at Subsequent Interactions:

To resolve degeneracy which occurs during optimality test, the quantity may be allocated to one or more cells which have become unoccupied recently to have m + n -1 member of occupied cells in the new solution.

Example 2:

Goods have to be transported from sources S₁, S₂ and S₃ to destinations D₁, D₂ and D₃. The transportation cost per unit capacities of the sources and requirements of the destination are given in the following table.

Determine a transportation schedule so that cost is minimized

Solution:

To find initial Basic feasible solution. Using north- west corner method. The non-degenerate initial basic feasible solution is given is Table 1.

Here total occupied cell = m + n – 1

= 3 + 3-1

= 5

Therefore there is no degeneracy. To test the optimality. We use MODI method, for this first we calculate µ_i, v_j & Δ_ij.

Since the unoccupied cell (S₃, D₁) has the largest negative opportunity cost of the therefore cell (S₃, D₁) is entered into the basis. Then we have chosen closed path

(S₃,D₁)→(S₃D₂)→ (S₂D₂)→(S₂D₁)→(S₃D₃)

Here maximum allocation to negative cell is 300.

Therefore modified solution is given below:

But in this solution degeneracy occur because total no of positive allocation become 4 which is less than the required no m + n – 1 = 3 + 3 – 1 =5

Hence this is degenerate solution, to remove degeneracy a quantity Δ assigned is to one of the cells that has become unoccupied so that m + n-1 occupied cell assign Δ to either (S₁,D₁) or (S₃, D₂) and proceed with the usual solution procedure.

Again proceed with the usual solution procedure. The optimal solution is given as follows: