Big M method

The Big-M-Method , or M-Method for short, or more rarely the Big-M-Method , is used in linear optimization , a main method of operations research . Linear programs are mathematical systems of objective functions and constraints (restrictions) that can consist of equations and / or inequalities. In particular, the Big-M method is a generalized form of the simplex method and allows both maximization and minimization problems to be solved with all types of restrictions (relational symbols:) . ${\ displaystyle \ leq, \ geq, =}$

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

Application examples

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

Simplex method

The Big M method can modify the simplex method . If there is an optimization model with restrictions that greater than or equal -Relationszeichen contain this leads to negative slip variable ( slack variable ). This means that there is initially no starting solution and this would only have to be constructed in a preliminary phase (for phase I and II of the simplex, see also Simplex method # Mathematical description ). The Big M method combines these phases so that the Simplex can work immediately.

example

The following linear optimization problem is to be brought into a normal form that the simplex algorithm can process.

${\ displaystyle {\ begin {aligned} ZF: 4x_ {1} + 3x_ {2} & \ rightarrow max \\ NB_ {1}: x_ {1} + 3x_ {2} & \ leq 9 \\ NB_ {2} : -x_ {1} + 2x_ {2} & \ geq 2 \\ NNB: x_ {1}, x_ {2} & \ geq 0 \ end {aligned}}}$

For the two problem variables ( PV), a slip variable (SV) is first introduced for each secondary condition . The system is not yet in canonical normal form. Therefore another artificial variable (KV) is introduced. Unlike the SV, this should receive an objective function coefficient, namely a very large negative value. As a result, the KV is "punished" and should ultimately disappear or assume the value zero. ${\ displaystyle NB_ {2}}$

${\ displaystyle {\ begin {aligned} ZF: 4x_ {1} + 3x_ {2} + 0x_ {3} + 0x_ {4} -Mx_ {5} \ rightarrow max \\ NB_ {1}: + x_ {1} + 3x_ {2} + x_ {3} + 0x_ {4} + 0x_ {5} = 9 \\ NB_ {2}: \ underbrace {-x_ {1} + 2x_ {2}} _ {PV} + \ underbrace {0x_ {3} -x_ {4}} _ {SV} + \ underbrace {x_ {5}} _ {KV} = 2 \\ NNB: x_ {1}, x_ {2}, x_ {3}, x_ {4}, x_ {5} \ geq 0 \ end {aligned}}}$

Fixed cost modeling

Fixed cost problems can also be modeled using a Big-M, for example .

Example: A company produces two products in quantities that generate different revenues and are subject to certain restrictions: ${\ displaystyle P_ {1}, P_ {2}}$ ${\ displaystyle x_ {1}, x_ {2}}$

${\ displaystyle {\ begin {aligned} ZF: 4x_ {1} + 5x_ {2} \ rightarrow max \\ NB_ {1}: 2x_ {1} + 3x_ {2} \ leq 80 \\ NB_ {2}: 1x_ {1} + 5x_ {2} \ leq 80 \\ NNB: x_ {1}, x_ {2} \ geq 0 \\\ end {aligned}}}$

However, fixed costs of 10 MU should now be taken into account for product 2. These are only incurred once if the product is included in the production plan.

${\ displaystyle {\ begin {aligned} ZF: 4x_ {1} + 5x_ {2} -10y \ rightarrow max \\ NB_ {1}: 2x_ {1} + 3x_ {2} \ leq 150 \\ NB_ {2} : 1x_ {1} + 5x_ {2} \ leq 150 \\ NB_ {3}: x_ {2} \ leq 30y \ qquad y \ in {0,1} \\ NNB: x_ {1}, x_ {2} \ geq 0 \ end {aligned}}}$

In the new secondary condition 3, the relationship between the product quantity 2 and the binary variable y is secured by, where has been selected. ${\ displaystyle (0 \ leq) x \ leq M \ cdot y}$ ${\ displaystyle M = 30}$

Individual evidence

^ Wolfgang Domschke, Andreas Drexl: Introduction to Operations Research . Jumper; Edition: 8th edition 2011 (April 9, 2011). ISBN 978-3642181115 . Page 29ff.
↑ Brigitte Werners: Basics of Operations Research: With tasks and solutions . Jumper; Edition: 2nd, revised. 2008 edition (September 10, 2008). ISBN 978-3540799733 . Page 79ff.
↑ Leena Suhl, Taieb Mellouli: Optimization systems: models, processes, software, applications . Jumper; Edition: 2nd, revised. 2009 edition (June 10, 2009). ISBN 978-3642015793 . Page 100f.

Web links

Big M method - brief description
Lesson 9: The Big M Method (PDF; 373 kB) - detailed explanation with invoice (English)

[1] Wolfgang Domschke, Andreas Drexl: Introduction to Operations Research . Jumper; Edition: 8th edition 2011 (April 9, 2011). ISBN 978-3642181115 . Page 29ff.

[2] Brigitte Werners: Basics of Operations Research: With tasks and solutions . Jumper; Edition: 2nd, revised. 2008 edition (September 10, 2008). ISBN 978-3540799733 . Page 79ff.

[3] Leena Suhl, Taieb Mellouli: Optimization systems: models, processes, software, applications . Jumper; Edition: 2nd, revised. 2009 edition (June 10, 2009). ISBN 978-3642015793 . Page 100f.