The Vogel approximation method (Unit cost penalty method) is an iterative procedure for computing a basic feasible solution of a transportation problem.
This method is preferred over the two methods discussed in the previous sections, because the initial basic feasible solution obtained by this method is either optimal or very close to the optimal solution.
The standard instructions are paraphrased below:
Consider the transportation problem presented in the following table:
Destination | |||||
---|---|---|---|---|---|
Origin | 1 | 2 | 3 | 4 | Supply |
1 | 20 | 22 | 17 | 4 | 120 |
2 | 24 | 37 | 9 | 7 | 70 |
3 | 32 | 37 | 20 | 15 | 50 |
Demand | 60 | 40 | 30 | 110 | 240 |
Solution.
Calculating penalty for table 1
17 - 4 = 13, 9 - 7 = 2, 20 - 15 = 5
24 - 20 = 4, 37 - 22 = 15, 17 - 9 = 8, 7 - 4 = 3
Table 1
Destination | ||||||
---|---|---|---|---|---|---|
Origin | 1 | 2 | 3 | 4 | Supply | Penalty |
1 | 20 | 17 | 4 | 13 | ||
2 | 24 | 37 | 9 | 7 | 70 | 2 |
3 | 32 | 37 | 20 | 15 | 50 | 5 |
Demand | 60 | 30 | 110 | 240 | ||
Penalty | 4 | 15 | 8 | 3 |
The highest penalty occurs in the second column. The minimum cij in this column is c12 (i.e., 22). So x12 = 40 and the second column is eliminated. The new reduced matrix is shown below:
Now again calculate the penalty.
Table 2
Origin | 1 | 3 | 4 | Supply | Penalty |
---|---|---|---|---|---|
1 | 20 | 17 | 13 | ||
2 | 24 | 9 | 7 | 70 | 2 |
3 | 32 | 20 | 15 | 50 | 5 |
Demand | 60 | 30 | 110 | ||
Penalty | 4 | 8 | 3 |
The highest penalty occurs in the first row. The minimum cij in this row is c14 (i.e., 4). So x14 = 80 and the first row is eliminated. The new reduced matrix is shown below:
Table 3
Origin | 1 | 3 | 4 | Supply | Penalty |
---|---|---|---|---|---|
2 | 24 | 7 | 70 | 2 | |
3 | 32 | 20 | 15 | 50 | 5 |
Demand | 60 | 30 | |||
Penalty | 8 | 11 | 8 |
The highest penalty occurs in the second column. The minimum cij in this column is c23 (i.e., 9). So x23 = 30 and the second column is eliminated. The reduced matrix is given in the following table.
Table 4
Origin | 1 | 4 | Supply | Penalty |
---|---|---|---|---|
2 | 17 | |||
3 | 15 | 17 | ||
Demand | ||||
Penalty | 8 | 8 |
The following table shows the computation of penalty for various rows and columns.
Destination | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Origin | 1 | 2 | 3 | 4 | Supply | Penalty | |||||
1 | 20 | 17 | 13 | 13 | - | - | - | - | |||
2 | 37 | 2 | 2 | 2 | 17 | 24 | 24 | ||||
3 | 37 | 20 | 15 | 5 | 5 | 5 | 17 | 32 | - | ||
Demand | 240 | ||||||||||
Penalty | 4 | 15 | 8 | 3 | |||||||
4 | - | 8 | 3 | ||||||||
8 | - | 11 | 8 | ||||||||
8 | - | - | 8 | ||||||||
8 | - | - | - | ||||||||
24 | - | - | - |
22 X 40 + 4 X 80 + 24 X 10 + 9 X 30 + 7 X 30 + 32 X 50 = 3520.