If the basic feasible solution of a transportation problem with m
origins and n destinations has fewer than m + n – 1 positive x_{ij} (occupied cells), the problem is said to be a **degenerate transportation
problem**. **Degeneracy** can occur at two stages:

- At the initial solution
- During the testing of the optimal solution

To resolve degeneracy, we make use of an artificial quantity (*d*).
The quantity *d* is assigned to that unoccupied cell, which has
the minimum transportation cost.

The use of *d* is illustrated in the following example.

Factory | Dealer | Supply | |||
---|---|---|---|---|---|

1 | 2 | 3 | 4 | ||

A | 2 | 2 | 2 | 4 | 1000 |

B | 4 | 6 | 4 | 3 | 700 |

C | 3 | 2 | 1 | 0 | 900 |

Requirement | 900 | 800 | 500 | 400 |

Solution.

An initial basic feasible solution is obtained by **Matrix Minimum Method**.

Table 1

Factory | Dealer | Supply | |||
---|---|---|---|---|---|

1 | 2 | 3 | 4 | ||

A | 2 | 4 | 1000 | ||

B | 4 | 4 | 3 | 700 | |

C | 3 | 2 | 900 | ||

Requirement | 900 | 800 | 500 | 400 |

Number of basic variables = m + n – 1 = 3 + 4 – 1 = 6

Since number of basic variables is less than 6, therefore, it is a degenerate
transportation problem.

To resolve *degeneracy*, we make use of an artificial quantity(d). The
quantity d is assigned to that unoccupied cell, which has the minimum
transportation cost.

In the above table, there is a tie in selecting the smallest unoccupied cell. In this situation, you can choose any cell arbitrarily. We select the cell C2 as shown in the following table.

Table 2

Factory | Dealer | Supply | |||
---|---|---|---|---|---|

1 | 2 | 3 | 4 | ||

A | 2 | 4 | 1000 | ||

B | 4 | 4 | 3 | 700 | |

C | 3 | 900 + d | |||

Requirement | 900 | 800 + d | 500 | 400 | 2600 + d |

Now, we use the **stepping stone method** to find an optimal solution.

Calculating opportunity cost

Unoccupied cells | Increase in cost per unit of reallocation | Remarks |
---|---|---|

A3 | +2 – 2 + 2 – 1 = 1 | Cost Increases |

A4 | +4 – 2 + 2 – 0 = 4 | Cost Increases |

B1 | +4 – 6 + 2 – 2 = –2 | Cost Decreases |

B3 | +4 – 6 + 2 – 1 = –1 | Cost Decreases |

B4 | +3 – 6 + 2 – 0 = –1 | Cost Decreases |

C1 | +3 – 2 + 2 – 2 = 1 | Cost Increases |

The cell B1 is having the maximum improvement potential, which is equal to -2. The maximum amount that can be allocated to B1 is 700 and this will make the current basic variable corresponding to cell B2 non basic. The improved solution is shown in the following table.

Table 3

Factory | Dealer | Supply | |||
---|---|---|---|---|---|

1 | 2 | 3 | 4 | ||

A | 2 | 4 | 1000 | ||

B | 6 | 4 | 3 | 700 | |

C | 3 | 900 | |||

Requirement | 900 | 800 | 500 | 400 | 2600 |

The optimal solution is

2 X 200 + 2 X 800 + 4 X 700 + 2 X d + 1 X 500 + 0 X 400 = 5300 + 2d.

Notice that *d* is a very small quantity so it can be neglected
in the **optimal solution**. Thus, the net transportation cost is Rs. 5300