Question

*5. Solve the following LP problem using two-phase Simplex method: Maximize f= 4x1+ x2 + x3 subject to: 2x1x22x3= 4 Зх1 +3x2 + хз %3D 3, X12 0, х2 20, х3 2 0. [Note: Since a BFS is not available, start Phase I simplex algorithm by introducing variables] two artificial

Answer 1

Here we have to maximize the function , but in two phase simplex method only minimization can be carried out , so we just change the sign of function , and will find the minimum value , that will be the answer .   

Minimize

  

=4x1-2 2r3

Subject to ,  

21 2r3 4

,  

Зл1 + 3г2 + аз — 3

T10, 20, x3 > 0

Here equality constraints is given , so only need to add artificial variables . So

  

21 22.x3 +A1=4

  

Br1323A2 3

Now the function becomes Minimize   

=-4r 2 - 23A1 A2

And since BFS is not available we can solve it by Simplex method with  revised objective function .

Cj 1 1 10 0 0 Solution A2 Bv х3 A1 x2 CB х1 2 A1 2 0 A2 3 7 Zi 5 0 0 4 -3 C-Zj5 st LO

  Where CB is coefficient of basic variable , and Cj coefficient of objective variable , and Bv is basic variables . This is optimal only if $Cj - Zj \geq 0$ , but here all values are negative , so we take the higher negative value that is -5 , so key column is column 1 and key row is the row with higher solution value . So key row is row 1 . So key element is 2 . A1 is now the leaving variable , and we can replace A1 with x1 .

And to find new values in the row with key element ,   New element = Element / Key element .   

For other rows , new value = Old value - Key column value  X New raw value .  

Cj 1 10 0 0 Solution A2 Bv x2 х3 CB х1 2 1/2 1 1 x1 0 -3 2 A2 3/2 0 -3 -2 3/2 Zi 0 0 -3/2 2 Ci-Zi 0

Here x2 does not satisfy optimal condition , so here the key column is column 2 and key row is row 1 . So key element is 1/2 .

And to find new values in the row with key element ,   New element = Element / Key element .   

For other rows , new value = Old value - Key column value  X New raw value .

Cj 0 0 10 Solution Bv CB х1 x2 х3 x1 1/2 0 5/3 8/3 0 x2 -1 -4/3 -4/3 0 -4/3 Zi -4/3 0 Ci-Zi 0 1 4/3 LO

So here the optimal condition is satisfied .  

Now phase II ,

Cj -4 1 -1 Solution Bv CB х1 x2 х3 -4 x1 1/2 0 5/3 8/3 x2 -1 -4/3 -4/3 -1 0 Zi 28/3 -2 -16/3 Cj-Zj 2 0 13/3 LO

So optimal condition is satisfied .