Q.For the same transportation problem in Worked Example 1, find the initial basic feasible solution using the Least Cost (Matrix Minima) Method and compare the total cost with the North-West Corner Method.

The north-west corner of a transportation table is its top-left cell.

The North-West Corner Rule is a method for finding an initial basic feasible solution of a transportation problem. "North-west" refers to the geographical top-left of a map, so in the transportation matrix it means the top-left corner cell (first row, first column), where allocation begins before moving right or down.

A non-degenerate solution has the number of allocations equal to $m+n-1$.

For a transportation problem with $m$ origins and $n$ destinations, a basic feasible solution has at most $m+n-1$ basic (occupied) cells. The solution is:

• non-degenerate when the number of allocations is exactly $m+n-1$, and
• degenerate when the number of allocations is fewer than $m+n-1$.

Hence a non-degenerate solution has allocations equal to $m+n-1$.

A transportation problem is balanced when total supply equals total demand; if they differ it is unbalanced, option (b).

Definition. A transportation problem is balanced when

$\sum(\text{supply})=\sum(\text{demand}).$

It is therefore unbalanced when

$\text{Total supply} e\text{Total demand}.$

Such a problem is made balanced by adding a dummy row (or column) with zero unit costs to absorb the excess before solving.

Non-degenerate $\Rightarrow$ allocations $=m+n-1$.

For an $m\times n$ transportation problem, a basic feasible solution has $m+n-1$ independent allocations. If the number of occupied cells equals $m+n-1$ the solution is non-degenerate; if it is fewer than $m+n-1$, the solution is degenerate.

A transportation problem is balanced when total supply $=$ total demand; it is unbalanced when they are unequal.

In a transportation problem the availability at the sources (supply) and the requirement at the destinations (demand) are compared:

$\text{Balanced}:\ \sum a_i=\sum b_j,\qquad \text{Unbalanced}:\ \sum a_i\neq\sum b_j.$

An unbalanced problem is first converted to a balanced one by adding a dummy row or column before solving. Hence it is unbalanced when total supply $\neq$ total demand.

The North-West corner of a transportation table is its top-left cell, the starting point of the North-West Corner Method.

In the North-West Corner Method for finding an initial basic feasible solution, allocation starts at the north-west (top-left) corner cell of the transportation matrix and proceeds towards the south-east (bottom-right). So the North-West corner refers to the top-left corner.

A basic feasible solution of an $m$-origin, $n$-destination transportation problem has $m + n - 1$ basic (allocated) cells; when exactly that many independent allocations exist, the solution is non-degenerate.

Reasoning. For a transportation problem with $m$ sources and $n$ destinations, the number of independent constraints is $m + n - 1$, so a basic feasible solution requires exactly $m + n - 1$ allocations.

• If the number of allocations $= m + n - 1$ (and they are independent), the solution is non-degenerate.

• If it is fewer than $m + n - 1$, the solution is degenerate.