Big-M-Methode

Die Big-M-Methode, kurz M-Methode oder seltener Groß-M-Methode, wird in der linearen Optimierung, einem Hauptverfahren des Operations Research, angewandt. Lineare Programme sind mathematische Systeme von Zielfunktionen und Nebenbedingungen (Restriktionen), die aus Gleichungen und/oder Ungleichungen bestehen können. Insbesondere ist die Big-M-Methode eine generalisierte Form des Simplex-Verfahrens und erlaubt es sowohl Maximierungs- und Minimierungsprobleme zu lösen und zwar mit allen Typen von Restriktionen (Relationszeichen: $\leq ,\geq ,=$).

Big-M steht zunächst für eine „hinreichend große Zahl“. Ihr genauer Wert hängt von der konkreten Aufgabenstellung ab.

Anwendungsbeispiele

Die folgenden Beispiele zeigen, dass ein Big-M sowohl als abstrakter Wert in die Zielfunktion oder auch als konkrete Ausprägung in das System der Nebenbedingungen integriert werden kann.

Simplex-Verfahren

Die Big-M-Methode kann das Simplex-Verfahren modifizieren. Liegt ein Optimierungsmodell mit Restriktionen vor, die größer-gleich-Relationszeichen enthalten führt dies zu negativen Schlupfvariablen (slack variable). Das bedeutet, dass zunächst keine Startlösung vorliegt und diese erst in einer Vorphase konstruiert werden müsste (für Phase I und II des Simplex siehe auch Simplex-Verfahren#Mathematische Beschreibung). Die Big-M-Methode fasst diese Phasen zusammen, sodass der Simplex sofort arbeiten kann.

Beispiel

Folgendes lineares Optimierungsproblem soll in eine Normalform gebracht werden, die der Simplex-Algorithmus verarbeiten kann.

${\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}}$

Zu den beiden Problemvariablen (PV) wird zunächst pro Nebenbedingung eine Schlupfvariable (SV) eingeführt. Das System liegt aber noch nicht in kanonischer Normalform vor. Deshalb wird für $NB_{2}$ eine weitere künstliche Variable (KV) eingeführt. Anders als die SV soll diese einen Zielfunktionskoeffizienten erhalten und zwar einen sehr großen negativen Wert. Dadurch wird die KV „bestraft“ und soll letztlich verschwinden bzw. den Wert null annehmen.

${\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}}$

Fixkostenmodellierung

Durch ein Big-M können beispielsweise auch Fixkostenprobleme modelliert werden.

• Beispiel: Ein Unternehmen produziert zwei Produkte $P_{1},P_{2}$ in dem Mengen $x_{1},x_{2}$ die verschiedene Erlöse erzielen und gewissen Restriktionen unterliegen:

${\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}}$

Allerdings sollen bei Produkt 2 nun Fixkosten in Höhe von 10 GE berücksichtigt werden. Diese fallen einmalig nur an, falls das Produkt in den Produktionsplan aufgenommen wird.

${\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 der neuen Nebenbedingung 3 wird der Zusammenhang der Produktmenge 2 und der binären Variable y durch $(0\leq )x\leq M\cdot y$ gesichert, wobei $M=30$ gewählt wurde.

Weblinks

• Big-M-Methode – Kurzbeschreibung
• Lesson 9 : The Big M Method (PDF; 373 kB) – ausführliche Erklärung mit Rechnung (englisch)