Degeneracy in Transportation Problems

Degeneracy in Transportation problems arise when there are to many routes that are not used. If there are    factories and    warehouses, and the number of used routes from factories to warehouses in a solution is less than  , then this solution is degenerate.
We resolve the degeneracy by allocating a small shipment    to an unused route. We calculate the change in cost, and if it is negative, We maximise    such that no entries are negative and start again.
Example: A transportation problem has cost structure and trial solution below.
Key cost/units

			Source
		\[F_1\]	\[F_2\]	\[F_3\]	Demand
	\[W_2\]	0.90/0	1.00/5	1.00/0	5
Destination	\[W_2\]	1.00/20	1.40/0	0.80/0	20
	\[W_3\]	1.30/0	1.00/10	0.80/10	20
		20	15	10	45

Let    be transported using previously unused route  . So that demand and supply constraints are satisfied, and the table has no negative for the quantity transported along each route, we MUST have the table below.

			Source
		\[F_1\]	\[F_2\]	\[F_3\]	Demand
	\[W_2\]	0.90/x	1.00/5-x	1.00/0	5
Destination	\[W_2\]	1.00/20-x	1.40/x	0.80/0	20
	\[W_3\]	1.30/0	1.00/10	0.80/10	20
		20	15	10	45

The change in cost is  . This is an increase in cost. Evaluating the other unused routes, looking for a decrease in costs results in the final solution below.

			Source
		\[F_1\]	\[F_2\]	\[F_3\]	Demand
	\[W_2\]	0.90/0	1.00/0-x	1.00/0	5
Destination	\[W_2\]	1.00/20-x	1.40/09	0.80/0	20
	\[W_3\]	1.30/0	1.00/10	0.80/10	20
		20	15	10	45

IN fact, repeating this for every unused route produces an increase in cost each time, so the trial solution is optimal. In general several iterations are required, and the final solution may not be unique.