Zum Inhalt
Anmelden
Alle Apps

Big M: Nebenbedingungen an- und ausschalten

Über diese App

Hilfs-Binärvariable mit großem M: Either-or (3x₁ + 2x₂ ≤ 18 oder x₁ + 4x₂ ≤ 16) als nicht-konvexe Vereinigung und Fixkosten mit Sprung. Die LP-Relaxation bläht sich mit M auf, Schranke über M logarithmisch, zu kleines M schneidet echte Lösungen ab. Mₘᵢₙ markiert, getrennte M₁/M₂, y-Schnitt, alle Werte exakt.

Mit Erklärmodus: Ein KI-Tutor führt dich durch die App, zeigt in der Szene, worauf es ankommt, und beantwortet deine Fragen.

Worum es geht

Viele Modelle sind fast lineare Programme, bis eine Ja-Nein-Bedingung dazukommt: nur eine von zwei Nebenbedingungen muss gelten, oder eine Tätigkeit verursacht Rüstkosten, sobald sie überhaupt genutzt wird. Der Trick ist eine Binärvariable y und eine große Konstante M. Die Nebenbedingung a·x ≤ b + M·y ist für y = 1 von jeder vernünftigen Lösung erfüllt, also abgeschaltet. M muss groß genug sein, um keine zulässige Lösung abzuschneiden, und sonst so klein wie möglich. Ein zu großes M macht die LP-Relaxation schwach und den Solver langsam. (Nicht zu verwechseln mit der Big-M-Methode des Simplexverfahrens, die künstliche Variablen bestraft.)

Was die App zeigt

Im Fall Either-or gilt 3x₁ + 2x₂ ≤ 18 oder x₁ + 4x₂ ≤ 16. Links stehen die beiden Teilgebiete, deren Vereinigung nicht konvex ist, darüber die LP-Relaxation als Schleier, abgeschnittene Teile schraffiert und die Optima von MIP und Relaxation. Rechts der Wert der Relaxation über M auf logarithmischer Achse: Ab M = 30 bleibt das MIP bei 16, die Relaxation wächst auf 23,5 bei M = 60 und 258,5 bei M = 1000. Im Fall Fixkosten (1000 € Rüstkosten, 20 € je Stück, Kapazität 50) zeigt die App die echte Kostenfunktion mit Sprung und die relaxierte Gerade (20 + 1000/M)·x.

Selbst ausprobieren

Zieh M in der rechten Karte von 10 bis 1000. Unter 30 fehlt ein Stück von B, und das MIP liefert ein falsches Optimum, etwa 13 statt 16 bei M = 20. Darüber bleibt das echte Gebiet gleich, nur die Relaxation bläht sich auf. Schalte auf getrennte M₁ und M₂: Mit 30 und 20 ist die Relaxation genau die konvexe Hülle beider Dreiecke. Der Regler für ein stetiges y zeigt einzelne Schnitte der Relaxation. Bei den Fixkosten wählst du die Menge x und siehst, wie stark die Relaxation die Rüstkosten unterschätzt.

Häufige Fragen

Was ist eine Big-M-Nebenbedingung?
Eine Nebenbedingung der Form a·x ≤ b + M·y mit einer Binärvariable y und einer großen Konstante M. Für y = 0 gilt die ursprüngliche Bedingung a·x ≤ b, für y = 1 ist sie so weit gelockert, dass jede vernünftige Lösung sie erfüllt. So lassen sich Entweder-oder-Bedingungen, K-aus-N-Bedingungen und Fixkosten in einem gemischt-ganzzahligen Programm ausdrücken.
Wie groß muss M gewählt werden?
M muss mindestens so groß sein wie die größte Verletzung der abgeschalteten Nebenbedingung auf den übrigen zulässigen Lösungen. Im Beispiel 3x₁ + 2x₂ ≤ 18 oder x₁ + 4x₂ ≤ 16 erreicht 3x₁ + 2x₂ auf dem zweiten Gebiet höchstens 48, also M₁ ≥ 30; umgekehrt M₂ ≥ 20. Bei Fixkosten mit x ≤ M·y genügt die größte mögliche Menge, etwa die Kapazität.
Warum schadet ein sehr großes M wie 10⁹?
Das Modell bleibt korrekt, aber die LP-Relaxation, in der y stetig zwischen 0 und 1 liegt, wird sehr schwach. Ihre Schranke liegt weit über dem echten Optimum, Branch and Bound kann kaum Äste abschneiden und braucht viel länger. Dazu kommen numerische Probleme, wenn 10⁹ neben Koeffizienten wie 0,3 steht. Ist M dagegen zu klein, schneidet das Modell zulässige Lösungen ab und liefert ein falsches Optimum.
Was kann ich in der App einstellen?
Den Fall (Either-or oder Fixkosten), ein gemeinsames M oder getrennte M₁ und M₂ zwischen 10 und 1000, einen Schnitt der Relaxation für ein stetiges y und bei den Fixkosten die Menge x. M lässt sich direkt in der rechten Karte ziehen. Das Panel Modell zeigt die Formeln mit eingesetztem M und alle Optima exakt als Brüche.

Fach: Lineare Probleme

Mehr aus Lineare Probleme

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps