Big M Method : Linear Programming

The big m method is a modified version of the simplex method in linear programming (LP) in which we assign a very large value (M) to each of the artificial variables.

We will illustrate this method with the help of following examples.

Big M Method Example: LPP

Maximize z = x₁ + 5x₂

subject to

3x₁ + 4x₂ ≤ 6
x₁ + 3x₂ ≥ 2

x₁, x₂ ≥ 0

Solution.

Converting inequalities to equalities

By introducing surplus variables, slack variables and artificial variables, the standard form of LPP becomes

Maximize x₁ + 5x₂+ 0x₃+ 0x₄– MA₁

subject to

3x₁ + 4x₂+ x₃= 6
x₁ + 3x₂ – x₄+ A₁ = 2

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0, A₁ ≥ 0

Where:
x₃ is a slack variable
x₄ is a surplus variable.
A₁ is an artificial variable.

Initial basic feasible solution

x₁ = x₂ = x₄ = 0
A₁ = 2, x₃ = 6

The Big M Method: Table 1

On small screens, scroll horizontally to view full calculation

Calculating values for index row (z_j– c_j)

z₁– c₁ = 0 X 3 + (–M) X 1 – 1 = –M – 1
z₂– c₂ = 0 X 4 + (–M) X 3 – 5 = –3M – 5
z₃– c₃ = 0 X 1 + (–M) X 0 – 0 = 0
z₄– c₄ = 0 X 0 + (–M) X (–1) – 0 = M
z₅– c₅ = 0 X 0 + (–M) X 1 – (–M) = 0

As M is a large positive number, the coefficient of M in the z_j–c_j row would decide the incoming basic variable.
As -3M < -M, x₂ becomes a basic variable in the next iteration.
Key column = x₂ column.
Minimum (6/4, 2/3) = 2/3
Key row = A1 row
Pivot element = 3.
A1 departs and x₂enters.

Note that in the iteration just completed, artificial variable A₁ was eliminated from the basis. The new solution is shown in the following table.

Table 2