1. Algorithm & Example-1
Algorithm
Vogel's Approximation Method (VAM) or penalty method
This method is preferred over the NWCM and LCM,
because the initial basic feasible solution obtained by this method is either optimal solution or very nearer to the optimal solution.
|
|
Vogel's Approximation Method (VAM) Steps (Rule)
|
|
Step-1:
|
Find the cells having smallest and next to smallest cost in each row and write the difference (called penalty) along the side of the table in row penalty.
|
|
Step-2:
|
Find the cells having smallest and next to smallest cost in each column and write the difference (called penalty) along the side of the table in each column penalty.
|
|
Step-3:
|
Select the row or column with the maximum penalty and find cell that has least cost in selected row or column. Allocate as much as possible in this cell.
If there is a tie in the values of penalties then select the cell where maximum allocation can be possible
|
|
Step-4:
|
Adjust the supply & demand and cross out (strike out) the satisfied row or column.
|
|
Step-5:
|
Repeat this steps until all supply and demand values are 0.
|
Example-1
Find Solution using Voggel's Approximation method
| 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 | `9=19-10` | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `10=40-30` | | `S_3` | 40 | 8 | 70 | 20 | | 18 | `12=20-8` | | | | Demand | 5 | 8 | 7 | 14 | | | | Column
Penalty | `21=40-19` | `22=30-8` | `10=50-40` | `10=20-10` | | | |
The maximum penalty, 22, 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-2
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19 | 30 | 50 | 10 | | 7 | `9=19-10` | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `20=60-40` | | `S_3` | 40 | 8(8) | 70 | 20 | | 10 | `20=40-20` | | | | Demand | 5 | 0 | 7 | 14 | | | | Column
Penalty | `21=40-19` | -- | `10=50-40` | `10=20-10` | | | |
The maximum penalty, 21, 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 | -- | -- | `10=50-40` | `10=20-10` | | | |
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,14) = 10.
It satisfy supply of `S_3` and adjust the demand of `D_4` from 14 to 4 (14 - 10 = 4).
Table-4
| | `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) | | 0 | -- | | | | Demand | 0 | 0 | 7 | 4 | | | | Column
Penalty | -- | -- | `10=50-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,4) = 2.
It satisfy supply of `S_1` and adjust the demand of `D_4` from 4 to 2 (4 - 2 = 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 | -- | -- | `40` | `60` | | | |
The maximum penalty, 60, occurs in column `D_4`.
The minimum `c_(ij)` in this column is `c_24` = 60.
The maximum allocation in this cell is min(9,2) = 2.
It satisfy demand of `D_4` and adjust the supply of `S_2` from 9 to 7 (9 - 2 = 7).
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 | 60(2) | | 7 | `40` | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 0 | -- | | | | Demand | 0 | 0 | 7 | 0 | | | | Column
Penalty | -- | -- | `40` | -- | | | |
The maximum penalty, 40, occurs in row `S_2`.
The minimum `c_(ij)` in this row is `c_23` = 40.
The maximum allocation in this cell is min(7,7) = 7.
It satisfy supply of `S_2` and demand of `D_3`.
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10(2) | | 7 | 9 | 9 | 40 | 40 | -- | -- | | | `S_2` | 70 | 30 | 40(7) | 60(2) | | 9 | 10 | 20 | 20 | 20 | 20 | 40 | | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 18 | 12 | 20 | 50 | -- | -- | -- | | | | | Demand | 5 | 8 | 7 | 14 | | | | Column
Penalty | 21
21
--
--
--
--
| 22
--
--
--
--
--
| 10
10
10
10
40
40
| 10
10
10
50
60
--
| | | |
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
|
