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

---

---