Big M method

It does so by associating the constraints with large negative constants which would not be part of any optimal solution, if it exists.

The simplex algorithm is the original and still one of the most widely used methods for solving linear maximization problems.

The Big M method introduces surplus and artificial variables to convert all inequalities into that form.

The "Big M" refers to a large number associated with the artificial variables, represented by the letter M. The steps in the algorithm are as follows: For example, x + y ≤  100 becomes x + y + s1 = 100, whilst x + y ≥ 100 becomes x + y − s1 + a1 = 100.

The value of M must be chosen sufficiently large so that the artificial variable would not be part of any feasible solution.

For a sufficiently large M, the optimal solution contains any artificial variables in the basis (i.e. positive values) if and only if the problem is not feasible.