Transportation Problem
Transportation problem is a special class of linear programming problem that deals with transporting (or shipping) a commodity from various origins or sources (e.g. factories) to various destinations or sinks (e.g., warehouses). In this type of problem the objective is to determine the transportation schedule that minimizes the total transportation cost while satisfying supply and demand conditions.
The general Transportation Problem (TP) can be defined as follows:
Suppose that there are $m$ origins $O_1, O_2, \ldots, O_m$ and $n$
destinations $D_1, D_2, \ldots, D_n$. Let $a_i$ be the quantity of
the product available at $i^{th}$ origin $O_i$ and $b_j$ be the
quantity of the product required at $j^{th}$ destination $D_j$.
Let the cost of transporting one unit from $i^{th}$ origin to $j^{th}$ destination be $c_{ij}$.
The tabular form of the transportation problem is as follows:
| 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$ |
Then the transportation problem is to determine the amount $x_{ij}$ to be transported from $i^{th}$ origin to $j^{th}$ destination in such a way that the availability conditions and requirement conditions are satisfied and the total transportation cost is minimum.
Mathematical Formulation
The transportation problem is to determine non-negative values
$x_{ij}$ satisfying (availability constraints)
$$ \begin{equation}\label{eq2.1} \sum_{j=1}^n x_{ij} =a_i,\; \text{ for } i=1,2,\ldots, m \end{equation} $$
and (requirement constraints)
$$ \begin{equation}\label{eq2.2} \sum_{i=1}^m x_{ij} =b_j,\; \text{ for } j=1,2,\ldots,n \end{equation} $$
and minimizing (objective function) the total cost of transportation
$$ \begin{equation}\label{eq2.3} z = \sum_{i=1}^m\sum_{j=1}^n x_{ij} c_{ij}. \end{equation} $$
Assume that $\sum_i a_i = \sum_j b_j$.
It may observed that the constraint equation \eqref{eq2.1}, \eqref{eq2.2} and the objective function \eqref{eq2.3} are all linear in $x_{ij}$. Hence Transportation Problem is a special type of Linear Programming Problem.
If in the above transportation problem, the total availability is not equal to the total requirement i.e. $\sum_i a_i \neq \sum_j b_j$, then the transportation problem is called an unbalanced transportation problem otherwise it is called balanced transportation problem.
