Stepping Stone Method

Step 1: Pick any empty cell and identify the closed path leading to that cell. A closed path consists of horizontal and vertical lines leading from an empty cell back to itself (If assignments have been made correctly, the matrix has only one closed path for each empty cell.) In the closed path there can only be one empty cell that we are examining. The 90-degree turns must therefore occur at those places that meet this requirement. Two closed paths are identified. Closed path a is required to evaluate empty cell A-E; closed path b is required to evaluate empty cell A-F.


Closed path "a"

Closed path "b"

Step 2: Move one unit into the empty cell from a filled cell at a corner of the closed path and modify the remaining filled cells at the other comers of the closed path to reflect this move. (More than one unit could be used to test the desirability of a shift. However, since the problem is linear, if it is desirable to shift one unit, it is desirable to shift more than one, and vice versa.) Modifying entails adding to and subtracting from filled cells in such a way that supply and demand constraints are not violated. This requires that one unit always be subtracted in a given row or column for each unit added to that row or column. Thus, the following additions and subtractions would be required :

For the path a:

For the path b, Step 3: Determine desirability of the move. This is easily done by (1) summing the cost values for the cell to which a unit has been added, (2) summing the cost values of the cells from which a unit has been subtracted, and (3) taking the difference between the two sums to determine if there is a cost reduction. If the cost is reduced by making the move, as many units as possible should be shifted out of the evaluated filled cells into the empty cell. If the cost is increased, no move should be made and the empty cell should be crossed.

For cell A-E, the pluses and minuses are


For cell A-H, the pluses and minuses are


Thus in both cases it is apparent that no move into either empty cell should be made.

Step 4: Repeat Steps 1 through 3 until all empty cells have been evaluated. To illustrate the mechanics of carrying out a move, consider cell X-F and the closed path leading to it, which is a short one: X-G, D-G, and D-F. The pluses and minuses are


Since there is a savings of $5 per unit from shipping via X-F, as many units as possible should be moved into this cell. In this case, however, the maximum amount that can be shifted is one unit—because the maximum amount added to any cell may not exceed the quantity found in the lowest-amount cell from which a subtraction is to be made. To do otherwise would violate the supply and demand constraints of the problem. Here we see that the limiting cell is X-G since it contains only one unit.

Applying the stepping stone method to this new solution (next table) indicates, that making this shift we obtained an optimal solution – there is no unfilled cell.

The table above indicates one marked cell B-H. This cell has closed path C-H, C-G, D-G, D-F and B-F.

The pluses and minuses are


Since there is a savings of $0 (70 - 70) per unit from shipping via B-H, we obtain a different – "alternate optimal solution" with the same transportation cost (next table).