5. Degeneracy at subsequent iterations
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 | Supply | | S1 | 8 | 5 | 6 | 120 | | S2 | 15 | 10 | 12 | 80 | | S3 | 3 | 9 | 10 | 80 | | Demand | 150 | 80 | 50 | |
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` | 8 | 5 | 6 | | 120 | | `S_2` | 15 | 10 | 12 | | 80 | | `S_3` | 3 | 9 | 10 | | 80 | | | | Demand | 150 | 80 | 50 | | |
Table-1
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty | | `S_1` | 8 | 5 | 6 | | 120 | `1=6-5` | | `S_2` | 15 | 10 | 12 | | 80 | `2=12-10` | | `S_3` | 3 | 9 | 10 | | 80 | `6=9-3` | | | | Demand | 150 | 80 | 50 | | | | Column
Penalty | `5=8-3` | `4=9-5` | `4=10-6` | | | |
The maximum penalty, 6, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_31` = 3.
The maximum allocation in this cell is min(80,150) = 80.
It satisfy supply of `S_3` and adjust the demand of `D_1` from 150 to 70 (150 - 80 = 70).
Table-2
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty | | `S_1` | 8 | 5 | 6 | | 120 | `1=6-5` | | `S_2` | 15 | 10 | 12 | | 80 | `2=12-10` | | `S_3` | 3(80) | 9 | 10 | | 0 | -- | | | | Demand | 70 | 80 | 50 | | | | Column
Penalty | `7=15-8` | `5=10-5` | `6=12-6` | | | |
The maximum penalty, 7, occurs in column `D_1`.
The minimum `c_(ij)` in this column is `c_11` = 8.
The maximum allocation in this cell is min(120,70) = 70.
It satisfy demand of `D_1` and adjust the supply of `S_1` from 120 to 50 (120 - 70 = 50).
Table-3
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty | | `S_1` | 8(70) | 5 | 6 | | 50 | `1=6-5` | | `S_2` | 15 | 10 | 12 | | 80 | `2=12-10` | | `S_3` | 3(80) | 9 | 10 | | 0 | -- | | | | Demand | 0 | 80 | 50 | | | | Column
Penalty | -- | `5=10-5` | `6=12-6` | | | |
The maximum penalty, 6, occurs in column `D_3`.
The minimum `c_(ij)` in this column is `c_13` = 6.
The maximum allocation in this cell is min(50,50) = 50.
It satisfy supply of `S_1` and demand of `D_3`.
Table-4
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty | | `S_1` | 8(70) | 5 | 6(50) | | 0 | -- | | `S_2` | 15 | 10 | 12 | | 80 | `10` | | `S_3` | 3(80) | 9 | 10 | | 0 | -- | | | | Demand | 0 | 80 | 0 | | | | Column
Penalty | -- | `10` | -- | | | |
The maximum penalty, 10, occurs in row `S_2`.
The minimum `c_(ij)` in this row is `c_22` = 10.
The maximum allocation in this cell is min(80,80) = 80.
It satisfy supply of `S_2` and demand of `D_2`.
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | | Supply | Row Penalty | | `S_1` | 8(70) | 5 | 6(50) | | 120 | 1 | 1 | 1 | -- | | | `S_2` | 15 | 10(80) | 12 | | 80 | 2 | 2 | 2 | 10 | | | `S_3` | 3(80) | 9 | 10 | | 80 | 6 | -- | -- | -- | | | | | Demand | 150 | 80 | 50 | | | | Column
Penalty | 5
7
--
--
| 4
5
5
10
| 4
6
6
--
| | | |
The minimum total transportation cost `= 8 xx 70 + 6 xx 50 + 10 xx 80 + 3 xx 80 = 1900`
Here, the number of allocated cells = 4, which is one less than to m + n - 1 = 3 + 3 - 1 = 5
`:.` 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_1D_2`, which has the minimum transportation cost = 5.
| | `D_1` | `D_2` | `D_3` | | Supply | | `S_1` | 8 (70) | 5 (d) | 6 (50) | | 120 | | `S_2` | 15 | 10 (80) | 12 | | 80 | | `S_3` | 3 (80) | 9 | 10 | | 80 | | | | Demand | 150 | 80 | 50 | | |
Optimality test using modi method...
Allocation Table is
| | `D_1` | `D_2` | `D_3` | | Supply | | `S_1` | 8 (70) | 5 (d) | 6 (50) | | 120 | | `S_2` | 15 | 10 (80) | 12 | | 80 | | `S_3` | 3 (80) | 9 | 10 | | 80 | | | | Demand | 150 | 80 | 50 | | |
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_1 = 0`, we get
`2. c_11 = u_1 + v_1=>v_1 = c_11 - u_1=>v_1 = 8 -0=>v_1 = 8`
`3. c_31 = u_3 + v_1=>u_3 = c_31 - v_1=>u_3 = 3 -8=>u_3 = -5`
`4. c_12 = u_1 + v_2=>v_2 = c_12 - u_1=>v_2 = 5 -0=>v_2 = 5`
`5. c_22 = u_2 + v_2=>u_2 = c_22 - v_2=>u_2 = 10 -5=>u_2 = 5`
`6. c_13 = u_1 + v_3=>v_3 = c_13 - u_1=>v_3 = 6 -0=>v_3 = 6`
| | `D_1` | `D_2` | `D_3` | | Supply | `u_i` | | `S_1` | 8 (70) | 5 (d) | 6 (50) | | 120 | `u_1=0` | | `S_2` | 15 | 10 (80) | 12 | | 80 | `u_2=5` | | `S_3` | 3 (80) | 9 | 10 | | 80 | `u_3=-5` | | | | Demand | 150 | 80 | 50 | | | | | `v_j` | `v_1=8` | `v_2=5` | `v_3=6` | | | |
2. Find `d_(ij)` for all unoccupied cells(i,j), where `d_(ij) = c_(ij) - (u_i + v_j)`
`1. d_21 = c_21 - (u_2 + v_1) = 15 - (5 +8) = color{blue}{2} `
`2. d_23 = c_23 - (u_2 + v_3) = 12 - (5 +6) = color{blue}{1} `
`3. d_32 = c_32 - (u_3 + v_2) = 9 - (-5 +5) = color{blue}{9} `
`4. d_33 = c_33 - (u_3 + v_3) = 10 - (-5 +6) = color{blue}{9} `
| | `D_1` | `D_2` | `D_3` | | Supply | `u_i` | | `S_1` | 8 (70) | 5 (d) | 6 (50) | | 120 | `u_1=0` | | `S_2` | 15 [2] | 10 (80) | 12 [1] | | 80 | `u_2=5` | | `S_3` | 3 (80) | 9 [9] | 10 [9] | | 80 | `u_3=-5` | | | | Demand | 150 | 80 | 50 | | | | | `v_j` | `v_1=8` | `v_2=5` | `v_3=6` | | | |
Since all `d_(ij)>=0`.
So final optimal solution is arrived.
| | `D_1` | `D_2` | `D_3` | | Supply | | `S_1` | 8 (70) | 5 (d) | 6 (50) | | 120 | | `S_2` | 15 | 10 (80) | 12 | | 80 | | `S_3` | 3 (80) | 9 | 10 | | 80 | | | | Demand | 150 | 80 | 50 | | |
The minimum total transportation cost `= 8 xx 70 + 6 xx 50 + 10 xx 80 + 3 xx 80 = 1900`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
