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.