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.
