Vogel's Approximation Method for Transportation Problems¶

Vogel's Approximation Method (VAM) is a heuristic used to find an initial feasible solution for transportation problems in linear programming. It aims to achieve a better initial solution by considering the penalty cost associated with not choosing the least cost route. The penalty is calculated as the difference between the lowest and second-lowest costs in each row and column, guiding the allocation process by highlighting where the greatest potential cost savings can be achieved.

Steps to Apply Vogel's Approximation Method¶

Calculate the penalty for each row and column.
The penalty is the difference between the two smallest costs in each row and column.
Identify the row or column with the highest penalty.
If there's a tie, break it arbitrarily.
Allocate as much as possible to the cell with the lowest cost in the selected row or column.
Adjust the supply and demand based on the allocation:
Subtract the allocated amount from both the corresponding row's supply and the column's demand.
Cross out the row or column if the supply or demand is exhausted.
If both are exhausted simultaneously, cross out one and set the remaining supply/demand of the other to zero.
Repeat steps 1-5 until all supplies and demands are met.

Example Problem¶

Consider three factories (A, B, C) supplying goods to three warehouses (X, Y, Z). The transportation costs per unit, supplies, and demands are given below:

	X	Y	Z	Supply
A	2	3	1	30
B	5	4	8	40
C	5	6	8	20
Demand	20	50	20

Step 1: Calculate the penalties for each row and column.¶

Row A: The smallest costs are 1 and 2, so the penalty is 2 - 1 = 1.
Row B: The smallest costs are 4 and 5, so the penalty is 5 - 4 = 1.
Row C: The smallest costs are 5 and 6, so the penalty is 6 - 5 = 1.
Column X: The smallest costs are 2 and 5, so the penalty is 5 - 2 = 3.
Column Y: The smallest costs are 3 and 4, so the penalty is 4 - 3 = 1.
Column Z: The smallest costs are 1 and 8, so the penalty is 8 - 1 = 7.

Step 2: Identify the highest penalty.¶

The highest penalty is 7 for column Z.

Step 3: Allocate to the cell with the lowest cost in column Z.¶

The lowest cost in column Z is 1 (A-Z).
The supply at A is 30, and the demand at Z is 20.
Allocate 20 units to A-Z.
Update the remaining supply at A to 30 - 20 = 10 and the remaining demand at Z to 20 - 20 = 0.
Cross out column Z.

Step 4: Recalculate the penalties.¶

After crossing out column Z, recalculate penalties for the remaining rows and columns:

Row A: The smallest costs are 2 and 3, so the penalty is 3 - 2 = 1.
Row B: The smallest costs are 4 and 5, so the penalty is 5 - 4 = 1.
Row C: The smallest costs are 5 and 6, so the penalty is 6 - 5 = 1.
Column X: The smallest costs are 2 and 5, so the penalty is 5 - 2 = 3.
Column Y: The smallest costs are 3 and 4, so the penalty is 4 - 3 = 1.

Step 5: Allocate to the row or column with the highest penalty.¶

The highest penalty is 3 for column X.

Step 6: Allocate to the cell with the lowest cost in column X.¶

The lowest cost in column X is 2 (A-X).
The supply at A is 10, and the demand at X is 20.
Allocate 10 units to A-X.
Update the remaining supply at A to 10 - 10 = 0 and the remaining demand at X to 20 - 10 = 10.
Cross out row A.

Step 7: Recalculate the penalties.¶

After crossing out row A, recalculate penalties for the remaining rows and columns:

Row B: The smallest costs are 4 and 5, so the penalty is 5 - 4 = 1.
Row C: The smallest costs are 5 and 6, so the penalty is 6 - 5 = 1.
Column X: The only cost left is 5, so the penalty is 0.
Column Y: The smallest costs are 4 and 6, so the penalty is 6 - 4 = 2.

Step 8: Allocate to the row or column with the highest penalty.¶

The highest penalty is 2 for column Y.

Step 9: Allocate to the cell with the lowest cost in column Y.¶

The lowest cost in column Y is 4 (B-Y).
The supply at B is 40, and the demand at Y is 50.
Allocate 40 units to B-Y.
Update the remaining supply at B to 40 - 40 = 0 and the remaining demand at Y to 50 - 40 = 10.
Cross out row B.

Step 10: Allocate the remaining units.¶

The only remaining cell is C-Y with a demand of 10 and a supply of 20.
Allocate 10 units to C-Y.
Update the remaining supply at C to 20 - 10 = 10 and the remaining demand at Y to 10 - 10 = 0.

Final Allocation¶

The final allocations are as follows:

	X	Y	Z
A	10	0	20
B	0	40	0
C	0	10	0

Summary¶

Vogel's Approximation Method attempts to find a better initial feasible solution by considering the penalties associated with not choosing the least cost route.
This method often provides a good starting solution, but further optimization using techniques like the stepping-stone method or the MODI (Modified Distribution) method may be needed to reach the optimal solution.

Hive Chat

Hi, I'm Hive Chat, an AI assistant created by CollegeHive.
How can I help you today?

🎶