optimal solution Stepping Stone Method

The Stepping Stone Method is an optimization technique used to improve an initial feasible solution obtained from methods like the North-West Corner, Least Cost, or Vogel's Approximation in transportation problems. This method is part of the iterative improvement algorithms applied in linear programming and operations research to find the optimal solution for the transportation problem.

Steps in the Stepping Stone Method:

Steps in the Stepping Stone Method 

Identify Empty Cells (Non-Basic Variables):

In the initial feasible solution obtained from heuristic methods, identify the cells (non-basic variables) with allocations equal to zero. These cells represent potential improvements in the solution.

Start the Stepping Stone Procedure:

Choose one of the empty cells and draw a closed loop connecting it to other non-zero allocations in the tableau.

Check for Circularity:

Check for circularity in the loop. A circular path should have an even number of lines.

Determine the Change in Cost:

Calculate the change in cost associated with the closed loop by summing the costs of the cells that are part of the loop but not originally part of the initial solution.

Evaluate Improvement:

If the change in cost is negative or zero, the current solution is optimal. If the change in cost is positive, there is room for improvement.

Allocate or Deallocate:

If the change in cost is positive, adjust the allocations along the closed loop. Allocate units in cells initially not included in the solution and deallocate units from cells originally part of the solution.

Repeat:

Repeat the process by choosing another empty cell and performing the Stepping Stone Procedure until all empty cells have been considered.

Optimality Check:

After making adjustments, check whether the modified solution is optimal. If not, continue the process until the optimal solution is reached.

Example of the Stepping Stone Method:

Consider a transportation problem with the following initial solution:

       | C1 | C2 | C3 | Supply

--------------------------------

S1   |  0  |  30 |  0  |   30

S2   |  20 |  0  |  30 |   50

S3   |  0  |  30 |  0  |   20

--------------------------------

Demand |  20 |  60 |  30 |

Using the Stepping Stone Method:

• Identify empty cells (non-basic variables), such as (S1, C1), (S1, C3), (S3, C1), and (S3, C3).
• Start the Stepping Stone Procedure by drawing a closed loop, connecting these empty cells to other non-zero allocations.
• Calculate the change in cost associated with the loop.
• If the change in cost is positive, allocate or deallocate units along the loop to improve the solution.
• Repeat the process with other empty cells until an optimal solution is achieved.

Advantages of Stepping Stone Method:

Advantages of Stepping Stone Method 

Optimization of Initial Solutions:

The Stepping Stone Method helps optimize initial feasible solutions obtained from heuristic methods, ensuring a more cost-effective solution.

Iterative Improvement:

This method follows an iterative process, gradually improving the solution by adjusting allocations along closed loops. This iterative approach allows for continuous refinement until the optimal solution is reached.

Flexibility:

The Stepping Stone Method is flexible and can be applied to various transportation problems. It accommodates changes in the allocation structure to achieve a more optimal solution.

Systematic Approach:

The method employs a systematic approach, systematically evaluating and adjusting allocations based on the change in cost associated with closed loops.

Applicability to Various Linear Programming Problems:

While commonly used in transportation problems, the Stepping Stone Method is applicable to various linear programming problems involving allocation and optimization.

For More Visit KMBN 206