Page 68 - DCOM303_DMGT504_OPERATION_RESEARCH
P. 68
Unit 3: Linear Programming Problem – Simplex Method
3.2 Big 'M' Method Notes
When the Linear Programming problem has greater than or equal to types of equations as
constraints, it is obvious that some quantity should be deducted to convert them into equalities.
The variables attached to it are known as 'surplus variables'. If the inequality is of the type
greater than or equal to then add surplus variables which carry a negative sign and their cost
coefficients in the objective function would be zero. As they would be considering slack or
artificial variables initially as basic variables, and as the surplus variables carry negative signs,
they represent vectors of identify matrix of the form,
1 0 0
0 1 0 , etc.,
0 0 1
which cannot be taken into the basis. Hence, artificial variables along with the surplus variables
would be added.
These artificial variables carry large negative values (-m) in the objective function. The artificial
variables can also be added to the equation. This helps in choosing the initial variable or
variables for the basis. The slack variables then would go to the basis whose cost coefficients are
supposed to be zero (0) and the cost coefficients of artificial variables are supposed to be -M for
maximization cases and +M for Minimization cases. The procedure for iteration follows when
Simplex technique to obtain the optimum solution is used. Since the method involves artificial
variables carrying -M as the cost coefficient, where M is a very large number which helps in the
optimum solution finding and hence it is known as 'Big M Method'.
Steps:
1. Express the problem in the standard form by using slack, surplus and artificial variables.
2. Select slack variables and artificial variables as the initial basic variables with the cost
coefficients as '0' or '-M' respectively.
3. Use simplex procedure for iterations & obtain optimum solution. During the iterations,
one can notice that the artificial variables leave the basis first and then the slack variables
with improved value of objective function at each iteration to obtain the optimum solution.
Example:
Minimise ‘Z’ = 4x + 8x + 3x [Subject to constraints]
1 2 3
x + x 2
1 2
2x + x 5
1 3
Where, x , x 0 [Non-negativity constraints]
1 2
Solution:
Step 1: Conversion of minimization case into maximisation case.
Therefore, ‘Z’ = – 4x – 8x – 3x [Subject to constraints]
1 2 3
Step 2: Conversion of inequalities into equalities adding slack variables and artificial variables.
– x + x – x + x = 2
1 2 4 6
2x + x – x + x = 5
1 3 5 7
Where, x and x are surplus variables, x and x are artificial variables.
4 5 6 7
LOVELY PROFESSIONAL UNIVERSITY 63
