Stepping Stone method

The stepping stone method is an iterative procedure used to improve an initial feasible solution for a transportation problem, in order to find the optimal solution. The method is based on the idea of moving from one feasible solution to another by making small changes in the allocation of goods from one cell to another, and then checking whether this change reduces the total transportation cost.

The stepping stone method involves the following steps:

1. Start with an initial feasible solution. This means that all supply and demand constraints are satisfied, and the total supply equals the total demand.
2. Identify any non-basic cells in the allocation table, and assign a value of zero to each of these cells. These cells are called “test cells”.
3. Construct a closed loop by starting from any test cell, and moving to adjacent cells (horizontally or vertically) that have positive allocations. Continue moving in this way until you reach the test cell that you started from, and close the loop.
4. Compute the opportunity cost for each test cell in the loop. The opportunity cost is the difference between the transportation cost of the current cell and the transportation costs of the cells in the loop that have positive allocations.
5. If all the opportunity costs are non-negative, then the current solution is optimal, and the algorithm terminates. Otherwise, select the test cell with the smallest opportunity cost, and increase its allocation by the minimum amount necessary to make one of the cells in the loop unoccupied, while keeping all supply and demand constraints satisfied. Set the allocation of the cell that becomes unoccupied to zero, and repeat the procedure from step 2.

By repeating steps 2 to 5, the stepping stone method gradually moves from the initial feasible solution to the optimal solution, by improving the allocation of goods in the cells of the allocation table.

Note that in the stepping stone method, the allocations are changed in a way that preserves the total supply and demand, and satisfies the non-negativity constraints of the problem. This ensures that the resulting solution remains feasible, and only improves the objective function value.

Stepping stone method examples

Sure, here is an example of the stepping stone method applied to a transportation problem:

Suppose we have a company that manufactures products in three factories (F1, F2, F3) and ships them to four warehouses (W1, W2, W3, W4). The transportation costs per unit are given in the following table:

The supply and demand for each factory and warehouse are given by:

• F1 has a supply of 120 units
• F2 has a supply of 180 units
• F3 has a supply of 110 units
• W1 has a demand of 50 units
• W2 has a demand of 120 units
• W3 has a demand of 180 units
• W4 has a demand of 70 units

To find the optimal solution, we can start with an initial feasible solution. For example, we can allocate 50 units from F1 to W1, 120 units from F2 to W2, 60 units from F2 to W4, and 110 units from F3 to W3. This allocation satisfies the supply and demand constraints, and the total supply equals the total demand. The allocation table is:

We can now apply the stepping stone method to improve this initial solution. We start by identifying the test cells, which are the cells with zero allocation: cell (1,2), cell (1,3), and cell (3,1). We then construct a closed loop by starting from cell (1,2), and moving to cell (2,2), cell (2,4), cell (1,4), cell (3,4), cell (3,3), and back to cell (1,2). The loop has an even number of cells, so we need to compute the opportunity cost for each test cell.

For cell (1,2), the loop goes right, up, left, and down to cell (1,2), and has an even number of cells. Therefore, the opportunity cost for cell (1,2) is zero.

For cell (1,3), the loop goes down, right, up, and left to cell (1,3), and has an odd number of cells. The smallest cost among the cells in the loop is 2, which is the opportunity cost for cell (1,3).

For cell (3,1), the loop goes right, up, left, down, right, and up to cell (3,1), and has an odd number of cells. The smallest cost among the cells in the loop is 6, which is the opportunity cost for cell (3,1).

To increase the allocation for cell (1,3), we need to find a way to increase the flow of units through this cell while maintaining feasibility. We can do this by using the stepping stone method again to find a new feasible solution with an improved objective function value.

To do this, we start by adding a flow of 2 units to cell (1,3), which will increase the allocation for this cell to 2 units. This will also decrease the available supply for F1 to 48 units and increase the demand for W3 to 182 units.

Next, we identify the test cells for the new allocation table, which are cells (1,2), (2,2), (2,4), and (3,1). We construct a closed loop by starting from cell (1,2), and moving to cell (2,2), cell (2,4), cell (1,4), cell (3,4), cell (3,3), and back to cell (1,2). The loop has an even number of cells, so we need to compute the opportunity cost for each test cell.

For cell (1,2), the loop goes right, up, left, and down to cell (1,2), and has an even number of cells. Therefore, the opportunity cost for cell (1,2) is zero.

For cell (2,2), the loop goes left, down, right, and up to cell (2,2), and has an even number of cells. Therefore, the opportunity cost for cell (2,2) is zero.

For cell (2,4), the loop goes up, left, down, and right to cell (2,4), and has an even number of cells. Therefore, the opportunity cost for cell (2,4) is zero.

For cell (3,1), the loop goes right, up, left, down, right, and up to cell (3,1), and has an odd number of cells. The smallest cost among the cells in the loop is 6, which is the opportunity cost for cell (3,1).

The cell with the smallest opportunity cost is cell (3,1), with an opportunity cost of 6. We can increase its allocation by 6 units, which will increase the allocation for cell (2,2) by 2 units, and decrease the allocation for cell (2,4) by 2 units. This new allocation table is:

We can now repeat the process of identifying the test cells, constructing a closed loop, and computing the opportunity costs to continue improving the solution until we reach an optimal solution.