1. Find Solution using Russell's Approximation method

	D1	D2	D3	D4	Supply
S1	19	30	50	10	7
S2	70	30	40	60	9
S3	40	8	70	20	18
Demand	5	8	7	14

Solution:
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 4
Problem Table is

	`D_1`	`D_2`	`D_3`	`D_4`		Supply
`S_1`	19	30	50	10		7
`S_2`	70	30	40	60		9
`S_3`	40	8	70	20		18
Demand	5	8	7	14

Table-1: Calculate `bar U_i` and `bar V_j` (where `bar U_i` is the largest cost in row and `bar V_j` is the largest cost in column)

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19	30	50	10		7	`50`
`S_2`	70	30	40	60		9	`70`
`S_3`	40	8	70	20		18	`70`
Demand	5	8	7	14
`bar V_j`	`70`	`30`	`70`	`60`

2. Compute reduced cost of each cell `Delta_(ij)`, where `Delta_(ij) = c_(ij) - (bar U_i + bar V_j)`

`1. Delta_11 = c_11 - (bar U_1 + bar V_1) = 19 - (50 +70) = color{blue}{-101} `

`2. Delta_12 = c_12 - (bar U_1 + bar V_2) = 30 - (50 +30) = color{blue}{-50} `

`3. Delta_13 = c_13 - (bar U_1 + bar V_3) = 50 - (50 +70) = color{blue}{-70} `

`4. Delta_14 = c_14 - (bar U_1 + bar V_4) = 10 - (50 +60) = color{blue}{-100} `

`5. Delta_21 = c_21 - (bar U_2 + bar V_1) = 70 - (70 +70) = color{blue}{-70} `

`6. Delta_22 = c_22 - (bar U_2 + bar V_2) = 30 - (70 +30) = color{blue}{-70} `

`7. Delta_23 = c_23 - (bar U_2 + bar V_3) = 40 - (70 +70) = color{blue}{-100} `

`8. Delta_24 = c_24 - (bar U_2 + bar V_4) = 60 - (70 +60) = color{blue}{-70} `

`9. Delta_31 = c_31 - (bar U_3 + bar V_1) = 40 - (70 +70) = color{blue}{-100} `

`10. Delta_32 = c_32 - (bar U_3 + bar V_2) = 8 - (70 +30) = color{blue}{-92} `

`11. Delta_33 = c_33 - (bar U_3 + bar V_3) = 70 - (70 +70) = color{blue}{-70} `

`12. Delta_34 = c_34 - (bar U_3 + bar V_4) = 20 - (70 +60) = color{blue}{-110} `

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19 [-101]	30 [-50]	50 [-70]	10 [-100]		7	`50`
`S_2`	70 [-70]	30 [-70]	40 [-100]	60 [-70]		9	`70`
`S_3`	40 [-100]	8 [-92]	70 [-70]	20 [-110]		18	`70`
Demand	5	8	7	14
`bar V_j`	`70`	`30`	`70`	`60`

The most negative `Delta_(ij)` is -110 in cell `S_3 D_4`

The allocation to this cell is min(18,14) = 14.
This satisfies the entire demand of `D_4` and leaves 18 - 14 = 4 units with `S_3`

Table-1: This leads to the following table

	`D_1`	`D_2`	`D_3`	`D_4`		Supply
`S_1`	19	30	50	10		7
`S_2`	70	30	40	60		9
`S_3`	40	8	70	20 (14)		4
Demand	5	8	7	0

Table-2: Calculate `bar U_i` and `bar V_j` (where `bar U_i` is the largest cost in row and `bar V_j` is the largest cost in column)

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19	30	50	10		7	`50`
`S_2`	70	30	40	60		9	`70`
`S_3`	40	8	70	20(14)		4	`70`
Demand	5	8	7	0
`bar V_j`	`70`	`30`	`70`	--

2. Compute reduced cost of each cell `Delta_(ij)`, where `Delta_(ij) = c_(ij) - (bar U_i + bar V_j)`

`1. Delta_11 = c_11 - (bar U_1 + bar V_1) = 19 - (50 +70) = color{blue}{-101} `

`2. Delta_12 = c_12 - (bar U_1 + bar V_2) = 30 - (50 +30) = color{blue}{-50} `

`3. Delta_13 = c_13 - (bar U_1 + bar V_3) = 50 - (50 +70) = color{blue}{-70} `

`4. Delta_21 = c_21 - (bar U_2 + bar V_1) = 70 - (70 +70) = color{blue}{-70} `

`5. Delta_22 = c_22 - (bar U_2 + bar V_2) = 30 - (70 +30) = color{blue}{-70} `

`6. Delta_23 = c_23 - (bar U_2 + bar V_3) = 40 - (70 +70) = color{blue}{-100} `

`7. Delta_31 = c_31 - (bar U_3 + bar V_1) = 40 - (70 +70) = color{blue}{-100} `

`8. Delta_32 = c_32 - (bar U_3 + bar V_2) = 8 - (70 +30) = color{blue}{-92} `

`9. Delta_33 = c_33 - (bar U_3 + bar V_3) = 70 - (70 +70) = color{blue}{-70} `

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19 [-101]	30 [-50]	50 [-70]	10		7	`50`
`S_2`	70 [-70]	30 [-70]	40 [-100]	60		9	`70`
`S_3`	40 [-100]	8 [-92]	70 [-70]	20(14)		4	`70`
Demand	5	8	7	0
`bar V_j`	`70`	`30`	`70`	--

The most negative `Delta_(ij)` is -101 in cell `S_1 D_1`

The allocation to this cell is min(7,5) = 5.
This satisfies the entire demand of `D_1` and leaves 7 - 5 = 2 units with `S_1`

Table-2: This leads to the following table

	`D_1`	`D_2`	`D_3`	`D_4`		Supply
`S_1`	19 (5)	30	50	10		2
`S_2`	70	30	40	60		9
`S_3`	40	8	70	20 (14)		4
Demand	0	8	7	0

Table-3: Calculate `bar U_i` and `bar V_j` (where `bar U_i` is the largest cost in row and `bar V_j` is the largest cost in column)

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19(5)	30	50	10		2	`50`
`S_2`	70	30	40	60		9	`40`
`S_3`	40	8	70	20(14)		4	`70`
Demand	0	8	7	0
`bar V_j`	--	`30`	`70`	--

2. Compute reduced cost of each cell `Delta_(ij)`, where `Delta_(ij) = c_(ij) - (bar U_i + bar V_j)`

`1. Delta_12 = c_12 - (bar U_1 + bar V_2) = 30 - (50 +30) = color{blue}{-50} `

`2. Delta_13 = c_13 - (bar U_1 + bar V_3) = 50 - (50 +70) = color{blue}{-70} `

`3. Delta_22 = c_22 - (bar U_2 + bar V_2) = 30 - (40 +30) = color{blue}{-40} `

`4. Delta_23 = c_23 - (bar U_2 + bar V_3) = 40 - (40 +70) = color{blue}{-70} `

`5. Delta_32 = c_32 - (bar U_3 + bar V_2) = 8 - (70 +30) = color{blue}{-92} `

`6. Delta_33 = c_33 - (bar U_3 + bar V_3) = 70 - (70 +70) = color{blue}{-70} `

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19(5)	30 [-50]	50 [-70]	10		2	`50`
`S_2`	70	30 [-40]	40 [-70]	60		9	`40`
`S_3`	40	8 [-92]	70 [-70]	20(14)		4	`70`
Demand	0	8	7	0
`bar V_j`	--	`30`	`70`	--

The most negative `Delta_(ij)` is -92 in cell `S_3 D_2`

The allocation to this cell is min(4,8) = 4.
This exhausts the capacity of `S_3` and leaves 8 - 4 = 4 units with `D_2`

Table-3: This leads to the following table

	`D_1`	`D_2`	`D_3`	`D_4`		Supply
`S_1`	19 (5)	30	50	10		2
`S_2`	70	30	40	60		9
`S_3`	40	8 (4)	70	20 (14)		0
Demand	0	4	7	0

Table-4: Calculate `bar U_i` and `bar V_j` (where `bar U_i` is the largest cost in row and `bar V_j` is the largest cost in column)

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19(5)	30	50	10		2	`50`
`S_2`	70	30	40	60		9	`40`
`S_3`	40	8(4)	70	20(14)		0	--
Demand	0	4	7	0
`bar V_j`	--	`30`	`50`	--

2. Compute reduced cost of each cell `Delta_(ij)`, where `Delta_(ij) = c_(ij) - (bar U_i + bar V_j)`

`1. Delta_12 = c_12 - (bar U_1 + bar V_2) = 30 - (50 +30) = color{blue}{-50} `

`2. Delta_13 = c_13 - (bar U_1 + bar V_3) = 50 - (50 +50) = color{blue}{-50} `

`3. Delta_22 = c_22 - (bar U_2 + bar V_2) = 30 - (40 +30) = color{blue}{-40} `

`4. Delta_23 = c_23 - (bar U_2 + bar V_3) = 40 - (40 +50) = color{blue}{-50} `

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19(5)	30 [-50]	50 [-50]	10		2	`50`
`S_2`	70	30 [-40]	40 [-50]	60		9	`40`
`S_3`	40	8(4)	70	20(14)		0	--
Demand	0	4	7	0
`bar V_j`	--	`30`	`50`	--

The most negative `Delta_(ij)` is -50 in cell `S_2 D_3`

The allocation to this cell is min(9,7) = 7.
This satisfies the entire demand of `D_3` and leaves 9 - 7 = 2 units with `S_2`

Table-4: This leads to the following table

	`D_1`	`D_2`	`D_3`	`D_4`		Supply
`S_1`	19 (5)	30	50	10		2
`S_2`	70	30	40 (7)	60		2
`S_3`	40	8 (4)	70	20 (14)		0
Demand	0	4	0	0

Table-5: Calculate `bar U_i` and `bar V_j` (where `bar U_i` is the largest cost in row and `bar V_j` is the largest cost in column)

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19(5)	30	50	10		2	`30`
`S_2`	70	30	40(7)	60		2	`30`
`S_3`	40	8(4)	70	20(14)		0	--
Demand	0	4	0	0
`bar V_j`	--	`30`	--	--

2. Compute reduced cost of each cell `Delta_(ij)`, where `Delta_(ij) = c_(ij) - (bar U_i + bar V_j)`

`1. Delta_12 = c_12 - (bar U_1 + bar V_2) = 30 - (30 +30) = color{blue}{-30} `

`2. Delta_22 = c_22 - (bar U_2 + bar V_2) = 30 - (30 +30) = color{blue}{-30} `

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19(5)	30 [-30]	50	10		2	`30`
`S_2`	70	30 [-30]	40(7)	60		2	`30`
`S_3`	40	8(4)	70	20(14)		0	--
Demand	0	4	0	0
`bar V_j`	--	`30`	--	--

The most negative `Delta_(ij)` is -30 in cell `S_1 D_2`

The allocation to this cell is min(2,4) = 2.
This exhausts the capacity of `S_1` and leaves 4 - 2 = 2 units with `D_2`

Table-5: This leads to the following table

	`D_1`	`D_2`	`D_3`	`D_4`		Supply
`S_1`	19 (5)	30 (2)	50	10		0
`S_2`	70	30	40 (7)	60		2
`S_3`	40	8 (4)	70	20 (14)		0
Demand	0	2	0	0

Table-6: Calculate `bar U_i` and `bar V_j` (where `bar U_i` is the largest cost in row and `bar V_j` is the largest cost in column)

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19(5)	30(2)	50	10		0	--
`S_2`	70	30	40(7)	60		2	`30`
`S_3`	40	8(4)	70	20(14)		0	--
Demand	0	2	0	0
`bar V_j`	--	`30`	--	--

2. Compute reduced cost of each cell `Delta_(ij)`, where `Delta_(ij) = c_(ij) - (bar U_i + bar V_j)`

`1. Delta_22 = c_22 - (bar U_2 + bar V_2) = 30 - (30 +30) = color{blue}{-30} `

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`bar U_i`
`S_1`	19(5)	30(2)	50	10		0	--
`S_2`	70	30 [-30]	40(7)	60		2	`30`
`S_3`	40	8(4)	70	20(14)		0	--
Demand	0	2	0	0
`bar V_j`	--	`30`	--	--

The most negative `Delta_(ij)` is -30 in cell `S_2 D_2`

The allocation to this cell is min(2,2) = 2.
Table-6: This leads to the following table

	`D_1`	`D_2`	`D_3`	`D_4`		Supply
`S_1`	19 (5)	30 (2)	50	10		0
`S_2`	70	30 (2)	40 (7)	60		0
`S_3`	40	8 (4)	70	20 (14)		0
Demand	0	0	0	0

Initial feasible solution is

	`D_1`	`D_2`	`D_3`	`D_4`		Supply
`S_1`	19 (5)	30 (2)	50	10		7
`S_2`	70	30 (2)	40 (7)	60		9
`S_3`	40	8 (4)	70	20 (14)		18
Demand	5	8	7	14

The minimum total transportation cost `= 19 xx 5 + 30 xx 2 + 30 xx 2 + 40 xx 7 + 8 xx 4 + 20 xx 14 = 807`

Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
`:.` This solution is non-degenerate