Higher Engineering Mathematics

Professor P. N. Agrawal
Department of Mathematics
Indian Institute of Technology Roorkee
Lecture - 48
Two Phase Method - I

Hello friends, welcome to my lecture on a first lecture on Two Phase Method, as an

alternative to Big M method there is another method known as Two Phase Method to deal
with linear programming problems, it involves involving artificial variables.

(Refer Slide Time: 01:16)

Now, in this method the solution is obtained in two phases, in phase one all the artificial
variables are eliminated from the basic variables, in phase two we use the solution from phase
one as the initial basic feasible solution and use the simplex method to determine the optimal
solution.

So, we in phase one all the artificial variables are eliminated from the basic variables and
then the solution which we get in from phase one that is treated as initial basic feasible
solution and we use the simplex method to determine the optimal solution.
(Refer Slide Time: 01:19)

So, in phase one what we do? Let us consider step 1, after making all bi’s positive we convert
each of the constants into equations by introducing slack, surplus and artificial variables. In
step 2 we assign zero coefficients to each of the primary, slack and surplus variables and the
coefficient - 1 to each of the artificial variables in the objective function.

So, here in the here this is in this method artificial variables are assigned the value - 1 each
coefficient I mean of the artificial variable is taken as - 1 as a result the new objective
function is of the form Z* = - sum of artificial variables because primary, slack and surplus
variables are assigned value 0, ok 0 coefficients they are assigned but the artificial variables
are assigned coefficient - 1.

So, when you write the new objective function say it is Z* then it will be - sum of artificial
variables. Now, we maximize Z* subject to the constants of the original problem using the
simplex method and then what we will have three cases will be there.
(Refer Slide Time: 02:32)

So, these cases are if maximum of Z¿ is less than 0, if maximum of Z* is less than 0 and at
least one artificial variable appears in the optimal optimum basis at a positive level then the
given problem does not possess any feasible solution. So, when maximum of Z* < 0 and one
at least one artificial variable appears in the optimum basis at a positively positive level
means? The value corresponding value in the B column is positive then we do then the
problem does not possess any feasible solution.

If maximum of Z* = 0 at least and at least one artificial variable appears in the optimum basis
at zero level, zero level means? In the B column the value corresponding to the optimum
artificial variable is 0, then we will proceed to phase two and in the third case when
maximum of Z* is 0 and no artificial variable appears in the optimum basis then also we
proceed to phase 2.

So, we proceed to phase two in two cases the two cases are when the maximum value of Z* is
0 and one at least one artificial variable appears in the optimum basis at 0 level or in the
second case maximum value of Z* is 0 and no artificial variable appears in the optimum
basis. So, but in the third case when maximum of Z* < 0 and at least one artificial variable
appears in the optimum basis at a positive level then the problem does not possess any
feasible solution.
(Refer Slide Time: 04:10)

So, now let us go to phase 2, in phase 2 we start with the optimal solution contained in the
final simplex table of phase 1, ok. So, we will start with this, final simplex table of phase 1.
The solution we got there that we will start with that, so then we assigned the actual cost to
the variables in the objective function and a zero cost to every surplus variable. Now, we
eliminate the artificial variables which are non-basic at the end of phase one, ok so they will
be eliminated artificial variables.

Now, we removes c j row values of the optimum table and replace them with c j values of the
original problem, ok then we apply simplex algorithm to the problem content in the new table
to obtain the optimal solution.

(Refer Slide Time: 05:04)

Now, what is the advantage of two-phase method over Big M method? What is the advantage
of two-phase method over Big M method? We can always use Big M method to check the
existence of a feasible solution, but it is computational procedure may be inconvenient
because of the manipulation of the constant M. Two phase method eliminates the artificial
variables in the beginning in the phase one itself the artificial variables are eliminated.

Now, when we solved the problem on a digital computer we have to assign some numerical
value to M which must be larger than the values c 1, c 2 present in the objective function, but a
computer can have a computer has only a fixed number of digits.

(Refer Slide Time: 05:50)

Now, let us solve the following problem by using two-phase method, so we have the problem
minimum of Z = 7 point 5 x 1 - 3 x2 subject to 3 x 1 - x2 - x3 ≥3, x 1 - x2 + x3 ≥ 2 ; x 1, x2 , x 3 ≥ 0.
So, let us see how we do this problem so first we will convert this minimum a minimization
problem to maximization problem, ok.
(Refer Slide Time: 06:15)

So, step 1, express the problem in the standard form, ok. Introducing the surplus variables,
now we see this is ≥ type this is ≥ type, so we will have to add 2, we will have to consider
two surplus variables and also two artificial variables, ok. So introducing surplus variables s1,
s2 artificial variables A 1, A 2 the phase one problem in a standard form becomes maximum Z*
=, now we have 0 into x 1, 0 into x2 , 0 into x3 , 0 and x s1, 0 into s2 then A 1 and A 2 the
coefficients of A 1 and A 2 are taken as - 1 each, so - A 1 - A 2 we have and subject to.

Now, the questions that we have by using surplus and artificial variables are 3 x 1 - x2 - x3 then
- s1 + 0 s2 + A 1 + 0 A 2 = 3 x 1 - x2 + s x 3 and then 0 s1 - s2 + 0 A 1 + A 2 = 2, x 1, x2 , x3 s1, s2 , A 1
, A 2 ≥0.
(Refer Slide Time: 07:25)

Now, we find any initial basic feasible solution, so we have how many equations are there?
We have two equations and the variables are 1, 2, 3, 4, 5, 6, 7, so we have seven variables
and the equations are 3, so 5 variables can be taken as 0. So, we will take x 1, x2 , x3 , s1, s2 = 0
and we get the values of A 1 and A 2, ok A 1 comes out to be 3, ok from here and A 2 comes out
to be 2 from here.

So, x 1, x2 , x 3 s1, s2 and A 1, A 2 are all ≥ 0 and Z* comes out to be - 5, Z* = at x 1, x2 , x 3 , s1, s2

are zeros A 1 is 3, A 2 is 2, so Z* = 5. Initial simplex table will be now, you see x 1, x2 , x 3 , s1, s2
, A 1, A 2 b column, ok and then the basic variables are basic variables are A 1, A 2 non basic
variables are x 1, x2 , x 1, s 3 because they are assigned value 0 here, 0 in the objective function,
ok they are assigned 0, 0, 0, 0, 0, 0, so we have 0, 0, 0, 0, 0 there are coefficients of x 1, x2 , x 3 ,
s1, s2 in the objective function and coefficient of A 1, A 2 in the objective function are - 1 each.

Now, coefficient of A 1 in the objective function is - 1, coefficient of A 2 in the objective

function is - 1 and this is your body matrix, ok 3, - 1, - 1, - 1 yeah 3, - 1, - 1, - 1 -, 1, 1 - 4, 2,
0 - 4, 4, -, ok so this 1 these are the coefficients of x 1 3, 1 (min) 3 and 1, ok the coefficients of
x 1 are 3 & 1, coefficient of x2 are - 1, - 1, coefficient of x3 is - 1, + 1, ok and these are the
coefficient of s1, s2 coefficient of A 1 and coefficient of A 2 and these are the elements in the b
column 3 and 2, this one 3 and 2 this one, ok so these are coefficients in the b column.

Now, we find Z* c sigma c be aij , so 3 (in) - 1 into 3 is -3, - 1 into 1 is - 1 so total is - 4, we

subtract - 4 from 0 we get 4 here and then sigma, similarly - 1 into - 1 is + 1, - 1 into - 1 is +
1, 1 and 1 is 2, 2 we subtract from 0 we get - 2 and similarly we get Z j¿ here as 0, here Z j¿ is
say star = 1, here 1, here - 1, here - 1 and here what we get? - 1 into 3 is -3 -, - 1 into 2 is - 2,
so we got total - 5, ok.

Now, C j is = 4 here, ok C j is C j - Z j¿, so 0 - - 4 gets you gives you 4 and 0 - - 0 - 2 gives

you - 2 here, this is 0, this is - 1, - 1, 0, 0. Now, we can see that C j is positive in this column,
ok so C j is positive under x 1 column and therefore this solution is not optimal. So, what we
will do? This is our key column, ok and we divide the elements of the b column by the
corresponding elements of key column.

So, (si) 3 divided by 3 gives you 1, ok and then 2 divided by 1 gives you 2 the minimum of 1
and 2 is to 2 1, so this is our key row, ok and at the intersection of key row and key column
we get key elements, so this is key element, 3 is the key element. Now, x 1 is the incoming
variable, A 1 is the outgoing variable, so here we will get in the new simple new next simplex
table A 1 between will be replaced by x 1 and this - 1 will be replaced by 0 the coefficient of x 1
, so we have this table, ok.
(Refer Slide Time: 11:38)

The x1 comes here be, the coefficient in of x 1 is 0, 0 is either, ok and then what we do? We
divide the elements of key row by the key element, ok so 3 by 3 we divide all the elements
off key row, ok so we get 1 here, - 1 by 3, - 1 by 3, - 1 by 3, 0, 1 by 3, 0 and we get 1 here
there ok, so we get this 1 -, 1 by 3, - 1 by 3, - 1 by 3, 0, 1 by 3, 0, 1, ok and then with the help
of this row this new row, ok.
(Refer Slide Time: 12:19)
With the help of this new row we make the element this, this element at 0, ok so what we will
do? We make this element 0 ok. So we have divided this row by 3 it became 1, so now this is
also 1, so we simply have to subtract this new key row, a new row that we have got this row
from the second row, ok so what we will get? When we have 1 - 1 we have this, ok 1 - 1, 1, 0,
- 1, 0, 1 and 2 from that we subtract this row and then we get this 0 - 2 by 3, 4 by 3, 1 by 3, -
1, - 1 by 3, 1, 1 ok.

And then, now we calculate Z j¿, Z j¿ is 0 into 1, - 1 into 0 is 0, 0 - 0 is 0 then 0 into - 1 by 3, -

1 into - 2 by 3 is 2 by 3, 0 - 2 by 3 is - 2 by 3, so we get the new values of C j are 0, - 2 by 3,
4 by 3, 1 by 3, - 1, - 1 by 3, 0 ok and here Z j¿ is - 1, now we can see C j is positive under x3
column ok and s1 column, ok.

So, maximum is 4 by 3 this is maximum, ok 4 by 3, so this is our key column, ok. So, now
we find we have to find key row, so divide - 1 by 3, divide this 3 divide by 1 by - 1 by 3 we
get - 3 and divide 1 by 4 by 3 we got 3 by 4 minimum positive value we have to consider here
in the theta column, so minimum positive value is 3 by 4 so this is our key row, ok this key
row and this is key column, so we have this as the key element, this is our key element, ok.

Now, so what will happen? Now x 3 will come in and A 2 will go out, so instead of A 2 now in
the new term a table they will have x3 here the value in the C B column will be 0, ok and
what we will do then? This element of the key row will then be divided by the key element
that is 4 by 3 to bring the unity here. So, we have this row this new table making key element
4 by 3 unity and replacing A 2 by x 3 we obtained it yeah, so this is our x3 here, ok this is x3 , ok
so we have 0 in the C B column 0 for x 1, 0 for x3 and we have here A 1 8, ok so right, so what
we have here?

Now, 4 by 3 we divided by 4 by 3 this elements of the key row, ok so - 2 by this will remain
0 this will become - 2 by 3 into 3 by 4, so we get - half, so this element will become - half,
this element will become - half, this will become 1, this will become 1 by 3 into 3 by 4, 1 by
4, ok so you can see here - half, 1, 1 by 4 ok and this element will become what? - 3 by 4 ok -
3 by 4 and this element will become 1 into 3 by 4, so this will become 3 by 4, 3 by 4 ok so in
this it will become 3 by 4 also this one 3 by 4 and this is - 1 by 4 in A 1 column, in A 1 column
yeah - 1 by 3 ok divided by 4 by 3 so we get 3 by 4 so we get - 1 by 4.

So, new row that we get after dividing by 4 by 3 we get this like this, ok. Now, what we will
do? This element we have made 1, ok by dividing by 4 by 3, ok now with the help of this one,
ok we make this 0 and this 0, ok the other elements in the column corresponding to x3 we
make them as 0, so this is - 1 by 3 here we have 1, so we multiply this by 1 by 3 and (sub)
add to this row, ok here it is - 4 by 3, here we have 1 by 3 it is 1, 1, so we multiplied by 4 by
3 and add to this, so we get this ok this is 0, this is 0, ok.

So, after that what happens is, ok with so this we have made as 1, here we have - 1 by 3, so
we multiply the elements of the key row by 1 by 3 and add to the above row, so what we
have? The above row is you see 1 - 1 by 3, - 1 by 3, ok - 1 by 3 and then we have 0, 1 by 3
and then we have 0, 1 this is 0, ok 1, - 1 by 3, - 1 by 3, - 1 by 3 0, 1 by 3, 0, 1.

Now, the row this row is what? 0 and what we have a - half, 1, 1 by 4, - 3 by 4, 1 by 4, - 3 by
4, - 1 by 4 (mi) and then 3 by 4, 3 by 4, ok. Now, what we do? With the help of this one we
make this element 0, ok so we multiply this row by 1 by 3 and add to that row, ok this row, so
what we will get? 1, 0 into 1 by 3 we add to this it will remain 1 then we multiply by 1 by 3
and add to that, so - 1 by 3 then we have - 1 by 6, ok.

Then 1 by 3 we add to this we get 0 here and then we multiply by 1 by 3 and add there, so - 1
by 3 + 1 by 12, ok that is what we get for this and then we multiplied by 1 by 3 and add there
so we get 0 and - 3 by 4 into 1 by 3 so - 1 by 4 and what we get here? 1 by 3 we multiply by 1
by 3 and add so - 1 by 12, ok then here we multiply by 1 by 3 and add, so 0 and 1 by 4 ok and
here we multiplied by 1 by 3 and add so what we will get? 1 + 3 by 4 into 1 by 3, so that
gives you 5 by 4.
So, what will be the elements now? So this will remain 1 then - 1 by 3, - 1 by 6 so this is - 3
by 6, ok then we have 0 then here how much we have? - 4 by 12 so - 4 + 1, - 3 by 12, ok here
we get - 1 by 4, here we get this is how much? 3 by 12, - 1 by 12 so 2 by 12 and then we get 1
by 4 and then we get 5 by 4, so what we get? 1, - 1 by 2, 0, - 1 by 4, - 1 by 4 then 1 by 6 then
1 by 4 then 5 by 4, ok so this is what we get?

Let us see, what we are getting there? 1, - half, 0, - 1 by 4, 1 - half, 0, - 1 by 4 right and then
we get - 1 by 4, 1 by 4, 1 by 4, 1 - half, 0, - 1 by 4, 1 - half, 0 into this is there, this is there,
this is there, this is there, then what is the next element? - 1 by 4, 1 by 4, 1 by 4, 1 by 4, 1 by
4, so this is this should be 1 by 4, ok and then last one is how much? 5 by 4, so this is ok only
we have this element we have to see, so 1, 2, 3, 4, 5, 6 element so 1, 2, 3, 4, 5, 6, so here how
much we have 1 by 3 - 1 by 12, so we get 4 by 12 - 1 by 12 so we get 3 by 12, so this is 1 by
4, so this 1 by 4 not 1 by 6, ok.

So, we get this table this this row, ok 1, 1 by, so we multiply it by 1 by 3 and add to the add
to this row add to this row, ok we get this row and now let us find Z j¿, Z j¿ is 0, ok C j is 0, 0,
0, 0, 0 - 1, - 1 so C j is ≤0 for all j and therefore this (sal) table gives us optimal solution and
Z*, maximum up Z* is how much? this Z*, ok so maximum Z* is also 0 because x 1 is x 1 is =
5 by 4 x3 is = 3 by 4, ok all other variables are non-basic variables so that means x2 0 then we
have s1 0, s2 0 and A 1, A 2 0.

So, in now maximum value of Z*, Z in Z* you take x 1 as 5 by 4, x 3 as 3 by 4, x2 , s1, s2 A 1, A 2

= 0 what you get is? 0 the value of Z* has 0. Now, no artificial variable appears in the basis,
ok at no artificial variable because the basis elements are x 1 and x 3 , so no artificial variable
appears in the basis that element that and therefore an optimal basic feasible solution to
auxiliary problem and therefore to the original problem has been attend because we have seen
that when no artificial variable appears in the basis and Z* is 0 then an optimal basic feasible
solution to the auxiliary problem and therefore to the original problem is obtained.

(Refer Slide Time: 23:33)

Now, let us consider phase 2, in phase to consider the actual cost associated with the original
variables and the objective function is then maximum of Z dash, now Z dash is - Z, ok. So
because we have the problem of minimization, ok so Z dash is - sub Z, so - of 7.5 x 1 + 3 x2 we
consider, so maximum value of - Z we are take, so maximum value of Z dash is maximum of
- 7.5, 7.5 x 1 + 7 3 x2 + 0 x3 + 0 s1+ 0 s2+ 0 A 1+ 0 A 2 are subject to these constants 3 x 1 - x2 - x3 - s1
+ 0 s2 + A 1 + 0 A 2 = 3 and then x 1 - x2 + x 3 , 0 s1 - s2+ 0 A 1 + A 2 = 2 and x 1, x2 , x 3 , s1, s2, A 1, A 2
≥ 0.
(Refer Slide Time: 24:28)

Now, the optimal initial basic feasible solution, ok thus obtained will be an optimal basic
feasible solution to the original L.P.P. So what we will do? The final table of phase 1 will
become now the initial simplex table of phase 2, ok. So basis is x 1, x3 we can see x 1, x3 is
basis, ok and the coefficient of x 1 now, coefficient of x 1 is - 15 by 2, ok so we write there - 15
by 2, coefficient of x3 here is 0, so we write 0 here ok and then we have 1 - half the same last
table one - half 0, - 1 by 4, - 1 by 4.

So, we just copy that, you see here we just copy that and then here x 1, coefficient of x 1 is - 15
by 2, coefficient of x2 is 3, coefficient of x3 is 0, coefficient of s1 is 0, coefficient of s2 is 0,
A 1, A 2 have been eliminated, ok. Now, we find Z j here, ok Z j is - 15 by 2 into 1 + 0 into 0,
so - 15 by 2, capital C j therefore is small c j - Z j gives you 0 and here we get - 15 by 2 into -
1 by 2 + 0 into - half gives Z j a s15 by 4 then 3 - 15 by 4 is - 3 by 4, here C j comes out to be
0, here - 15 by 8, here it is - 15 by 8 and here what we get? - 15 by 2 into 5 by 8 + 0 into 3 by
4 that is - 75 by 8.

Now, let us see C j is 0 here, here negative, here 0, here negative, here negative, so C j ≤ 0
and therefore this solution is optimal and so an optimal basic feasible solution to the given
problem is x 1 = 5 by 4, x 3 = 3 by 4, x2 = 0 because x2 is non-basic variable, so x2 = 0 and
minimum value of Z, ok.

Now, (max) this is - 75 by 8, so minimum value of Z = - maximum value of your Z dash, ok

which is –( - 75) by 8 and we get 75 by 8, so that is the minimum value of Z. So, there is
solution to the linear programming problem, so that is all in this lecture, thank you very much
for your attention.