Home » Operations Research » Least Cost Entry Method For Transportation Problem

Least Cost Entry Method For Transportation Problem

Least Cost Entry Method For Transportation Problem

Least cost entry method (also known as Matrix 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 Least Cost Entry method is as follows:

Step 1

Select the smallest cost in the cost matrix of the transportation table. Let it be $c_{ij}$. Allocate $x_{ij} = min_{i,j}(a_i, b_j)$ in the cell $(i,j)$.

Step 2

  • If $x_{ij} = a_i$, then cross-out the $i^{th}$ row of the transportation table and decrease $b_j$ by $a_i$ and goto Step 3.
  • If $x_{ij} = b_j$, then cross-out the $j^{th}$ column of the transportation table and decrease $a_i$ by $b_j$ and goto Step 3.
  • If $x_{ij} = a_i=b_j$, then cross-out the $i^{th}$ row of the, cross-out $i^{th}$ row and $j^{th}$ column of the transportation table and decrease $b_j$ by $a_i$ and goto Step 3.

Step 3

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

If the minimum cost is not unique, make an arbitrary choice among the minimum costs.

Leave a Comment