Stepping Stone Method

Steps to find out optimal solution using stepping stone method

1. PRESENTATION ON “ STEPPING STONE METHOD ” OPERATIONS RESEARCH SUBMITTED BY: HIMANSHI GUPTA ( 140120119057)/ ME/A1 GUIDED BY : PROF. PARANJAY PATEL ( 2171901) GANDHINAGAR INSTITUTE OF TECHNOLOGY

2. INTRODUCTION This is a one of the methods used to determine optimality of an initial basic feasible solution (i.e. Northwest Corner Rule, Least Cost or Vogel’s Approximation ). The method is derived from the analogy of crossing a pond using stepping stones. This means that the entire transportation table is assumed to be a pond and the occupied cells are the stones needed to make certain movements within the pond.

3. STEPS INVOLVED Starting at an unused/empty cell, trace a closed path or loop back to the original cell via cells that are currently being used and/or occupied. Note : A closed path or loop is a sequence of cells in the transportation table such that the first cell is unused/empty and all the other cells are used/occupied with the following conditions: Each pair of consecutive used/occupied cells lies in either the same row or column. No three consecutive used/occupied cells lie in the same row or column. The first and last cells of a sequence lies in the same row or column. No cell appears more than once in a sequence (i.e. no duplication). Only horizontal and vertical moves allowed and can only change directions at used/occupied cells

4. PROBLEM Q. This is the transportation table for a company from its different warehouses. Find the most optimum solution.

5. SOLUTION STEP 1 By VAM we find the initial basic feasible solution . Here number of allotments is 6 which is equal to n+m-1

6. SOLUTION STEP 2 Now for every unoccupied cell form a loop Δ =+ 8-6+7-8+5-4=2

7. SOLUTION STEP 3 Δ =+8-8+5-4=1

8. SOLUTION STEP 4 Δ=+6-7+8-5=2

9. SOLUTION STEP 5 Δ=+8-7+8-5+4-6=2 

10. SOLUTION STEP 6 Δ=+4-6+7-5=0

11. SOLUTION STEP 7 Δ =+7-8+6-6=-1

12. SOLUTION STEP 8 Each n egative cost indicates the amount by which transportation cost can be reduced by allocating one unit of product were to be shipped from that source Choose the source which has most negative amount We can find maximum possible units which can be transported by forming a loop Now for cell C-3 the value is negative so we will have to form a loop and do reallocation of units

13. SOLUTION STEP 9 The maximum quantity that can be shipped on the new money-saving route can be found by referring to the closed path of plus signs and minus signs drawn for the route and selecting the smallest number found in those squares containing minus signs To find the new solution add the smallest number to all the squares with positive sign and subtract it from cells with negative sign

14. SOLUTION STEP 10

15. We have a new basic feasible solution:

16. FINAL SOLUTION

17. Repeat all the above steps to calculate an Improvement Index for all unused squares in order to test whether an optimal solution has been reached . Since the results of all indices calculated are greater than or equal to zero , then, an optimal solution had been reached . In second iteration, there is an improvement index equal to zero. This means that there is an ALTERNATE optimum solution.