1. Algorithm & Example-1
Algorithm
|
MODI Method Steps (Rule)
|
|
Step-1:
|
Find an initial basic feasible solution using any one of the three methods NWCM, LCM or VAM.
|
|
Step-2:
|
Find `u_i` and `v_j` for rows and columns. To start
a. assign 0 to `u_i` or `v_j` where maximum number of allocation in a row or column respectively.
b. Calculate other `u_i`'s and `v_j`'s using `c_(ij) = u_i + v_j`, for all occupied cells.
|
|
Step-3:
|
For all unoccupied cells, calculate `d_(ij) = c_(ij) - (u_i + v_j)`, .
|
|
Step-4:
|
Check the sign of `d_(ij)`
a. If `d_(ij) > 0`, then current basic feasible solution is optimal and stop this procedure.
b. If `d_(ij)=0` then alternative soluion exists, with different set allocation and same transportation cost. Now stop this procedure.
b. If `d_(ij) < 0`, then the given solution is not an optimal solution and further improvement in the solution is possible.
|
|
Step-5:
|
Select the unoccupied cell with the largest negative value of `d_(ij)`, and included in the next solution.
|
|
Step-6:
|
Draw a closed path (or loop) from the unoccupied cell (selected in the previous step). The right angle turn in this path is allowed only at occupied cells and at the original unoccupied cell. Mark (+) and (-) sign alternatively at each corner, starting from the original unoccupied cell.
|
|
Step-7:
|
1. Select the minimum value from cells marked with (-) sign of the closed path.
2. Assign this value to selected unoccupied cell (So unoccupied cell becomes occupied cell).
3. Add this value to the other occupied cells marked with (+) sign.
4. Subtract this value to the other occupied cells marked with (-) sign.
|
|
Step-8:
|
Repeat Step-2 to step-7 until optimal solution is obtained. This procedure stops when all `d_(ij) >= 0` for unoccupied cells.
|
Example-1
1. Find Solution using Voggel's Approximation method, also find optimal solution using modi method,
| D1 | D2 | D3 | D4 | Supply | | S1 | 19 | 30 | 50 | 10 | 7 | | S2 | 70 | 30 | 40 | 60 | 9 | | S3 | 40 | 8 | 70 | 20 | 18 | | Demand | 5 | 8 | 7 | 14 | |
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` | 19 | 30 | 50 | 10 | | 7 | | `S_2` | 70 | 30 | 40 | 60 | | 9 | | `S_3` | 40 | 8 | 70 | 20 | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
Table-1
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19 | 30 | 50 | 10 | | 7 | `9=19-10` | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `10=40-30` | | `S_3` | 40 | 8 | 70 | 20 | | 18 | `12=20-8` | | | | Demand | 5 | 8 | 7 | 14 | | | | Column
Penalty | `21=40-19` | `22=30-8` | `10=50-40` | `10=20-10` | | | |
The maximum penalty, 22, occurs in column `D_2`.
The minimum `c_(ij)` in this column is `c_32` = 8.
The maximum allocation in this cell is min(18,8) = 8.
It satisfy demand of `D_2` and adjust the supply of `S_3` from 18 to 10 (18 - 8 = 10).
Table-2
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19 | 30 | 50 | 10 | | 7 | `9=19-10` | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `20=60-40` | | `S_3` | 40 | 8(8) | 70 | 20 | | 10 | `20=40-20` | | | | Demand | 5 | 0 | 7 | 14 | | | | Column
Penalty | `21=40-19` | -- | `10=50-40` | `10=20-10` | | | |
The maximum penalty, 21, occurs in column `D_1`.
The minimum `c_(ij)` in this column is `c_11` = 19.
The maximum allocation in this cell is min(7,5) = 5.
It satisfy demand of `D_1` and adjust the supply of `S_1` from 7 to 2 (7 - 5 = 2).
Table-3
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10 | | 2 | `40=50-10` | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `20=60-40` | | `S_3` | 40 | 8(8) | 70 | 20 | | 10 | `50=70-20` | | | | Demand | 0 | 0 | 7 | 14 | | | | Column
Penalty | -- | -- | `10=50-40` | `10=20-10` | | | |
The maximum penalty, 50, occurs in row `S_3`.
The minimum `c_(ij)` in this row is `c_34` = 20.
The maximum allocation in this cell is min(10,14) = 10.
It satisfy supply of `S_3` and adjust the demand of `D_4` from 14 to 4 (14 - 10 = 4).
Table-4
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10 | | 2 | `40=50-10` | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `20=60-40` | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 0 | -- | | | | Demand | 0 | 0 | 7 | 4 | | | | Column
Penalty | -- | -- | `10=50-40` | `50=60-10` | | | |
The maximum penalty, 50, occurs in column `D_4`.
The minimum `c_(ij)` in this column is `c_14` = 10.
The maximum allocation in this cell is min(2,4) = 2.
It satisfy supply of `S_1` and adjust the demand of `D_4` from 4 to 2 (4 - 2 = 2).
Table-5
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10(2) | | 0 | -- | | `S_2` | 70 | 30 | 40 | 60 | | 9 | `20=60-40` | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 0 | -- | | | | Demand | 0 | 0 | 7 | 2 | | | | Column
Penalty | -- | -- | `40` | `60` | | | |
The maximum penalty, 60, occurs in column `D_4`.
The minimum `c_(ij)` in this column is `c_24` = 60.
The maximum allocation in this cell is min(9,2) = 2.
It satisfy demand of `D_4` and adjust the supply of `S_2` from 9 to 7 (9 - 2 = 7).
Table-6
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10(2) | | 0 | -- | | `S_2` | 70 | 30 | 40 | 60(2) | | 7 | `40` | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 0 | -- | | | | Demand | 0 | 0 | 7 | 0 | | | | Column
Penalty | -- | -- | `40` | -- | | | |
The maximum penalty, 40, occurs in row `S_2`.
The minimum `c_(ij)` in this row is `c_23` = 40.
The maximum allocation in this cell is min(7,7) = 7.
It satisfy supply of `S_2` and demand of `D_3`.
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | Row Penalty | | `S_1` | 19(5) | 30 | 50 | 10(2) | | 7 | 9 | 9 | 40 | 40 | -- | -- | | | `S_2` | 70 | 30 | 40(7) | 60(2) | | 9 | 10 | 20 | 20 | 20 | 20 | 40 | | | `S_3` | 40 | 8(8) | 70 | 20(10) | | 18 | 12 | 20 | 50 | -- | -- | -- | | | | | Demand | 5 | 8 | 7 | 14 | | | | Column
Penalty | 21
21
--
--
--
--
| 22
--
--
--
--
--
| 10
10
10
10
40
40
| 10
10
10
50
60
--
| | | |
The minimum total transportation cost `= 19 xx 5 + 10 xx 2 + 40 xx 7 + 60 xx 2 + 8 xx 8 + 20 xx 10 = 779`
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_4` | | Supply | | `S_1` | 19 (5) | 30 | 50 | 10 (2) | | 7 | | `S_2` | 70 | 30 | 40 (7) | 60 (2) | | 9 | | `S_3` | 40 | 8 (8) | 70 | 20 (10) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
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, `v_4 = 0`, we get
`2. c_14 = u_1 + v_4=>u_1 = c_14 - v_4=>u_1 = 10 -0=>u_1 = 10`
`3. c_11 = u_1 + v_1=>v_1 = c_11 - u_1=>v_1 = 19 -10=>v_1 = 9`
`4. c_24 = u_2 + v_4=>u_2 = c_24 - v_4=>u_2 = 60 -0=>u_2 = 60`
`5. c_23 = u_2 + v_3=>v_3 = c_23 - u_2=>v_3 = 40 -60=>v_3 = -20`
`6. c_34 = u_3 + v_4=>u_3 = c_34 - v_4=>u_3 = 20 -0=>u_3 = 20`
`7. c_32 = u_3 + v_2=>v_2 = c_32 - u_3=>v_2 = 8 -20=>v_2 = -12`
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | `u_i` | | `S_1` | 19 (5) | 30 | 50 | 10 (2) | | 7 | `u_1=10` | | `S_2` | 70 | 30 | 40 (7) | 60 (2) | | 9 | `u_2=60` | | `S_3` | 40 | 8 (8) | 70 | 20 (10) | | 18 | `u_3=20` | | | | Demand | 5 | 8 | 7 | 14 | | | | | `v_j` | `v_1=9` | `v_2=-12` | `v_3=-20` | `v_4=0` | | | |
2. Find `d_(ij)` for all unoccupied cells(i,j), where `d_(ij) = c_(ij) - (u_i + v_j)`
`1. d_12 = c_12 - (u_1 + v_2) = 30 - (10 -12) = color{blue}{32} `
`2. d_13 = c_13 - (u_1 + v_3) = 50 - (10 -20) = color{blue}{60} `
`3. d_21 = c_21 - (u_2 + v_1) = 70 - (60 +9) = color{blue}{1} `
`4. d_22 = c_22 - (u_2 + v_2) = 30 - (60 -12) = color{blue}{-18} `
`5. d_31 = c_31 - (u_3 + v_1) = 40 - (20 +9) = color{blue}{11} `
`6. d_33 = c_33 - (u_3 + v_3) = 70 - (20 -20) = color{blue}{70} `
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | `u_i` | | `S_1` | 19 (5) | 30 [32] | 50 [60] | 10 (2) | | 7 | `u_1=10` | | `S_2` | 70 [1] | 30 [-18] | 40 (7) | 60 (2) | | 9 | `u_2=60` | | `S_3` | 40 [11] | 8 (8) | 70 [70] | 20 (10) | | 18 | `u_3=20` | | | | Demand | 5 | 8 | 7 | 14 | | | | | `v_j` | `v_1=9` | `v_2=-12` | `v_3=-20` | `v_4=0` | | | |
3. Now choose the minimum negative value from all `d_(ij)` (opportunity cost) = `d_(22` = [-18]
and draw a closed path from `S_2D_2`.
Closed path is `S_2D_2->S_2D_4->S_3D_4->S_3D_2`
Closed path and plus/minus sign allocation...
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | `u_i` | | `S_1` | 19 (5) | 30 [32] | 50 [60] | 10 (2) | | 7 | `u_1=10` | | `S_2` | 70 [1] | 30 [-18] (+) | 40 (7) | 60 (2) (-) | | 9 | `u_2=60` | | `S_3` | 40 [11] | 8 (8) (-) | 70 [70] | 20 (10) (+) | | 18 | `u_3=20` | | | | Demand | 5 | 8 | 7 | 14 | | | | | `v_j` | `v_1=9` | `v_2=-12` | `v_3=-20` | `v_4=0` | | | |
4. Minimum allocated value among all negative position (-) on closed path = 2
Substract 2 from all (-) and Add it to all (+)
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 (5) | 30 | 50 | 10 (2) | | 7 | | `S_2` | 70 | 30 (2) | 40 (7) | 60 | | 9 | | `S_3` | 40 | 8 (6) | 70 | 20 (12) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
5. Repeat the step 1 to 4, until an optimal solution is obtained.
Iteration-2 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 = 19 -0=>v_1 = 19`
`3. c_14 = u_1 + v_4=>v_4 = c_14 - u_1=>v_4 = 10 -0=>v_4 = 10`
`4. c_34 = u_3 + v_4=>u_3 = c_34 - v_4=>u_3 = 20 -10=>u_3 = 10`
`5. c_32 = u_3 + v_2=>v_2 = c_32 - u_3=>v_2 = 8 -10=>v_2 = -2`
`6. c_22 = u_2 + v_2=>u_2 = c_22 - v_2=>u_2 = 30 +2=>u_2 = 32`
`7. c_23 = u_2 + v_3=>v_3 = c_23 - u_2=>v_3 = 40 -32=>v_3 = 8`
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | `u_i` | | `S_1` | 19 (5) | 30 | 50 | 10 (2) | | 7 | `u_1=0` | | `S_2` | 70 | 30 (2) | 40 (7) | 60 | | 9 | `u_2=32` | | `S_3` | 40 | 8 (6) | 70 | 20 (12) | | 18 | `u_3=10` | | | | Demand | 5 | 8 | 7 | 14 | | | | | `v_j` | `v_1=19` | `v_2=-2` | `v_3=8` | `v_4=10` | | | |
2. Find `d_(ij)` for all unoccupied cells(i,j), where `d_(ij) = c_(ij) - (u_i + v_j)`
`1. d_12 = c_12 - (u_1 + v_2) = 30 - (0 -2) = color{blue}{32} `
`2. d_13 = c_13 - (u_1 + v_3) = 50 - (0 +8) = color{blue}{42} `
`3. d_21 = c_21 - (u_2 + v_1) = 70 - (32 +19) = color{blue}{19} `
`4. d_24 = c_24 - (u_2 + v_4) = 60 - (32 +10) = color{blue}{18} `
`5. d_31 = c_31 - (u_3 + v_1) = 40 - (10 +19) = color{blue}{11} `
`6. d_33 = c_33 - (u_3 + v_3) = 70 - (10 +8) = color{blue}{52} `
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | `u_i` | | `S_1` | 19 (5) | 30 [32] | 50 [42] | 10 (2) | | 7 | `u_1=0` | | `S_2` | 70 [19] | 30 (2) | 40 (7) | 60 [18] | | 9 | `u_2=32` | | `S_3` | 40 [11] | 8 (6) | 70 [52] | 20 (12) | | 18 | `u_3=10` | | | | Demand | 5 | 8 | 7 | 14 | | | | | `v_j` | `v_1=19` | `v_2=-2` | `v_3=8` | `v_4=10` | | | |
Since all `d_(ij)>=0`.
So final optimal solution is arrived.
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 (5) | 30 | 50 | 10 (2) | | 7 | | `S_2` | 70 | 30 (2) | 40 (7) | 60 | | 9 | | `S_3` | 40 | 8 (6) | 70 | 20 (12) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
The minimum total transportation cost `= 19 xx 5 + 10 xx 2 + 30 xx 2 + 40 xx 7 + 8 xx 6 + 20 xx 12 = 743`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
