Simplex Method

The Big M Method

It is a modified version of the simplex method, in which we assign a very large value (M) to each of the artificial variables. We illustrate this method with the help of following examples.

Example 1

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

Table 1

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

Table 3

The optimal solution is:

x₁ = 0, x₂ = 3/2
z = 0 + 5 X 3/2 =15/2