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 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.