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.
Importatnt Definitions
Feasible Solution
A set of non-negative values $x_{ij}$ which simultaneously satisfies the availability and requirement conditions of the given transportation problem is called a feasible solution.
Basic Feasible Solution
A feasible solution to $m$ origin and $n$ destimation transportation problem (i.e., $m\times n$ transportation problem) is said to be basic feasible solution if the number of positive allocation are $m+n-1$.
Degenerate Basic Feasible Solution
If the number of allocations in a basic feasible solution of $m\times n$ transportation problem are less than $m+n-1$, then such a solution is called degenerate basic feasible solution, otherwise it is called non-degenerate basic feasible solution.
Optimum Solution
A feasible (not necessarily basic) is said to be optimal solution if it minimizes the total transportation cost.
Existence of feasible solution
A necessary and sufficient condition for the existence of feasible solution of a transportation problem is $\sum_i a_i = \sum_j b_j$ for $i=1,2,\ldots, m$ and $j=1,2,\ldots n$.
The number of basic variables in a transportation problem are at the most $m+n-1$.
Endnote
In this tutorial you learn about what is Transportation problem?, what is the mathematical formulation of Transportation Problem and important definitions related to transportation problem.
To learn more about transportation problem and methods of solving transportation problem, please refer to the following tutorials:
Let me know in the comments if you have any questions on Transportation Problem and your thoughts on this article.
