Vogel's Approximation Method (VAM)

Vogel's Approximation Method (VAM)

Vogel's Approximation Method is the most reliable of the three IBFS methods because it uses a penalty — the extra cost of not choosing the cheapest cell in a row or column — to decide where to allocate next, rather than looking only at the single cheapest cell in the whole table.

Rule (repeated until all rows/columns are exhausted):

1. For every remaining row and every remaining column, compute the penalty = (second-lowest cost) − (lowest cost) in that row/column.
2. Select the row or column with the largest penalty.
3. In that row/column, allocate the maximum possible to its lowest-cost cell.
4. Cross out the row or column that is now exhausted, and recompute penalties for what remains.

Worked example — same cost matrix as the earlier examples

Round 1 — penalties: Row $O_1$: $8-6=2$. Row $O_2$: $11-7=4$. Row $O_3$: $5-4=1$. Column $D_1$: $6-4=2$. Column $D_2$: $8-5=3$. Column $D_3$: $11-10=1$.

Largest penalty is 4 (row $O_2$). Lowest cost in that row is $(O_2,D_1)=7$: allocate $\min(50,25)=25$. $D_1$ is exhausted; $O_2$ has 25 units left.

Round 2 (remaining columns $D_2,D_3$; supplies $O_1=30,O_2=25,O_3=20$) — penalties: Row $O_1$: $10-8=2$. Row $O_2$: $11-11=0$. Row $O_3$: $12-5=7$. Column $D_2$: $8-5=3$. Column $D_3$: $11-10=1$.

Largest penalty is 7 (row $O_3$). Lowest cost in that row is $(O_3,D_2)=5$: allocate $\min(20,35)=20$. $O_3$ is exhausted; $D_2$ has 15 units left.

Round 3 (remaining $D_2=15,D_3=40$; supplies $O_1=30,O_2=25$) — penalties: Row $O_1$: $10-8=2$. Row $O_2$: $11-11=0$. Column $D_2$: $11-8=3$. Column $D_3$: $11-10=1$.

Largest penalty is 3 (column $D_2$). Lowest cost in that column is $(O_1,D_2)=8$: allocate $\min(30,15)=15$. $D_2$ is exhausted; $O_1$ has 15 units left.

Round 4 (only $D_3$ left; $O_1=15,O_2=25$, $D_3=40$): allocate $(O_1,D_3)=\min(15,40)=15$, then $(O_2,D_3)=\min(25,25)=25$.

Allocation table (VAM)

Feasible, with 5 occupied cells ($=m+n-1$).

Total cost

Comparing the three methods on the identical cost matrix …