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; `

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`

Tableau-1	`C_j`	`0`	`0`	`0`	`0`	`1`	`1`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`A_1`	`A_2`	`RHS`	`"Ratio"=(RHS)/(x_2)`
`R_1` `1`	`A_1`	`2`	`1`	`-1`	`0`	`1`	`0`	`4`	`(4)/(1)=4`
`R_2` `1`	`A_2`	`1`	`(7)`	`0`	`-1`	`0`	`1`	`7`	`(7)/(7)=1``->`
	`Z_j`	`3`	`8`	`-1`	`-1`	`1`	`1`	`Z=11`
	`C_j-Z_j`	`-3`	`-8``uarr`	`1`	`1`	`0`	`0`

Most Negative `C_j-Z_j` is `-8`. So, the entering variable is `x_2`.

Minimum ratio is `1`. 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`

	`x_1`	`x_2`	`S_1`	`S_2`	`A_1`	`A_2`	`RHS`
`R_2`(old) =	`1`	`7`	`0`	`-1`	`0`	`1`	`7`
`R_2`(new)`= R_2`(old) `-: 7`	`0.1429`	`1`	`0`	`-0.1429`	`0`	`0.1429`	`1`

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

	`x_1`	`x_2`	`S_1`	`S_2`	`A_1`	`A_2`	`RHS`
`R_1`(old) =	`2`	`1`	`-1`	`0`	`1`	`0`	`4`
`R_2`(new) =	`0.1429`	`1`	`0`	`-0.1429`	`0`	`0.1429`	`1`
`R_1`(new)`= R_1`(old) - `R_2`(new)	`1.8571`	`0`	`-1`	`0.1429`	`1`	`-0.1429`	`3`

Tableau-2	`C_j`	`0`	`0`	`0`	`0`	`1`	`1`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`A_1`	`A_2`	`RHS`	`"Ratio"=(RHS)/(x_1)`
`R_1` `1`	`A_1`	`(1.8571)`	`0`	`-1`	`0.1429`	`1`	`-0.1429`	`3`	`(3)/(1.8571)=1.6154``->`
`R_2` `0`	`x_2`	`0.1429`	`1`	`0`	`-0.1429`	`0`	`0.1429`	`1`	`(1)/(0.1429)=7`
	`Z_j`	`1.8571`	`0`	`-1`	`0.1429`	`1`	`-0.1429`	`Z=3`
	`C_j-Z_j`	`-1.8571``uarr`	`0`	`1`	`-0.1429`	`0`	`1.1429`

Most Negative `C_j-Z_j` is `-1.8571`. So, the entering variable is `x_1`.

Minimum ratio is `1.6154`. So, the leaving basis variable is `A_1`.

`:.` The pivot element is `1.8571`.

Entering `=x_1`, Departing `=A_1`, Key Element `=1.8571`

`R_1`(new)`= R_1`(old) `-: 1.8571`

	`x_1`	`x_2`	`S_1`	`S_2`	`A_1`	`A_2`	`RHS`
`R_1`(old) =	`1.8571`	`0`	`-1`	`0.1429`	`1`	`-0.1429`	`3`
`R_1`(new)`= R_1`(old) `-: 1.8571`	`1`	`0`	`-0.5385`	`0.0769`	`0.5385`	`-0.0769`	`1.6154`

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

	`x_1`	`x_2`	`S_1`	`S_2`	`A_1`	`A_2`	`RHS`
`R_2`(old) =	`0.1429`	`1`	`0`	`-0.1429`	`0`	`0.1429`	`1`
`R_1`(new) =	`1`	`0`	`-0.5385`	`0.0769`	`0.5385`	`-0.0769`	`1.6154`
`0.1429 xx R_1`(new) =	`0.1429`	`0`	`-0.0769`	`0.011`	`0.0769`	`-0.011`	`0.2308`
`R_2`(new)`= R_2`(old) - `0.1429 R_1`(new)	`0`	`1`	`0.0769`	`-0.1538`	`-0.0769`	`0.1538`	`0.7692`

Tableau-3	`C_j`	`0`	`0`	`0`	`0`	`1`	`1`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`A_1`	`A_2`	`RHS`	`"Ratio"`
`R_1` `0`	`x_1`	`1`	`0`	`-0.5385`	`0.0769`	`0.5385`	`-0.0769`	`1.6154`
`R_2` `0`	`x_2`	`0`	`1`	`0.0769`	`-0.1538`	`-0.0769`	`0.1538`	`0.7692`
	`Z_j`	`0`	`0`	`0`	`0`	`0`	`0`	`Z=0`
	`C_j-Z_j`	`0`	`0`	`0`	`0`	`1`	`1`

Since all `C_j-Z_j >= 0`

Hence, optimal solution is arrived with value of variables as :
`x_1=1.6154,x_2=0.7692`

Min `Z=0`


we eliminate the artificial variables and change the objective function for the original,
Min `Z=x_1 + x_2 + 0S_1 + 0S_2`

Tableau-1	`C_j`	`1`	`1`	`0`	`0`
`C_B`	`"Basis"`	`x_1`	`x_2`	`S_1`	`S_2`	`RHS`	`"Ratio"`
`R_1` `1`	`x_1`	`1`	`0`	`-0.5385`	`0.0769`	`1.6154`
`R_2` `1`	`x_2`	`0`	`1`	`0.0769`	`-0.1538`	`0.7692`
	`Z_j`	`1`	`1`	`-0.4615`	`-0.0769`	`Z=2.3846`
	`C_j-Z_j`	`0`	`0`	`0.4615`	`0.0769`

Since all `C_j-Z_j >= 0`

Hence, optimal solution is arrived with value of variables as :
`x_1=1.6154,x_2=0.7692`

Min `Z=2.3846`

---

---