Find Solution using Voggel's Approximation method, also find optimal solution using stepping stone method

	D1	D2	D3	D4	Supply
S1	11	13	17	14	250
S2	16	18	14	10	300
S3	21	24	13	10	400
Demand	200	225	275	250

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`	11	13	17	14		250
`S_2`	16	18	14	10		300
`S_3`	21	24	13	10		400
Demand	200	225	275	250

Table-1

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11	13	17	14		250	`2=13-11`
`S_2`	16	18	14	10		300	`4=14-10`
`S_3`	21	24	13	10		400	`3=13-10`
Demand	200	225	275	250
Column Penalty	`5=16-11`	`5=18-13`	`1=14-13`	`0=10-10`

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

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

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

Table-2

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11(200)	13	17	14		50	`1=14-13`
`S_2`	16	18	14	10		300	`4=14-10`
`S_3`	21	24	13	10		400	`3=13-10`
Demand	0	225	275	250
Column Penalty	--	`5=18-13`	`1=14-13`	`0=10-10`

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

The minimum `c_(ij)` in this column is `c_12` = 13.

The maximum allocation in this cell is min(50,225) = 50.
It satisfy supply of `S_1` and adjust the demand of `D_2` from 225 to 175 (225 - 50 = 175).

Table-3

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11(200)	13(50)	17	14		0	--
`S_2`	16	18	14	10		300	`4=14-10`
`S_3`	21	24	13	10		400	`3=13-10`
Demand	0	175	275	250
Column Penalty	--	`6=24-18`	`1=14-13`	`0=10-10`

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

The minimum `c_(ij)` in this column is `c_22` = 18.

The maximum allocation in this cell is min(300,175) = 175.
It satisfy demand of `D_2` and adjust the supply of `S_2` from 300 to 125 (300 - 175 = 125).

Table-4

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11(200)	13(50)	17	14		0	--
`S_2`	16	18(175)	14	10		125	`4=14-10`
`S_3`	21	24	13	10		400	`3=13-10`
Demand	0	0	275	250
Column Penalty	--	--	`1=14-13`	`0=10-10`

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

The minimum `c_(ij)` in this row is `c_24` = 10.

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

Table-5

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11(200)	13(50)	17	14		0	--
`S_2`	16	18(175)	14	10(125)		0	--
`S_3`	21	24	13	10		400	`3=13-10`
Demand	0	0	275	125
Column Penalty	--	--	`13`	`10`

The maximum penalty, 13, occurs in column `D_3`.

The minimum `c_(ij)` in this column is `c_33` = 13.

The maximum allocation in this cell is min(400,275) = 275.
It satisfy demand of `D_3` and adjust the supply of `S_3` from 400 to 125 (400 - 275 = 125).

Table-6

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11(200)	13(50)	17	14		0	--
`S_2`	16	18(175)	14	10(125)		0	--
`S_3`	21	24	13(275)	10		125	`10`
Demand	0	0	0	125
Column Penalty	--	--	--	`10`

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

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

The maximum allocation in this cell is min(125,125) = 125.
It satisfy supply of `S_3` and demand of `D_4`.


Initial feasible solution is

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11(200)	13(50)	17	14		250	2 |  1 | -- | -- | -- | -- |
`S_2`	16	18(175)	14	10(125)		300	4 |  4 |  4 |  4 | -- | -- |
`S_3`	21	24	13(275)	10(125)		400	3 |  3 |  3 |  3 |  3 | 10 |
Demand	200	225	275	250
Column Penalty	5 -- -- -- -- --	5 5 6 -- -- --	1 1 1 1 13 --	0 0 0 0 10 10

The minimum total transportation cost `= 11 xx 200 + 13 xx 50 + 18 xx 175 + 10 xx 125 + 13 xx 275 + 10 xx 125 = 12075`

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`	11 (200)	13 (50)	17	14		250
`S_2`	16	18 (175)	14	10 (125)		300
`S_3`	21	24	13 (275)	10 (125)		400
Demand	200	225	275	250

Iteration-1 of optimality test

1. Create closed loop for unoccupied cells, we get

Unoccupied cell	Closed path	Net cost change
`S_1D_3`	`S_1D_3->S_1D_2->S_2D_2->S_2D_4->S_3D_4->S_3D_3`	17 - 13 + 18 - 10 + 10 - 13 = 9
`S_1D_4`	`S_1D_4->S_1D_2->S_2D_2->S_2D_4`	14 - 13 + 18 - 10 = 9
`S_2D_1`	`S_2D_1->S_2D_2->S_1D_2->S_1D_1`	16 - 18 + 13 - 11 = 0
`S_2D_3`	`S_2D_3->S_2D_4->S_3D_4->S_3D_3`	14 - 10 + 10 - 13 = 1
`S_3D_1`	`S_3D_1->S_3D_4->S_2D_4->S_2D_2->S_1D_2->S_1D_1`	21 - 10 + 10 - 18 + 13 - 11 = 5
`S_3D_2`	`S_3D_2->S_3D_4->S_2D_4->S_2D_2`	24 - 10 + 10 - 18 = 6

Since all net cost change `>=0`

So final optimal solution is arrived.

	`D_1`	`D_2`	`D_3`	`D_4`		Supply
`S_1`	11 (200)	13 (50)	17	14		250
`S_2`	16	18 (175)	14	10 (125)		300
`S_3`	21	24	13 (275)	10 (125)		400
Demand	200	225	275	250

The minimum total transportation cost `= 11 xx 200 + 13 xx 50 + 18 xx 175 + 10 xx 125 + 13 xx 275 + 10 xx 125 = 12075`

Notice alternate solution is available with unoccupied cell `S_2D_1=0`, but with the same optimal value.

---