1. Introduction
Transportation problem is a special kind of Linear Programming Problem in which goods are transported from supply source to demand destination, such that the total transportation cost is minimized.
| `D_1` | `D_2` | `D_3` | `D_4` | Supply | | `S_1` |
`c_11` `(x_11)` |
`c_12` `(x_12)` |
`c_13` `(x_13)` |
`c_14` `(x_14)` |
`s_1` | | `S_2` |
`c_21` `(x_21)` |
`c_22` `(x_22)` |
`c_23` `(x_23)` |
`c_24` `(x_24)` |
`s_2` | | `S_3` |
`c_31` `(x_31)` |
`c_32` `(x_32)` |
`c_33` `(x_33)` |
`c_34` `(x_34)` |
`s_3` | | Demand |
`d_1` |
`d_2` |
`d_3` |
`d_4` | |
Here
`S_1,S_2,S_3` are supply source (total m supply)
`D_1,D_2,D_3,D_4` are demand destinations (total n demand)
`c_(ij)` is cost of transportation from source i to destination j
`x_(ij)` is number of transpored units from source i to destination j,
`s_1,s_2,s_3` are supply capacity of `S_1,S_2,S_3`
`d_1,d_2,d_3,d_4` are demand requirement of `D_1,D_2,D_3,D_4`
General Mathematical Model
minimize `sum_{i=1}^{m}\ sum_{j=1}^{n} c_(ij)*x_(ij)`
subject to
`sum_{j=1}^{n} x_(ij)= s_(i)` (supply constraints)
`sum_{i=1}^{m} x_(ij)= d_(j)` (demand constraints)
and `x_(ij)>=0`
For feasible solution
Total supply must be equal to Total demand
`sum_{i=1}^{m} s_i=sum_{j=1}^{n} d_j`
Notes (Basic Info):
1. If Total supply = Total demand then the problem is called balanced transportation problem,
otherwise it is called an unbalanced transportation problem.
2. For unbalanced transportation problem, we have to add either a dummy row or a dummy column (with 0 cell values) to make it balanced.
3. If Cells in the table has positive allocation (xij > 0) then it is called occupied cells, otherwise called empty cells.
4. If the number of allocations of the feasible solution is equal to m + n - 1, then it is called non-degenerate solution
Transportation Problem Algorithm
1. arrange problem data in the matrix form
2. Find the initial basic feasible solution using
- North West Corner Method
- Least Cost Method (Matrix Minima Method)
- Vogel's Approximation Method
- Row minima method
- Column minima method
- Russell's approximation method
- Heuristic method
3. Optimality Test using
- Modified Distribution Method (MODI)
- Stepping Stone Method
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
