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.

Maximize z = x_{1} + 5x_{2}

subject to

3x_{1} + 4x_{2} ≤ 6

x_{1} + 3x_{2} ≥ 2

x_{1}, x_{2} ≥ 0

Solution.

Converting inequalities to equalities

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

Maximize x_{1} + 5x_{2 }+ 0x_{3 }+ 0x_{4 }– MA_{1}

subject to

3x_{1} + 4x_{2 }+ x_{3 }= 6

x_{1} + 3x_{2} – x_{4 }+ A_{1} = 2

x_{1} ≥ 0, x_{2} ≥
0, x_{3} ≥ 0, x_{4} ≥ 0, A_{1} ≥
0

Where:

x_{3} is a slack variable

x_{4} is a surplus variable.

A_{1} is an artificial variable.

Initial basic feasible solution

x_{1} = x_{2} = x_{4} = 0

A_{1} = 2, x_{3} = 6

Calculating
values for index row (z_{j }– c_{j})

z_{1 }– c_{1} = 0 X 3 + (–M) X 1 – 1
= –M – 1

z_{2 }– c_{2} = 0 X 4 + (–M) X 3 – 5
= –3M – 5

z_{3 }– c_{3} = 0 X 1 + (–M) X 0 –
0 = 0

z_{4 }– c_{4} = 0 X 0 + (–M) X (–1) –
0 = M

z_{5 }– c_{5} = 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_{2} becomes a basic variable in the next
iteration.

Key column = x_{2} column.

Minimum (6/4, 2/3) = 2/3

Key row = A1 row

Pivot element = 3.

A1 departs and x_{2 }enters.

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

Table 2

c_{j} |
1 | 5 | 0 | 0 | ||
---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1} |
x_{2} |
x_{3} |
x_{4} |
Solution values b (= X _{B}) |

0 | x_{3} |
5/3 | 0 | 1 | 4/3 | 10/3 |

5 | x_{2} |
1/3 | 1 | 0 | –1/3 | 2/3 |

z_{j}–c_{j} |
2/3 | 0 | 0 | –5/3 |

c_{j} |
1 | 5 | 0 | 0 | ||
---|---|---|---|---|---|---|

c_{B} |
Basic variables B |
x_{1} |
x_{2} |
x_{3} |
x_{4} |
Solution values b (= X _{B}) |

0 | x_{4} |
5/4 | 0 | 3/4 | 1 | 5/2 |

5 | x_{2} |
3/4 | 1 | 1/4 | 0 | 3/2 |

z_{j}–c_{j} |
11/4 | 0 | 5/4 | 0 |

The optimal solution is:

x_{1} = 0, x_{2 }= 3/2

z = 0 + 5 X 3/2 =15/2