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