Find Solution using Heuristic method-2

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

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

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

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

Table-2

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

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

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

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

Table-3

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11	13(225)	17	14		25	`6=17-11`
`S_2`	16	18	14	10		300	`2=16-14`
`S_3`	21	24	13	10(250)		150	`8=21-13`
Demand	200	0	275	0
Column Penalty	`10=21-11`	--	`4=17-13`	--

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

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

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

Table-4

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11(25)	13(225)	17	14		0	--
`S_2`	16	18	14	10		300	`2=16-14`
`S_3`	21	24	13	10(250)		150	`8=21-13`
Demand	175	0	275	0
Column Penalty	`5=21-16`	--	`1=14-13`	--

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

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

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

Table-5

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11(25)	13(225)	17	14		0	--
`S_2`	16	18	14	10		300	`2=16-14`
`S_3`	21	24	13(150)	10(250)		0	--
Demand	175	0	125	0
Column Penalty	`0=16-16`	--	`0=14-14`	--

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

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

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

Table-6

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	11(25)	13(225)	17	14		0	--
`S_2`	16	18	14(125)	10		175	`0=16-16`
`S_3`	21	24	13(150)	10(250)		0	--
Demand	175	0	0	0
Column Penalty	`0=16-16`	--	--	--

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

The minimum `c_(ij)` in this row is `c_21` = 16.

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


Initial feasible solution is

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

The minimum total transportation cost `= 11 xx 25 + 13 xx 225 + 16 xx 175 + 14 xx 125 + 13 xx 150 + 10 xx 250 = 12200`

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

---

---