3. Alternate optimal solutions example
alternative soluion
If `d_(ij)=0` then alternative soluion exists, with different set allocation and same transportation cost.
Example
Find Solution using Voggel's Approximation method, also find optimal solution using modi 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
Optimality test using modi method...
Allocation Table is
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | | `S_1` | 4 | 8 (76) | 8 | 0 | | 76 | | `S_2` | 16 | 24 (21) | 16 (41) | 0 (20) | | 82 | | `S_3` | 8 (72) | 16 (5) | 24 | 0 | | 77 | | | | Demand | 72 | 102 | 41 | 20 | | |
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_2 = 0`, we get
`2. c_22 = u_2 + v_2=>v_2 = c_22 - u_2=>v_2 = 24 -0=>v_2 = 24`
`3. c_12 = u_1 + v_2=>u_1 = c_12 - v_2=>u_1 = 8 -24=>u_1 = -16`
`4. c_32 = u_3 + v_2=>u_3 = c_32 - v_2=>u_3 = 16 -24=>u_3 = -8`
`5. c_31 = u_3 + v_1=>v_1 = c_31 - u_3=>v_1 = 8 +8=>v_1 = 16`
`6. c_23 = u_2 + v_3=>v_3 = c_23 - u_2=>v_3 = 16 -0=>v_3 = 16`
`7. c_24 = u_2 + v_4=>v_4 = c_24 - u_2=>v_4 = 0 -0=>v_4 = 0`
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | `u_i` | | `S_1` | 4 | 8 (76) | 8 | 0 | | 76 | `u_1=-16` | | `S_2` | 16 | 24 (21) | 16 (41) | 0 (20) | | 82 | `u_2=0` | | `S_3` | 8 (72) | 16 (5) | 24 | 0 | | 77 | `u_3=-8` | | | | Demand | 72 | 102 | 41 | 20 | | | | | `v_j` | `v_1=16` | `v_2=24` | `v_3=16` | `v_4=0` | | | |
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) = 4 - (-16 +16) = color{blue}{4} `
`2. d_13 = c_13 - (u_1 + v_3) = 8 - (-16 +16) = color{blue}{8} `
`3. d_14 = c_14 - (u_1 + v_4) = 0 - (-16 +0) = color{blue}{16} `
`4. d_21 = c_21 - (u_2 + v_1) = 16 - (0 +16) = color{blue}{0} `
`5. d_33 = c_33 - (u_3 + v_3) = 24 - (-8 +16) = color{blue}{16} `
`6. d_34 = c_34 - (u_3 + v_4) = 0 - (-8 +0) = color{blue}{8} `
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | `u_i` | | `S_1` | 4 [4] | 8 (76) | 8 [8] | 0 [16] | | 76 | `u_1=-16` | | `S_2` | 16 [0] | 24 (21) | 16 (41) | 0 (20) | | 82 | `u_2=0` | | `S_3` | 8 (72) | 16 (5) | 24 [16] | 0 [8] | | 77 | `u_3=-8` | | | | Demand | 72 | 102 | 41 | 20 | | | | | `v_j` | `v_1=16` | `v_2=24` | `v_3=16` | `v_4=0` | | | |
Since all `d_(ij)>=0`.
So final optimal solution is arrived.
| | `D_1` | `D_2` | `D_3` | `D_(dummy)` | | Supply | | `S_1` | 4 | 8 (76) | 8 | 0 | | 76 | | `S_2` | 16 | 24 (21) | 16 (41) | 0 (20) | | 82 | | `S_3` | 8 (72) | 16 (5) | 24 | 0 | | 77 | | | | Demand | 72 | 102 | 41 | 20 | | |
The minimum total transportation cost `= 8 xx 76 + 24 xx 21 + 16 xx 41 + 0 xx 20 + 8 xx 72 + 16 xx 5 = 2424`
Notice alternate solution is available with unoccupied cell `S_2D_1 : d_(21` = [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
|
