7.2 Finding a first solution

Three rules give a starting BFS, each allocating as much as possible to one cell at a time and crossing out the row or column that is exhausted:

• the north-west corner rule starts at cell \((1, 1)\) and moves right or down, ignoring costs;
• the least-cost rule takes the cheapest remaining cell;
• Vogel’s approximation method (VAM) computes, for each row and column, the penalty, the difference between its two smallest remaining costs, and allocates to the cheapest cell of the row or column with the largest penalty: the line where a wrong choice would cost most.

For Example 7.1.2 they cost \(1015\), \(814\) and \(779\) against the optimum \(743\) (Software 7.6.1). VAM usually starts close to the optimum, which is why hand methods use it.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.