1. Find Solution using Voggel's Approximation method, also find optimal solution using modi 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

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	19	30	50	10		7	`9=19-10`
`S_2`	70	30	40	60		9	`10=40-30`
`S_3`	40	8	70	20		18	`12=20-8`
Demand	5	8	7	14
Column Penalty	`21=40-19`	`22=30-8`	`10=50-40`	`10=20-10`

The maximum penalty, 22, occurs in column `D_2`.

The minimum `c_(ij)` in this column is `c_32` = 8.

The maximum allocation in this cell is min(18,8) = 8.
It satisfy demand of `D_2` and adjust the supply of `S_3` from 18 to 10 (18 - 8 = 10).

Table-2

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	19	30	50	10		7	`9=19-10`
`S_2`	70	30	40	60		9	`20=60-40`
`S_3`	40	8(8)	70	20		10	`20=40-20`
Demand	5	0	7	14
Column Penalty	`21=40-19`	--	`10=50-40`	`10=20-10`

The maximum penalty, 21, occurs in column `D_1`.

The minimum `c_(ij)` in this column is `c_11` = 19.

The maximum allocation in this cell is min(7,5) = 5.
It satisfy demand of `D_1` and adjust the supply of `S_1` from 7 to 2 (7 - 5 = 2).

Table-3

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

The maximum penalty, 50, occurs in row `S_3`.

The minimum `c_(ij)` in this row is `c_34` = 20.

The maximum allocation in this cell is min(10,14) = 10.
It satisfy supply of `S_3` and adjust the demand of `D_4` from 14 to 4 (14 - 10 = 4).

Table-4

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

The maximum penalty, 50, occurs in column `D_4`.

The minimum `c_(ij)` in this column is `c_14` = 10.

The maximum allocation in this cell is min(2,4) = 2.
It satisfy supply of `S_1` and adjust the demand of `D_4` from 4 to 2 (4 - 2 = 2).

Table-5

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	19(5)	30	50	10(2)		0	--
`S_2`	70	30	40	60		9	`20=60-40`
`S_3`	40	8(8)	70	20(10)		0	--
Demand	0	0	7	2
Column Penalty	--	--	`40`	`60`

The maximum penalty, 60, occurs in column `D_4`.

The minimum `c_(ij)` in this column is `c_24` = 60.

The maximum allocation in this cell is min(9,2) = 2.
It satisfy demand of `D_4` and adjust the supply of `S_2` from 9 to 7 (9 - 2 = 7).

Table-6

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

The maximum penalty, 40, occurs in row `S_2`.

The minimum `c_(ij)` in this row is `c_23` = 40.

The maximum allocation in this cell is min(7,7) = 7.
It satisfy supply of `S_2` and demand of `D_3`.


Initial feasible solution is

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	19(5)	30	50	10(2)		7	9 |  9 | 40 | 40 | -- | -- |
`S_2`	70	30	40(7)	60(2)		9	10 | 20 | 20 | 20 | 20 | 40 |
`S_3`	40	8(8)	70	20(10)		18	12 | 20 | 50 | -- | -- | -- |
Demand	5	8	7	14
Column Penalty	21 21 -- -- -- --	22 -- -- -- -- --	10 10 10 10 40 40	10 10 10 50 60 --

The minimum total transportation cost `= 19 xx 5 + 10 xx 2 + 40 xx 7 + 60 xx 2 + 8 xx 8 + 20 xx 10 = 779`

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

---

Optimality test using modi method...
Allocation Table is

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

Iteration-1 of optimality test
1. Find `u_i` and `v_j` for all occupied cells(i,j), where `c_(ij) = u_i + v_j`

`1.` Substituting, `v_4 = 0`, we get

`2. c_14 = u_1 + v_4=>u_1 = c_14 - v_4=>u_1 = 10 -0=>u_1 = 10`

`3. c_11 = u_1 + v_1=>v_1 = c_11 - u_1=>v_1 = 19 -10=>v_1 = 9`

`4. c_24 = u_2 + v_4=>u_2 = c_24 - v_4=>u_2 = 60 -0=>u_2 = 60`

`5. c_23 = u_2 + v_3=>v_3 = c_23 - u_2=>v_3 = 40 -60=>v_3 = -20`

`6. c_34 = u_3 + v_4=>u_3 = c_34 - v_4=>u_3 = 20 -0=>u_3 = 20`

`7. c_32 = u_3 + v_2=>v_2 = c_32 - u_3=>v_2 = 8 -20=>v_2 = -12`

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`u_i`
`S_1`	19 (5)	30	50	10 (2)		7	`u_1=10`
`S_2`	70	30	40 (7)	60 (2)		9	`u_2=60`
`S_3`	40	8 (8)	70	20 (10)		18	`u_3=20`
Demand	5	8	7	14
`v_j`	`v_1=9`	`v_2=-12`	`v_3=-20`	`v_4=0`

2. Find `d_(ij)` for all unoccupied cells(i,j), where `d_(ij) = c_(ij) - (u_i + v_j)`

`1. d_12 = c_12 - (u_1 + v_2) = 30 - (10 -12) = color{blue}{32} `

`2. d_13 = c_13 - (u_1 + v_3) = 50 - (10 -20) = color{blue}{60} `

`3. d_21 = c_21 - (u_2 + v_1) = 70 - (60 +9) = color{blue}{1} `

`4. d_22 = c_22 - (u_2 + v_2) = 30 - (60 -12) = color{blue}{-18} `

`5. d_31 = c_31 - (u_3 + v_1) = 40 - (20 +9) = color{blue}{11} `

`6. d_33 = c_33 - (u_3 + v_3) = 70 - (20 -20) = color{blue}{70} `

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`u_i`
`S_1`	19 (5)	30 [32]	50 [60]	10 (2)		7	`u_1=10`
`S_2`	70 [1]	30 [-18]	40 (7)	60 (2)		9	`u_2=60`
`S_3`	40 [11]	8 (8)	70 [70]	20 (10)		18	`u_3=20`
Demand	5	8	7	14
`v_j`	`v_1=9`	`v_2=-12`	`v_3=-20`	`v_4=0`

3. Now choose the minimum negative value from all `d_(ij)` (opportunity cost) = `d_(22` = [-18]

and draw a closed path from `S_2D_2`.

Closed path is `S_2D_2->S_2D_4->S_3D_4->S_3D_2`

Closed path and plus/minus sign allocation...

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`u_i`
`S_1`	19 (5)	30 [32]	50 [60]	10 (2)		7	`u_1=10`
`S_2`	70 [1]	30 [-18] (+)	40 (7)	60 (2) (-)		9	`u_2=60`
`S_3`	40 [11]	8 (8) (-)	70 [70]	20 (10) (+)		18	`u_3=20`
Demand	5	8	7	14
`v_j`	`v_1=9`	`v_2=-12`	`v_3=-20`	`v_4=0`

4. Minimum allocated value among all negative position (-) on closed path = 2
Substract 2 from all (-) and Add it to all (+)

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

5. Repeat the step 1 to 4, until an optimal solution is obtained.

---

Iteration-2 of optimality test
1. Find `u_i` and `v_j` for all occupied cells(i,j), where `c_(ij) = u_i + v_j`

`1.` Substituting, `u_1 = 0`, we get

`2. c_11 = u_1 + v_1=>v_1 = c_11 - u_1=>v_1 = 19 -0=>v_1 = 19`

`3. c_14 = u_1 + v_4=>v_4 = c_14 - u_1=>v_4 = 10 -0=>v_4 = 10`

`4. c_34 = u_3 + v_4=>u_3 = c_34 - v_4=>u_3 = 20 -10=>u_3 = 10`

`5. c_32 = u_3 + v_2=>v_2 = c_32 - u_3=>v_2 = 8 -10=>v_2 = -2`

`6. c_22 = u_2 + v_2=>u_2 = c_22 - v_2=>u_2 = 30 +2=>u_2 = 32`

`7. c_23 = u_2 + v_3=>v_3 = c_23 - u_2=>v_3 = 40 -32=>v_3 = 8`

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`u_i`
`S_1`	19 (5)	30	50	10 (2)		7	`u_1=0`
`S_2`	70	30 (2)	40 (7)	60		9	`u_2=32`
`S_3`	40	8 (6)	70	20 (12)		18	`u_3=10`
Demand	5	8	7	14
`v_j`	`v_1=19`	`v_2=-2`	`v_3=8`	`v_4=10`

2. Find `d_(ij)` for all unoccupied cells(i,j), where `d_(ij) = c_(ij) - (u_i + v_j)`

`1. d_12 = c_12 - (u_1 + v_2) = 30 - (0 -2) = color{blue}{32} `

`2. d_13 = c_13 - (u_1 + v_3) = 50 - (0 +8) = color{blue}{42} `

`3. d_21 = c_21 - (u_2 + v_1) = 70 - (32 +19) = color{blue}{19} `

`4. d_24 = c_24 - (u_2 + v_4) = 60 - (32 +10) = color{blue}{18} `

`5. d_31 = c_31 - (u_3 + v_1) = 40 - (10 +19) = color{blue}{11} `

`6. d_33 = c_33 - (u_3 + v_3) = 70 - (10 +8) = color{blue}{52} `

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	`u_i`
`S_1`	19 (5)	30 [32]	50 [42]	10 (2)		7	`u_1=0`
`S_2`	70 [19]	30 (2)	40 (7)	60 [18]		9	`u_2=32`
`S_3`	40 [11]	8 (6)	70 [52]	20 (12)		18	`u_3=10`
Demand	5	8	7	14
`v_j`	`v_1=19`	`v_2=-2`	`v_3=8`	`v_4=10`

Since all `d_(ij)>=0`.

So final optimal solution is arrived.

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

The minimum total transportation cost `= 19 xx 5 + 10 xx 2 + 30 xx 2 + 40 xx 7 + 8 xx 6 + 20 xx 12 = 743`