Big M method
||This article needs attention from an expert on the subject. (March 2011)|
In operations research, the Big M method is a method of solving linear programming problems. It is a variation of the simplex method designed for solving problems typically encompassing "greater-than" constraints as well as "less-than" constraints - where the zero vector is not a feasible solution. The "Big M" refers to a large number associated with the artificial variables, represented by the letter M.
Constructed as a series of equations and inequalities that must hold, as well as some function that is to be maximised. As with the simplex method, in the Big M method extra variables (surplus and artificial) are created to turn inequalities into equations. For example x + y < 100 becomes x + y + s1 = 100, whilst x + y > 100 becomes x + y − a1 = 100. The artificial variables must be shown to be 0. The function to be maximised is rewritten to include the sum of all the artificial variables. Then row reductions are applied to gain a final solution.
- Karush–Kuhn–Tucker conditions, which apply to Non-Linear Optimization problems with inequality constraints.
- Griva, Igor; Nash, Stephan G.; Sofer, Ariela. Linear and Nonlinear Optimization (2nd ed.). Society for Industrial Mathematics. ISBN 978-0-89871-661-0.
- Simplex – Big M Method, Lynn Killen, Dublin City University.
- The Big M Method, businessmanagementcourses.org
- The Big M Method, Mark Hutchinson