Participants:
Maryam Saeed 21-NTU-CS-1337
Mazhar Abbas 21-NTU-CS-1338
Minahil Ismail 21-NTU-CS-1339
Two Phase Simplex Method
Why we need the Two Phase Simplex
Method?
Max Z=2𝑥1 +𝑥2 ;
Subject to
4𝑥1 +3𝑥2 ≤ 12
4𝑥1 +2𝑥2 ≤8;
And 𝑥1 , 𝑥2 ≥ 0
Why we need the Two Phase Simplex
Method?
4𝑥1 +3𝑥2 +𝑆1 = 12
4𝑥1 +2𝑥2 +𝑆2 =8
And 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 ≥ 0
Why we need the Two Phase Simplex
Method?
4𝑥1 +3𝑥2 ≤12 4𝑥1 +3𝑥2 +𝑆1 = 12
4𝑥1 +2𝑥2 ≤8 4𝑥1 +2𝑥2 +𝑆2 =8
And 𝑥1 , 𝑥2 ≥ 0 And 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 ≥ 0
If we put x1=x2=0,
Then
𝑆1 =12,
𝑆2 =8
Why we need the Two Phase Simplex
Method?
Max Z=-2𝑥1 -𝑥2 ;
Subject to
3𝑥1 +𝑥2 =3;
4𝑥1 +3𝑥2 ≥6;
𝑥1 +2𝑥2 ≤6;
And 𝑥1 , 𝑥2 ≥ 0
Why we need the Two Phase Simplex
Method?
3𝑥1 +𝑥2 =3
4𝑥1 +3𝑥2 - 𝑆1 =6;
𝑥1 +2𝑥2 +𝑆2 =6;
And 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 ≥ 0
If we put x1=x2=0,
Then
𝑆1 =-6,
𝑆2 =6
Key Points
<= + slack variable (S)
>= - surplus (S)+ artificial variable(A)
= +artificial variable(A);
3𝑥1 +𝑥2 +𝐴1 =3
4𝑥1 +3𝑥2 - 𝑆1 +𝐴2 =6;
𝑥1 +2𝑥2 +𝑆2 =6;
And 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 ≥ 0
How to implement?
Two Phase Simplex Method
The process of eliminating artificial variables is performed in phase-I of
the solution and phase II is used to get an optimal solution. Since the
solution of LPP is computed in two phases, it is called as Two-Phase
Simplex Method.
Phases of Two phase Simplex Method
(Phase-I)
Step 1
(a)
If all the constraints in the given LP problem are ‘less than or equal to’ (≤) type, then Phase II
can be directly used to solve the problem. Otherwise, the necessary number of surplus and
artificial variables are added to convert constraints into equality constraints.
(b)
If the given LP problem is of minimization, then convert it to the maximization type by the usual
method.
Step 2:
Assign zero coefficient to each of the decision variables and to the surplus variables; and
assign – 1 coefficient to each of the artificial variables
Phases of Two Phase Simplex Method
(Phase-I)
Step 3:
Apply the simplex algorithm to solve this auxiliary LP problem. The following three cases may
arise at optimality.
(a)
Max Z * = 0 and at least one artificial variable is present in the basis with positive value. This
means that no feasible solution exists for the original LP problem.
(b)
Max Z * = 0 and no artificial variable is present in the basis. This means that only decision
variables are present in the basis and hence proceed to Phase II to obtain an optimal basic
feasible solution on the original LP problem.
Phases of Two Phase Simplex Method
(Phase-I)
(c)
Max Z * = 0 and at least one artificial variable is present in the basis at zero value. This means
that a feasible solution to the auxiliary LP problem is also a feasible solution to the original LP
problem. In order to arrive at the basic feasible solution, proceed directly to Phase II or else
eliminate the artificial basic variable and then proceed to Phase II.
Once an artificial variable has left the basis, it has served its purpose and
can, therefore, be removed from the simplex table. An artificial variable is
never considered for re-entry into the basis.
Phases of Two phase Simplex Method
(Phase-II)
▪ Assign actual coefficients to the variables in the objective function and zero coefficient to
the artificial variables which appear at zero value in the basis at the end of Phase I.
▪ The last simplex table of An artificial variable is added to the constraints to get an initial
solution to an LP problem.
▪ Linear Programming: The Simplex Method Phase I can be used as the initial simplex
table for Phase II. Then apply the usual simplex algorithm to the modified simplex table
in order to get the optimal solution to the original problem. Artificial variables that do not
appear in the basis may be removed.
▪ Simplex method Is then applied to arrive at optimum solution
Example NO. 1
Max Z=3𝑥1 - 𝑥2 ;
Subject to
2𝑥1 +𝑥2 ≥2;
𝑥1 +3𝑥2 ≤2;
𝑥2 ≤4 ;
And 𝑥1 , 𝑥2 ≥0
Standard Form:
2𝑥1 +𝑥2 - 𝑆1 +𝐴1 = 2
𝑥1 +3𝑥2 +𝑆2 = 2
𝑥2 + 𝑆3 = 4
And 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 , 𝑆3 , 𝐴1 ≥ 0
Standard Form:
2𝑥1 + 𝑥2 - 𝑆1 + 0𝑆2 + 0𝑆3 + 𝐴1 = 2
𝑥1 + 3𝑥2 + 0𝑆1 + 𝑆2 + 0𝑆3 +0𝐴1 = 2
𝑥2 + 0𝑆1 +0𝑆2 + 𝑆3 +0𝐴1 = 4
And 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 , 𝑆3 , 𝐴1 ≥ 0
Phase-I
Auxiliary Linear Programming Problem
Maximize 𝑍 ∗ = 0𝑥1 −0𝑥2 − 0𝑆1 + 0𝑆2 + 0𝑆3 − 𝐴1 ;
Subject To:
2𝑥1 +𝑥2 - 𝑆1 +𝐴1 =2
𝑥1 +3𝑥2 +𝑆2 =2
𝑥2 + 𝑆3 =4
And 𝑥1 , 𝑥2 , 𝑆1 , 𝑆2 , 𝑆3 , 𝐴1 >=0
Phase-I
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 𝐴1 Ratio
Variable R.H.S
Cj 0 0 0 0 0 -1
𝐴1 -1 2 1 -1 0 0 1 2
𝑆2 0 1 3 0 1 0 0 2
𝑆3 0 0 1 0 0 1 0 4
𝑪𝒋 =Coefficients of objective function
𝑪𝑩 = Coefficients of basic variables
𝑿𝑩 =R.H.S
𝒁 ∗ = 𝑪 𝑩 x 𝑿𝑩
(-1,0,0)(2,2,4)-2+0+0=-2
𝐶𝐵 for the other two variables is zero so no need to solve it as it will give
zero.
𝒁𝒋 =(𝑪𝑩 x 𝑿𝒋 ) 𝒁𝟏 =(-1,0,0)(2,1,0) -2+0+0
𝑪𝒋 − 𝒁𝒋 = 0-(-2)2
Similarly we’ll find out the values of 𝑪𝒋 − 𝒁𝒋 for other variables
Phase-I
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 𝐴1 Ratio
Variable R.H.S
Cj 0 0 0 0 0 -1
𝐴1 -1 2 1 -1 0 0 1 2
𝑆2 0 1 3 0 1 0 0 2
𝑆3 0 0 1 0 0 1 0 4
𝒁𝒋 2 1 -1 0 0 0
Phase-I
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 𝐴1 Ratio
Variable R.H.S
Cj 0 0 0 0 0 -1
𝐴1 -1 2 1 -1 0 0 1 2
𝑆2 0 1 3 0 1 0 0 2
𝑆3 0 0 1 0 0 1 0 4
𝒁𝒋 = -2 -1 1 0 0 -1
𝑪𝒋 − 𝒁𝒋 = 2 1 -1 0 0 0
Phase-I
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 𝐴1 Ratio
Variable R.H.S
Cj 0 0 0 0 0 -1
𝐴1 -1 2 1 -1 0 0 1 2
𝑆2 0 1 3 0 1 0 0 2
𝑆3 0 0 1 0 0 1 0 4
𝒁𝒋 = -2 -1 1 0 0 -1
𝑪𝒋 − 𝒁𝒋 = 2 1 -1 0 0 0
Phase-I
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 𝐴1 Ratio
Variable R.H.S
Cj 0 0 0 0 0 -1
𝐴1 -1 2 1 -1 0 0 1 2 1
𝑆2 0 1 3 0 1 0 0 2 2
𝑆3 0 0 1 0 0 1 0 4 -
𝒁𝒋 = -2 -1 1 0 0 -1
𝑪𝒋 − 𝒁 𝒋 = 2 1 -1 0 0 0
Entering
Phase-I Variable
Leaving
Variable
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 𝐴1 Ratio
Variable R.H.S
Cj 0 0 0 0 0 -1
𝐴1 -1 2 1 -1 0 0 1 2 1
𝑆2 0 1 3 0 1 0 0 2 2
𝑆3 0 0 1 0 0 1 0 4 -
𝒁𝒋 = -2 -1 1 0 0 -1
𝑪𝒋 − 𝒁 𝒋 = 2 1 -1 0 0 0
Performing Row Operation
R1’=R1/2
Phase-I
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 𝐴1 Ratio
Variable R.H.S
Cj 0 0 0 0 0 -1
𝑥1 0 1 1/2 -1/2 0 0 1/2 1 1
𝑆2 0 1 3 0 1 0 0 2 2
𝑆3 0 0 1 0 0 1 0 4 -
Performing Row Operation
R2’=R2-R1’
Phase-I
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 𝐴1 Ratio
Variable R.H.S
Cj 0 0 0 0 0 -1
𝑥1 0 1 1/2 -1/2 0 0 1/2 1 1
𝑆2 0 0 5/2 1/2 1 0 -1/2 1 2
𝑆3 0 0 1 0 0 1 0 4 -
Phase-I
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 𝐴1 Ratio
Variable R.H.S
Cj 0 0 0 0 0 -1
𝑥1 0 1 1/2 -1/2 0 0 1/2 1 1
𝑆2 0 0 5/2 1/2 1 0 -1/2 1 2
𝑆3 0 0 1 0 0 1 0 4 -
𝒁𝒋 = 0 0 0 0 0 0
𝑪𝒋 − 𝒁 𝒋 = 0 0 0 0 0 -1
Max 𝒁∗ =0
No artificial variable appears in the basis, so we proceed to Phase-II
Phase-I (Last Table)
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 𝐴1 Ratio
Variable R.H.S
Cj 0 0 0 0 0 -1
𝑥1 0 1 1/2 -1/2 0 0 1/2 1 1
𝑆2 0 0 5/2 1/2 1 0 -1/2 1 2
𝑆3 0 0 1 0 0 1 0 4 -
Phase-II
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 Ratio
Variable R.H.S
Cj
𝑥1 1 1/2 -1/2 0 0 1
𝑆2 0 5/2 1/2 1 0 1
𝑆3 0 1 0 0 1 4
Phase-II Max Z=3𝒙𝟏 - 𝒙𝟐 + 𝟎𝑺𝟏 + 𝟎𝑺𝟐 + 𝟎𝑺𝟑 ;
Basic
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3
Variable
(𝑋𝐵 )
Cj 3 -1 0 0 0
R.H.S
Ratio
𝑥1 3 1 1/2 -1/2 0 0 1
𝑆2 0 0 5/2 1/2 1 0 1
𝑆3 0 0 1 0 0 1 4
Phase-II
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 Ratio
Variable R.H.S
Cj 3 -1 0 0 0
𝑥1 3 1 1/2 -1/2 0 0 1
𝑆2 0 0 5/2 1/2 1 0 1
𝑆3 0 0 1 0 0 1 4
𝒁𝒋 = 3 3/2 -3/2 0 0
𝑪𝒋 − 𝒁 𝒋 = 0 -5/2 3/2 0 0
Entering
Phase-II Variable
Basic (𝑋𝐵 )
Leaving Variable 𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3
R.H.S
Ratio
Variable
Cj 3 -1 0 0 0
𝑥1 3 1 1/2 -1/2 0 0 1 -2
𝑆2 0 0 5/2 1/2 1 0 1 2
𝑆3 0 0 1 0 0 1 4 -
𝒁𝒋 = 3 3/2 -3/2 0 0
𝑪𝒋 − 𝒁 𝒋 = 0 -5/2 3/2 0 0
Performing Row Operation
R2’=2*R2
Phase-II
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 Ratio
Variable R.H.S
Cj 3 -1 0 0 0
𝑥1 3 1 1/2 -1/2 0 0 1 -2
𝑆1 0 0 5 1 2 0 2 2
𝑆3 0 0 1 0 0 1 4 -
Performing Row Operation
R1’=R1 + (1/2)*R2
Phase-II
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 Ratio
Variable R.H.S
Cj 3 -1 0 0 0
𝑥1 3 1 3 0 1 0 2 -2
𝑆1 0 0 5 1 2 0 2 2
𝑆3 0 0 1 0 0 1 4 -
Phase-II
Basic (𝑋𝐵 )
𝐶𝐵 𝑥1 𝑥2 𝑆1 𝑆2 𝑆3 Ratio
Variable R.H.S
Cj 3 -1 0 0 0
𝑥1 3 1 3 0 1 0 2 -2
𝑆1 0 0 5 1 2 0 2 2
𝑆3 0 0 1 0 0 1 4 -
𝒁𝒋 = 3 9 0 3 0
𝑪 −𝒁 = 0 -10 0 -3 0
As All 𝑪𝒋 − 𝒁𝒋 ≤ 0, so we’ll stop further modifying our table
Here we have Z= 3 x 2=6
Here we get the value of 𝒙𝟏 = 𝟐
And as 𝒙𝟐 is not present in the column of basic variables so the value
of 𝒙𝟐 = 𝟎.
Now as the real objective function was:
Max Z=3𝑥1 - 𝑥2 ;
Subject to
2𝑥1 +𝑥2 ≥2;
𝑥1 +3𝑥2 ≤2;
𝑥2 ≤4 ;
And 𝑥1 , 𝑥2 ≥0
Max Z=3𝑥1 - 𝑥2 ;
Subject to
2𝑥1 +𝑥2 ≥2;
𝑥1 +3𝑥2 ≤2;
𝑥2 ≤4 ;
And 𝑥1 , 𝑥2 ≥0
Max Z=3(2) – 0 Z=6
Subject to
2(2)+0 ≥2;
2+3(0)≤2;
0 ≤4 ;
And 𝑥1 , 𝑥2 ≥0 2 ≥0 and 0 ≥0
Example NO. 2
Min Z=𝑥1 - 2𝑥2 -3 𝑥3 ;
Subject to
-2𝑥1 + 𝑥2 +3𝑥3 =2;
2𝑥1 + 3𝑥2 +4𝑥3 = 1;
And 𝑥1 ,𝑥2 , 𝑥3 , ≥0
Standard Form:
For Max Z , multiply with –ve
Max Z= -𝑥1 + 2𝑥2 +3 𝑥3 ;
-2𝑥1 +𝑥2 +3𝑥3 +𝐴1 =2;
2𝑥1 +3𝑥2 +4𝑥3 +𝐴2 = 1;
And 𝑥1 ,𝑥2 , 𝑥3 , 𝐴1,𝐴2 ≥0
▪ Auxiliary Linear Programming Problem
Maximize 𝑍 ∗ = 0𝑥1 −0𝑥2 − 0 𝑥3 − 𝐴1 ;
Subject To:
-2𝑥1 +𝑥2 +3𝑥3 +𝐴1 =2;
2𝑥1 +3𝑥2 +4𝑥3 +𝐴2 = 1;
And 𝑥1 ,𝑥2 , 𝑥3 , 𝐴1,𝐴2 ≥0
Phase-I
(𝑋𝐵 )
Cj 0 0 0 -1 -1
R.H.S
Ratio
Basic
𝐶𝐵 𝑥1 𝑥2 𝑥3 𝐴1 𝐴2
Variable
𝐴1 -1 -2 1 3 1 0 2
𝐴2 -1 2 3 4 0 1 1
𝒁∗ = 𝑪 𝑩 x 𝑿𝑩
(-1,-1)(2,1)-2-1=-3
△j=(𝑪𝑩 x 𝑿𝒋 ) − 𝑪𝒋
△1=((-1(-2)+(-1)(2))-0=0
△2=(-1(1)+(-1)(3))-0=-4
Similarly we’ll find out the values of other variables △3, △4…
Phase-I
Incoming
Vector
(𝑋𝐵 )
Cj 0 0 0 -1 -1
R.H.S
Ratio
Basic
𝐶𝐵 𝑥1 𝑥2 𝑥3 𝐴1 𝐴2
Variable
𝐴1 -1 -2 1 3 1 0 2 2/3
𝐴2 -1 2 3 4 0 1 1 1/4
𝒁∗ =-3 △j 0 -4 -7 0 0
Phase-I
Performing Row Operation
R2’=R2/2
Phase-I
(𝑋𝐵 )
Cj 0 0 0 -1 -1
R.H.S
Ratio
Basic
𝐶𝐵 𝑥1 𝑥2 𝑥3 𝐴1 𝐴2
Variable
𝐴1 -1 -2 1 3 1 0 2 2/3
𝑥3 0 1/2 3/4 1 0 1/4 1 1/4
𝒁∗ =-3 △j 0 -4 -7 0 0
Phase-I
Performing Row Operation
R1’=R1-3R2’
Phase-I
(𝑋𝐵 )
Cj 0 0 0 -1 -1
R.H.S
Basic
𝐶𝐵 𝑥1 𝑥2 𝑥3 𝐴1 𝐴2
Variable
𝐴1 -1 -7/2 -5/4 0 1 -3/4 5/4
𝑥3 0 1/2 3/4 1 0 1/4 1/4
𝒁∗ =-5/4 △j 7/2 5/4 0 0 7/4
since △j ≥ 0
An optimum solution to the auxiliary LPP has been
attained ,But
Max 𝒁∗ 𝒊𝒔 − ve
And Auxiliary Variable A1 appears at the Positive Level
Hence The original LPP doesn’t possess any feasible
solution
