written 8.2 years ago by | modified 3.2 years ago by |
Mumbai University > Mechanical Engineering > Sem 7 > Operations Research
Marks: 10 Marks
Year: Dec 2015
written 8.2 years ago by | modified 3.2 years ago by |
Mumbai University > Mechanical Engineering > Sem 7 > Operations Research
Marks: 10 Marks
Year: Dec 2015
written 8.2 years ago by | • modified 8.2 years ago |
As demand is more than supply, we introduce a dummy row, whose supply is difference between total demand and total supply with cost coefficient of the cells as zero.
| a | W | X | Y | Z| | |
|-|-|-|-|-|-|-|
|A| 17| 20| 14| 12| 60| [2]|
|B| 15| 21| 25| 14| 75| [1]|
|C| 15| 14| 15| 16| 105| [1]|
|DUMMY| 0 (50)| 0| 0| 0| 50/0| [0]|
| | 50/0| 65| 75| 100| | |
| | [15] ↑| [14]| [14]| [12]| | |
| | X| Y| Z| | |
|-|-|-|-|-|-|
|A| 20| 14| 12| 60| [2]|
|B| 21| 25| 14 (75)| 75/0| [7]←|
|C| 14| 15| 16| 105| [1]|
| | 65| 75| 100/25| | |
| | [6]| [1]| [2]| | |
| | X| Y| Z| | |
|-|-|-|-|-|-|
|A| 20| 14| 12| 60| [2]|
|C| 14 (65) |15| 16| 105/40| [1]|
| | 65/0| 75| 25| | |
| | [6] ↑| [1]| [4]| | |
| | Y| Z| | |
|-|-|-|-|
|A| 14| 12 (25)| 60/35| [2]|
|C| 15| 16| 40| [1]|
| | 75| 25/0| | |
| | [1]| [4] ↑| | |
Y | ||
---|---|---|
A | 14 (35) | 35/0 |
C | 15 (40) | 40/0 |
75/0 |
The single final matrix showing allocations is shown below,
| | W| X| Y| Z| | | | | |
|-|-|-|-|
|A| 17| 20| 14 (35)| 12 (25)| 60| [2]| [2]| [2]| [2]|
|B| 15| 21| 25| 14 (75)| 75/0| [1]| [7]←| | |
|C| 15| 14 (65)| 15 (40)| 16| 105/40/0| [1]| [1]| [1]| [2]|
|DUMMY| 0 (50)| 0| 0| 0| 50/0| [0]| | | |
| | 50/0| 65/0| 75/0| 100/25/0| | | | |
| | [15] ↑| [14]| [14]| [12] | | | | |
| | | [6]| [1] |[2] | | | | |
| | | [6] ↑| [1]| [4] | | | | |
| | | | [1]| [4] ↑ | | | | |
Transportation cost :-
Z =14∗35+12∗25+14∗75+14∗65+15∗40+0∗50=3350
But, m + n – 1 = 7 and no. of allocations = 8, here degeneracy exists.
The minimum cost in the unallocated cells is 0. Selecting Dummy-Z cell arbitrarily for assigning ‘ɛ’ allocation to it. Also checking for optimality by UV rule/ MODI method.
v1 | v2 | v3 | v4 | |
---|---|---|---|---|
u1 | 17 | 20 | 14 (35) | 12 (25) |
u2 | 15 | 21 | 25 | 14 (75) |
u3 | 15 | 14 (65) | 15 (40) | 16 |
u4 | 0 (50) | 0 | 0 | 0 (ɛ) |
u4+v1=0,u3+v2=14,u1+v3=14,u1+v4=12,u2+v4=14,u3+v2=14,u3+v3=15,u4+v4=0Letu1=0,v3=14,v4=12,u2=2,u3=1,v2=13,u4=−12,v1=12.
As we can see θ = 35, again checking for optimality with new allocations.
v1 = 13 | v2 = 12 | v3 = 13 | v4 = 12 | |||
---|---|---|---|---|---|---|
u1 = 0 | 17 (4) | 20 (8) | 14 (1) | 12 | 60 | |
u2 = 2 | 15 | 35 | 21 (7) | 25 (10) | 14 | 40 |
u3 = 2 | 15 (0) | 14 | 65 | 15 | 40 | 16 (2) |
u4 = -13 | 0 | 15 | 0 (1) | 0 | 35 | 0 (1) |
No negative numbers are present, which shows we have obtained the optimal solution.
W | X | Y | Z | ||
---|---|---|---|---|---|
A | 17 | 20 | 14 | 12 60 | |
B | 15 | 35 | 21 | 25 | 14 40 |
C | 15 | 14 65 | 15 40 | 16 | |
DUMMY | 0 15 | 0 | 0 35 | 0 |
Minimum transportation cost =15∗35+0∗15+14∗65+15∗40+0∗35+12∗60+14∗40=3315.