Unbalanced Transportation Problem

Unbalanced Transportation Problem
In the previous section we discussed about the balanced transportation problem i.e. the total supply (capacity) at the origins is equal to the total demand (requirement) at the destination. In this section we are going to discuss about the unbalanced transportation problems i.e. when the total supply is not equal to the total demand, which are called as unbalanced transportation problem.
In the unbalanced transportation problem if the total supply is more than the total demand then we introduce an additional column which will indicate the surplus supply with transportation cost zero.
Similarly, if the total demand is more than the total supply an additional row is introduced in the transportation table which indicates unsatisfied demand with zero transportation cost.



Example:
Consider the following unbalanced transportation problem
Warehouses
Plant w1 w2 w3 Supply
X 20 17 25 400
Y 10 10 20 500
Demand 400 400 500

In this problem the demand is 1300 whereas the total supply is 900. Thus, we now introduce an additional row with zero transportation cost denoting the unsatisfied demand. So that the modified transportation problem table is as follows:
Warehouses
Plant w1 w2 w3 Supply
X 20 17 25 400
Y 10 10 20 500
Unsatisfied
Demand 0 0 0 400
Demand 400 400 500 1300

Now we can solve as balanced problem discussed as in the previous sections.


Degenerate transport problem

A transport problem is said to be a degenerate transport problem if it has a basic feasible solution with number of nonzero basic variables less than m + n - 1.
A degenerate basic feasible solution (BFS) in a transportation problem exists if and only if some partial sum of availabilities (row) is equal to a partial sum of requirements (column).
Thus degeneracy occurs in the transportation problem whenever a number of occupied cells is less than m + n - 1.
We recall that a basic feasible solution to an m-origin and n-destination transportation problem can have at most m + n -1 number of positive (non- zero) basic variables. If this number is exactly m + n - I, the BFS is said to be non-degenerate; and if less than m + n – 1, then the basic feasible solution degenerates. It follows that whenever the number of basic cells is less than m + n - I, the transportation problem is a degenerate one.
The basic feasible solutions may be degenerate from the initial stage onward and they may become degenerate at any intermediate stage.
The degeneracy problem does not cause any serious difficulty, but it can cause computational problem wile determining the optimal minimum solution. Therefore it is important to identify a degenerate problem as early as beginning and take the necessary action to avoid any computational difficulty. In a transportation problem, the other cause to occur the degenerate basic feasible solution is, if some partial sum of supply (row) is equal to a partial sum of demand (column).
For example the following transportation problem is degenerate. Because in this problem
a1 = 400 = b1
a2 + a3 = 900 = b2 + b3
Warehouses

Plant W1 W2 W3 Supply (ai)
X 20 17 25 400
Y 10 10 20 500
Unsatisfied demand 0 0 0 400
Demand (bi) 400 400 500 1300

There is a technique called perturbation helps to solve the degenerate problems.
Perturbation Technique:
The degeneracy of the transportation problem can be certain that no partial sum of ai (supply) equal to the sum of bi (demand). We set up a new problem where:
ai = ai + d
bj = bj
bn = bn + md
Where i = 1, 2, ……, m , j = 1, 2, ……, n -1 and d > 0
This modified problem is constructed in such a way that no partial sum of ai is equal to the bj.