## Degeneracy in Transportation Problems

\[F\]

factories and \[W\]

warehouses, and the number of used routes from factories to warehouses in a solution is less than \[F+W-1\]

, then this solution is degenerate.We resolve the degeneracy by allocating a small shipment

\[x\]

to an unused route. We calculate the change in cost, and if it is negative, We maximise \[x\]

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 |

\[x\]

be transported using previously unused route \[F_1W_1\]

. 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 |

\[0.90x-1.00x+1.00x-1.40x=0.30x\]

. 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 |