1. Find Solution using Voggel's Approximation method, also find optimal solution using stepping stone 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 stepping stone 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. Create closed loop for unoccupied cells, we get

Unoccupied cell	Closed path	Net cost change
`S_1D_2`	`S_1D_2->S_1D_4->S_3D_4->S_3D_2`	30 - 10 + 20 - 8 = 32
`S_1D_3`	`S_1D_3->S_1D_4->S_2D_4->S_2D_3`	50 - 10 + 60 - 40 = 60
`S_2D_1`	`S_2D_1->S_2D_4->S_1D_4->S_1D_1`	70 - 60 + 10 - 19 = 1
`S_2D_2`	`S_2D_2->S_2D_4->S_3D_4->S_3D_2`	30 - 60 + 20 - 8 = -18
`S_3D_1`	`S_3D_1->S_3D_4->S_1D_4->S_1D_1`	40 - 20 + 10 - 19 = 11
`S_3D_3`	`S_3D_3->S_3D_4->S_2D_4->S_2D_3`	70 - 20 + 60 - 40 = 70

2. Select the unoccupied cell having the highest negative net cost change i.e. cell `S_2D_2=-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 allocation for current unoccupied cell `S_2D_2`

	`D_1`	`D_2`	`D_3`	`D_4`		Supply
`S_1`	19 (5)	30 [32]	50 [60]	10 (2)		7
`S_2`	70 [1]	30 [-18] (+)	40 (7)	60 (2) (-)		9
`S_3`	40 [11]	8 (8) (-)	70 [70]	20 (10) (+)		18
Demand	5	8	7	14

3. 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

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

---

Iteration-2 of optimality test

1. Create closed loop for unoccupied cells, we get

Unoccupied cell	Closed path	Net cost change
`S_1D_2`	`S_1D_2->S_1D_4->S_3D_4->S_3D_2`	30 - 10 + 20 - 8 = 32
`S_1D_3`	`S_1D_3->S_1D_4->S_3D_4->S_3D_2->S_2D_2->S_2D_3`	50 - 10 + 20 - 8 + 30 - 40 = 42
`S_2D_1`	`S_2D_1->S_2D_2->S_3D_2->S_3D_4->S_1D_4->S_1D_1`	70 - 30 + 8 - 20 + 10 - 19 = 19
`S_2D_4`	`S_2D_4->S_2D_2->S_3D_2->S_3D_4`	60 - 30 + 8 - 20 = 18
`S_3D_1`	`S_3D_1->S_3D_4->S_1D_4->S_1D_1`	40 - 20 + 10 - 19 = 11
`S_3D_3`	`S_3D_3->S_3D_2->S_2D_2->S_2D_3`	70 - 8 + 30 - 40 = 52

Since all net cost change `>=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`