Find Solution using Heuristic method-2
| D1 | D2 | D3 | D4 | Supply |
| S1 | 11 | 13 | 17 | 14 | 250 |
| S2 | 16 | 18 | 14 | 10 | 300 |
| S3 | 21 | 24 | 13 | 10 | 400 |
| Demand | 200 | 225 | 275 | 250 | |
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` | 11 | 13 | 17 | 14 | | 250 |
| `S_2` | 16 | 18 | 14 | 10 | | 300 |
| `S_3` | 21 | 24 | 13 | 10 | | 400 |
| |
| Demand | 200 | 225 | 275 | 250 | | |
Table-1
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty |
| `S_1` | 11 | 13 | 17 | 14 | | 250 | `6=17-11` |
| `S_2` | 16 | 18 | 14 | 10 | | 300 | `8=18-10` |
| `S_3` | 21 | 24 | 13 | 10 | | 400 | `14=24-10` |
| |
| Demand | 200 | 225 | 275 | 250 | | | |
Column
Penalty | `10=21-11` | `11=24-13` | `4=17-13` | `4=14-10` | | | |
The maximum penalty, 14, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_34` = 10.
The maximum allocation in this cell is min(400,250) = 250.
It satisfy demand of `D_4` and adjust the supply of `S_3` from 400 to 150 (400 - 250 = 150).
Table-2
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty |
| `S_1` | 11 | 13 | 17 | 14 | | 250 | `6=17-11` |
| `S_2` | 16 | 18 | 14 | 10 | | 300 | `4=18-14` |
| `S_3` | 21 | 24 | 13 | 10(250) | | 150 | `11=24-13` |
| |
| Demand | 200 | 225 | 275 | 0 | | | |
Column
Penalty | `10=21-11` | `11=24-13` | `4=17-13` | -- | | | |
The maximum penalty, 11, occurs in column `D_2`.
The minimum `c_(ij)` in this column is `c_12` = 13.
The maximum allocation in this cell is min(250,225) = 225.
It satisfy demand of `D_2` and adjust the supply of `S_1` from 250 to 25 (250 - 225 = 25).
Table-3
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty |
| `S_1` | 11 | 13(225) | 17 | 14 | | 25 | `6=17-11` |
| `S_2` | 16 | 18 | 14 | 10 | | 300 | `2=16-14` |
| `S_3` | 21 | 24 | 13 | 10(250) | | 150 | `8=21-13` |
| |
| Demand | 200 | 0 | 275 | 0 | | | |
Column
Penalty | `10=21-11` | -- | `4=17-13` | -- | | | |
The maximum penalty, 10, occurs in column `D_1`.
The minimum `c_(ij)` in this column is `c_11` = 11.
The maximum allocation in this cell is min(25,200) = 25.
It satisfy supply of `S_1` and adjust the demand of `D_1` from 200 to 175 (200 - 25 = 175).
Table-4
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty |
| `S_1` | 11(25) | 13(225) | 17 | 14 | | 0 | -- |
| `S_2` | 16 | 18 | 14 | 10 | | 300 | `2=16-14` |
| `S_3` | 21 | 24 | 13 | 10(250) | | 150 | `8=21-13` |
| |
| Demand | 175 | 0 | 275 | 0 | | | |
Column
Penalty | `5=21-16` | -- | `1=14-13` | -- | | | |
The maximum penalty, 8, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_33` = 13.
The maximum allocation in this cell is min(150,275) = 150.
It satisfy supply of `S_3` and adjust the demand of `D_3` from 275 to 125 (275 - 150 = 125).
Table-5
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty |
| `S_1` | 11(25) | 13(225) | 17 | 14 | | 0 | -- |
| `S_2` | 16 | 18 | 14 | 10 | | 300 | `2=16-14` |
| `S_3` | 21 | 24 | 13(150) | 10(250) | | 0 | -- |
| |
| Demand | 175 | 0 | 125 | 0 | | | |
Column
Penalty | `0=16-16` | -- | `0=14-14` | -- | | | |
The maximum penalty, 2, occurs in row `S_2`.
The minimum `c_(ij)` in this row is `c_23` = 14.
The maximum allocation in this cell is min(300,125) = 125.
It satisfy demand of `D_3` and adjust the supply of `S_2` from 300 to 175 (300 - 125 = 175).
Table-6
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty |
| `S_1` | 11(25) | 13(225) | 17 | 14 | | 0 | -- |
| `S_2` | 16 | 18 | 14(125) | 10 | | 175 | `0=16-16` |
| `S_3` | 21 | 24 | 13(150) | 10(250) | | 0 | -- |
| |
| Demand | 175 | 0 | 0 | 0 | | | |
Column
Penalty | `0=16-16` | -- | -- | -- | | | |
The maximum penalty, 0, occurs in row `S_2`.
The minimum `c_(ij)` in this row is `c_21` = 16.
The maximum allocation in this cell is min(175,175) = 175.
It satisfy supply of `S_2` and demand of `D_1`.
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty |
| `S_1` | 11(25) | 13(225) | 17 | 14 | | 250 | 6 | 6 | 6 | -- | -- | -- | |
| `S_2` | 16(175) | 18 | 14(125) | 10 | | 300 | 8 | 4 | 2 | 2 | 2 | 0 | |
| `S_3` | 21 | 24 | 13(150) | 10(250) | | 400 | 14 | 11 | 8 | 8 | -- | -- | |
| |
| Demand | 200 | 225 | 275 | 250 | | | |
Column
Penalty | 10
10
10
5
0
0
| 11
11
--
--
--
--
| 4
4
4
1
0
--
| 4
--
--
--
--
--
| | | |
The minimum total transportation cost `= 11 xx 25 + 13 xx 225 + 16 xx 175 + 14 xx 125 + 13 xx 150 + 10 xx 250 = 12200`
Here, the number of allocated cells = 6 is equal to m + n - 1 = 3 + 4 - 1 = 6
`:.` This solution is non-degenerate
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
