Big M method

The Big -M method, short M- method or rare large -M method in linear programming, a main method of operations research, applied. Linear programs are mathematical systems of objective functions and constraints ( restrictions ) which may consist of equations and / or inequalities. In particular, the Big -M method is a generalized form of the simplex method and allows to solve both maximization and minimization problems, and indeed with all types of restrictions ( relation symbol: ).

Big- M is initially for a " sufficiently large number ." Its exact value depends on the specific task.

Application Examples

The following examples show that a Big -M can be integrated as an abstract value in the objective function or as a concrete expression in the system of constraints.

Simplex method

Big -M method can modify the simplex method. If an optimization model with constraints are present that contain greater than or equal Relations mark this leads to negative slack variables ( surplus variable ). This means that initially there is no starting solution, and this would have to be constructed only in a preliminary phase ( Phase I and II of the Simplex see also Simplex Method # Mathematische_Beschreibung ). The Big -M method summarizes these stages, so that the simplex can work immediately.

Example

The following linear optimization problem is to be placed in a normal form, which can process the simplex algorithm.

The two problem variables (PV ) is a slack variable ( SV) is first introduced per constraint. However, the system is not yet available in canonical normal form. Therefore introduced an additional artificial variable (CV). Unlike the SV should get this one objective function coefficients and that a very large negative value. This is the KV "punished" and will ultimately disappear or take the value zero.

Fixed cost modeling

Through a Big -M also fixed problems may for example be modeled.

• Example: A company produces two products in the quantities to achieve the various revenues and are subject to certain restrictions:

However, to be considered in product 2 is now fixed in the amount of 10 GE. This one-time charge only if the product is taken in the production plan.

In the new constraint 3, the relationship of the amount of product 2 and the binary variable y is secured by, was being selected.