Big M Method

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)

Big M Method

Uploaded by

Copyright:

Available Formats

Big M Method

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Big M Method

Uploaded by

Copyright:

Available Formats

BIG M METHOD

In operations research, the Big M method is a method of

The Big M method extends the simplex algorithm to problems that

If the problem is of minimization, transform to maximization by multiplying the objective by −1

Solve the problem using the usual simplex method.

Basis Variables Cj 1 5 0 0 -M Minimum

S1 0 10/3 5/3 0 1 ( 4/3) 10/4 = 5/2

Iteration 2 Zj = CB 5/3 5 0 -5/3

S2 0 5/2 5/4 0 3/4 1

Iteration 3 Zj = CB 15/4 5 5/4 0

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

The advantage to Big M method is that the problem is

With the two phase method, there’s no guarantee of the

By(Speakers):- Harshit Tahlani (149)

You might also like