In the standard simplex table
The coefficients of the basic variables in the z-row
should be zero.
The respective coefficients in the constraint matrix
must be identity coefficients.
In case it is not we have to use elementary row
operations to keep it in the standard simplex form
before we apply the simplex method
Contents
Artificial Variables Techniques
Big M Method
Two Phase Method
If in a starting simplex tableau, we dont have an
identity sub matrix (i.e. an obvious starting BFS), then
we introduce artificial variables to have a starting BFS.
This is known as artificial variable technique.
There are two methods to find the starting BFS and
solve the problem
(1) Big M Method
(2) Two-Phase Method.
Big M Method
Suppose that ith constraint equation doesn't have a
slack variable. i.e.
ith constraint in the original LPP is either or = type .
Then an artificial variable Ri is added, to form the ith
unit vector column.
Since the artificial variables are not part of the
original LPP, they are assigned a very high penalty in
the objective function and thus forcing them to equal
zero in the optimum solution.
Artificial variable objective coefficient
= - M (Sum of artificial variables) in a maximization
problem,
= M (sum of the artificial variables ) in a minimization
problem
where M is a very large positive number.
Mathematically M
Example 1
Min z = 4x1 + 3x2
Subject to
2x1 + x2
10
x1 + x2
6
-3x1 + 2x2
6
x10, x20
Writing z as equation and adding
slack and surplus variables to the
constraints
z 4x1 3x2
=0
= 10
2x1 +x2 S1
x1 + x2 - S2
=6
+ S3 = 6
-3x1 + 2x2
7
Addition of artificial variables to obtain a starting BFS
2x1 + x2 S1 +R1
= 10
x1 + x2 S2
+R2 = 6
+ S3 = 6
- 3x1 + 2x2
Artificial
variables
R1 and R2 added to
the constraints
These artificial variables are penalized in the objective
function by assigning some very large value (say M) to
them in the objective function
z = 4x1 + 3x2 + MR1 + MR2
2x1 + x2 s1 +R1
x1 + x2 s2
+R2
- 3x1 + 2x2
+ s3
Objective function
= 10
=6
=6
constraints
Where M is a very large penalty assigned on
artificial variables R1 and R2
Tabular form
Basic
x1
x2
S1
-4
-3
R1
R2
S3
-3
S2
R1
R2
S3
solution
-M
-M
-1
10
-1
10
Since the z column does not change in the iterations, it may be
deleted
Basic
x1
x2
S1
-4
-3
R1
R2
S3
-3
S2
R1
R2
S3
solution
-M
-M
-1
10
-1
The initial BFS as obtained from the table is
R1 = 10; R2 = 6 and z = 0
Is this table
correct ?
11
But if R1 = 10; R2 = 6 then the value of
objective function should be z = 16 M, since
we have defined the objective function as:
z = 4x1 + 3x2 + MR1 + MR2
Why does this inconsistency appears?
This is because of the fact that the elements
of the basic variable have a non zero
coefficient in the z-row.
The starting table now becomes
12
Basic
x1
x2
S1
-4 + 3M
-3+2M
-M
R1
R2
S3
-3
S2
R1
R2
S3
solution
-M
16M
-1
10
-1
Apply the usual simplex method for solving
minimization problem
13
Selecting pivot row and pivot column for a minimization problem
Basic
x1
x2
S1
-4 + 3M
-3+2M
-M
R1
-1
R2
S3
-3
S2
R1
R2
S3
solution
-M
16M
10
Min.
ratio
10/2
0
-1
6
6/1
---
Select the most positive element of the z row
14
Second iteration
Bas
ic
x1
x2
S1
-2+M
2
-4-M
2
x1
1/2
R2
S3
R1
R2
S3
-M
4 3M
2
20 +M
-1/2
1/2
1/2
-1
7/2
-3/2
21
1/2
S2
solution Min.
ratio
5/1/2
1/1/2
21/7/2
15
Final iteration
Basic
x1
x2
S1
S2
R1
R2
S3
solution
-1
-2
1M
(2-M)/2
22
x1
-1
x2
-1
S3
-13/2
14
Solution x1 = 4; x2 = 2; z = 22
16
Consider the following LPP:
Maximize
Subject to
z = 2 x1 + 3 x 2 5 x3
x1 + x 2 + x3 = 7
2 x1 5 x 2 + x3 10
x1 , x 2 , x3 0
17
Introducing surplus and artificial variables, s2, R1 and R2 , the
LPP is modified as follows:
Maximize
Subject to
z = 2 x1 + 3 x 2 5 x3 MR1 MR 2
x1 +
x2 + x3
2 x1 5 x 2 + x 3 s 2
+ R1
= 7
+ R2 = 10
x1 , x 2 , x 3 , s 2 , R 1 , R 2 0
Now we solve the above LPP by the Simplex method.
18
Basic z
x1
x2
x3
s2
-2-3M -3+4M 5-2M M
-2
-3
5
0
R1
R2
Sol.
0
M
0
M
-17M
0
R1
R2
z
0
1
0
0
0
1
1
6M/2
1/2
1/2
-1
-1 M/2
1/2
-1/2
0
0
R1
x1
-5
-8 7M/2
7/2
-5/2
50/7
102/7
x2
1/7
1/7 16/7 + -1/7
M
+M
1/7 2/7 -1/7
x1
6/7
-1/7
45/7
1
0
5/7
1
10
1+
10 3M/2 2M
-1/2
2
1/2
5
1/7
4/7
The optimum (Maximum) value of
z = 102/7
and it occurs at
x1 = 45/7, x2 = 4/7, x3 = 0
20
If in any iteration, there is a tie for leaving variable
between an artificial variable and other variable
(decision, surplus or slack), we must prefer the
artificial variable to leave the basis.
An artificial variable is never considered for re-entry
into the basis.
If in the final optimal tableau, an artificial variable is
present in the basis at a non-zero level, this means our
original problem has no feasible solution.
21
Tutorial - 3
22
(1). Solve the following LPPs using Simplex method:
(i) Max.
subject to
z = 1 2 x1 1 5 x 2
4 x1 + 3 x 2
12
2 x1 + 5 x 2 1 0
x1 , x 2 0
z = 2 x1 3 x 2
(ii) Max.
subject to x 1 + x 2 2
2 x1 x 2 2
x1 x 2 2
x1 0 , x 2 u n re s tric e d
23
(iii) Max.
subject to
z = 3 x1 + 2 x 2 + 5 x 3
x1 + 2 x 2 + x 3 4 3 0
3 x1 2 x 3 4 6 0
x1 + 4 x 2 4 2 0
x1 , x 2 , x 3 0
(iv) Min.
subject to
z = 6 x1 2 x 2 6 x 3
2 x1 3 x 2 + x 3 1 4
4 x1 + 4 x 2 + 1 0 x 3 4 6
2 x1 + 2 x 2 4 x 3 3 7
x1 2 , x 2 1, x 3 3
24
(2). Solve the following LPPs using Big-M method:
(i) Max.
subject to
z = x1 + 3 x 2
x1 + 2 x 2
3 x1 + x 2 3
x1 4
x1 , x 2 0
z = 9 x1 + x 2 + 2 x 3
(ii) Min.
subject to 4 x 1 + 2 x 2 + x 3 5
x1 + 2 x 2 + 3 x 3 4
x1 , x 2 , x 3 0
25
TWO PHASE METHOD
26
Why use two phase method when Big M - method
is already there ?
One major disadvantage of Big M - method is that it
is computationally inefficient.
Mathematically it is said that M should be a very
large number, but sometimes very large values of M
may lead to a wrong result.
27
Phase - I
We construct an auxiliary LPP (always a minimization
problem).
The objective function is sum of artificial variables,
with the original constraints
The optimal solution of the auxiliary problem will give
a starting BFS for the original problem.
28
Phase - II
We use the basic feasible solution available from the
Phase-I to find the optimal solution of the original
problem.
29
Example
Min
z = 4x1 + 6x2 + 5x3
Subject to
2x1 + 4x2 + 3x3 32
x1 + 2x2 + 4x3 28
x1, x2, x3 0
30
s1, s2 surplus variable
R1 , R2 artificial variables
Min z = 4x1 + 6x2 + 5x3
Subject to
2x1 + 4x2 + 3x3 s1 + R1
= 32
x1 + 2x2 + 4x3
s2
+ R2 = 28
x1, x2, x3 0
Artificial variables are added to get an identity sub matrix
31
Phase I: (construct an auxiliary LPP)
construct a new objective function in which the
coefficients of artificial variables are 1 and the
coefficients of all other variables are zero
Min r = R1 + R2
New objective function
2x1 + 4x2 + 3x3 s1
+ R1
= 32
x1 + 2x2 + 4x3
s2
+ R2 = 28
x1, x2, x3 0
Constraints
32
Basic
x1
x2
x3
s1
R1
R2
s2
R1
R2
solution
-1
-1
-1
32
-1
28
form a new r row (similar to the manner in which new z- row is
formed in Big M method)
Thus
New r-row = r-row + R1 row + R2 row
33
Standard simplex table
Basic
x1
x2
x3
s1
-1
R1
R2
s2
R1
R2
solution
-1
60
-1
32
-1
28
34
Applying the usual simplex method for solving a
minimization problem
Basic
x1
x2
x3
s1
-1
R1
R2
s2
R1
R2
solution
-1
60
-1
32
32/3
-1
28
28/4
Min.
ratio
35
Basic
x1
x2
x3
s1
3/4
5/2
-1
R1
5/4
5/2
5/2
x3
1/4
1/2
s2
R1
R2
solution
7/4
-7/4
11
-1
3/4
-3/4
11
-1/4
1/4
36
Basic
x1
x2
x3
s1
x2
1/2
x3
s2
R1
R2
solution
-1
-1
-2/5
3/10
2/5
-3/10
22/5
1/5
-2/5
-1/5
2/5
24/5
At this point both the artificial variables have completed their
purpose and hence their columns can be removed from the
table.
37
Phase II
We will use the BFS obtained in Phase-I as a starting
BFS of the given problem, and use simplex method to
find the optimal solution.
38
Form a simplex table
Basic
x1
x2
x3
s1
s2
solution
-4
-6
-5
x2
1/2
-2/5
3/10
22/5
x3
1/5
-2/5
24/5
Is this standard simplex table?
39
z row = z row + 6*(x2 row) + 5*(x3 row)
Basic
x1
x2
x3
s1
s2
solution
-1
-12/5
-2
252/5
x2
1/2
-2/5
3/10
22/5
x3
1/5
-2/5
24/5
Since all the conditions for optimality (for a minimization problem) are
being satisfied. Phase two ends at this point.
40
Solve the following LPP using Two-Phase method:
Minimize
Subject to
z = 2 x1 + 5 x2 + 3 x3
x1 2 x 2 + x 3 2 0
2 x1 + 4 x 2 + x 3 = 5 0
x1 , x 2 , x 3 0
41
Phase I:
Minimize
Subject to
r = R1 + R2
x1 2 x2 + x3 s1 + R1
2 x1 + 4 x2 + x3
= 20
+ R2 = 50
x1 , x2 , x3 , s1 , R1 , R2 0
42
x1
x2
x3
s1
R1
3
0
2
0
2
0
-1
0
0
-1
0
-1
70
0
R1
-2
-1
20
R2
50
-1
-3
10
x1
-2
-1
20
R2
-1
-2
10
Basic
R2
Sol
43
Basic r
x1
x2
x3
s1
R1
-1
-3
x1
-2
R2
x1
x2
R2
Sol
10
-1
20
-1
-2
10
-1
-1
3/4
-1/2
1/2
1/4
45/2
-1/8
1/4 -1/4
1/8
5/4
44
This is optimal tableau. Thus Phase I has ended and we
now start Phase II with the starting BFS as the optimal
solution of Phase I.
Phase II:
Minimize
z = 2 x1 + 5 x2 + 3x3
subject to the same constraints as given in the original
problem.
45
Basic z
x1
x2
0
-2
0
-5
-17/8
-3
1/4
0
205/4
0
x1
3/4
-1/2
45/2
x2
-1/8
1/4
5/4
-1
-2
50
x1
1/2
25
s1
x3
-1/2
s1
R1
R2
Sol
Thus the optimal solution is : x1 = 25, x2 = 0, x3 = 0 and the
optimal z = Min z = 50.
46
In Phase I we always minimize the sum of the
artificial variables.
If in the optimal table of phase I an artificial variables
remains at non-zero level in the basis, then the problem
has no feasible solution.
47
Tutorial - 4
48
Solve the following LPPs using Two-Phase Method
(i) Maximize
Subject to
z = 2 x1 + 3 x 2 5 x3
x1 + x 2 + x3 = 7
2 x1 5 x 2 + x3 10
x1 , x 2 , x3 0
49
(ii) Maximize
z = 2 x1 + 2 x2 + 4 x3
Subject to
2 x1 + x2 + x3 2
3 x1 + 4 x2 + 2 x3 8
x1 , x2 , x3 0
50
(iii) Max.
subject to
z = x1 + 3 x 2
x1 + 2 x 2
3 x1 + x 2 3
x1 4
x1 , x 2 0
(iv) Min.
z = 9 x1 + x 2 + 2 x 3
subject to
4 x1 + 2 x 2 + x 3 5
x1 + 2 x 2 + 3 x 3 4
x1 , x 2 , x 3 0
51
