North-West Corner Method
The North-West cornet method is a method of finding an initial basic feasible solution to the transportation problem.
Consider a general transportation problem with $m$ origins and $n$ destinations.
| Origin Destination | $D_1$ | $D_2$ | $\cdots$ | $D_j$ | $\cdots$ | $D_n$ | Availability |
|---|---|---|---|---|---|---|---|
| $O_1$ | $c_{11}$ | $c_{12}$ | $\cdots$ | $c_{1j}$ | $\cdots$ | $c_{1n}$ | $a_1$ |
| $O_2$ | $c_{21}$ | $c_{22}$ | $\cdots$ | $c_{2j}$ | $\cdots$ | $c_{2n}$ | $a_2$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | |
| $O_i$ | $c_{i1}$ | $c_{i2}$ | $\cdots$ | $c_{ij}$ | $\cdots$ | $c_{in}$ | $a_i$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | |
| $O_m$ | $c_{m1}$ | $c_{m2}$ | $\cdots$ | $c_{mj}$ | $\cdots$ | $c_{mn}$ | $a_m$ |
| Requirement | $b_1$ | $b_2$ | $\cdots$ | $b_j$ | $\cdots$ | $b_n$ | $\sum_i a_i = \sum_j b_j$ |
If the transportation problem is unbalanced (i.e. the total availability is not equal to the total requirement, $\sum_i a_i \neq \sum_j b_j$) then convert it into a balanced transportation problem by adding a dummy row or dummy column as per the requirement taking zero costs.
Step by Step procedure
Step by step procedure of North-West Corner method is as follows:
Step 1
Allocate as much as possible to the selected cell, and adjust the associated amounts of supply and demand by subtracting the allocated amount. The maximum possible amount is allocated in in (1,1) cell, i.e., $x_{11} = \min(a_1, b_1)$.
Step 2
- If $b_1 > a_1$, move vertically downwards to the second row and make the second allocation of amount
$x_{21} = \min(a_2,b_1-x_{11})$in the cell (2,1). - If $b_1 < a_1$, move horizontally right-side to the second column and make the second allocation of amount
$x_{12} = \min(a_1-x_{11}, b_2)$in the cell (1,2). - If $b_1 = a_1$, then goto step 3.
Step 3
Start from a new northwest corner of the transportation table and repeat step 1 and 2 until all the requirements are satisfied.
The solution obtained by North-West Corner method is a basic feasible solution. In the allocation we do not consider the unit cost of transportation, hence the solution may not be an optimal solution. But this solution will serve as an initial basic feasible solution, which can be improved further.
