3. Unbalanced supply and demand example
Unbalanced supply and demand
If the total supply is not equal to the total demand then the problem is called unbalanced transportation problem.
It's solution :
1. If the total supply is more than the total demand, then we add a new column, with transportation cost 0
2. If the total demand is more than the total supply, then we add a new row, with transportation cost 0
Example
Find Solution using Voggel's Approximation method
| D1 | D2 | D3 | Supply | | S1 | 4 | 8 | 8 | 76 | | S2 | 16 | 24 | 16 | 82 | | S3 | 8 | 16 | 24 | 77 | | Demand | 72 | 102 | 41 | |
Solution:
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 3
Problem Table is
| | `D_1` | `D_2` | `D_3` | | Supply | | `S_1` | 4 | 8 | 8 | | 76 | | `S_2` | 16 | 24 | 16 | | 82 | | `S_3` | 8 | 16 | 24 | | 77 | | | | Demand | 72 | 102 | 41 | | |
Here Total Demand = 215 is less than Total Supply = 235. So We add a dummy demand constraint with 0 unit cost and with allocation 20.
Now, The modified table is
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | | `S_1` | 4 | 8 | 8 | 0 | | 76 | | `S_2` | 16 | 24 | 16 | 0 | | 82 | | `S_3` | 8 | 16 | 24 | 0 | | 77 | | | | Demand | 72 | 102 | 41 | 20 | | |
Table-1
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | Row Penalty | | `S_1` | 4 | 8 | 8 | 0 | | 76 | `4=4-0` | | `S_2` | 16 | 24 | 16 | 0 | | 82 | `16=16-0` | | `S_3` | 8 | 16 | 24 | 0 | | 77 | `8=8-0` | | | | Demand | 72 | 102 | 41 | 20 | | | | Column
Penalty | `4=8-4` | `8=16-8` | `8=16-8` | `0=0-0` | | | |
The maximum penalty, 16, occurs in row `S_2`.
The minimum `c_(ij)` in this row is `c_24` = 0.
The maximum allocation in this cell is min(82,20) = 20.
It satisfy demand of `D_(dummy)` and adjust the supply of `S_2` from 82 to 62 (82 - 20 = 62).
Table-2
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | Row Penalty | | `S_1` | 4 | 8 | 8 | 0 | | 76 | `4=8-4` | | `S_2` | 16 | 24 | 16 | 0(20) | | 62 | `0=16-16` | | `S_3` | 8 | 16 | 24 | 0 | | 77 | `8=16-8` | | | | Demand | 72 | 102 | 41 | 0 | | | | Column
Penalty | `4=8-4` | `8=16-8` | `8=16-8` | -- | | | |
The maximum penalty, 8, occurs in column `D_2`.
The minimum `c_(ij)` in this column is `c_12` = 8.
The maximum allocation in this cell is min(76,102) = 76.
It satisfy supply of `S_1` and adjust the demand of `D_2` from 102 to 26 (102 - 76 = 26).
Table-3
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | Row Penalty | | `S_1` | 4 | 8(76) | 8 | 0 | | 0 | -- | | `S_2` | 16 | 24 | 16 | 0(20) | | 62 | `0=16-16` | | `S_3` | 8 | 16 | 24 | 0 | | 77 | `8=16-8` | | | | Demand | 72 | 26 | 41 | 0 | | | | Column
Penalty | `8=16-8` | `8=24-16` | `8=24-16` | -- | | | |
The maximum penalty, 8, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_31` = 8.
The maximum allocation in this cell is min(77,72) = 72.
It satisfy demand of `D_1` and adjust the supply of `S_3` from 77 to 5 (77 - 72 = 5).
Table-4
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | Row Penalty | | `S_1` | 4 | 8(76) | 8 | 0 | | 0 | -- | | `S_2` | 16 | 24 | 16 | 0(20) | | 62 | `8=24-16` | | `S_3` | 8(72) | 16 | 24 | 0 | | 5 | `8=24-16` | | | | Demand | 0 | 26 | 41 | 0 | | | | Column
Penalty | -- | `8=24-16` | `8=24-16` | -- | | | |
The maximum penalty, 8, occurs in row `S_2`.
The minimum `c_(ij)` in this row is `c_23` = 16.
The maximum allocation in this cell is min(62,41) = 41.
It satisfy demand of `D_3` and adjust the supply of `S_2` from 62 to 21 (62 - 41 = 21).
Table-5
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | Row Penalty | | `S_1` | 4 | 8(76) | 8 | 0 | | 0 | -- | | `S_2` | 16 | 24 | 16(41) | 0(20) | | 21 | `24` | | `S_3` | 8(72) | 16 | 24 | 0 | | 5 | `16` | | | | Demand | 0 | 26 | 0 | 0 | | | | Column
Penalty | -- | `8=24-16` | -- | -- | | | |
The maximum penalty, 24, occurs in row `S_2`.
The minimum `c_(ij)` in this row is `c_22` = 24.
The maximum allocation in this cell is min(21,26) = 21.
It satisfy supply of `S_2` and adjust the demand of `D_2` from 26 to 5 (26 - 21 = 5).
Table-6
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | Row Penalty | | `S_1` | 4 | 8(76) | 8 | 0 | | 0 | -- | | `S_2` | 16 | 24(21) | 16(41) | 0(20) | | 0 | -- | | `S_3` | 8(72) | 16 | 24 | 0 | | 5 | `16` | | | | Demand | 0 | 5 | 0 | 0 | | | | Column
Penalty | -- | `16` | -- | -- | | | |
The maximum penalty, 16, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_32` = 16.
The maximum allocation in this cell is min(5,5) = 5.
It satisfy supply of `S_3` and demand of `D_2`.
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | Row Penalty | | `S_1` | 4 | 8(76) | 8 | 0 | | 76 | 4 | 4 | -- | -- | -- | -- | | | `S_2` | 16 | 24(21) | 16(41) | 0(20) | | 82 | 16 | 0 | 0 | 8 | 24 | -- | | | `S_3` | 8(72) | 16(5) | 24 | 0 | | 77 | 8 | 8 | 8 | 8 | 16 | 16 | | | | | Demand | 72 | 102 | 41 | 20 | | | | Column
Penalty | 4
4
8
--
--
--
| 8
8
8
8
8
16
| 8
8
8
8
--
--
| 0
--
--
--
--
--
| | | |
The minimum total transportation cost `= 8 xx 76 + 24 xx 21 + 16 xx 41 + 0 xx 20 + 8 xx 72 + 16 xx 5 = 2424`
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
|
