Home > Operation Research calculators > Two-Phase 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 method (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
  9. Revised Simplex method

1. Algorithm & Example-1



Algorithm
Two-Phase Method Steps (Rule)
Step-1: Phase-1

a. Form a new objective function by assigning zero to every original variable (including slack and surplus variables) and -1 to each of the artificial variables.

eg. Max Z = - A1 - A2

b. Using simplex method, try to eliminate the artificial varibles from the basis.

c. The solution at the end of Phase-1 is the initial basic feasible solution for Phase-2.
Step-2: Phase-2

a. The original objective function is used and coefficient of artificial variable is 0 (so artificial variable is removed from the calculation process).

b. Then simplex algorithm is used to find optimal solution.

Example
Find solution using Two-Phase method
MIN Z = x1 + x2
subject to
2x1 + x2 >= 4
x1 + 7x2 >= 7
and x1,x2 >= 0


Solution:
Problem is
Min `Z``=``````x_1`` + ````x_2`
subject to
```2``x_1`` + ````x_2``4`
`````x_1`` + ``7``x_2``7`
and `x_1,x_2 >= 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 subtract surplus variable `S_1` and add artificial variable `A_1`

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

After introducing surplus,artificial variables
Min `Z``=``````A_1`` + ````A_2`
subject to
```2``x_1`` + ````x_2`` - ````S_1`` + ````A_1`=`4`
`````x_1`` + ``7``x_2`` - ````S_2`` + ````A_2`=`7`
and `x_1,x_2,S_1,S_2,A_1,A_2 >= 0`


Iteration-1 `C_j``0``0``0``0``1``1`
`B``C_B``X_B``x_1` `x_2` Entering variable   `S_1``S_2``A_1``A_2`MinRatio
`(X_B)/(x_2)`
`A_1``1``4``2``1``-1``0``1``0``(4)/(1)=4`
 `A_2` Leaving variable   `1``7``1` `(7)`  (pivot element)   `0``-1``0``1``(7)/(7)=1``->`
 `Z=0` `0=`
`Z_j=sum C_B X_B`
 
 `Z_j` `Z_j=sum C_B x_j`    `3` `3=1xx2+1xx1`
`Z_j=sum C_B x_1`
 
 `8` `8=1xx1+1xx7`
`Z_j=sum C_B x_2`
 
 `-1` `-1=1xx(-1)+1xx0`
`Z_j=sum C_B S_1`
 
 `-1` `-1=1xx0+1xx(-1)`
`Z_j=sum C_B S_2`
 
 `1` `1=1xx1+1xx0`
`Z_j=sum C_B A_1`
 
 `1` `1=1xx0+1xx1`
`Z_j=sum C_B A_2`
 
`C_j-Z_j` `-3` `-3=0-3`    `-8` `-8=0-8`   `uarr` `1` `1=0-(-1)`    `1` `1=0-(-1)`    `0` `0=1-1`    `0` `0=1-1`  


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

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

`:.` The pivot element is `7`.

Entering `=x_2`, Departing `=A_2`, Key Element `=7`

`R_2`(new)`= R_2`(old)`-: 7`

`R_1`(new)`= R_1`(old)`- R_2`(new)

Iteration-2 `C_j``0``0``0``0``1`
`B``C_B``X_B` `x_1` Entering variable   `x_2``S_1``S_2``A_1`MinRatio
`(X_B)/(x_1)`
 `A_1` Leaving variable   `1` `3` `3=4-1`
`R_1`(new)`= R_1`(old)`- R_2`(new)
 
 `(13/7)` `13/7=2-1/7` (pivot element)
`R_1`(new)`= R_1`(old)`- R_2`(new)
 
 `0` `0=1-1`
`R_1`(new)`= R_1`(old)`- R_2`(new)
 
 `-1` `-1=(-1)-0`
`R_1`(new)`= R_1`(old)`- R_2`(new)
 
 `1/7` `1/7=0-(-1/7)`
`R_1`(new)`= R_1`(old)`- R_2`(new)
 
 `1` `1=1-0`
`R_1`(new)`= R_1`(old)`- R_2`(new)
 
`(3)/(13/7)=1.62``->`
`x_2``0` `1` `1=7-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 
 `1/7` `1/7=1-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 
 `1` `1=7-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 
 `0` `0=0-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 
 `-1/7` `-1/7=(-1)-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 
 `0` `0=0-:7`
`R_2`(new)`= R_2`(old)`-: 7`
 
`(1)/(1/7)=7`
 `Z=0` `0=0xx1`
`Z_j=sum C_B X_B`
 
 `Z_j` `Z_j=sum C_B x_j`    `13/7` `13/7=1xx13/7+0xx1/7`
`Z_j=sum C_B x_1`
 
 `0` `0=1xx0+0xx1`
`Z_j=sum C_B x_2`
 
 `-1` `-1=1xx(-1)+0xx0`
`Z_j=sum C_B S_1`
 
 `1/7` `1/7=1xx1/7+0xx(-1/7)`
`Z_j=sum C_B S_2`
 
 `1` `1=1xx1+0xx0`
`Z_j=sum C_B A_1`
 
`C_j-Z_j` `-13/7` `-13/7=0-13/7`   `uarr` `0` `0=0-0`    `1` `1=0-(-1)`    `-1/7` `-1/7=0-1/7`    `0` `0=1-1`  


Negative minimum `C_j-Z_j` is `-13/7` and its column index is `1`. So, the entering variable is `x_1`.

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

`:.` The pivot element is `13/7`.

Entering `=x_1`, Departing `=A_1`, Key Element `=13/7`

`R_1`(new)`= R_1`(old)`xx7/13`

`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)

Iteration-3 `C_j``0``0``0``0`
`B``C_B``X_B``x_1``x_2``S_1``S_2`MinRatio
`x_1``0` `21/13` `21/13=3xx7/13`
`R_1`(new)`= R_1`(old)`xx7/13`
 
 `1` `1=13/7xx7/13`
`R_1`(new)`= R_1`(old)`xx7/13`
 
 `0` `0=0xx7/13`
`R_1`(new)`= R_1`(old)`xx7/13`
 
 `-7/13` `-7/13=(-1)xx7/13`
`R_1`(new)`= R_1`(old)`xx7/13`
 
 `1/13` `1/13=1/7xx7/13`
`R_1`(new)`= R_1`(old)`xx7/13`
 
`x_2``0` `10/13` `10/13=1-1/7xx21/13`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
 
 `0` `0=1/7-1/7xx1`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
 
 `1` `1=1-1/7xx0`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
 
 `1/13` `1/13=0-1/7xx(-7/13)`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
 
 `-2/13` `-2/13=(-1/7)-1/7xx1/13`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
 
 `Z=0` `0=0xx21/13+0xx10/13`
`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(-7/13)+0xx1/13`
`Z_j=sum C_B S_1`
 
 `0` `0=0xx1/13+0xx(-2/13)`
`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`  


Since all `C_j-Z_j >= 0`

Hence, optimal solution is arrived with value of variables as :
`x_1=21/13,x_2=10/13`

Min `Z = 0`

-->Phase-2<--

we eliminate the artificial variables and change the objective function for the original,
Iteration-1 `C_j``1``1``0``0`
`B``C_B``X_B``x_1``x_2``S_1``S_2`MinRatio
`x_1``1``21/13``1``0``-7/13``1/13`
`x_2``1``10/13``0``1``1/13``-2/13`
 `Z=31/13` `31/13=1xx21/13+1xx10/13`
`Z_j=sum C_B X_B`
 
 `Z_j` `Z_j=sum C_B x_j`    `1` `1=1xx1+1xx0`
`Z_j=sum C_B x_1`
 
 `1` `1=1xx0+1xx1`
`Z_j=sum C_B x_2`
 
 `-6/13` `-6/13=1xx(-7/13)+1xx1/13`
`Z_j=sum C_B S_1`
 
 `-1/13` `-1/13=1xx1/13+1xx(-2/13)`
`Z_j=sum C_B S_2`
 
`C_j-Z_j` `0` `0=1-1`    `0` `0=1-1`    `6/13` `6/13=0-(-6/13)`    `1/13` `1/13=0-(-1/13)`  


Since all `C_j-Z_j >= 0`

Hence, optimal solution is arrived with value of variables as :
`x_1=21/13,x_2=10/13`

Min `Z = 31/13`




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









 
Copyright © 2020. All rights reserved. Terms, Privacy





Adblocker detected!

Dear user,

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add atozmath.com to your ad blocking whitelist or disable your adblocking software.

Thanks for your support

×