1. Algorithm & Example-1
Algorithm
|
Stepping Stone Method Steps (Rule)
|
|
Step-1:
|
Find an initial basic feasible solution using any one of the three methods NWCM, LCM or VAM.
|
|
Step-2:
|
1. Draw a closed path (or loop) from an unoccupied cell. The right angle turn in this path is allowed only at occupied cells and at the original unoccupied cell. Mark (+) and (-) sign alternatively at each corner, starting from the original unoccupied cell.
2. Add the transportation costs of each cell traced in the closed path. This is called net cost change.
3. Repeat this for all other unoccupied cells.
|
|
Step-3:
|
1. If all the net cost change are `>=0`, an optimal solution has been reached. Now stop this procedure.
2. If not then select the unoccupied cell having the highest negative net cost change and draw a closed path.
|
|
Step-4:
|
1. Select minimum allocated value among all negative position (-) on closed path
2. Assign this value to selected unoccupied cell (So unoccupied cell becomes occupied cell).
3. Add this value to the other occupied cells marked with (+) sign.
4. Subtract this value to the other occupied cells marked with (-) sign.
|
|
Step-5:
|
Repeat Step-2 to step-4 until optimal solution is obtained. This procedure stops when all net cost change `>= 0` for unoccupied cells.
|
Example-1
Find Solution using Voggel's Approximation method, also find optimal solution using stepping stone method
| D1 | D2 | D3 | D4 | Supply | | S1 | 19 | 30 | 50 | 10 | 7 | | S2 | 70 | 30 | 40 | 60 | 9 | | S3 | 40 | 8 | 70 | 20 | 18 | | Demand | 5 | 8 | 7 | 14 | |
Solution:
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 4
Problem Table is
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 | 30 | 50 | 10 | | 7 | | `S_2` | 70 | 30 | 40 | 60 | | 9 | | `S_3` | 40 | 8 | 70 | 20 | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
Table-1
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19 | 30 | 50 | 10 | | 7 | `9=19-10` | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `10=40-30` | | `S_3` | 40 | 8 | 70 | 20 | | 18 | `12=20-8` | | | | Demand | 5 | 8 | 7 | 14 | | | | Column
Penalty | `21=40-19` | `22=30-8` | `10=50-40` | `10=20-10` | | | |
The maximum penalty, 22, occurs in column `D_2`.
The minimum `c_(ij)` in this column is `c_32` = 8.
The maximum allocation in this cell is min(18,8) = 8.
It satisfy demand of `D_2` and adjust the supply of `S_3` from 18 to 10 (18 - 8 = 10).
Table-2
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19 | 30 | 50 | 10 | | 7 | `9=19-10` | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `20=60-40` | | `S_3` | 40 | 8(8) | 70 | 20 | | 10 | `20=40-20` | | | | Demand | 5 | 0 | 7 | 14 | | | | Column
Penalty | `21=40-19` | -- | `10=50-40` | `10=20-10` | | | |
The maximum penalty, 21, occurs in column `D_1`.
The minimum `c_(ij)` in this column is `c_11` = 19.
The maximum allocation in this cell is min(7,5) = 5.
It satisfy demand of `D_1` and adjust the supply of `S_1` from 7 to 2 (7 - 5 = 2).
Table-3
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10 | | 2 | `40=50-10` | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `20=60-40` | | `S_3` | 40 | 8(8) | 70 | 20 | | 10 | `50=70-20` | | | | Demand | 0 | 0 | 7 | 14 | | | | Column
Penalty | -- | -- | `10=50-40` | `10=20-10` | | | |
The maximum penalty, 50, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_34` = 20.
The maximum allocation in this cell is min(10,14) = 10.
It satisfy supply of `S_3` and adjust the demand of `D_4` from 14 to 4 (14 - 10 = 4).
Table-4
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10 | | 2 | `40=50-10` | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `20=60-40` | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 0 | -- | | | | Demand | 0 | 0 | 7 | 4 | | | | Column
Penalty | -- | -- | `10=50-40` | `50=60-10` | | | |
The maximum penalty, 50, occurs in column `D_4`.
The minimum `c_(ij)` in this column is `c_14` = 10.
The maximum allocation in this cell is min(2,4) = 2.
It satisfy supply of `S_1` and adjust the demand of `D_4` from 4 to 2 (4 - 2 = 2).
Table-5
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10(2) | | 0 | -- | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `20=60-40` | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 0 | -- | | | | Demand | 0 | 0 | 7 | 2 | | | | Column
Penalty | -- | -- | `40` | `60` | | | |
The maximum penalty, 60, occurs in column `D_4`.
The minimum `c_(ij)` in this column is `c_24` = 60.
The maximum allocation in this cell is min(9,2) = 2.
It satisfy demand of `D_4` and adjust the supply of `S_2` from 9 to 7 (9 - 2 = 7).
Table-6
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10(2) | | 0 | -- | | `S_2` | 70 | 30 | 40 | 60(2) | | 7 | `40` | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 0 | -- | | | | Demand | 0 | 0 | 7 | 0 | | | | Column
Penalty | -- | -- | `40` | -- | | | |
The maximum penalty, 40, occurs in row `S_2`.
The minimum `c_(ij)` in this row is `c_23` = 40.
The maximum allocation in this cell is min(7,7) = 7.
It satisfy supply of `S_2` and demand of `D_3`.
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10(2) | | 7 | 9 | 9 | 40 | 40 | -- | -- | | | `S_2` | 70 | 30 | 40(7) | 60(2) | | 9 | 10 | 20 | 20 | 20 | 20 | 40 | | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 18 | 12 | 20 | 50 | -- | -- | -- | | | | | Demand | 5 | 8 | 7 | 14 | | | | Column
Penalty | 21
21
--
--
--
--
| 22
--
--
--
--
--
| 10
10
10
10
40
40
| 10
10
10
50
60
--
| | | |
The minimum total transportation cost `= 19 xx 5 + 10 xx 2 + 40 xx 7 + 60 xx 2 + 8 xx 8 + 20 xx 10 = 779`
Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
`:.` This solution is non-degenerate
Optimality test using stepping stone method...
Allocation Table is
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 (5) | 30 | 50 | 10 (2) | | 7 | | `S_2` | 70 | 30 | 40 (7) | 60 (2) | | 9 | | `S_3` | 40 | 8 (8) | 70 | 20 (10) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
Iteration-1 of optimality test
1. Create closed loop for unoccupied cells, we get
| Unoccupied cell | Closed path | Net cost change | | `S_1D_2` | `S_1D_2->S_1D_4->S_3D_4->S_3D_2` | 30 - 10 + 20 - 8 = 32 | | `S_1D_3` | `S_1D_3->S_1D_4->S_2D_4->S_2D_3` | 50 - 10 + 60 - 40 = 60 | | `S_2D_1` | `S_2D_1->S_2D_4->S_1D_4->S_1D_1` | 70 - 60 + 10 - 19 = 1 | | `S_2D_2` | `S_2D_2->S_2D_4->S_3D_4->S_3D_2` | 30 - 60 + 20 - 8 = -18 | | `S_3D_1` | `S_3D_1->S_3D_4->S_1D_4->S_1D_1` | 40 - 20 + 10 - 19 = 11 | | `S_3D_3` | `S_3D_3->S_3D_4->S_2D_4->S_2D_3` | 70 - 20 + 60 - 40 = 70 |
2. Select the unoccupied cell having the highest negative net cost change i.e. cell `S_2D_2=-18`.
and draw a closed path from `S_2D_2`.
Closed path is `S_2D_2->S_2D_4->S_3D_4->S_3D_2`
Closed path and plus/minus allocation for current unoccupied cell `S_2D_2`
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 (5) | 30 [32] | 50 [60] | 10 (2) | | 7 | | `S_2` | 70 [1] | 30 [-18] (+) | 40 (7) | 60 (2) (-) | | 9 | | `S_3` | 40 [11] | 8 (8) (-) | 70 [70] | 20 (10) (+) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
3. Minimum allocated value among all negative position (-) on closed path = 2
Substract 2 from all (-) and Add it to all (+)
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 (5) | 30 | 50 | 10 (2) | | 7 | | `S_2` | 70 | 30 (2) | 40 (7) | 60 | | 9 | | `S_3` | 40 | 8 (6) | 70 | 20 (12) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
4. Repeat the step 1 to 3, until an optimal solution is obtained.
Iteration-2 of optimality test
1. Create closed loop for unoccupied cells, we get
| Unoccupied cell | Closed path | Net cost change | | `S_1D_2` | `S_1D_2->S_1D_4->S_3D_4->S_3D_2` | 30 - 10 + 20 - 8 = 32 | | `S_1D_3` | `S_1D_3->S_1D_4->S_3D_4->S_3D_2->S_2D_2->S_2D_3` | 50 - 10 + 20 - 8 + 30 - 40 = 42 | | `S_2D_1` | `S_2D_1->S_2D_2->S_3D_2->S_3D_4->S_1D_4->S_1D_1` | 70 - 30 + 8 - 20 + 10 - 19 = 19 | | `S_2D_4` | `S_2D_4->S_2D_2->S_3D_2->S_3D_4` | 60 - 30 + 8 - 20 = 18 | | `S_3D_1` | `S_3D_1->S_3D_4->S_1D_4->S_1D_1` | 40 - 20 + 10 - 19 = 11 | | `S_3D_3` | `S_3D_3->S_3D_2->S_2D_2->S_2D_3` | 70 - 8 + 30 - 40 = 52 |
Since all net cost change `>=0`
So final optimal solution is arrived.
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 (5) | 30 | 50 | 10 (2) | | 7 | | `S_2` | 70 | 30 (2) | 40 (7) | 60 | | 9 | | `S_3` | 40 | 8 (6) | 70 | 20 (12) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
The minimum total transportation cost `= 19 xx 5 + 10 xx 2 + 30 xx 2 + 40 xx 7 + 8 xx 6 + 20 xx 12 = 743`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
