Column Minima Method for Transportation Problem

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.

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