R. Sivakumar
P. R. Vittal

Production, storage and consumption points rarely coincide factories, warehouses and retail outlets are usually geographically separate. Where there are several sources of supply such as in a multi-plant enterprise and a number of demand points, the question arises as to which customers are best supplied from which sources. Finding the least cost pattern of shipments is a transportation problem, for which it is worth devising a special solution procedure or algorithm.

A difficulty that sometimes occurs in transportation problems is degeneracy. For any non-degenerate solution, the number of used squares must be equal to the number of rim requirements minus 1. Alternatively, the number of rows plus the number of columns minus 1. Where this rule is not met the solution is Degenerate.

Failure to meet the test for degeneracy in the transportation problem is indicated in two ways: There may be an excessive number of stone squares in a solution; the number of stone squares is greater than the number of rim requirements minus 1. This type of degeneracy arises only in developing the initial solution and is caused by an improper assignment or an error in formulating the problem. In such cases, one must modify the initial solution to get a solution that satisfies the rule of rim requirement minus 1.

There may be an insufficient number of stone squares in a solution. Degeneracy of this type may occur either in the initial or subsequent solutions. This type of degeneracy requires special procedures to resolve. With an insufficient number of stone squares in a solution, it would be impossible to trace a closed path for each unused square, and with the MODI method it would be impossible to compute the row and column values.

In the recent CA Final Examination, the Cost Management paper had a problem on transportation (annexure).

The problem is a modified version of one of the classic problems on degeneracy. Further, a peculiar aspect of the problem is that if a student starts with the North-West Corner Rule, for initial allocation it would clearly take a a minimum of one-and-half hours as there will be as many as eight iterations. However under the Vogel's Method, the initial allocation itself is the optimal solution in-spite of it being a degenerate situation.


To resolve degeneracy a zero allocation is assigned to one of the unused squares. Although there is a great deal of flexibility in choosing the unused square for the zero stone, the general procedure, when using the North-West Corner Rule, is to assign it to a square in such a way that it maintains an unbroken chain of stone squares. However, where the Vogel's method is used, the zero allocation is carried in a least cost independent cell. An independent cell in this context means that a cell which will not lead to a closed-path on such allocation.

With regard to the problem asked, the least cost cell happens to be R4C2 (cost Rs 3). But it is not independent. Since a closed path will be formed through the cells R1C2, R1C4 and R4C4. The next cell with least cost of Rs 5 is R4C3. This is independent as a closed path is not possible. With a zero allocation on this and with the MODI method for optimality the optimal cost is Rs 204 (solution on the web).

It can be seen that an alternative solution also exists, but the number of allocation still remains 7. Since what gets transferred from the cells is only zero. This leads to the following issues. Will a least cost independent cell always be optimal?

In case the problem is unbalanced the least cost independent cell to be chosen can be either a cell in the row or a column with the least cost zero, and

What happens if any cell which is independent is chosen?

The answer to the above is quite straight-forward. For issue 1, there is no necessity that a zero allocation in the least cost independent cell should always be optimal. It all depends upon the differences in the cost between the stone-squares. As regards issue 2, zero cost should be considered and in majority of the cases it can be seen that choosing a zero on such cells will lead to further iterations. The same is the case with respect to issue 3.


Step 1:

Form Equations through allocated cells

Step 2:

Evaluation of unallocated cells

Since all the evaluation is 0 or +ve, the optimal solution is obtained.

Optimal cost

= (8 x 2)+(6 x 6) + (4 x 2) + (10 x 9) + (8 x 3) + (2 x 9) + (0 x 5) + (2 x 6)= 16 + 36 + 8 + 90 + 24 + 18 + 10 + 12 = Rs 204.

(The authors are faculty at the SIRC of ICAI.)

(This article was published in the Business Line print edition dated June 25, 2007)
XThese are links to The Hindu Business Line suggested by Outbrain, which may or may not be relevant to the other content on this page. You can read Outbrain's privacy and cookie policy here.