Row Minima Method for Transportation Problem

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.

VRCBuzz co-founder and passionate about making every day the greatest day of life. Raju is nerd at heart with a background in Statistics. Raju looks after overseeing day to day operations as well as focusing on strategic planning and growth of VRCBuzz products and services. Raju has more than 25 years of experience in Teaching fields. He gain energy by helping people to reach their goal and motivate to align to their passion. Raju holds a Ph.D. degree in Statistics. Raju loves to spend his leisure time on reading and implementing AI and machine learning concepts using statistical models.

Leave a Comment