2. Algorithm & Example-1
Algorithm
|
North-West Corner Method (NWCM) Steps (Rule)
|
|
Step-1:
|
Select the upper left corner cell of the transportation matrix and allocate min(s1, d1).
|
|
Step-2:
|
a. Subtract this value from supply and demand of respective row and column.
b. If the supply is 0, then cross (strike) that row and move down to the next cell.
c. If the demand is 0, then cross (strike) that column and move right to the next cell.
d. If supply and demand both are 0, then cross (strike) both row & column and move diagonally to the next cell.
|
|
Step-3:
|
Repeat this steps until all supply and demand values are 0.
|
|
|
|
Example-1
Find Solution using North-West Corner 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 | | |
The rim values for `S_1`=7 and `D_1`=5 are compared.
The smaller of the two i.e. min(7,5) = 5 is assigned to `S_1` `D_1`
This meets the complete demand of `D_1` and leaves 7 - 5=2 units with `S_1`
Table-1
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30 | 50 | 10 | | 2 | | `S_2` | 70 | 30 | 40 | 60 | | 9 | | `S_3` | 40 | 8 | 70 | 20 | | 18 | | | | Demand | 0 | 8 | 7 | 14 | | |
Move horizontally,
The rim values for `S_1`=2 and `D_2`=8 are compared.
The smaller of the two i.e. min(2,8) = 2 is assigned to `S_1` `D_2`
This exhausts the capacity of `S_1` and leaves 8 - 2=6 units with `D_2`
Table-2
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30(2) | 50 | 10 | | 0 | | `S_2` | 70 | 30 | 40 | 60 | | 9 | | `S_3` | 40 | 8 | 70 | 20 | | 18 | | | | Demand | 0 | 6 | 7 | 14 | | |
Move vertically,
The rim values for `S_2`=9 and `D_2`=6 are compared.
The smaller of the two i.e. min(9,6) = 6 is assigned to `S_2` `D_2`
This meets the complete demand of `D_2` and leaves 9 - 6=3 units with `S_2`
Table-3
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30(2) | 50 | 10 | | 0 | | `S_2` | 70 | 30(6) | 40 | 60 | | 3 | | `S_3` | 40 | 8 | 70 | 20 | | 18 | | | | Demand | 0 | 0 | 7 | 14 | | |
Move horizontally,
The rim values for `S_2`=3 and `D_3`=7 are compared.
The smaller of the two i.e. min(3,7) = 3 is assigned to `S_2` `D_3`
This exhausts the capacity of `S_2` and leaves 7 - 3=4 units with `D_3`
Table-4
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30(2) | 50 | 10 | | 0 | | `S_2` | 70 | 30(6) | 40(3) | 60 | | 0 | | `S_3` | 40 | 8 | 70 | 20 | | 18 | | | | Demand | 0 | 0 | 4 | 14 | | |
Move vertically,
The rim values for `S_3`=18 and `D_3`=4 are compared.
The smaller of the two i.e. min(18,4) = 4 is assigned to `S_3` `D_3`
This meets the complete demand of `D_3` and leaves 18 - 4=14 units with `S_3`
Table-5
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30(2) | 50 | 10 | | 0 | | `S_2` | 70 | 30(6) | 40(3) | 60 | | 0 | | `S_3` | 40 | 8 | 70(4) | 20 | | 14 | | | | Demand | 0 | 0 | 0 | 14 | | |
Move horizontally,
The rim values for `S_3`=14 and `D_4`=14 are compared.
The smaller of the two i.e. min(14,14) = 14 is assigned to `S_3` `D_4`
Table-6
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19(5) | 30(2) | 50 | 10 | | 0 | | `S_2` | 70 | 30(6) | 40(3) | 60 | | 0 | | `S_3` | 40 | 8 | 70(4) | 20(14) | | 0 | | | | Demand | 0 | 0 | 0 | 0 | | |
Initial feasible solution is
| | `D_1` | `D_2` | `D_3` | `D_4` | | Supply | | `S_1` | 19 (5) | 30 (2) | 50 | 10 | | 7 | | `S_2` | 70 | 30 (6) | 40 (3) | 60 | | 9 | | `S_3` | 40 | 8 | 70 (4) | 20 (14) | | 18 | | | | Demand | 5 | 8 | 7 | 14 | | |
The minimum total transportation cost `=19 xx 5+30 xx 2+30 xx 6+40 xx 3+70 xx 4+20 xx 14=1015`
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
|
