## Degenerate Solutions to the Transportation Problem

If a feasible solution to a transportation problem with n rows and m columns exists, but the solution uses less than cells, then the solution is said to be degenerate. This can happen when the demand of a single destination depot can be supplied by a single source depot.

 A B C Supply 1 25 20 10 40 2 40 15 30 80 3 20 50 40 60 Demand 40 60 80 180

The cost associated with each route from a supply depot to a demand depot are highlighted.

The North West Corner solution is

 A B C Supply 1 40 0 40 2 60 20 80 3 60 60 Demand 40 60 80 180

The total cost of this solution is C=40*25+0*20+60*15+20*30+60*40=4900

The supply and demand for each depot can also be satisfied by placing the zero is cell 2A instead of 1B, to give a total cost of C=40*25+0*40+60*15+20*30+60*40=4900.

These costs are the same so the solution is degenerate.

Notice that the number of rows is and the number of columns is  There are only 4 non zero cells used in the solution. Since The number of cells used is less than the number of rows plus the number of columns less one, the solution is degenerate. 