Degeneracy in Transportation Problems

Degeneracy in Transportation problems arise when there are to many routes that are not used. If there are  
\[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
Let  
\[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
The change in cost is  
\[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
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.

You have no rights to post comments