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
• 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;
• After introducing surplus,artificial variables
• Min Z= A1+A2
subject to
2x1+x2-S1+A1=4
x1+7x2-S2+A2=7 and
x1,x2,S1,S2,A1,A2≥0
Cj 0 0 0 0 1 1
Valu Ratio
B CB x1 x2 S1 S2 A1 A2
e
A1 4/1=
1 4 2 1 -1 0 1 0
4
A2 (7) 7/7=
1 7 1 0 -1 0 1
1→
Z=0 Zj 3 8 -1 -1 1 1
-8
Cj-Zj -3 1 1 0 0
↑
• Negative minimum Cj-Zj is -8 and Minimum ratio
is 1. So, the entering variable is x2 and the leaving
basis variable is A2.
∴ The pivot element is 7.
R2(new)=R2(old)÷7
R1(new)=R1(old)-R2(new)
Cj 0 0 0 0 1
Ratio
B CB Value x1 x2 S1 S2 A1
3/
(13/7)
A1 1 3 13/7 0 -1 1/7 1 =
1.62
→
1/
x2 0 1 1/7 1 0 -1/7 0 (1/7)=
7
Z=0 Zj 13/7 0 -1 1/7 1
-13/7 0 -1/7
• Negative minimum Cj-Zj is -13/7 and Minimum ratio
is 1.62. So, the entering variable is x1 and the
leaving basis variable is A1.
∴ The pivot element is 137.
R1(new)=R1(old) ÷(13/7)
R2(new)=R2(old)-(1/7)R1(new)
Cj 0 0 0 0
Ratio
B CB Value x1 x2 S1 S2
x1 0 21/13 1 0 -7/13 1/13
x2 0 10/13 0 1 1/13 -2/13
Z=0 Zj 0 0 0 0
0 0 0
Cj-Zj 0
Since all Cj-Zj≥0. Hence, optimal solution is arrived with value
of variables as : x1=21/13, x2=10/13 and Min Z=0
-->Phase-2<--
we eliminate the artificial variables and change the
objective function for the original,
Cj 1 1 0 0
Ratio
B CB Value x1 x2 S1 S2
x1 1 21/13 1 0 -7/13 1/13
x2 1 10/13 0 1 1/13 -2/13
Z= 1
Zj 1 -6/13 -1/13
31/13
0 0 1/13
Cj-Zj 6/13
• Since all Cj-Zj≥0
Hence, optimal solution is arrived with value of variables as
:
x1=21/13,x2=10/13
Min Z=31/13
• Infeasible solution
If there is no any solution that satifies all the constraints,
then it is called Infeasible solution
In the final simplex table when all cj-zj imply optimal
solution but at least one artificial variable present in the
basis with positive value. Then the problem has no feasible
solution.
• Example
Find solution using Two-Phase method
MIN Z = X1 - 2X2 - 3X3
subject to
-2X1 + X2 + 3X3 = 2
2X1 + 3X2 + 4X3 = 1
and X1,X2,X3 ≥ 0
Soln
-->Phase-1<--
After introducing artificial variables
Min Z=A1+A2
subject to
-2X1+X2+3X3+A1=2
2X1+3X2+4X3+A2=1
and X1,X2,X3,A1,A2≥0
Cj 0 0 0 1
B CB Value X1 X2 X3 A1 A2 Ratio
2/3=
0.666
A1 1 2 -2 1 3 1 0 7
¼=
A2 1 1 2 3 (4) 0 1 0.25
→
Z=0 Zj 0 4 7 1 1
-7
Cj-Zj 0 -4 0 0
↑
• Negative minimum Cj-Zj is -7 and the entering
variable is X3.
Minimum ratio is 0.25 and the leaving basis variable
is A2.
∴ The pivot element is 4.
• R2(new)=R2 (old)÷4
R1(new)=R1(old)-3R2 (new)
Cj 0 0 0 1
B CB Value X1 X2 X3 A1 Ratio
A1 1 5/4 -7/2 -5/4 0 1
X3 0 1/4 1/2 3/4 1 0
Z=0 Zj -7/2 -5/4 0 1
Cj-Zj 7/2 5/4 0 1
• Since all Cj-Zj≥0
Hence, optimal solution is arrived with value of
variables as :
X1=0,X2=0,X3=14 and Min Z=0
• But this solution is not feasible since the artificial
variable A1 appears in the basis with positive
value 5/4
• Remark:
If no artifical variable is present or an artifical
variable is present with zero value then go to PHASE
II.
