Interview Questions

Linear Programming: Simplex Method

BIG M METHOD

So far, we have seen the linear programming constraints with less than type. We come across problems with ‘greater than’ and ‘equal to’ type also. Each of these types must be converted as equations. In case of ‘greater than’ type, the constraints are rewritten with a negative surplus variable s1 and by adding an artificial variable a.

Artificial variables are simply used for finding the initial basic solutions and are thereafter eliminated. In case of an ‘equal to’ constraint, just add the artificial variable to the constraint. The co-efficient of artificial variables a1, a2,….. are represented by a very high value M, and hence the method is known as BIG-M Method.

Example : Solve the following LPP using Big M Method.

Minimize Z = 3x1 + x2
Subject to constraints
4x1 + x2 = 4               ....................(i)
5x1 + 3x2 ≥ 7             ....................(ii)
3x1 + 2x2 ≤ 6             ....................(iii)
where x1 , x2 ≥0

Solution: Introduce slack and auxiliary variables to represent in the standard form. Constraint 4x1 + x2 = 4 is introduced by adding an artificial variable a1, i.e., 4x1 + x2 + a1 = 4 Constraint, 5x1 + 3x2 ≥ 7 is converted by subtracting a slack s1 and adding an auxiliary variable a2.

5x1+ 3x2 – s1 + a2 = 7

Constraint 3x2 + 2x2 ≤ 6 is included with a slack variable s2

3x2 + 2x2 + s2 = 6

The objective must also be altered if auxiliary variables exist. If the objective function is minimization, the co-efficient of auxiliary variable is +M (and -M, in case of maximization)

The objective function is minimization,

Minimize Z = 3x1+ x2 + 0s1+ 0s2+ Ma1+ Ma2

zmin = 3x1 + x2+ Ma1+ Ma2

The initial feasible solution is (Put x1, x2, s1 = 0)

a1 = 4
a2 = 7
s2 = 6

Establish a table as shown below and solve:

Simplex Table

The solution is,

x1 = 5/7 or 0.71
x2 = 8/7 or 1.14
zmin = 3 x 5 / 7 + 8/7
= 23/7 or 3.29


Pragna Meter
Next Chapter  
e-University Search
Related Jobs