Find Solution of Transshipment Problem using vogel's approximation method
| S1 | S2 | S3 | S4 | D1 | D2 | Supply |
| S1 | 0 | 6 | 24 | 7 | 24 | 10 | 200 |
| S2 | 10 | 0 | 6 | 12 | 5 | 20 | 250 |
| S3 | 15 | 20 | 0 | 8 | 45 | 7 | 300 |
| S4 | 18 | 25 | 10 | 0 | 30 | 6 | 450 |
| D1 | 15 | 20 | 60 | 15 | 0 | 10 | 0 |
| D2 | 10 | 25 | 25 | 23 | 4 | 0 | 0 |
| Demand | 0 | 0 | 0 | 0 | 600 | 600 | |
Solution:Problem Table is
| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply |
| `S_1` | 0 | 6 | 24 | 7 | 24 | 10 | | 200 |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 250 |
| `S_3` | 15 | 20 | 0 | 8 | 45 | 7 | | 300 |
| `S_4` | 18 | 25 | 10 | 0 | 30 | 6 | | 450 |
| `D_1` | 15 | 20 | 60 | 15 | 0 | 10 | | 0 |
| `D_2` | 10 | 25 | 25 | 23 | 4 | 0 | | 0 |
| |
| Demand | 0 | 0 | 0 | 0 | 600 | 600 | | |
`S_1,S_2,S_3,S_4,D_1,D_2` are transshipment nodes
Add Total value `=1200` in supply and demand for transshipment nodes `S_1,S_2,S_3,S_4,D_1,D_2`
So again Problem Table is
| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply |
| `S_1` | 0 | 6 | 24 | 7 | 24 | 10 | | 1400 |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 1450 |
| `S_3` | 15 | 20 | 0 | 8 | 45 | 7 | | 1500 |
| `S_4` | 18 | 25 | 10 | 0 | 30 | 6 | | 1650 |
| `D_1` | 15 | 20 | 60 | 15 | 0 | 10 | | 1200 |
| `D_2` | 10 | 25 | 25 | 23 | 4 | 0 | | 1200 |
| |
| Demand | 1200 | 1200 | 1200 | 1200 | 1800 | 1800 | | |
Now, we solve this Transshipment problem
Table-1| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0 | 6 | 24 | 7 | 24 | 10 | | 1400 | `6=6-0` |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 1450 | `5=5-0` |
| `S_3` | 15 | 20 | 0 | 8 | 45 | 7 | | 1500 | `7=7-0` |
| `S_4` | 18 | 25 | 10 | 0 | 30 | 6 | | 1650 | `6=6-0` |
| `D_1` | 15 | 20 | 60 | 15 | 0 | 10 | | 1200 | `10=10-0` |
| `D_2` | 10 | 25 | 25 | 23 | 4 | 0 | | 1200 | `4=4-0` |
| |
| Demand | 1200 | 1200 | 1200 | 1200 | 1800 | 1800 | | | |
Column
Penalty | `10=10-0` | `6=6-0` | `6=6-0` | `7=7-0` | `4=4-0` | `6=6-0` | | | |
The maximum penalty, 10, occurs in row `D_1`.
The minimum `c_(ij)` in this row is `c_55`=0.
The maximum allocation in this cell is min(1200,1800) =
1200.
It satisfy supply of `D_1` and adjust the demand of `D_1` from 1800 to 600 (1800 - 1200=600).
Table-2| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0 | 6 | 24 | 7 | 24 | 10 | | 1400 | `6=6-0` |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 1450 | `5=5-0` |
| `S_3` | 15 | 20 | 0 | 8 | 45 | 7 | | 1500 | `7=7-0` |
| `S_4` | 18 | 25 | 10 | 0 | 30 | 6 | | 1650 | `6=6-0` |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 0 | -- |
| `D_2` | 10 | 25 | 25 | 23 | 4 | 0 | | 1200 | `4=4-0` |
| |
| Demand | 1200 | 1200 | 1200 | 1200 | 600 | 1800 | | | |
Column
Penalty | `10=10-0` | `6=6-0` | `6=6-0` | `7=7-0` | `1=5-4` | `6=6-0` | | | |
The maximum penalty, 10, occurs in column `S_1`.
The minimum `c_(ij)` in this column is `c_11`=0.
The maximum allocation in this cell is min(1400,1200) =
1200.
It satisfy demand of `S_1` and adjust the supply of `S_1` from 1400 to 200 (1400 - 1200=200).
Table-3| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0(1200) | 6 | 24 | 7 | 24 | 10 | | 200 | `1=7-6` |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 1450 | `5=5-0` |
| `S_3` | 15 | 20 | 0 | 8 | 45 | 7 | | 1500 | `7=7-0` |
| `S_4` | 18 | 25 | 10 | 0 | 30 | 6 | | 1650 | `6=6-0` |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 0 | -- |
| `D_2` | 10 | 25 | 25 | 23 | 4 | 0 | | 1200 | `4=4-0` |
| |
| Demand | 0 | 1200 | 1200 | 1200 | 600 | 1800 | | | |
Column
Penalty | -- | `6=6-0` | `6=6-0` | `7=7-0` | `1=5-4` | `6=6-0` | | | |
The maximum penalty, 7, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_33`=0.
The maximum allocation in this cell is min(1500,1200) =
1200.
It satisfy demand of `S_3` and adjust the supply of `S_3` from 1500 to 300 (1500 - 1200=300).
Table-4| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0(1200) | 6 | 24 | 7 | 24 | 10 | | 200 | `1=7-6` |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 1450 | `5=5-0` |
| `S_3` | 15 | 20 | 0(1200) | 8 | 45 | 7 | | 300 | `1=8-7` |
| `S_4` | 18 | 25 | 10 | 0 | 30 | 6 | | 1650 | `6=6-0` |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 0 | -- |
| `D_2` | 10 | 25 | 25 | 23 | 4 | 0 | | 1200 | `4=4-0` |
| |
| Demand | 0 | 1200 | 0 | 1200 | 600 | 1800 | | | |
Column
Penalty | -- | `6=6-0` | -- | `7=7-0` | `1=5-4` | `6=6-0` | | | |
The maximum penalty, 7, occurs in column `S_4`.
The minimum `c_(ij)` in this column is `c_44`=0.
The maximum allocation in this cell is min(1650,1200) =
1200.
It satisfy demand of `S_4` and adjust the supply of `S_4` from 1650 to 450 (1650 - 1200=450).
Table-5| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0(1200) | 6 | 24 | 7 | 24 | 10 | | 200 | `4=10-6` |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 1450 | `5=5-0` |
| `S_3` | 15 | 20 | 0(1200) | 8 | 45 | 7 | | 300 | `13=20-7` |
| `S_4` | 18 | 25 | 10 | 0(1200) | 30 | 6 | | 450 | `19=25-6` |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 0 | -- |
| `D_2` | 10 | 25 | 25 | 23 | 4 | 0 | | 1200 | `4=4-0` |
| |
| Demand | 0 | 1200 | 0 | 0 | 600 | 1800 | | | |
Column
Penalty | -- | `6=6-0` | -- | -- | `1=5-4` | `6=6-0` | | | |
The maximum penalty, 19, occurs in row `S_4`.
The minimum `c_(ij)` in this row is `c_46`=6.
The maximum allocation in this cell is min(450,1800) =
450.
It satisfy supply of `S_4` and adjust the demand of `D_2` from 1800 to 1350 (1800 - 450=1350).
Table-6| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0(1200) | 6 | 24 | 7 | 24 | 10 | | 200 | `4=10-6` |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 1450 | `5=5-0` |
| `S_3` | 15 | 20 | 0(1200) | 8 | 45 | 7 | | 300 | `13=20-7` |
| `S_4` | 18 | 25 | 10 | 0(1200) | 30 | 6(450) | | 0 | -- |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 0 | -- |
| `D_2` | 10 | 25 | 25 | 23 | 4 | 0 | | 1200 | `4=4-0` |
| |
| Demand | 0 | 1200 | 0 | 0 | 600 | 1350 | | | |
Column
Penalty | -- | `6=6-0` | -- | -- | `1=5-4` | `7=7-0` | | | |
The maximum penalty, 13, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_36`=7.
The maximum allocation in this cell is min(300,1350) =
300.
It satisfy supply of `S_3` and adjust the demand of `D_2` from 1350 to 1050 (1350 - 300=1050).
Table-7| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0(1200) | 6 | 24 | 7 | 24 | 10 | | 200 | `4=10-6` |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 1450 | `5=5-0` |
| `S_3` | 15 | 20 | 0(1200) | 8 | 45 | 7(300) | | 0 | -- |
| `S_4` | 18 | 25 | 10 | 0(1200) | 30 | 6(450) | | 0 | -- |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 0 | -- |
| `D_2` | 10 | 25 | 25 | 23 | 4 | 0 | | 1200 | `4=4-0` |
| |
| Demand | 0 | 1200 | 0 | 0 | 600 | 1050 | | | |
Column
Penalty | -- | `6=6-0` | -- | -- | `1=5-4` | `10=10-0` | | | |
The maximum penalty, 10, occurs in column `D_2`.
The minimum `c_(ij)` in this column is `c_66`=0.
The maximum allocation in this cell is min(1200,1050) =
1050.
It satisfy demand of `D_2` and adjust the supply of `D_2` from 1200 to 150 (1200 - 1050=150).
Table-8| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0(1200) | 6 | 24 | 7 | 24 | 10 | | 200 | `18=24-6` |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 1450 | `5=5-0` |
| `S_3` | 15 | 20 | 0(1200) | 8 | 45 | 7(300) | | 0 | -- |
| `S_4` | 18 | 25 | 10 | 0(1200) | 30 | 6(450) | | 0 | -- |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 0 | -- |
| `D_2` | 10 | 25 | 25 | 23 | 4 | 0(1050) | | 150 | `21=25-4` |
| |
| Demand | 0 | 1200 | 0 | 0 | 600 | 0 | | | |
Column
Penalty | -- | `6=6-0` | -- | -- | `1=5-4` | -- | | | |
The maximum penalty, 21, occurs in row `D_2`.
The minimum `c_(ij)` in this row is `c_65`=4.
The maximum allocation in this cell is min(150,600) =
150.
It satisfy supply of `D_2` and adjust the demand of `D_1` from 600 to 450 (600 - 150=450).
Table-9| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0(1200) | 6 | 24 | 7 | 24 | 10 | | 200 | `18=24-6` |
| `S_2` | 10 | 0 | 6 | 12 | 5 | 20 | | 1450 | `5=5-0` |
| `S_3` | 15 | 20 | 0(1200) | 8 | 45 | 7(300) | | 0 | -- |
| `S_4` | 18 | 25 | 10 | 0(1200) | 30 | 6(450) | | 0 | -- |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 0 | -- |
| `D_2` | 10 | 25 | 25 | 23 | 4(150) | 0(1050) | | 0 | -- |
| |
| Demand | 0 | 1200 | 0 | 0 | 450 | 0 | | | |
Column
Penalty | -- | `6=6-0` | -- | -- | `19=24-5` | -- | | | |
The maximum penalty, 19, occurs in column `D_1`.
The minimum `c_(ij)` in this column is `c_25`=5.
The maximum allocation in this cell is min(1450,450) =
450.
It satisfy demand of `D_1` and adjust the supply of `S_2` from 1450 to 1000 (1450 - 450=1000).
Table-10| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0(1200) | 6 | 24 | 7 | 24 | 10 | | 200 | `6` |
| `S_2` | 10 | 0 | 6 | 12 | 5(450) | 20 | | 1000 | `0` |
| `S_3` | 15 | 20 | 0(1200) | 8 | 45 | 7(300) | | 0 | -- |
| `S_4` | 18 | 25 | 10 | 0(1200) | 30 | 6(450) | | 0 | -- |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 0 | -- |
| `D_2` | 10 | 25 | 25 | 23 | 4(150) | 0(1050) | | 0 | -- |
| |
| Demand | 0 | 1200 | 0 | 0 | 0 | 0 | | | |
Column
Penalty | -- | `6=6-0` | -- | -- | -- | -- | | | |
The maximum penalty, 6, occurs in column `S_2`.
The minimum `c_(ij)` in this column is `c_22`=0.
The maximum allocation in this cell is min(1000,1200) =
1000.
It satisfy supply of `S_2` and adjust the demand of `S_2` from 1200 to 200 (1200 - 1000=200).
Table-11| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0(1200) | 6 | 24 | 7 | 24 | 10 | | 200 | `6` |
| `S_2` | 10 | 0(1000) | 6 | 12 | 5(450) | 20 | | 0 | -- |
| `S_3` | 15 | 20 | 0(1200) | 8 | 45 | 7(300) | | 0 | -- |
| `S_4` | 18 | 25 | 10 | 0(1200) | 30 | 6(450) | | 0 | -- |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 0 | -- |
| `D_2` | 10 | 25 | 25 | 23 | 4(150) | 0(1050) | | 0 | -- |
| |
| Demand | 0 | 200 | 0 | 0 | 0 | 0 | | | |
Column
Penalty | -- | `6` | -- | -- | -- | -- | | | |
The maximum penalty, 6, occurs in row `S_1`.
The minimum `c_(ij)` in this row is `c_12`=6.
The maximum allocation in this cell is min(200,200) =
200.
It satisfy supply of `S_1` and demand of `S_2`.
Initial feasible solution is
| | `S_1` | `S_2` | `S_3` | `S_4` | `D_1` | `D_2` | | Supply | Row Penalty |
| `S_1` | 0(1200) | 6(200) | 24 | 7 | 24 | 10 | | 1400 | 6 | 6 | 1 | 1 | 4 | 4 | 4 | 18 | 18 | 6 | 6 | |
| `S_2` | 10 | 0(1000) | 6 | 12 | 5(450) | 20 | | 1450 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 0 | -- | |
| `S_3` | 15 | 20 | 0(1200) | 8 | 45 | 7(300) | | 1500 | 7 | 7 | 7 | 1 | 13 | 13 | -- | -- | -- | -- | -- | |
| `S_4` | 18 | 25 | 10 | 0(1200) | 30 | 6(450) | | 1650 | 6 | 6 | 6 | 6 | 19 | -- | -- | -- | -- | -- | -- | |
| `D_1` | 15 | 20 | 60 | 15 | 0(1200) | 10 | | 1200 | 10 | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | |
| `D_2` | 10 | 25 | 25 | 23 | 4(150) | 0(1050) | | 1200 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 21 | -- | -- | -- | |
| |
| Demand | 1200 | 1200 | 1200 | 1200 | 1800 | 1800 | | | |
Column
Penalty | 10
10
--
--
--
--
--
--
--
--
--
| 6
6
6
6
6
6
6
6
6
6
6
| 6
6
6
--
--
--
--
--
--
--
--
| 7
7
7
7
--
--
--
--
--
--
--
| 4
1
1
1
1
1
1
1
19
--
--
| 6
6
6
6
6
7
10
--
--
--
--
| | | |
The minimum total transportation cost `=0 xx 1200+6 xx 200+0 xx 1000+5 xx 450+0 xx 1200+7 xx 300+0 xx 1200+6 xx 450+0 xx 1200+4 xx 150+0 xx 1050=8850`
Here, the number of allocated cells = 11 is equal to m + n - 1 = 6 + 6 - 1 = 11
`:.` This solution is non-degenerate
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
