Die Big-M-Methode, kurz M-Methode[1] oder seltener Groß-M-Methode[2], 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: ).

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

Anwendungsbeispiele

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

 

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   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.

 

Fixkostenmodellierung

Bearbeiten

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

  • Beispiel: Ein Unternehmen produziert zwei Produkte   in dem Mengen   die verschiedene Erlöse erzielen und gewissen Restriktionen unterliegen:

 

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.

 

In der neuen Nebenbedingung 3 wird der Zusammenhang der Produktmenge 2 und der binären Variable y durch   gesichert, wobei   gewählt wurde.

Einzelnachweise

Bearbeiten
  1. Wolfgang Domschke, Andreas Drexl: Einführung in Operations Research. Springer; Auflage: 8. Aufl. 2011 (9. April 2011). ISBN 978-3-642-18111-5. Seite 29ff.
  2. Brigitte Werners: Grundlagen Des Operations Research: Mit Aufgaben und Lösungen. Springer; Auflage: 2., überarb. Aufl. 2008 (10. September 2008). ISBN 978-3-540-79973-3. Seite 79ff.
  3. Leena Suhl, Taieb Mellouli: Optimierungssysteme: Modelle, Verfahren, Software, Anwendungen. Springer; Auflage: 2., überarb. Aufl. 2009 (10. Juni 2009). ISBN 978-3-642-01579-3. Seite 100f.
Bearbeiten