written 7.9 years ago by | modified 2.8 years ago by |
Mumbai University > Mechanical Engineering > Sem 7 > Operations Research
Marks: 10 Marks
Year: Dec 2015
written 7.9 years ago by | modified 2.8 years ago by |
Mumbai University > Mechanical Engineering > Sem 7 > Operations Research
Marks: 10 Marks
Year: Dec 2015
written 7.9 years ago by |
Introducing slack, surplus & artificial variables in constraints
$3x + y – S_1 + A_1 = 120 \\ 3x + 11y – S_2 + A_2 =330 \\ x + y + S_3 = 80$
So the objective function becomes
$Z = 15x + 20y + 0S_1 + 0S_2 + 0S_3 + A_1 + A_2$
Phase I: Assigning coefficients of ‘-1’ to artificial variables & coefficient of ‘0’ o all other variables in the objective function.
Cj→ | 0 | 0 | 0 | 0 | 0 | -1 | -1 | ||
---|---|---|---|---|---|---|---|---|---|
x | y | $S_1$ | $S_2$ | $S_3$ | $A_1$ | $A_2$ | RHS | θ | |
$-1A_1$ | 3 | 1 | -1 | 0 | 0 | 1 | 0 | 120 | 120 |
$-1A_2$ | 3 | 11 | 0 | -1 | 0 | 0 | 1 | 330 | 30← |
$0S_3$ | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 80 | 80 |
Zj | -6 | -12 | 1 | 1 | 0 | -1 | -1 | -450 | |
Cj - Zj | 6 | 12↑ | -1 | -1 | 0 | 0 | 0 |
Here Pivot point is 11.
Entering variable in basis = y
Leaving variable in basis = $A_2$
| | Cj→ |0| 0| 0| 0| 0| -1| -1| | |
|-|-|-|-|-|
|Operations| | x| y| $S_1$| $S_2$| $S_3$| $A_1$| $A_2$| RHS| θ|
|$R_2/11$| $-1A_1$| 30/11| 0| -1| 1/11| 0| 1| -1/11| 90| 990|
|$R_1 – R_2$| 20y| 3/11| 1| 0| -1/11| 0| 0| 1/11| 30| -330|
|$R_3 – R_2$| $0S_3$| 8/11| 0| 0| 1/11| 1| 0| -1/11| 50| 550←|
| | Zj| 30/11| 20| 1| -21/11| 0| -1| 21/11| | |
| | Cj - Zj| -30/11| -20| -1| 21/11↑| 0| 0| -32/11| | |
Entering variable = $S_2$
Leaving variable = $S_3$
| | Cj→| 0| 0| 0| 0| 0| -1| -1| | |
|-|-|-|-|-|
|operation | | x| y| $S_1$| $S_2$| $S_3$| $A_1$| $A_2$| RHS| θ|
|$R_3 * 11$| $-1A_1$| 2| 0| -1| 0| -1| 1| 0| 40| |
|$R_2+R_3/11$| 20y| 1| 1| 0| 0| 1| 0| 0| 80| |
|$R_1-R_3/11$| $0S_2$| 8| 0| 0| 1| 11| 0| -1| 550| |
| | Zj| 18| 20| 1| 0| 1| -1| 0| 1560| |
| | Cj - Zj| -18| -20| -1| 0| -1| 0| -1| | |
This is the end of Phase I, since all values of Cj – Zj are less than or equal to zero.
But one artificial variable still present in the basis, this indicates that this problem does not have feasible solution.