Simplex-Methode für lineare Programmierungsprobleme

Dieses Makro findet die optimale Lösung eines linearen Programms mit Hilfe der überarbeiteten Form der Simplex-Methode. Lineare Programmierung (LP) beschäftigt sich mit einer Zielfunktion mit ausschließlich linearen Termen unter der Annahme, dass nur lineare Nebenbedingungen vorliegen.

Wenn die Anzahl der Nebenbedingungen viel kleiner als die Anzahl der Entscheidungsvariablen ist, ist die ursprüngliche Form der Simplex-Methode nicht effizient.

Die Zielfunktion kann entweder die Maximierung oder Minimierung einer mathematischen Funktion sein, z. B. die Darstellung von Gewinn oder Kosten. Die Optimierung weist normalerweise Nebenbedingungen auf, d. h., die optimale Lösung muss innerhalb bestimmter Grenzen liegen, die i. d. R. durch die Anzahl der verfügbaren Ressourcen bzw. des Budgets für ein Projekt festgelegt sind.

Herunterladen des Makros

Vergewissern Sie sich, dass Sie in Minitab den Speicherort des heruntergeladenen Makros angegeben haben. Wählen Sie Extras > Optionen > Allgemein aus. Navigieren Sie im Feld Speicherort für Makros zu dem Speicherort, an dem Sie Makrodateien ablegen.

Wichtig

Wenn Sie einen älteren Webbrowser verwenden und auf die Schaltfläche Herunterladen klicken, wird die Datei möglicherweise in Quicktime geöffnet; für dieses Programm wird dieselbe Dateinamenerweiterung „.mac“ wie für Minitab-Makros verwendet. Um das Makro zu speichern, klicken Sie mit der rechten Maustaste auf die Schaltfläche Herunterladen, und wählen Sie Ziel speichern unter aus.

Erforderliche Eingaben

  • Eine Spalte mit den Koeffizienten der Zielfunktion.
  • Spalten, die den einzelnen Elementen der Zielfunktion entsprechen, einschließlich Variablen, Gleichheitszeichen und Ergebnis. Jede Zeile in dieser Gruppe von Spalten gibt eine Nebenbedingung für die Optimierung an.

Das folgende Beispiel stammt von Hillier und Lieberman und stellt die Herstellung von zwei Produkten (x1, x2) für die Wyndor Glass Co. dar. Die drei Nebenbedingungen stellen die Fähigkeit jedes ihrer drei Werke dar, Ressourcen für die Produktion von Produkt 1 (x1) und Produkt 2 (x2) zu verwenden.

MAXIMIEREN Gewinn = 3x1 + 5x2 (Zielfunktion)

UNTER DEN BEDINGUNGEN:

x1   <= 4 (Werk 1)
  2x2 <= 12 (Werk 2)
3x1 +2x2 <= 18 (Werk 3)

x1 ≥ 0; x2 ≥ 0 (Nebenbedingung der Nicht-Negativität)

Die Koeffizienten, Gleichheitszeichen und Ergebnisse müssen wie folgt in ein Minitab-Arbeitsblatt eingegeben werden:

C1 C2 C3 C4 C5
x1 x2 Ungleichung Ergebnisse Zielstellung
1 0 <= 4 3
0 2 <= 12 5
3 2 <= 18  

Optionale Eingaben

MIN
Das Makro löst standardmäßig ein Maximierungsproblem. Wenn Sie die Zielfunktion minimieren möchten, geben Sie nach dem Hauptbefehl ein Semikolon und in der zweiten Zeile den Befehl MIN gefolgt von einem Punkt („.“) ein. Dieser kennzeichnet das Ende des Befehls.

Ausführen des Makros

Angenommen, Ihre Daten sind wie oben abgebildet angeordnet. Um das Makro auszuführen, wählen Sie Bearbeiten > Befehlszeilen-Editor aus, und geben Sie Folgendes ein:

%SIMPLEX C1-C2 C4 C5; 
INEQ C3.

Klicken Sie auf Befehle übermitteln.

Weitere Informationen

Normalerweise werden zur Formulierung des Problems n + 2 Spalten angegeben. Das letzte im Hauptbefehl eingegebene Argument entspricht der Spalte mit den Koeffizienten der Zielfunktion. Das vorletzte Argument muss eine Spalte sein, in der die rechten Seiten aller Ungleichheiten im Problem angegeben sind (mit Ausnahme von Nicht-Negativität, da dies standardmäßig angenommen wird). Die ersten n Spalten enthalten die Koeffizienten (a11, a12, ..., a1n) für alle linearen Nebenbedingungen vom Typ a11*x1 + a12*x2 + ... + a1n*xn.

Wenn schließlich alle Ungleichheiten vom Typ „<=“ sind, müssen Sie nichts tun. Geben Sie andernfalls die Symbole für alle Nebenbedingungen in einer Spalte an. Die folgenden Symbole sind zulässig: >=, >, ≥, ≤, <=, <, =.

Weitere technische Details zum Algorithmus finden Sie in:

Bazaraa, M.S., Jarvis, J.J. und Sherali, H.D. „Linear Programming and Network Flows“, Fourth Edition. John Wiley & Sons, New Jersey, 2010.

Durch Ihre Nutzung dieser Website stimmen Sie zu, dass Cookies verwendet werden. Cookies dienen zu Analysezwecken und zum Bereitstellen personalisierter Inhalte.  Lesen Sie unsere Richtlinien