1. Find Solution of Transshipment Problem using vogel's approximation method

	S1	S2	S3	S4	D1	D2	Supply
S1	0	4	20	5	25	12	100
S2	10	0	6	10	5	20	200
S3	15	20	0	8	45	7	150
S4	20	25	10	0	30	6	350
D1	20	18	60	15	0	10	0
D2	10	25	30	23	4	0	0
Demand	0	0	0	0	350	450

Solution:
Problem Table is

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply
`S_1`	0	4	20	5	25	12		100
`S_2`	10	0	6	10	5	20		200
`S_3`	15	20	0	8	45	7		150
`S_4`	20	25	10	0	30	6		350
`D_1`	20	18	60	15	0	10		0
`D_2`	10	25	30	23	4	0		0
Demand	0	0	0	0	350	450

`S_1,S_2,S_3,S_4,D_1,D_2` are transshipment nodes

Add Total value `=800` in supply and demand for transshipment nodes `S_1,S_2,S_3,S_4,D_1,D_2`

So again Problem Table is

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply
`S_1`	0	4	20	5	25	12		900
`S_2`	10	0	6	10	5	20		1000
`S_3`	15	20	0	8	45	7		950
`S_4`	20	25	10	0	30	6		1150
`D_1`	20	18	60	15	0	10		800
`D_2`	10	25	30	23	4	0		800
Demand	800	800	800	800	1150	1250

Now, we solve this Transshipment problem
Table-1

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0	4	20	5	25	12		900	`4=4-0`
`S_2`	10	0	6	10	5	20		1000	`5=5-0`
`S_3`	15	20	0	8	45	7		950	`7=7-0`
`S_4`	20	25	10	0	30	6		1150	`6=6-0`
`D_1`	20	18	60	15	0	10		800	`10=10-0`
`D_2`	10	25	30	23	4	0		800	`4=4-0`
Demand	800	800	800	800	1150	1250
Column Penalty	`10=10-0`	`4=4-0`	`6=6-0`	`5=5-0`	`4=4-0`	`6=6-0`

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

The minimum `c_(ij)` in this row is `c_55`=0.

The maximum allocation in this cell is min(800,1150) = 800.
It satisfy supply of `D_1` and adjust the demand of `D_1` from 1150 to 350 (1150 - 800=350).

Table-2

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0	4	20	5	25	12		900	`4=4-0`
`S_2`	10	0	6	10	5	20		1000	`5=5-0`
`S_3`	15	20	0	8	45	7		950	`7=7-0`
`S_4`	20	25	10	0	30	6		1150	`6=6-0`
`D_1`	20	18	60	15	0(800)	10		0	--
`D_2`	10	25	30	23	4	0		800	`4=4-0`
Demand	800	800	800	800	350	1250
Column Penalty	`10=10-0`	`4=4-0`	`6=6-0`	`5=5-0`	`1=5-4`	`6=6-0`

The maximum penalty, 10, occurs in column `S_1`.

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

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

Table-3

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0(800)	4	20	5	25	12		100	`1=5-4`
`S_2`	10	0	6	10	5	20		1000	`5=5-0`
`S_3`	15	20	0	8	45	7		950	`7=7-0`
`S_4`	20	25	10	0	30	6		1150	`6=6-0`
`D_1`	20	18	60	15	0(800)	10		0	--
`D_2`	10	25	30	23	4	0		800	`4=4-0`
Demand	0	800	800	800	350	1250
Column Penalty	--	`4=4-0`	`6=6-0`	`5=5-0`	`1=5-4`	`6=6-0`

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

The minimum `c_(ij)` in this row is `c_33`=0.

The maximum allocation in this cell is min(950,800) = 800.
It satisfy demand of `S_3` and adjust the supply of `S_3` from 950 to 150 (950 - 800=150).

Table-4

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0(800)	4	20	5	25	12		100	`1=5-4`
`S_2`	10	0	6	10	5	20		1000	`5=5-0`
`S_3`	15	20	0(800)	8	45	7		150	`1=8-7`
`S_4`	20	25	10	0	30	6		1150	`6=6-0`
`D_1`	20	18	60	15	0(800)	10		0	--
`D_2`	10	25	30	23	4	0		800	`4=4-0`
Demand	0	800	0	800	350	1250
Column Penalty	--	`4=4-0`	--	`5=5-0`	`1=5-4`	`6=6-0`

The maximum penalty, 6, occurs in row `S_4`.

The minimum `c_(ij)` in this row is `c_44`=0.

The maximum allocation in this cell is min(1150,800) = 800.
It satisfy demand of `S_4` and adjust the supply of `S_4` from 1150 to 350 (1150 - 800=350).

Table-5

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0(800)	4	20	5	25	12		100	`8=12-4`
`S_2`	10	0	6	10	5	20		1000	`5=5-0`
`S_3`	15	20	0(800)	8	45	7		150	`13=20-7`
`S_4`	20	25	10	0(800)	30	6		350	`19=25-6`
`D_1`	20	18	60	15	0(800)	10		0	--
`D_2`	10	25	30	23	4	0		800	`4=4-0`
Demand	0	800	0	0	350	1250
Column Penalty	--	`4=4-0`	--	--	`1=5-4`	`6=6-0`

The maximum penalty, 19, occurs in row `S_4`.

The minimum `c_(ij)` in this row is `c_46`=6.

The maximum allocation in this cell is min(350,1250) = 350.
It satisfy supply of `S_4` and adjust the demand of `D_2` from 1250 to 900 (1250 - 350=900).

Table-6

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0(800)	4	20	5	25	12		100	`8=12-4`
`S_2`	10	0	6	10	5	20		1000	`5=5-0`
`S_3`	15	20	0(800)	8	45	7		150	`13=20-7`
`S_4`	20	25	10	0(800)	30	6(350)		0	--
`D_1`	20	18	60	15	0(800)	10		0	--
`D_2`	10	25	30	23	4	0		800	`4=4-0`
Demand	0	800	0	0	350	900
Column Penalty	--	`4=4-0`	--	--	`1=5-4`	`7=7-0`

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

The minimum `c_(ij)` in this row is `c_36`=7.

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

Table-7

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0(800)	4	20	5	25	12		100	`8=12-4`
`S_2`	10	0	6	10	5	20		1000	`5=5-0`
`S_3`	15	20	0(800)	8	45	7(150)		0	--
`S_4`	20	25	10	0(800)	30	6(350)		0	--
`D_1`	20	18	60	15	0(800)	10		0	--
`D_2`	10	25	30	23	4	0		800	`4=4-0`
Demand	0	800	0	0	350	750
Column Penalty	--	`4=4-0`	--	--	`1=5-4`	`12=12-0`

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

The minimum `c_(ij)` in this column is `c_66`=0.

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

Table-8

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0(800)	4	20	5	25	12		100	`21=25-4`
`S_2`	10	0	6	10	5	20		1000	`5=5-0`
`S_3`	15	20	0(800)	8	45	7(150)		0	--
`S_4`	20	25	10	0(800)	30	6(350)		0	--
`D_1`	20	18	60	15	0(800)	10		0	--
`D_2`	10	25	30	23	4	0(750)		50	`21=25-4`
Demand	0	800	0	0	350	0
Column Penalty	--	`4=4-0`	--	--	`1=5-4`	--

The maximum penalty, 21, occurs in row `S_1`.

The minimum `c_(ij)` in this row is `c_12`=4.

The maximum allocation in this cell is min(100,800) = 100.
It satisfy supply of `S_1` and adjust the demand of `S_2` from 800 to 700 (800 - 100=700).

Table-9

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0(800)	4(100)	20	5	25	12		0	--
`S_2`	10	0	6	10	5	20		1000	`5=5-0`
`S_3`	15	20	0(800)	8	45	7(150)		0	--
`S_4`	20	25	10	0(800)	30	6(350)		0	--
`D_1`	20	18	60	15	0(800)	10		0	--
`D_2`	10	25	30	23	4	0(750)		50	`21=25-4`
Demand	0	700	0	0	350	0
Column Penalty	--	`25=25-0`	--	--	`1=5-4`	--

The maximum penalty, 25, occurs in column `S_2`.

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

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

Table-10

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0(800)	4(100)	20	5	25	12		0	--
`S_2`	10	0(700)	6	10	5	20		300	`5`
`S_3`	15	20	0(800)	8	45	7(150)		0	--
`S_4`	20	25	10	0(800)	30	6(350)		0	--
`D_1`	20	18	60	15	0(800)	10		0	--
`D_2`	10	25	30	23	4	0(750)		50	`4`
Demand	0	0	0	0	350	0
Column Penalty	--	--	--	--	`1=5-4`	--

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

The minimum `c_(ij)` in this row is `c_25`=5.

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

Table-11

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0(800)	4(100)	20	5	25	12		0	--
`S_2`	10	0(700)	6	10	5(300)	20		0	--
`S_3`	15	20	0(800)	8	45	7(150)		0	--
`S_4`	20	25	10	0(800)	30	6(350)		0	--
`D_1`	20	18	60	15	0(800)	10		0	--
`D_2`	10	25	30	23	4	0(750)		50	`4`
Demand	0	0	0	0	50	0
Column Penalty	--	--	--	--	`4`	--

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

The minimum `c_(ij)` in this row is `c_65`=4.

The maximum allocation in this cell is min(50,50) = 50.
It satisfy supply of `D_2` and demand of `D_1`.


Initial feasible solution is

	`S_1`	`S_2`	`S_3`	`S_4`	`D_1`	`D_2`		Supply	Row Penalty
`S_1`	0(800)	4(100)	20	5	25	12		900	4 |  4 |  1 |  1 |  8 |  8 |  8 | 21 | -- | -- | -- |
`S_2`	10	0(700)	6	10	5(300)	20		1000	5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 | -- |
`S_3`	15	20	0(800)	8	45	7(150)		950	7 |  7 |  7 |  1 | 13 | 13 | -- | -- | -- | -- | -- |
`S_4`	20	25	10	0(800)	30	6(350)		1150	6 |  6 |  6 |  6 | 19 | -- | -- | -- | -- | -- | -- |
`D_1`	20	18	60	15	0(800)	10		800	10 | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- |
`D_2`	10	25	30	23	4(50)	0(750)		800	4 |  4 |  4 |  4 |  4 |  4 |  4 | 21 | 21 |  4 |  4 |
Demand	800	800	800	800	1150	1250
Column Penalty	10 10 -- -- -- -- -- -- -- -- --	4 4 4 4 4 4 4 4 25 -- --	6 6 6 -- -- -- -- -- -- -- --	5 5 5 5 -- -- -- -- -- -- --	4 1 1 1 1 1 1 1 1 1 4	6 6 6 6 6 7 12 -- -- -- --

The minimum total transportation cost `=0 xx 800+4 xx 100+0 xx 700+5 xx 300+0 xx 800+7 xx 150+0 xx 800+6 xx 350+0 xx 800+4 xx 50+0 xx 750=5250`

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

---

---