Big-M Method [Introduction]
In order to obtain an initial basic feasible solution, it is necessary to convert the
given LPP into its standard form; in order to obtain the standard form; a non-negative
variable is added to the left side of each of the equation that lacks the much needed
starting basic variables. So added variable is called an artificial variable and it places
the role in providing initial basic feasible solution.
The starting point of the big-M method is a basic solution that is feasible to the
artificial problem. This solution allows us to start the Simplex algorithm
expeditiously, but it is not a feasible solution to the original problem. Our goal is to
iterate toward solutions that are inside the original feasible set, assuming that it is not
empty.
The artificial variables have no physical meaning from the view of the original
problem; the method will be valid only if it is possible to force these variables at zero
level when the optimum solution is attained.
To accomplish this goal, we designed an artificial objective function that is an
aggregation of two functional parts, of which one is a copy of the original objective
function and the other is a “penalty function” associated with the artificial variables.
The magnitude of the penalty, M, needs to be chosen to ensure that the
contribution to this aggregate objective function from the second part, whenever it is
positive, always outweighs that from the first part, for any solution.
Artificial Variable
If there is a constraint which is of > = or equality type then it is needed to write
the constraint in standard form because it is not possible to get unit column vector.
The additional variable, which is added in order to get unit column vector, is called an
artificial variable.
Two methods are generally employed for the solution of linear programming
problems having artificial variables:
1. Two-Phase Method.
2. Big-M Method (or) Method of Penalties. We will have discussion only on Big-M
Method here.
The Big M Method Procedure
If an LP has any ≥ or = constraints, the Big M method
or the two-phase simplex method may be used to
solve the problem.
The Big M method is a version of the Simplex Algorithm that first finds a best
feasible solution by adding “artificial” variables to the problem. The objective
function of the original LP must, of course, be modified to ensure that the artificial
variables are all equal to 0 at the conclusion of the simplex algorithm.
Step-1
Modify the constraints so that the RHS of each constraint is non-negative (This
requires that each constraint with a negative RHS be multiplied by -1. Remember that
if any negative number multiplies an inequality, the direction of the inequality is
reversed). After modification, identify each constraint as a ≤ , ≥ , or = constraint.
Step-2
Convert each inequality constraint to standard form (If a constraint is a ≤ constraint,
then add a slack variable and if any constraint is a ≥ constraint, then subtract an excess
variable known as surplus variable).
Step-3
Add an artificial variable a1 to the constraints identified as ‘≥’ or with ‘=’ constraints
at the end of Step2. Also add the sign restriction ai ≥ 0.
‘≤’ constraint: add a slack variable
‘≥’constraint: subtract a surplus variable & add an artificial variable
‘=’ constraints: add an artificial variable
Step-4
Let M denote a very large positive number. If the LP is a minimization problem, add
(for each artificial variable) Mai to the objective function. If the LP is a maximization
problem, add (for each artificial variable) -Mai to the objective function.
Step-5
Since each artificial variable will be in the starting basis, all artificial variables must
be eliminated from row before beginning the simplex.
Now we solve the transformed problem by the simplex (In choosing the entering
variable, remember that M is a very large positive number). If all artificial variables
are equal to zero in the optimal solution, we have found the optimal solution to the
original problem. If any artificial variables are positive in the optimal solution, the
original problem is infeasible!!!
Solve the following LPP by using Big -M Method
Maximize Z = 6X1+4X2
Subject to constraints:
2X1+3X2 ≤ 30
3X1+2X2 ≤ 24
X1+X2 ≥ 3
Solution
Introducing slack variables S1, S2 to the first and second equations in order to convert ≤
type to equality and add surplus variable to the third equation S3 to convert ≥ type to
equality. an artificial variable A1 is added in the third equation. Now the standard form will
be
Then the standard form of LPP is
Max Z = 6X1+4X2+0S1+0S2+0S3-MA1
Sub to:
2X1+3X2+S1=30
3X1+2X2+S2=24
X1+X2-S3+A1=3
Now the first simplex table is placed below with following additional information.
0 0
Cj 6 4 0 -M
S2 S3 solutio
CBj BV X1 X2 S1 A1 n Min ratio
0 S1 2 3 1 0 0 0 30 30/2= 15
0 S2 3 2 0 1 0 0 24 24/3 = 8
-M A1 1 1 0 0 -1 1 3 3/1=3
Zj -M -M 0 0 M -M
6-(- 4-(- 0 -M
Cj-Zj M) M) 0 0
Cj 6 4 0 0 0
CBj BV X1 X2 S1 S2 S3 solution Min ratio
0 S1 0 1 1 0 2 24 24/2= 12
1 3
0 S2 0 -1 0 15 15/3= 5
6 X1 1 1 0 0 -1 3 3/-1
Zj 6 6 0 0 -6
Cj-Zj 0 -2 0 0 6
NEW R1 NEW R2
2-2(1)= 0 3-3(1)= 0
3-2(1) = 1 2-3(1)= -1
1-2(0) = 1 0-3(0) = 0
0-2(0) = 0 1-3(0) = 1
0-2(-1) = 2 0-3(-1) = 3
30-2(3) = 24 24-3(3)= 15
0 0
Cj 6 4 0
CBj BV X1 X2 S1 S2 S3 solution Min ratio
0 S1 0 5/3 1 -2/3 0 14
- 1/3 1
0 S3 0 1/3 0 5
6 X1 1 2/3 0 1/3 0 8
Zj 6 4 0 2 0
Cj-Zj 0 0 0 -2 0 Cj-Zj ≤ 0
R1 R3
0-2(0) = 0 1-(-1)0= 1
1-2(-1/3) = 5/3 1-(-1)-1/3 = 2/3
1-2(0) = 1 0-(-1)0 = 0
0-2(1/3)= -2/3 0-(-1)1/3 = 1/3
2-2(1)= 0 -1-(-1)1 = 0
24-2(5) = 14 3-(-1)5 = 8
X1= 8, X2 = 0
Max Z = 6X1+4X2
Max Z = 6(8)+4(0)
Max Z = 48+0 = 48
Min Z= 5X1+3X2
2X1+4X2 ≤ 12
2X1+2X2 = 10
5X1+2X2 ≥ 10
X1+X2 ≥ 0
Min Z = 5X1+3X2+0S1+0S2+MA1+MA2
2X1+4X2 +S1= 12
2X1+2X2 +A1= 10
5X1+2X2 –S2+A2=10
X1+X2+S1+S2+A1+A2 ≥ 0
Cj 5 3 0 0 M M
CBj BV X1 X2 S1 S2 A1 A2 solution Min ratio
0 S1 2 4 1 0 0 0 12 12/2= 6
M A1 2 2 0 0 1 0 10 10/2= 5
M A2 5 2 0 -1 0 1 10 10/5= 2
Zj 7M 4M 0 -M M M
5- 3- M 0
Cj-Zj 7M 4M 0 0
Cj 5 3 0 0 M
CB X S S2 A solutio
j BV 1 X2 1 1 n Min ratio
0 8/(16/5) =
0 S1 0 16/5 1 2/5 8 5/2
M A1 0 6/5 0 2/5 1 6 6/(6/5) = 5
5 X1 1 2/5 0 -1/5 0 2 2/(2/5) = 5
(2M/5)- M
Zj 5 (6M/5)+2 0 1
(- 0
Cj- (- 2M/5)+
Zj 0 6M/5)+1 0 1
R1 R2
2 – 2(1) = 0 2- 2(1) = 0
4 – 2(2/5)= 16/5 2 – 2(2/5) =6/5
1- 2(0) = 1 0- 2(0) = 0
0- 2(-1/5) = 2/5 0- 2(-1/5)= 2/5
0- 2(0) = 0 1- 2(0) = 1
12- 2 (2) = 8 10- 2(2) = 6
Cj 5 3 0 0 M
CB X S2 A solutio
j BV 1 X2 S1 1 n Min ratio
3 X2 0 1 5/16 1/8 0 5/2
M A1 0 0 -3/8 1/4 1 3
5 X1 1 0 -1/8 -1/4 0 1
- M/4-7/8 M
Zj 5 3 3M/8+5/16
Cj- -M/4+7/8
Zj 0 0 3M/8-5/16
R2 R3
0 – 6/5(0) = 0 1 – 2/5 (0) = 1
6/5– 6/5(1) = 0 2/5– 2/5(1) = 0
0– 6/5(5/16) = -3/8 0– 2/5(5/16) = -1/8
2/5– 6/5(1/8) = 1/4 -1/5– 2/5(1/8) = -1/4
1– 6/5(0) =1 0– 2/5(0) = 0
6– 6/5(5/2)= 3 2– 2/5(5/2) = 1
Max Z= 2X1+X2+X3
Sub to
4X1+6X2+3X3 ≤ 8
3X1-6X2-4X3 ≤ 1
2X1+3X2-5X3 ≥ 3
X1,X2,X3 ≥ 0
Max Z = 2X1+X2+X3+0S1+0S2+0S3-MA1
Sub to :
4X1+6X2+3X3+S1=8
3X1-6X2-4X3+S2=1
2X1+3X2-5X3-S3+A1=3
solutio
0 0 0 -M
Cj 2 1 1 n Min ratio
CB S1 S S3
j BV X1 X2 X3 2 A1
0 S1 4 6 3 1 0 0 0 8 8/6= 1.33
0 S2 3 -6 -4 0 1 0 0 1 1/-6
-M A1 2 3 -5 0 0 -1 1 3 3/3= 1
Zj -2M -3M 5M 0 0 M -M
Cj- 2-(- 1-(- 1- 0 0 -M
ZJ 2M) 3M) 5M 0
solutio
0 0 0
Cj 2 1 1 n Min ratio
CB S1 S S3
j BV X1 X2 X3 2
0 S1 0 0 13 1 0 2 2 2/13
0 S2 7 0 -14 0 1 -2 7 7/-14
1 X2 2/3 1 -5/3 0 0 -1/3 1 1/-5/3
Zj 2/3 1 -5/3 0 0 -1/3
Cj-Zj 4/3 0 8/3 0 0 1/3
NEW R1 NEW R2
4-6(2/3) = 0 3-(-6)(2/3) = 7
6-6(1) = 0 -6-(-6)(1) = 0
3-6(-5/3) = 13 -4-(-6)(-5/3) = -14
1-6(0) = 1 0-(-6)(0) = 0
0-6(0) = 0 1-(-6)(0) = 1
0-6(-1/3) = 2 0-(-6)(-1/3) = -2
8-6(1)= 2 1-(-6)(1) = 7
Cj 2 1 1 0 0 0 solution Min ratio
CB S1 S S3
j BV X1 X2 X3 2
1 X3 0 0 1 1/13 0 2/13 2/13 ∞
14/3 1 2/13 (109/13)/7=
0 S2 7 0 0 109/13 1.19
5/39 0 -9/117 (49/39)/(2/3)
1 X2 2/3 1 0 49/39 = 1.88
Zj 2/3 1 1 8/39 0 1/3
Cj- - 0 -1/3
Zj 4/3 0 0 8/39
R2 R3
7-(-14)(0) = 7 2/3 –(-5/3)(0) = 2/3
0-(-14)(0) = 0 1–(-5/3)(0) = 1
-14-(-14)(1) = 0 -5/3–(-5/3)(1) = 0
0-(-14)(1/13) = 14/13 0–(-5/3)(1/13) = 5/39
1-(-14)(0) = 1 0–(-5/3)(0) = 0
-2-(-14)(2/13) = 2/13 -1/3–(-5/3)(2/13) = -9/117
7-(-14)(2/13) = 109/13 1–(-5/3)(2/13) = 49/39
solutio Min
0 0 0
Cj 2 1 1 n ratio
CB S1 S2 S3
j BV X1 X2 X3
1 X3 0 0 1 1/3 0 2/13 2/13
2 X1 1 0 0 2/3 1/7 2/91 17/13
1 X2 0 1 0 -37/117 2/21 -25/273 5/13
Zj 2 1 1 2/117 8/21 17/273
Cj- -2/117 -8/21 -17/273
ZJ 0 0 0 Cj-Zj ≤ 0
R1 R3
0-0(1) =0 2/3-2/3(1) = 0
0-0(0)= 0 1-2/3(0) = 1
1-0(0) = 1 0-2/3(0) = 0
1/13-0(2/3)= 1/3 5/39-2/3(2/3) = -37/117
0-0(1/7)= 0 0-2/3(1/7)= 2/21
2/13-0(2/91)= 2/13 -9/117-2/3(2/91) = -25/273
2/13-0(17/13)= 2/13 49/39-2/3(17/13) = 5/13
X1= 17/13, X2= 5/13, X3= 2/13
Max Z = 2X1+1X2+1X3
Max Z = 2(17/13)+1(5/13)+1(2/13) = 41/13
