Big M method

In operations research, the Big M method is a method of solving linear programming problems using the simplex algorithm. The Big M method extends the simplex algorithm to problems that contain "greater-than" constraints. 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. It is obvious that the points with the optimal objective must be reached on a vertex of the simplex which is the shape of feasible region of an LP (linear program). Points on the vertex of the simplex are represented as a basis. So, to apply the simplex algorithm which aims improve the basis until a global optima is reached, one needs to find a feasible basis first. The trivial basis (all problem variables equal to 0) is not always part of the simplex. It is feasible if and only if all the constraints (except non-negativity) are less-than constraints and with positive constant on the right-hand side. The Big M method introduces surplus and artificial variables to convert all inequalities into that form and there by extends the simplex in higher dimensions to be valid in the trivial basis.