Home > Operation Research calculators > Simplex method example

2. Two-Phase method example ( Enter your problem )
  1. Algorithm & Example-1
  2. Example-2
  3. Infeasible solution example
Other related methods
  1. Simplex (BigM) method
  2. Two-Phase method
  3. Graphical method
  4. Primal to dual conversion
  5. Dual simplex method
  6. Integer simplex method
  7. Branch and Bound method
  8. 0-1 Integer programming problem

2. Example-2

Find solution using Two-Phase method
MIN Z = 5x1 + 2x2 + 10x3
subject to
x1 - x3 <= 10
x2 + x3 >= 10
and x1,x2,x3 >= 0


Solution:
Problem is
Min `Z``=````5``x_1`` + ``2``x_2`` + ``10``x_3`
subject to
`````x_1`` - ````x_3``10`
`````x_2`` + ````x_3``10`
and `x_1,x_2,x_3 >= 0; `


-->Phase-1<--

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint-1 is of type '`<=`' we should add slack variable `S_1`

2. As the constraint-2 is of type '`>=`' we should subtract surplus variable `S_2` and add artificial variable `A_1`

After introducing slack,surplus,artificial variables
Min `Z``=``````A_1`
subject to
`````x_1`` - ````x_3`` + ````S_1`=`10`
`````x_2`` + ````x_3`` - ````S_2`` + ````A_1`=`10`
and `x_1,x_2,x_3,S_1,S_2,A_1 >= 0`


Iteration-1 `C_j``0``0``0``0``0``1`
`B``C_B``X_B``x_1` `x_2` Entering variable`x_3``S_1``S_2``A_1`MinRatio
`(X_B)/(x_2)`
`S_1``0``10``1``0``-1``1``0``0`---
 `A_1` Leaving variable`1``10``0` `(1)`  (pivot element)`1``0``-1``1``(10)/(1)=10``->`
 `Z=0` `0=`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `0` `0=0xx1+1xx0`
`Z_j=sum C_B x_1`
 `1` `1=0xx0+1xx1`
`Z_j=sum C_B x_2`
 `1` `1=0xx(-1)+1xx1`
`Z_j=sum C_B x_3`
 `0` `0=0xx1+1xx0`
`Z_j=sum C_B S_1`
 `-1` `-1=0xx0+1xx(-1)`
`Z_j=sum C_B S_2`
 `1` `1=0xx0+1xx1`
`Z_j=sum C_B A_1`
`C_j-Z_j` `0` `0=0-0` `-1` `-1=0-1``uarr` `-1` `-1=0-1` `0` `0=0-0` `1` `1=0-(-1)` `0` `0=1-1`


Negative minimum `C_j-Z_j` is `-1` and its column index is `2`. So, the entering variable is `x_2`.

Minimum ratio is `10` and its row index is `2`. So, the leaving basis variable is `A_1`.

`:.` The pivot element is `1`.

Entering `=x_2`, Departing `=A_1`, Key Element `=1`

`R_2`(new)`= R_2`(old)

`R_1`(new)`= R_1`(old)

Iteration-2 `C_j``0``0``0``0``0`
`B``C_B``X_B``x_1``x_2``x_3``S_1``S_2`MinRatio
`S_1``0` `10` `10=10`
`R_1`(new)`= R_1`(old)
 `1` `1=1`
`R_1`(new)`= R_1`(old)
 `0` `0=0`
`R_1`(new)`= R_1`(old)
 `-1` `-1=-1`
`R_1`(new)`= R_1`(old)
 `1` `1=1`
`R_1`(new)`= R_1`(old)
 `0` `0=0`
`R_1`(new)`= R_1`(old)
`x_2``0` `10` `10=10`
`R_2`(new)`= R_2`(old)
 `0` `0=0`
`R_2`(new)`= R_2`(old)
 `1` `1=1`
`R_2`(new)`= R_2`(old)
 `1` `1=1`
`R_2`(new)`= R_2`(old)
 `0` `0=0`
`R_2`(new)`= R_2`(old)
 `-1` `-1=-1`
`R_2`(new)`= R_2`(old)
 `Z=0` `0=0xx10`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `0` `0=0xx1+0xx0`
`Z_j=sum C_B x_1`
 `0` `0=0xx0+0xx1`
`Z_j=sum C_B x_2`
 `0` `0=0xx(-1)+0xx1`
`Z_j=sum C_B x_3`
 `0` `0=0xx1+0xx0`
`Z_j=sum C_B S_1`
 `0` `0=0xx0+0xx(-1)`
`Z_j=sum C_B S_2`
`C_j-Z_j` `0` `0=0-0` `0` `0=0-0` `0` `0=0-0` `0` `0=0-0` `0` `0=0-0`


Since all `C_j-Z_j >= 0`

Hence, optimal solution is arrived with value of variables as :
`x_1=0,x_2=10,x_3=0`

Min `Z = 0`

-->Phase-2<--

we eliminate the artificial variables and change the objective function for the original,
Iteration-1 `C_j``5``2``10``0``0`
`B``C_B``X_B``x_1``x_2``x_3``S_1``S_2`MinRatio
`S_1``0``10``1``0``-1``1``0`
`x_2``2``10``0``1``1``0``-1`
 `Z=20` `20=2xx10`
`Z_j=sum C_B X_B`
 `Z_j` `Z_j=sum C_B x_j` `0` `0=0xx1+2xx0`
`Z_j=sum C_B x_1`
 `2` `2=0xx0+2xx1`
`Z_j=sum C_B x_2`
 `2` `2=0xx(-1)+2xx1`
`Z_j=sum C_B x_3`
 `0` `0=0xx1+2xx0`
`Z_j=sum C_B S_1`
 `-2` `-2=0xx0+2xx(-1)`
`Z_j=sum C_B S_2`
`C_j-Z_j` `5` `5=5-0` `0` `0=2-2` `8` `8=10-2` `0` `0=0-0` `2` `2=0-(-2)`


Since all `C_j-Z_j >= 0`

Hence, optimal solution is arrived with value of variables as :
`x_1=0,x_2=10,x_3=0`

Min `Z = 20`




This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here


Share with your friends
 
Copyright © 2018. All rights reserved. Terms, Privacy