Big-M-Methode

Damit der Simplex-Algorithmus arbeiten kann, muss er am Anfang eine Startecke bestimmen. Gerade bei praxisrelevanten Problemen ist dies aber nicht immer so einfach umsetzbar, da das Problem nicht in kanonischer Form vorliegt. Deshalb gibt es verschiedene Möglichkeiten, wie eine Startecke konstruiert werden kann. Einer dieser Möglichkeiten ist die Big-M-Methode.

Die Big-M-Methode basiert auf der Phase-I Methode. Unter anderem ist bei der Phase-1-Methode problematisch, dass die Generierung der Startecke in der sogenannten Phase-1 stattfindet, während die Lösung des Problems dann erst separat in der sogenannten Phase-2 erfolgt. Genau hier setzt die Big-M-Methode an. Die Big-M-Methode unterscheidet nämlich nicht mehr zwischen Phase I und Phase II, sondern verfolgt den Ansatz der „Bestrafung“ des Wert der originalen Zielfunktion in seinem Hilfsproblem mit den Wert von künstlichen Variablen. Deshalb spricht man im Zusammenhang mit der Big-M-Methode auch von einem Straftermverfahren mit Straftermparameter M. Die Idee hinter der Big-M-Methode ist die Anwendung des primalen Simplex-Algorithmus auf ein Hilfsproblem mit bekannter Basislösung. Dies geschieht so lange, bis eine zulässige Basislösung für das Ausgangsproblem erreicht ist. Diese Basislösung wird dann mit dem primalen Simplex-Verfahren noch optimiert.

Vorgehen bei der Big-M-Methode

Anbei wie man bei der Big-M-Methode vorgeht:

  1. Bringe das Problem in Normalform
  2. Addiere die Hilfsvariablen yi zu allen Gleichungen ohne positiven Schlupf
  3. Erweitere die Zielkooeffizienten in den Spalten der yi mit -Myi
  4. Führe Primalen Simplex auf das dieses erweiterte Tableaut aus, bis die Hilfsvariablen alle die Basis verlassen haben -> zulässige Basislösung
  5. Führe nun Primaler Simplex-Algorithmus auf die gefundene Basislösung aus