Zum Inhalt springen
Zurück zu den Suchergebnissen

Simplex-Algorithmus

Eingeführt von
George Dantzig
Jahr
1947
Typ
algorithm
Familie
Optimization

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Der Simplex-Algorithmus, entwickelt von George Dantzig im Jahr 1947, ist ein grundlegender Algorithmus zur Lösung von linearen Optimierungsproblemen.

Er durchsucht systematisch die Eckpunkte des zulässigen Bereichs, um die optimale Lösung zu finden, bei der die Zielfunktion unter linearen Nebenbedingungen maximiert oder minimiert wird.

Die Intuition hinter der Methode

Die Methode funktioniert, indem sie an einem Eckpunkt des durch lineare Nebenbedingungen definierten zulässigen Bereichs beginnt und sich dann zu benachbarten Eckpunkten bewegt, die den Wert der Zielfunktion verbessern. Sie wird fortgesetzt, bis ein Eckpunkt erreicht ist, bei dem kein benachbarter Eckpunkt eine weitere Verbesserung bietet, was die Optimalität garantiert. Der Algorithmus nutzt die geometrische Eigenschaft, dass lineare Programme ihre optimalen Lösungen an den Eckpunkten des Nebenbedingungspolytops haben.

Geschichte

George Dantzig führte den Simplex-Algorithmus 1947 ein und revolutionierte damit die Operations Research. Er wurde jahrzehntelang zum Standardalgorithmus für die lineare Optimierung. Klee und Minty (1972) zeigten die exponentielle Worst-Case-Komplexität, doch empirisch blieb die Methode schnell. In den 1980er Jahren wurden Innere-Punkte-Methoden als Alternativen entwickelt, aber der Simplex-Algorithmus blieb aufgrund seiner Robustheit und der Raffinesse moderner Implementierungen für viele praktische Anwendungen dominant.

Wann wird sie eingesetzt?

Wende den Simplex-Algorithmus an, wenn lineare Optimierungsprobleme mit beschränkten zulässigen Bereichen und einer linearen Zielfunktion gelöst werden. Er ist besonders effektiv für Probleme mit Hunderten oder Tausenden von Variablen und Nebenbedingungen. Vermeide seine Anwendung, wenn das Problem nichtlinear oder unbeschränkt ist. Innere-Punkte-Methoden können für sehr große Probleme bevorzugt werden.

Grenzen und Hinweise

  • Exponentielle Worst-Case-Zeitkomplexität (obwohl in der Praxis selten)
  • Kann bei stark degenerierten Problemen schlecht abschneiden
  • Weniger wettbewerbsfähig als Innere-Punkte-Methoden bei sehr großen Problemen
  • Erfordert, dass Probleme in Standardform mit expliziter Nebenbedingungenbehandlung vorliegen

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Garantierte Ermittlung der optimalen Lösung in endlicher Zeit für lineare Programme
  • Effizient in der Praxis bei sorgfältiger Implementierung und Handhabung von Degenerationen
  • Weit verbreitet und unterstützt durch ausgereifte Optimierungsbibliotheken
  • Grundlage für das Verständnis fortgeschrittenerer Optimierungsalgorithmen

Anwendungen

  • Produktionsplanung: Optimierung von Produktionsmengen zur Minimierung von Kosten bei gleichzeitiger Erfüllung von Nachfragebeschränkungen
  • Transport und Logistik: Bestimmung optimaler Versandrouten und -mengen zwischen Lagerhäusern und Distributionszentren
  • Portfolio-Optimierung: Allokation von Kapital über verschiedene Vermögenswerte zur Maximierung der Renditen unter Berücksichtigung von Risiko- und Budgetbeschränkungen
  • Ressourcenallokation: Verteilung begrenzter Ressourcen wie Arbeitskraft und Materialien zur Maximierung des organisatorischen Outputs
  • Mischungsprobleme: Mischen von Rohstoffen in optimalen Proportionen zur Erfüllung von Qualitätsanforderungen und Minimierung der Kosten
  • Personaleinsatzplanung: Zuweisung von Mitarbeitern zu Schichten zur Minimierung der Arbeitskosten bei gleichzeitiger Erfüllung der Nachfrage

So funktioniert es

So funktioniert es

1

Konvertiere das lineare Programm in die Standardform mit Schlupfvariablen und identifiziere eine anfängliche zulässige Basislösung (üblicherweise der Ursprung, falls zulässig).

2

Führe Pivot-Operationen am Simplex-Tableau durch: Wähle eine eintretende Variable mit negativem reduzierten Kostenwert, identifiziere die austretende Variable mittels des Minimum-Quotienten-Tests und aktualisiere die Basis.

3

Überprüfe die Optimalitätsbedingungen anhand der reduzierten Kosten; wenn alle reduzierten Kosten für eine Maximierung nicht-negativ sind, ist die aktuelle Lösung optimal; andernfalls kehre zum Pivot-Schritt zurück.

Häufige Fallstricke

  • Fehlende korrekte Handhabung von Zyklen bei degenerierten Basen (Verwendung der Bland'schen Regel oder Perturbationsmethoden)
  • Falsche Pivot-Auswahl oder arithmetische Fehler bei Tableau-Aktualisierungen, die zu numerischer Instabilität führen
  • Nichtprüfung auf Unbeschränktheit oder Unzulässigkeit vor Beginn des Algorithmus

Häufig gestellte Fragen

Warum heißt der Simplex-Algorithmus 'Simplex'?

Der Begriff 'Simplex' bezieht sich auf die einfachste Form eines Polyeders in einer gegebenen Dimension. Der Algorithmus bewegt sich entlang der Kanten und Eckpunkte des durch die Nebenbedingungen definierten Polyeders.

Was ist der Unterschied zwischen dem Simplex-Algorithmus und der Innere-Punkte-Methode?

Der Simplex-Algorithmus verbleibt an den Eckpunkten an der Grenze des zulässigen Bereichs, während Innere-Punkte-Methoden durch das Innere traversieren. Innere-Punkte-Methoden haben eine bessere Worst-Case-Komplexität, aber der Simplex-Algorithmus ist in der Praxis für mittelgroße Probleme oft schneller.

Wie geht man mit Unzulässigkeit oder Unbeschränktheit um?

Verwende die Zwei-Phasen-Simplex-Methode: Phase eins löst ein Hilfsproblem, um eine zulässige Basislösung zu finden oder Unzulässigkeit festzustellen; Phase zwei wendet den Standard-Simplex-Algorithmus auf das ursprüngliche Problem an.

Was ist Degeneration und warum ist sie wichtig?

Degeneration tritt auf, wenn eine zulässige Basislösung mehr als eine Basisdarstellung hat, was zu Zyklen führen kann. Behandle sie mit der Bland'schen Regel (Auswahl von Variablen nach Indexreihenfolge) oder Perturbationsmethoden.

Verwandte Methoden

Quellen

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.

    DOI-Referenz öffnen
    Kopiert.
  2. Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.

    DOI-Referenz öffnen
    Kopiert.