## Degeneracy Assignment Problem Solving

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.

For calculation purposes, the value of d is assumed to be zero.

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

## Example: Degeneracy in Transportation Problem

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

Use Horizontal Scrollbar to View Full Table Calculation.

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.

The quantity d is so small that it does not affect the supply and demand constraints.

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

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

On small screens, scroll horizontally to view full calculation

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

Share this article with your friends

Prof Vinay Pandit

ASSIGNMENT AND TRANSPORTATION THEORY1) What is an Assignment Problem?

•

The assignment problem can be stated as a problem where different jobs are to beassigned to different machines on the basis of the cost of doing these jobs. Theobjective is to minimize the total cost of doing all the jobs on different machines

•

The peculiarity of the assignment problem is only one job can be assigned to onemachine i.e., it should be a one-to-one assignment

•

The cost data is given as a matrix where rows correspond to jobs and columns tomachines and there are as many rows as the number of columns i.e. the number of jobs and number of Machines should be equal

•

This can be compared to demand equals supply condition in a balancedtransportation problem. In the optimal solution there should be only oneassignment in each row and columns of the given assignment table. one canobserve various situations where assignment problem can exist

e.g.,

assignmentof workers to jobs like assigning clerks to different counters in a bank or salesmanto different areas for sales, different contracts to bidders.

•

Assignment becomes a problem because each job requires different skills and thecapacity or efficiency of each person with respect to these jobs can be different.This gives rise to cost differences. If each person is able to do all jobs equallyefficiently then all costs will be the same and each job can be assigned to any person.

•

When assignment is a problem it becomes a typical optimization problem it cantherefore be compared to a transportation problem. The cost elements are givenand is a square matrix and requirement at each destination is one and availabilityat each origin is also one.

OR MMS

## One thought on “Degeneracy Assignment Problem Solving”