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
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
|
