A balanced transportation problem with supply and demand points has basic variables in any basic feasible solution (BFS). 3 methods construct a starting BFS.
North-West Corner Method
- Start at the north-west (top-left) cell of the cost matrix.
- Allocate to that cell.
- Cross out the row or column that’s exhausted (both, if they’re exhausted simultaneously, leaving a 0 allocation in the next cell to preserve basic variables).
- Move to the next cell (right if the row remains, down if the column remains) and repeat until all supply and demand is allocated.
Ignores cost, so the result is usually far from optimal.
Least Cost Method
- Allocate as much as possible to the cell with the lowest cost in the matrix.
- Cross out the exhausted row or column.
- Repeat on the remaining cells until fully allocated.
A tie in the lowest cost is broken by choosing the cell allowing the larger allocation.
Vogel’s Approximation Method (VAM)
- For every remaining row and column, compute the penalty: the difference between the lowest and second-lowest cost in it.
- Select the row or column with the largest penalty. Allocate as much as possible to its lowest-cost cell.
- Cross out the exhausted row or column and recompute penalties.
- Repeat until fully allocated.
Generally gives a BFS closer to optimal than the other 2 methods.
Degenerate BFS
Occurs when an allocation exhausts a row and a column simultaneously before all supply/demand is used, leaving fewer than positive allocations. Add a 0 allocation to an unoccupied cell (chosen so the solution stays a basic feasible solution) to restore the count.