Finding the optimum solution

   Once an initial solution has been found the next step is to test that solution for optimality. The following two methods are widely used for testing the solution.

1.      Stepping Stone Method

2.      Modified Distribution (MODI) Method

  The two methods differ in their computational approach but give exactly the same testing procedure being used is to test each unoccupied cell one at a time by computing the cost change if the inclusion of any unoccupied cell can decrease the transportation cost then this unoccupied cell will be considered for allocation in the improved solution. we selct that unoccupied cell for allocation for which the cost change is most negative. The procedure is continued till the lowest possible transportation cost. The procedure is continued till the lowest possible transportation cost. i.e., optimum solution is obtained.

5.6. Stepping -stone Method. In this method we calculate the net cost change that can be obtained by introducing any of the unoccupied cells into the solution. the important rule to keep in mind is that every increase (or decrease) in supply at one occupied cell must be associated by a decrease (or increase) in supply at another. The same rule holds true for demand. Thus there must be two changes in every row or column that is changed one change increasing the allocation (or quantity) and one change decreasing it. This is easily done by evaluating re-allocation in a closed path sequence with only right angel turns permitted.

The criterion for making a re-allocation is simply to know the desired effect upon costs. The net cost change is determined by listing the unit costs associated with each cell and then summing over the path to find the net effect. Signs are alternate from positive (+)to negative (-) depending upon whether shipments are being added or subtracted at a given point. A negative sing on the net cost change indicates that a cost reduction can be made by making the change. The positive sign on the net cost change indicates a cost increase.

The stepping stone method can be summarised as follows.

Step 1. Determine an initial basic feasible solution using any of the three methods discussed earlier.

Step 2. Make sure that the number of occupied cells is exactly equal to m+n+-1 where m is number of rows and n is number of columns.

Step 3. Evaluate the cost-effectiveness of shipping goods via transportation routes not currently in the solution. this testing  of each unoccupied cell is conducted by the following five steps as follows:

(a)    Select an unoccupied cell where as shipment should be made.

(b)   Beginning at this cell trace a closed path using the most direct rout through at least three occupied cells used in the solution and then back to the original occupied cell and moving with only horizontal and vertical moves. Further since only the cell at the turning points are considered to be on the closed path both unoccupied and occupied boxes may be skipped over. The cells at the turning points are called stepping stones' on the path.

(c)    Assigning plus (+) and signs alternatively each corner cell of the closed path just traced starting with a plus sign at the unoccupied cell to be evaluated.

(d)   Compute the net change in the cost along the closed path by adding together the unit cost figures found in each cell containing the minus sign.

(e)    Repeat sup-step (a) through sub-step (b) unit net change in cost has been calculated for all unoccupied cells of the transportation table.

Step 4 Checks the sign of each of the net changes. If all 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 total shipping costs.

Step 5 Select the unoccupied cells having the highest 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 minims sign.