1. Algorithm & Example-1
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
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
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
