(NOTE: This problem is exactly the same as the previous one, except that in the May 13 paper, it was asked to find the basic feasible solution by north-west rule. Here, we’ll do so by using Vogel’s approximation, also called the Penalty method, which leads to a final optimal solution in fewer steps.)

Using Penalty Method:

We assign the maximum possible, to the minimum cost, in whichever row or column has the maximum penalty. Right now, the maximum penalty is 2, and in that column the minimum cost is 4. So we assign the maximum possible there. As evident, no more allocations can be made in that column.

Similarly, the penalty is then calculated again, and assignments are carried out as follows:

• After penalty is calculated again, 30 is allocated in 2B.
• Penalty is calculated again; 20 is allocated in 4A.
• Penalty is calculated again; 5 is allocated in 1A.
• Penalty is calculated again. However there is no maximum, as all the penalties are the same, i.e. 1. So the remaining allocations are made depending on what is balance in the Required and Available section.

The allocations made are as follows:

The solution is degenerate (no. of allocations < m + n – 1). So we add an infinitesimal value ‘ε’ in a cell which has the least cost among all the unallocated cells.

The minimum cost in the unallocated cells is 6, in the cells 2A, 3B, 4C and 5D. ‘ε’ cannot be added in 4C and 5D, since it would form a loop with ‘4A,1A,1C’ and ‘5C,1C,1D’ respectively.

Either of 2A or 3B can be chosen. Let’s choose 3B:

(NOTE: it is evident that we have already got the solution that was obtained in the previous problem. However, we have to still prove it is optimal.)

Checking for optimality by UV rule:

Starting the loop from the ‘-1’:

As can be seen, θ = ε; so all that happens is that ‘ε’ moves from 3B to 1B.

Checking for optimality again:

No negative numbers are present, which shows we have obtained the optimal solution.

(NOTE: We could have obtained the solution in one less if we had put ‘ε’ in 2A instead of 3B in the 1st step, like how it is done in the previous problem. However, by choosing 3B, we have shown that it does not matter where the ‘ε’ is allocated. The solution still turns out to be the same.)

Optimal solution:

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