Algorithm

Heuristic Method-1:
Step-1:	Calculate the difference between the two lowest cost cells (called Penalty) for each row and column. These are called as row and column penalties, P, respectively.
Step-2:	Add the cost of cells for each row and column. These summations are called row and column cost, T, respectively.
Step-3:	Compute the product of penalty 'P' and the total cost 'T', that is PT for each row and column.
Step-4:	Identify the row/column having lowest 'PT'.
Step-5:	Choose the cell having minimum cost in row/column identified in Step-4.
Step-6:	Make maximum feasible allocation to the cell chosen in Step-5, if the cost of this cell is also minimum in its column/row. Otherwise allocation is avoided and goto Step-7.
Step-7:	Identify the row/column having next to lowest 'PT'.
Step-8:	Choose the cell having minimum cost in row/column identified in step 7.
Step-9:	Make maximum feasible allocation to the cell chosen in Step-8.
Step-10:	Cross out the satisfied row/column.
Step-11:	Repeat the procedure until all the requirements are satisfied.

---

Example-1
1. Find Solution using Heuristic method-1

	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 (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10		7	`9=19-10`	109	`981=9xx109`
`S_2`	70	30	40	60		9	`10=40-30`	200	`2000=10xx200`
`S_3`	40	8	70	20		18	`12=20-8`	138	`1656=12xx138`
Demand	5	8	7	14
Column Penalty (P)	`21=40-19`	`22=30-8`	`10=50-40`	`10=20-10`
Total (T)	129	68	160	90
P`xx`T	`2709=21xx129`	`1496=22xx68`	`1600=10xx160`	`900=10xx90`

The lowest PT = 900, occurs in column `D_4`.

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

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

Table-2

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)		0	--	109	--
`S_2`	70	30	40	60		9	`10=40-30`	200	`2000=10xx200`
`S_3`	40	8	70	20		18	`12=20-8`	138	`1656=12xx138`
Demand	5	8	7	7
Column Penalty (P)	`30=70-40`	`22=30-8`	`30=70-40`	`40=60-20`
Total (T)	129	68	160	90
P`xx`T	`3870=30xx129`	`1496=22xx68`	`4800=30xx160`	`3600=40xx90`

The lowest PT = 1496, 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-3

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)		0	--	109	--
`S_2`	70	30	40	60		9	`20=60-40`	200	`4000=20xx200`
`S_3`	40	8(8)	70	20		10	`20=40-20`	138	`2760=20xx138`
Demand	5	0	7	7
Column Penalty (P)	`30=70-40`	--	`30=70-40`	`40=60-20`
Total (T)	129	68	160	90
P`xx`T	`3870=30xx129`	--	`4800=30xx160`	`3600=40xx90`

The lowest PT = 2760, 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,7) = 7.
It satisfy demand of `D_4` and adjust the supply of `S_3` from 10 to 3 (10 - 7 = 3).

Table-4

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)		0	--	109	--
`S_2`	70	30	40	60		9	`30=70-40`	200	`6000=30xx200`
`S_3`	40	8(8)	70	20(7)		3	`30=70-40`	138	`4140=30xx138`
Demand	5	0	7	0
Column Penalty (P)	`30=70-40`	--	`30=70-40`	--
Total (T)	129	68	160	90
P`xx`T	`3870=30xx129`	--	`4800=30xx160`	--

The lowest PT = 3870, occurs in column `D_1`.

The minimum `c_(ij)` in this column is `c_31` = 40.

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

Table-5

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)		0	--	109	--
`S_2`	70	30	40	60		9	`30=70-40`	200	`6000=30xx200`
`S_3`	40(3)	8(8)	70	20(7)		0	--	138	--
Demand	2	0	7	0
Column Penalty (P)	`70`	--	`40`	--
Total (T)	129	68	160	90
P`xx`T	`9030=70xx129`	--	`6400=40xx160`	--

The lowest PT = 6000, occurs in row `S_2`.

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

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

Table-6

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)		0	--	109	--
`S_2`	70	30	40(7)	60		2	`70`	200	`14000=70xx200`
`S_3`	40(3)	8(8)	70	20(7)		0	--	138	--
Demand	2	0	0	0
Column Penalty (P)	`70`	--	--	--
Total (T)	129	68	160	90
P`xx`T	`9030=70xx129`	--	--	--

The lowest PT = 9030, occurs in column `D_1`.

The minimum `c_(ij)` in this column is `c_21` = 70.

The maximum allocation in this cell is min(2,2) = 2.
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 (P)	Total (T)	P`xx`T
`S_1`	19	30	50	10(7)		7	9 | -- | -- | -- | -- | -- |	109	981 | -- | -- | -- | -- | -- |
`S_2`	70(2)	30	40(7)	60		9	10 | 10 | 20 | 30 | 30 | 70 |	200	2000 | 2000 | 4000 | 6000 | 6000 | 14000 |
`S_3`	40(3)	8(8)	70	20(7)		18	12 | 12 | 20 | 30 | -- | -- |	138	1656 | 1656 | 2760 | 4140 | -- | -- |
Demand	5	8	7	14
Column Penalty (P)	21 30 30 30 70 70	22 22 -- -- -- --	10 30 30 30 40 --	10 40 40 -- -- --
Total (T)	129	68	160	90
P`xx`T	2709 3870 3870 3870 9030 9030	1496 1496 -- -- -- --	1600 4800 4800 4800 6400 --	900 3600 3600 -- -- --

The minimum total transportation cost `= 10 xx 7 + 70 xx 2 + 40 xx 7 + 40 xx 3 + 8 xx 8 + 20 xx 7 = 814`

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

---

---