Find the basic feasible solution of the following transportation problem by north-west corner rule. Also find the optimal transportation plan. -

To find the basic feasible solution by north-west corner rule, we start by allocating in the top left corner:

Checking for optimality (UV rule):

So presence of so many negative numbers indicate that the solution is not optimal at all. Let’s consider the smallest number (-6) first in order to start optimizing the solution.

θ = 5, new allocation:

However, we now have a degenerate solution (no. of allocations < m + n – 1). UV rule cannot be applied; so we have to first introduce an infinitesimal value (ε) in an unallocated cell, with the lowest cost.

Cell u1v3 has the lowest cost of 4; but we cannot put ‘ε’ here since it would form a closed loop with the three cells having an allocation of 15 each. So we choose the next minimum cost, i.e. 5. There are two cells with cost of 5, u1v4, and u3v5. Either can be used.

Putting ‘ε’ in u1v4, and checking for optimality:

Solution is not optimal since negative numbers are present. Starting the loop at the ‘-4’ cell:

θ = 5, new allocation& checking for optimality again

Solution is not optimal since negative numbers are present. Starting the loop from the ‘-3’:

θ = 15, new allocation & checking for optimality again:

However, we now have a degenerate solution (no. of allocations < m + n – 1).

Putting ‘ε’ in the cell that has least cost of 6, i.e. u1v2, and checking for optimality:

Solution is not optimal since negative numbers are present. Starting the loop from the ‘-2’:

θ = 15, new allocation, and checking for optimality again (ε is added because of degeneracy):

No negative numbers are present. Hence the optimal solution has been obtained.

Minimum cost = 5×7 + 15×6 + 10×5 + 30×5 +15×4 + 20×5 + 5×5 = Rs. 510