Algorithm

Heuristic Method-2: (This alternate method is developed with little modification to VAM)
Step-1:	Determine the penalty cost i.e. the difference between the lowest and highest cost element of that row/column.
Step-2:	Identify the row/column having highest penalty and choose the variable having lowest cost in this selected row/column. Allocate as much as possible to this variable.
Step-3:	Cross out the row or column which ever is satisfied and adjust the variable and required quantities.
Step-4:	Compute the penalties and repeat procedure till all rows and columns are satisfied.

---

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

	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	`40=50-10`
`S_2`	70	30	40	60		9	`40=70-30`
`S_3`	40	8	70	20		18	`62=70-8`
Demand	5	8	7	14
Column Penalty	`51=70-19`	`22=30-8`	`30=70-40`	`50=60-10`

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

The minimum `c_(ij)` in this row 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	`40=50-10`
`S_2`	70	30	40	60		9	`30=70-40`
`S_3`	40	8(8)	70	20		10	`50=70-20`
Demand	5	0	7	14
Column Penalty	`51=70-19`	--	`30=70-40`	`50=60-10`

The maximum penalty, 51, 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	--	--	`30=70-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,14) = 2.
It satisfy supply of `S_1` and adjust the demand of `D_4` from 14 to 12 (14 - 2 = 12).

Table-4

	`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	`50=70-20`
Demand	0	0	7	12
Column Penalty	--	--	`30=70-40`	`40=60-20`

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,12) = 10.
It satisfy supply of `S_3` and adjust the demand of `D_4` from 12 to 2 (12 - 10 = 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	--	--	`0=40-40`	`0=60-60`

The maximum penalty, 20, 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
`S_1`	19(5)	30	50	10(2)		0	--
`S_2`	70	30	40(7)	60		2	`0=60-60`
`S_3`	40	8(8)	70	20(10)		0	--
Demand	0	0	0	2
Column Penalty	--	--	--	`0=60-60`

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

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

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


Initial feasible solution is

	`D_1`	`D_2`	`D_3`	`D_4`		Supply	Row Penalty
`S_1`	19(5)	30	50	10(2)		7	40 | 40 | 40 | -- | -- | -- |
`S_2`	70	30	40(7)	60(2)		9	40 | 30 | 20 | 20 | 20 |  0 |
`S_3`	40	8(8)	70	20(10)		18	62 | 50 | 50 | 50 | -- | -- |
Demand	5	8	7	14
Column Penalty	51 51 -- -- -- --	22 -- -- -- -- --	30 30 30 30 0 --	50 50 50 40 0 0

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

---

---