written 7.8 years ago by | modified 2.7 years ago by |
Mumbai University > Mechanical Engineering > Sem 7 > Operations Research
Marks: 10 Marks
Year: Dec 2015
written 7.8 years ago by | modified 2.7 years ago by |
Mumbai University > Mechanical Engineering > Sem 7 > Operations Research
Marks: 10 Marks
Year: Dec 2015
written 7.8 years ago by | • modified 7.8 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.
$v_1$ | $v_2$ | $v_3$ | $v_4$ | |
---|---|---|---|---|
$u_1$ | 17 | 20 | 14 (35) | 12 (25) |
$u_2$ | 15 | 21 | 25 | 14 (75) |
$u_3$ | 15 | 14 (65) | 15 (40) | 16 |
$u_4$ | 0 (50) | 0 | 0 | 0 (ɛ) |
$u_4 + v_1 = 0, u_3 + v_2 = 14, u_1 + v_3 = 14, u_1 + v_4 = 12, u_2 + v_4 = 14, u_3 + v_2 = 14, u_3 + v_3 = 15, u_4+v_4= 0 \\ Let u_1 = 0, \\ v_3 = 14, v_4 = 12, u_2 = 2, u_3 = 1, v_2 = 13, u_4 = -12, v_1 = 12.$
As we can see θ = 35, again checking for optimality with new allocations.
$v_1$ = 13 | $v_2$ = 12 | $v_3$ = 13 | $v_4$ = 12 | |||
---|---|---|---|---|---|---|
$u_1$ = 0 | 17 (4) | 20 (8) | 14 (1) | 12 | 60 | |
$u_2$ = 2 | 15 | 35 | 21 (7) | 25 (10) | 14 | 40 |
$u_3$ = 2 | 15 (0) | 14 | 65 | 15 | 40 | 16 (2) |
$u_4$ = -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.$