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 thancells, 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 isand 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.

Add comment

Security code
Refresh