BIG M METHOD
Group 2
WHAT IS BIG M METHOD ?
In operations research, the Big M method is a method of
solving linear programming problems using the simplex algorithm.
The Big M method extends the simplex algorithm to problems that
contain "greater-than" constraints. It does so by associating the
constraints with large negative constants which would not be part of
any optimal solution, if it exists.
SPECIAL VARIABLES
Slack variable: It is used o convert a Less than or equal to (≤) constraint into equality to
write standard form. It is ADDED to ≤ constraint.
E. g. 2×1 + 4×2 ≤ 40 will become 2×1 + 4×2 + S1 = 40. Where, S1 is slack variable.
Surplus & Artificial variables: They are used to convert Greater than or equal to (≥)
constraint into equality to write standard form. Surplus variable is SUBTRACTED from
≥ constraint and Artificial variable is ADDED to the ≥ constraint.
ALGORITHM
Multiply the inequality constraints to ensure that the right hand side is positive.
If the problem is of minimization, transform to maximization by multiplying the objective by −1
For any greater-than constraints, introduce surplus and artificial variables (as shown below)
Choose a large positive Value M and introduce a term in the objective of the form −M
multiplying the artificial variables
For less-than or equal constraints, introduce slack variables so that all constraints are equalities
Solve the problem using the usual simplex method.
Illustration
Suppose we want to maximize a function say,
Maximize Z = x1 + 5x2
Subject to the following constraints:-
1. 3x1 + 4x2 ≤ 6
2. x1 + 3x2 ≥ 2
Solution :
Converting the constraints to standard form by introducing surplus variables, slack variables and artificial variables.
Max Z = x1 + 5x2 + 0.S1 + 0.S2 – MA1
Subject to
where,
I. 3x1 + 4x2 + S1 = 6
S1 is a slack variable
II. x1 + 3x2 – S2 + A1 = 2
S2 is a surplus variable
A1 is an artificial variable.
x1 ≥ 0, x2 ≥ 0, S1 ≥ 0, S2 ≥ 0, A1≥ 0.
We find by substituting X1 and X2 =0 in the constraints , S1=6 ; S2 = -2. But S1 and S2 should be non negative numbers.
Therefore, to solve this and get a starting basic feasible solution, we introduce Artificial variable A1 wherever there is ‘ ≥ ’ or
‘ = ‘ in the constraints. However, these artificial variables should not appear in the final solution, so they are assigned a
Simplex table format
Basis Variables Cj 1 5 0 0 -M Minimum
Ratio
CB XB X1 X2 S1 S2 A1
S1 0 6 3 4 1 0 0
A1 -M 2 1 3 0 -1 1
Zj = CB -M -3M 0 M -M
j = Zj - Cj -M-1 -3M-5 0 M 0
Basis Variables Cj 1 5 0 0 -M Minimum
Ratio
CB XB X1 X2 S1 S2 A1
S1 0 6 3 4 1 0 0 6/4 = 1.5
A1 -M 2 1 (3) 0 -1 1 2/3 = .67
Zj = CB -M -3M 0 M -M
j = Zj - Cj -M-1 -3M-5 0 M 0
As M is a very large positive number, the coefficient of M in the Z j–Cj row would decide the incoming vector.
As -3M < -M, X2 becomes the incoming variable.
And the Variable with the lowest ratio will be the outgoing vector i.e. A 1.
Basis Variables Cj 1 5 0 0 Minimum
Ratio
CB XB X1 X2 S1 S2
S1 0 10/3 5/3 0 1 ( 4/3) 10/4 = 5/2
X2 5 2/3 ----
1/3 1 0 -1/3
Iteration 2 Zj = CB 5/3 5 0 -5/3
j = Zj - Cj 2/3 0 0 -5/3
Basis Variables Cj 1 5 0 0 Minimum
Ratio
CB XB X1 X2 S1 S2
S2 0 5/2 5/4 0 3/4 1
X2 5 3/2 3/4 1 1/4 0
Iteration 3 Zj = CB 15/4 5 5/4 0
j = Zj - C j 11/4 0 5/4 0
As all the j = Zj - Cj ≥ 0 , the solution is optimal.
X1 = 0
X2 = 3/2
The final optimal solution is :-
Max Z = x1 + 5x2
= 0 + 5. (3/2)
Drawbacks
Four drawbacks of BIG-M method:
1. How large should M be?
2.If M is too large, serious numerical difficulties in a computer
3.Big-M method is inferior than 2 phase method
4.Here feasibility is not known until optimality
ADVANTAGE
The advantage to Big M method is that the problem is
solved in just one single phase.
With the two phase method, there’s no guarantee of the
quality of the initial solution to Phase Two as the original
objective is not considered at all in Phase One.
THANK YOU
By(Speakers):- Harshit Tahlani (149)
Yash Bhushan Aggarwal (108)
Binit Agarwal (31)
Richa Tantia (82)
