Stepping Stone Method of Optimality Test

Stepping Stone Method of Optimality Test

Once, we get the basic feasible solution for a transportation problem, the next duty is to test whether the solution we got is an optimal solution or not?
1. Steps to test unused squares;
2. Select an unused square,
3. Allocate + ? unit to unused square and locate - ? and + ? alternatively to corners of the selected closed path.
4. Calculate the improvement index .
5. If improvement index is negative allocate as much as you can to that unused square.
Repeat the allocation till the improvement index is ? 0 for all unused squares.

Retail Agency

Factories 1 2 3 4 5

1 50 1
-1
9
+1
13 36 51

2 50 24
+1
50 12
-1 16
20
1


3 14
10 33
50 1
50 23
40 26

Improvement index (1 – 2) = 1*9-1*1+1*24-1*12= + 20 , this means if we allocate (1 – 2) +1 unit , then the transport cost will increase by +20.
Retail Agency

Factories 1 2 3 4 5

1 50 1
-1
9
13
+1
36 51

2 50 24
+1
50 12
-1
16
20
1


3 14
10 33
+1
50 1
-1 50 23
40 26

Improvement index (1 – 3) = 1*13-1*1+1*24-1*12+1*33-1*1= + 56 , this means if we allocate (1 – 3) +1 unit , then the transport cost will increase by +56.
Retail Agency

Factories 1 2 3 4 5

1 50 1
-1
9
13
36
+1
51


2 50 24
+1
50 12
-1
16
20
1


3 14
10 33
+1
50 1
50 23
-1 40 26


Improvement index (1– 4) = 1*13-1*1+1*24-1*12+1*33-1*23= + 34 , this means if we allocate (1 – 4) +1 unit , then the transport cost will increase by +24.
And so on …
Improvement index (1– 5) = 1*51-1*1+1*24-1*12+1*33-1*26= +73, this means if we allocate (1 – 5) +1 unit , then the transport cost will increase by +73.
Improvemen]t index (2– 3) = 1*16-1*12+1*33-1*1= +36, this means if we allocate (2 – 3) +1 unit , then the transport cost will increase by +36.

Improvement index (2– 4) = 1*20-1*12+1*33-1*23=+18, this means if we allocate (2 – 4) +1 unit , then the transport cost will increase by +18.

Improvement index (2– 5) = 1*1-1*12+1*33-1*26= - 4, this means if we allocate (2 – 5) +1 unit , then the transport cost will decrease by - 4.

Since there is a decrease in the cost, we will allocate as much as we can to ( 2 – 5 ). To further improve the current solution, select the "smallest" number found in the path ( 2-5 , 2-2 , 3-2 , 3-5 ) containing minus ( - ) signs. This number is added to all cells on the closed path with plus ( + ) signs, and subtracted from all cells on the path with minus ( - ) signs.
Retail Agency

Factories 1 2 3 4 5 Capacity

1 1
50 9 13 36 51 50

2 24
50 12
10 16
20
1
40
100

3 14
33
50 1
50 23
50 26

150
Requirement 100 60 50 50 40

Z= 50 * 1 + 50 * 24 + 10 * 12 + 50 * 33 + 50 * 1 + 50 * 23 + 40 * 1 = 4260.

1 2 3 4 5
1
50 9 13 36 51
50 24
-1
10 12
+1
16
20
1
40
14
+1
50 33
-1 1
50 23
50 26


Improvement index (3 – 1) = 1*14-1*33+1*12-1*24= - 31, this means if we allocate (3 – 1) +1 unit , then the transport cost will decrease by - 31.

Since there is a decrease in the cost, so,