# 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.

Example 1, Example 2

## Big M Method Example: LPP

Maximize z = x1 + 5x2

subject to

3x1 + 4x2 ≤ 6
x1 + 3x2 ≥ 2

x1, x2 ≥ 0

Solution.

Converting inequalities to equalities

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

Maximize x1 + 5x2 + 0x3 + 0x4 – MA1

subject to

3x1 + 4x2 + x3 = 6
x1 + 3x2 – x4 + A1 = 2

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, A1 ≥ 0

Where:
x3 is a slack variable
x4 is a surplus variable.
A1 is an artificial variable.

Initial basic feasible solution

x1 = x2 = x4 = 0
A1 = 2, x3 = 6

### The Big M Method: Table 1

On small screens, scroll horizontally to view full calculation

Calculating values for index row (zj – cj)

z1 – c1 = 0 X 3 + (–M) X 1 – 1 = –M – 1
z2 – c2 = 0 X 4 + (–M) X 3 – 5 = –3M – 5
z3 – c3 = 0 X 1 + (–M) X 0 – 0 = 0
z4 – c4 = 0 X 0 + (–M) X (–1) – 0 = M
z5 – c5 = 0 X 0 + (–M) X 1 – (–M) = 0

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

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

Table 2

cj 1 5 0 0
cB Basic variables
B
x1 x2 x3 x4 Solution values
b (= XB)
0 x3 5/3 0 1 4/3 10/3
5 x2 1/3 1 0 –1/3 2/3
zj–cj   2/3 0 0 –5/3

#### Final Optimal Table: The Big M Method

Use Horizontal Scrollbar to View Full Table Calculation

cj 1 5 0 0
cB Basic variables
B
x1 x2 x3 x4 Solution values
b (= XB)
0 x4 5/4 0 3/4 1 5/2
5 x2 3/4 1 1/4 0 3/2
zj–cj   11/4 0 5/4 0

The optimal solution is:

x1 = 0, x2 = 3/2
z = 0 + 5 X 3/2 =15/2