Row Minima Method for Transportation Problem

## Row Minima Method

Row 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 **Row Minima method** is as follows:

#### Step 1

Select the smallest cost in the first row of the transportation table. Let it be $c_{1j}$. Allocate as much as possible amount `$x_{1j} = min_j(a_1, b_j)$`

in the cell $(1,j)$, so that either the capacity of origin $O_1$ is exhausted or the requirement at destination $D_j$ is satisfied or both.

#### Step 2

- If $x_{1j} = a_1$, the availability at origin $O_1$ is completely exhausted, cross-out the first row of the table and move down to the second row.
- If $x_{1j}= b_j$, the requirement at destination $D_j$ is satisfied, cross-out the $j^{th}$ column and reconsider the first row with the remaining availability of origin $O_i$.
- If $x_{1j} = a_1= b_j$, the availability at origin $O_1$ and the requirement at destination $D_j$ are completely exhausted. So cross-out $1^{st}$ row and $j^{th}$ column simultaneously. Move down to the second row.

#### Step 3

Repeat Step 1 and Step 2 for the reduced transportation table until all the requirements and availabilities are satisfied.