Page 127 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research

Notes 6.2 Stepping Stone Method

It is a method for computing optimum solution of a transportation problem.

Steps Involved:

Step 1: Determine an initial basic feasible solution using any one of the following:
(a) North West Corner Rule

(b) Matrix Minimum Method
(c) Vogel Approximation Method
Step 2: Make sure that the number of occupied cells is exactly equal to m+n–1, where m is the
number of rows and n is the number of columns.
Step 3: Select an unoccupied cell.
Step 4: Beginning at this cell, trace a closed path using the most direct route through at least
three occupied cells used in a solution and then back to the original occupied cell and
moving with only horizontal and vertical moves. The cells at the turning points are
called “Stepping Stones” on the path.

Step 5: Assign plus (+) and minus (-) signs alternatively on each corner cell of the closed path
just traced, starting with the plus sign at unoccupied cell to be evaluated.
Step 6: Compute the net change in the cost along the closed path by adding together the unit
cost figures found in each cell containing a plus sign and then subtracting the unit costs
in each square containing the minus sign.
Step 7: Check the sign of each of the net changes. If all the net changes computed are greater than
or equal to zero, an optimum solution has been reached. If not, it is possible to improve
the current solution and decrease the total transportation cost.
Step 8: Select the unoccupied cell having the most negative net cost change and determine the
maximum number of units that can be assigned to a cell marked with a minus sign on the
closed path corresponding to this cell. Add this number to the unoccupied cell and to all
other cells on the path marked with a plus sign. Subtract this number from cells on the
closed path marked with a minus sign.
Step 9: Repeat the procedure until you get an optimum solution

Example: Consider the following transportation problem (cost in rupees). Find the
optimum solution

Factory D E F G Capacity
A 4 6 8 6 700
B 3 5 2 5 400

C 3 9 6 5 600
Requirement 400 450 350 500 1700

122 LOVELY PROFESSIONAL UNIVERSITY