Column Minima Method for Transportation Problem
Column Minima Method
Column minima method is a method of finding initial basic feasible solution for a 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 Column Minima method is as follows:
Step 1
Select the smallest cost in the first column of the transportation table. Let it be $c_{i1}$. Allocate as much as possible amount $x_{i1} = min_i(a_i, b_1)$ in the cell $(i,1)$, so that either the capacity of origin $O_i$ is exhausted or the requirement at destination $D_1$ is satisfied or both.
Step 2
- If $x_{i1} = b_1$, the requirement at destination $D_1$ is completely exhausted, cross-out the first column of the table and move down to the second column.
- If $x_{i1}= a_i$, the availability at origin $O_i$ is satisfied, cross-out the $i^{th}$ row and reconsider the first column with the remaining requirement of destination $D_1$.
- If $x_{i1} = a_i= b_1$, the availability at origin $O_i$ and the requirement at destination $D_1$ are completely exhausted. So cross-out $1^{st}$ column and $i^{th}$ row simultaneously. Move down to the second column.
Step 3
Repeat Step 1 and Step 2 for the reduced transportation table until all the requirements and availabilities are satisfied.
The solution so obtained is the initial basic feasible solution to the transportation problem using Column minima method.
