Testing the IBFS for Optimality

Testing the IBFS for Optimality

An Initial Basic Feasible Solution — however it was obtained — is only a starting point. It must be tested to see whether the total cost can be reduced further, and improved if it can. Two named methods are used for this in Business Mathematics and Statistics:

• Stepping-Stone Method — for each currently unoccupied cell, trace a closed loop through occupied cells and compute the net change in cost if one unit were shipped through that unoccupied cell instead. If every unoccupied cell's net change is zero or positive, the current solution is optimal; if any cell gives a negative net change, reallocate along that loop to reduce total cost, and repeat.
• Modified Distribution (MODI) Method — a faster equivalent that assigns a number $u_i$ to each row and $v_j$ to each column (using $u_i+v_j=c_{ij}$ for every occupied cell, with $u_1=0$ as the starting reference) and then computes $\Delta_{ij}=c_{ij}-(u_i+v_j)$ for every unoccupied cell. If every $\Delta_{ij}\ge 0$, the solution is optimal; a negative $\Delta_{ij}$ signals room for improvement, and the cell with the most negative $\Delta_{ij}$ is brought into the solution next via a stepping-stone loop.

Both methods test the same condition — that no unoccupied cell can lower the total cost — and both require the number of occupied cells to equal $m+n-1$, adding a tiny quantity $\epsilon$ to an otherwise-empty cell if the solution is degenerate (fewer occupied cells than $m+n-1$), so the $u_i,v_j$ system can still be solved. …