4. Degeneracy at initial solution
Degeneracy
If the basic feasible solution of a transportation problem with m rows and n columns has less than m + n - 1 allocation, then the problem is called degenerate transportation problem.
It may occur at
1. At the initial solution
2. At subsequent iterations of testing of the optimal solution
Example
Find Solution using Voggel's Approximation method, also find optimal solution using modi method,
| D1 | D2 | D3 | D4 | D5 | Supply | | S1 | 5 | 8 | 6 | 6 | 3 | 8 | | S2 | 4 | 7 | 7 | 6 | 5 | 5 | | S3 | 8 | 4 | 6 | 6 | 4 | 9 | | Demand | 4 | 4 | 5 | 4 | 8 | |
Solution:
TOTAL number of supply constraints : 3
TOTAL number of demand constraints : 5
Problem Table is
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | | `S_1` | 5 | 8 | 6 | 6 | 3 | | 8 | | `S_2` | 4 | 7 | 7 | 6 | 5 | | 5 | | `S_3` | 8 | 4 | 6 | 6 | 4 | | 9 | | | | Demand | 4 | 4 | 5 | 4 | 8 | | |
Here Total Demand = 25 is greater than Total Supply = 22. So We add a dummy supply constraint with 0 unit cost and with allocation 3.
Now, The modified table is
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | | `S_1` | 5 | 8 | 6 | 6 | 3 | | 8 | | `S_2` | 4 | 7 | 7 | 6 | 5 | | 5 | | `S_3` | 8 | 4 | 6 | 6 | 4 | | 9 | | `S_(dummy)` | 0 | 0 | 0 | 0 | 0 | | 3 | | | | Demand | 4 | 4 | 5 | 4 | 8 | | |
Table-1
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | Row Penalty | | `S_1` | 5 | 8 | 6 | 6 | 3 | | 8 | `2=5-3` | | `S_2` | 4 | 7 | 7 | 6 | 5 | | 5 | `1=5-4` | | `S_3` | 8 | 4 | 6 | 6 | 4 | | 9 | `0=4-4` | | `S_(dummy)` | 0 | 0 | 0 | 0 | 0 | | 3 | `0=0-0` | | | | Demand | 4 | 4 | 5 | 4 | 8 | | | | Column
Penalty | `4=4-0` | `4=4-0` | `6=6-0` | `6=6-0` | `3=3-0` | | | |
The maximum penalty, 6, occurs in column `D_3`.
The minimum `c_(ij)` in this column is `c_43` = 0.
The maximum allocation in this cell is min(3,5) = 3.
It satisfy supply of `S_(dummy)` and adjust the demand of `D_3` from 5 to 2 (5 - 3 = 2).
Table-2
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | Row Penalty | | `S_1` | 5 | 8 | 6 | 6 | 3 | | 8 | `2=5-3` | | `S_2` | 4 | 7 | 7 | 6 | 5 | | 5 | `1=5-4` | | `S_3` | 8 | 4 | 6 | 6 | 4 | | 9 | `0=4-4` | | `S_(dummy)` | 0 | 0 | 0(3) | 0 | 0 | | 0 | -- | | | | Demand | 4 | 4 | 2 | 4 | 8 | | | | Column
Penalty | `1=5-4` | `3=7-4` | `0=6-6` | `0=6-6` | `1=4-3` | | | |
The maximum penalty, 3, occurs in column `D_2`.
The minimum `c_(ij)` in this column is `c_32` = 4.
The maximum allocation in this cell is min(9,4) = 4.
It satisfy demand of `D_2` and adjust the supply of `S_3` from 9 to 5 (9 - 4 = 5).
Table-3
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | Row Penalty | | `S_1` | 5 | 8 | 6 | 6 | 3 | | 8 | `2=5-3` | | `S_2` | 4 | 7 | 7 | 6 | 5 | | 5 | `1=5-4` | | `S_3` | 8 | 4(4) | 6 | 6 | 4 | | 5 | `2=6-4` | | `S_(dummy)` | 0 | 0 | 0(3) | 0 | 0 | | 0 | -- | | | | Demand | 4 | 0 | 2 | 4 | 8 | | | | Column
Penalty | `1=5-4` | -- | `0=6-6` | `0=6-6` | `1=4-3` | | | |
The maximum penalty, 2, occurs in row `S_1`.
The minimum `c_(ij)` in this row is `c_15` = 3.
The maximum allocation in this cell is min(8,8) = 8.
It satisfy supply of `S_1` and demand of `D_5`.
Table-4
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | Row Penalty | | `S_1` | 5 | 8 | 6 | 6 | 3(8) | | 0 | -- | | `S_2` | 4 | 7 | 7 | 6 | 5 | | 5 | `2=6-4` | | `S_3` | 8 | 4(4) | 6 | 6 | 4 | | 5 | `0=6-6` | | `S_(dummy)` | 0 | 0 | 0(3) | 0 | 0 | | 0 | -- | | | | Demand | 4 | 0 | 2 | 4 | 0 | | | | Column
Penalty | `4=8-4` | -- | `1=7-6` | `0=6-6` | -- | | | |
The maximum penalty, 4, occurs in column `D_1`.
The minimum `c_(ij)` in this column is `c_21` = 4.
The maximum allocation in this cell is min(5,4) = 4.
It satisfy demand of `D_1` and adjust the supply of `S_2` from 5 to 1 (5 - 4 = 1).
Table-5
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | Row Penalty | | `S_1` | 5 | 8 | 6 | 6 | 3(8) | | 0 | -- | | `S_2` | 4(4) | 7 | 7 | 6 | 5 | | 1 | `1=7-6` | | `S_3` | 8 | 4(4) | 6 | 6 | 4 | | 5 | `0=6-6` | | `S_(dummy)` | 0 | 0 | 0(3) | 0 | 0 | | 0 | -- | | | | Demand | 0 | 0 | 2 | 4 | 0 | | | | Column
Penalty | -- | -- | `1=7-6` | `0=6-6` | -- | | | |
The maximum penalty, 1, occurs in column `D_3`.
The minimum `c_(ij)` in this column is `c_33` = 6.
The maximum allocation in this cell is min(5,2) = 2.
It satisfy demand of `D_3` and adjust the supply of `S_3` from 5 to 3 (5 - 2 = 3).
Table-6
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | Row Penalty | | `S_1` | 5 | 8 | 6 | 6 | 3(8) | | 0 | -- | | `S_2` | 4(4) | 7 | 7 | 6 | 5 | | 1 | `6` | | `S_3` | 8 | 4(4) | 6(2) | 6 | 4 | | 3 | `6` | | `S_(dummy)` | 0 | 0 | 0(3) | 0 | 0 | | 0 | -- | | | | Demand | 0 | 0 | 0 | 4 | 0 | | | | Column
Penalty | -- | -- | -- | `0=6-6` | -- | | | |
The maximum penalty, 6, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_34` = 6.
The maximum allocation in this cell is min(3,4) = 3.
It satisfy supply of `S_3` and adjust the demand of `D_4` from 4 to 1 (4 - 3 = 1).
Table-7
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | Row Penalty | | `S_1` | 5 | 8 | 6 | 6 | 3(8) | | 0 | -- | | `S_2` | 4(4) | 7 | 7 | 6 | 5 | | 1 | `6` | | `S_3` | 8 | 4(4) | 6(2) | 6(3) | 4 | | 0 | -- | | `S_(dummy)` | 0 | 0 | 0(3) | 0 | 0 | | 0 | -- | | | | Demand | 0 | 0 | 0 | 1 | 0 | | | | Column
Penalty | -- | -- | -- | `6` | -- | | | |
The maximum penalty, 6, occurs in row `S_2`.
The minimum `c_(ij)` in this row is `c_24` = 6.
The maximum allocation in this cell is min(1,1) = 1.
It satisfy supply of `S_2` and demand of `D_4`.
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | Row Penalty | | `S_1` | 5 | 8 | 6 | 6 | 3(8) | | 8 | 2 | 2 | 2 | -- | -- | -- | -- | | | `S_2` | 4(4) | 7 | 7 | 6(1) | 5 | | 5 | 1 | 1 | 1 | 2 | 1 | 6 | 6 | | | `S_3` | 8 | 4(4) | 6(2) | 6(3) | 4 | | 9 | 0 | 0 | 2 | 0 | 0 | 6 | -- | | | `S_(dummy)` | 0 | 0 | 0(3) | 0 | 0 | | 3 | 0 | -- | -- | -- | -- | -- | -- | | | | | Demand | 4 | 4 | 5 | 4 | 8 | | | | Column
Penalty | 4
1
1
4
--
--
--
| 4
3
--
--
--
--
--
| 6
0
0
1
1
--
--
| 6
0
0
0
0
0
6
| 3
1
1
--
--
--
--
| | | |
The minimum total transportation cost `= 3 xx 8 + 4 xx 4 + 6 xx 1 + 4 xx 4 + 6 xx 2 + 6 xx 3 + 0 xx 3 = 92`
Here, the number of allocated cells = 7, which is one less than to m + n - 1 = 4 + 5 - 1 = 8
`:.` This solution is degenerate
To resolve degeneracy, we make use of an artifical quantity(d).
The quantity d is assigned to that unoccupied cell, which has the minimum transportation cost.
The quantity d is assigned to `S_3D_5`, which has the minimum transportation cost = 4.
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | | `S_1` | 5 | 8 | 6 | 6 | 3 (8) | | 8 | | `S_2` | 4 (4) | 7 | 7 | 6 (1) | 5 | | 5 | | `S_3` | 8 | 4 (4) | 6 (2) | 6 (3) | 4 (d) | | 9 | | `S_(dummy)` | 0 | 0 | 0 (3) | 0 | 0 | | 3 | | | | Demand | 4 | 4 | 5 | 4 | 8 | | |
Optimality test using modi method...
Allocation Table is
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | | `S_1` | 5 | 8 | 6 | 6 | 3 (8) | | 8 | | `S_2` | 4 (4) | 7 | 7 | 6 (1) | 5 | | 5 | | `S_3` | 8 | 4 (4) | 6 (2) | 6 (3) | 4 (d) | | 9 | | `S_(dummy)` | 0 | 0 | 0 (3) | 0 | 0 | | 3 | | | | Demand | 4 | 4 | 5 | 4 | 8 | | |
Iteration-1 of optimality test
1. Find `u_i` and `v_j` for all occupied cells(i,j), where `c_(ij) = u_i + v_j`
`1.` Substituting, `u_3 = 0`, we get
`2. c_32 = u_3 + v_2=>v_2 = c_32 - u_3=>v_2 = 4 -0=>v_2 = 4`
`3. c_33 = u_3 + v_3=>v_3 = c_33 - u_3=>v_3 = 6 -0=>v_3 = 6`
`4. c_43 = u_4 + v_3=>u_4 = c_43 - v_3=>u_4 = 0 -6=>u_4 = -6`
`5. c_34 = u_3 + v_4=>v_4 = c_34 - u_3=>v_4 = 6 -0=>v_4 = 6`
`6. c_24 = u_2 + v_4=>u_2 = c_24 - v_4=>u_2 = 6 -6=>u_2 = 0`
`7. c_21 = u_2 + v_1=>v_1 = c_21 - u_2=>v_1 = 4 -0=>v_1 = 4`
`8. c_35 = u_3 + v_5=>v_5 = c_35 - u_3=>v_5 = 4 -0=>v_5 = 4`
`9. c_15 = u_1 + v_5=>u_1 = c_15 - v_5=>u_1 = 3 -4=>u_1 = -1`
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | `u_i` | | `S_1` | 5 | 8 | 6 | 6 | 3 (8) | | 8 | `u_1=-1` | | `S_2` | 4 (4) | 7 | 7 | 6 (1) | 5 | | 5 | `u_2=0` | | `S_3` | 8 | 4 (4) | 6 (2) | 6 (3) | 4 (d) | | 9 | `u_3=0` | | `S_(dummy)` | 0 | 0 | 0 (3) | 0 | 0 | | 3 | `u_4=-6` | | | | Demand | 4 | 4 | 5 | 4 | 8 | | | | | `v_j` | `v_1=4` | `v_2=4` | `v_3=6` | `v_4=6` | `v_5=4` | | | |
2. Find `d_(ij)` for all unoccupied cells(i,j), where `d_(ij) = c_(ij) - (u_i + v_j)`
`1. d_11 = c_11 - (u_1 + v_1) = 5 - (-1 +4) = color{blue}{2} `
`2. d_12 = c_12 - (u_1 + v_2) = 8 - (-1 +4) = color{blue}{5} `
`3. d_13 = c_13 - (u_1 + v_3) = 6 - (-1 +6) = color{blue}{1} `
`4. d_14 = c_14 - (u_1 + v_4) = 6 - (-1 +6) = color{blue}{1} `
`5. d_22 = c_22 - (u_2 + v_2) = 7 - (0 +4) = color{blue}{3} `
`6. d_23 = c_23 - (u_2 + v_3) = 7 - (0 +6) = color{blue}{1} `
`7. d_25 = c_25 - (u_2 + v_5) = 5 - (0 +4) = color{blue}{1} `
`8. d_31 = c_31 - (u_3 + v_1) = 8 - (0 +4) = color{blue}{4} `
`9. d_41 = c_41 - (u_4 + v_1) = 0 - (-6 +4) = color{blue}{2} `
`10. d_42 = c_42 - (u_4 + v_2) = 0 - (-6 +4) = color{blue}{2} `
`11. d_44 = c_44 - (u_4 + v_4) = 0 - (-6 +6) = color{blue}{0} `
`12. d_45 = c_45 - (u_4 + v_5) = 0 - (-6 +4) = color{blue}{2} `
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | `u_i` | | `S_1` | 5 [2] | 8 [5] | 6 [1] | 6 [1] | 3 (8) | | 8 | `u_1=-1` | | `S_2` | 4 (4) | 7 [3] | 7 [1] | 6 (1) | 5 [1] | | 5 | `u_2=0` | | `S_3` | 8 [4] | 4 (4) | 6 (2) | 6 (3) | 4 (d) | | 9 | `u_3=0` | | `S_(dummy)` | 0 [2] | 0 [2] | 0 (3) | 0 [0] | 0 [2] | | 3 | `u_4=-6` | | | | Demand | 4 | 4 | 5 | 4 | 8 | | | | | `v_j` | `v_1=4` | `v_2=4` | `v_3=6` | `v_4=6` | `v_5=4` | | | |
Since all `d_(ij)>=0`.
So final optimal solution is arrived.
| | `D_1` | `D_2` | `D_3` | `D_4` | `D_5` | | Supply | | `S_1` | 5 | 8 | 6 | 6 | 3 (8) | | 8 | | `S_2` | 4 (4) | 7 | 7 | 6 (1) | 5 | | 5 | | `S_3` | 8 | 4 (4) | 6 (2) | 6 (3) | 4 (d) | | 9 | | `S_(dummy)` | 0 | 0 | 0 (3) | 0 | 0 | | 3 | | | | Demand | 4 | 4 | 5 | 4 | 8 | | |
The minimum total transportation cost `= 3 xx 8 + 4 xx 4 + 6 xx 1 + 4 xx 4 + 6 xx 2 + 6 xx 3 + 0 xx 3 = 92`
Notice alternate solution is available with unoccupied cell `S_(dummy)D_4 : d_(44` = [0], but with the same optimal value.
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
