Prohibited Routes
There may be situations where it is not possible to use certain routes in a transportation problem. For example, strike, unexpected floods, local traffic rules, road construction etc.
A very large cost represented by M or - is assigned to each of such routes, which are not available.
Note : I have used 999999 to represent this in the calculation
Example
Find Solution using Least Cost method
| D1 | D2 | D3 | Supply |
| S1 | 16 | - | 12 | 200 |
| S2 | 14 | 8 | 18 | 160 |
| S3 | 26 | - | 16 | 90 |
| Demand | 180 | 120 | 150 | |
Solution:
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 3
Problem Table is
| | `D_1` | `D_2` | `D_3` | | Supply |
| `S_1` | 16 | 999999 | 12 | | 200 |
| `S_2` | 14 | 8 | 18 | | 160 |
| `S_3` | 26 | 999999 | 16 | | 90 |
| |
| Demand | 180 | 120 | 150 | | |
The smallest transportation cost is 8 in cell `S_2 D_2`
The allocation to this cell is min(160,120) = 120.
This satisfies the entire demand of `D_2` and leaves 160 - 120=40 units with `S_2`
Table-1
| | `D_1` | `D_2` | `D_3` | | Supply |
| `S_1` | 16 | 999999 | 12 | | 200 |
| `S_2` | 14 | 8(120) | 18 | | 40 |
| `S_3` | 26 | 999999 | 16 | | 90 |
| |
| Demand | 180 | 0 | 150 | | |
The smallest transportation cost is 12 in cell `S_1 D_3`
The allocation to this cell is min(200,150) = 150.
This satisfies the entire demand of `D_3` and leaves 200 - 150=50 units with `S_1`
Table-2
| | `D_1` | `D_2` | `D_3` | | Supply |
| `S_1` | 16 | 999999 | 12(150) | | 50 |
| `S_2` | 14 | 8(120) | 18 | | 40 |
| `S_3` | 26 | 999999 | 16 | | 90 |
| |
| Demand | 180 | 0 | 0 | | |
The smallest transportation cost is 14 in cell `S_2 D_1`
The allocation to this cell is min(40,180) = 40.
This exhausts the capacity of `S_2` and leaves 180 - 40=140 units with `D_1`
Table-3
| | `D_1` | `D_2` | `D_3` | | Supply |
| `S_1` | 16 | 999999 | 12(150) | | 50 |
| `S_2` | 14(40) | 8(120) | 18 | | 0 |
| `S_3` | 26 | 999999 | 16 | | 90 |
| |
| Demand | 140 | 0 | 0 | | |
The smallest transportation cost is 16 in cell `S_1 D_1`
The allocation to this cell is min(50,140) = 50.
This exhausts the capacity of `S_1` and leaves 140 - 50=90 units with `D_1`
Table-4
| | `D_1` | `D_2` | `D_3` | | Supply |
| `S_1` | 16(50) | 999999 | 12(150) | | 0 |
| `S_2` | 14(40) | 8(120) | 18 | | 0 |
| `S_3` | 26 | 999999 | 16 | | 90 |
| |
| Demand | 90 | 0 | 0 | | |
The smallest transportation cost is 26 in cell `S_3 D_1`
The allocation to this cell is min(90,90) = 90.
Table-5
| | `D_1` | `D_2` | `D_3` | | Supply |
| `S_1` | 16(50) | 999999 | 12(150) | | 0 |
| `S_2` | 14(40) | 8(120) | 18 | | 0 |
| `S_3` | 26(90) | 999999 | 16 | | 0 |
| |
| Demand | 0 | 0 | 0 | | |
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | | Supply |
| `S_1` | 16 (50) | 999999 | 12 (150) | | 200 |
| `S_2` | 14 (40) | 8 (120) | 18 | | 160 |
| `S_3` | 26 (90) | 999999 | 16 | | 90 |
| |
| Demand | 180 | 120 | 150 | | |
The minimum total transportation cost `=16 xx 50+12 xx 150+14 xx 40+8 xx 120+26 xx 90=6460`
Here, the number of allocated cells = 5 is equal to m + n - 1 = 3 + 3 - 1 = 5
`:.` This solution is non-degenerate
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
