0
1.9kviews
Solve the following problem using two phase method. Maximize: $\\Z = 15x + 20y \\$ Subjected to: $3x + y \ge 120 \\ 3x + 11y \ge 330 \\ x + y \le 80 \\ x, y \ge 0$

Mumbai University > Mechanical Engineering > Sem 7 > Operations Research

Marks: 10 Marks

Year: Dec 2015

1 Answer
0
25views

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.

Please log in to add an answer.