Was ist Simplex-Methode?
Die Simplex-Methode ist in der mathematischen Optimierung ein bekannter Algorithmus, der für die lineare Programmierung verwendet wird. Laut der Zeitschrift Computing in Science & Engineering gilt diese Methode als einer der Top-10-Algorithmen, die während des zwanzigsten Jahrhunderts entstanden.
Die Simplex-Methode präsentiert eine organisierte Strategie zur Bewertung der Eckpunkte einer realisierbaren Region. Dies hilft, den optimalen Wert der Zielfunktion herauszufinden.
George Dantzig entwickelte 1946 die Simplex-Methode. Die Methode wird auch als Simplex-Algorithmus bezeichnet.
Die Simplex-Methode wird verwendet, um die Probleme in der linearen Programmierung zu beseitigen. Er prüft die benachbarten Knoten der machbaren Menge in der Reihenfolge, um sicherzustellen, dass die Zielfunktion an jedem neuen Knoten erhöht oder nicht beeinflusst wird.
Im Allgemeinen ist die Simplex-Methode extrem leistungsfähig, was normalerweise höchstens 2 m bis 3 m Iterationen erfordert (hier bezeichnet m den Bereich der Gleichheitsbedingungen), und sie konvergiert in der erwarteten Polynomzeit für spezifische Verteilungen von Zufallseingaben.
Die Simplex-Methode verwendet eine systematische Strategie zum Erstellen und Testen von Kandidaten-Vertex-Lösungen für ein lineares Programm. Bei jeder Iteration wählt es die Variable aus, die die größte Änderung gegenüber der minimalen Lösung vornehmen kann. Diese Variable ersetzt dann eine ihrer Kovariablen, was sie drastisch einschränkt, wodurch die Simplex-Methode auf einen anderen Teil der Lösungsmenge und auf die endgültige Lösung verschoben wird.
Außerdem kann die Simplex-Methode auswerten, ob tatsächlich keine Lösung existiert. Es kann beobachtet werden, dass der Algorithmus gierig ist, da er sich bei jeder Iteration für die beste Option entscheidet, ohne dass Informationen von früheren oder bevorstehenden Iterationen benötigt werden.
Manchmal wird die Hauptdatenstruktur, die durch die Simplex-Methode angewendet wird, als ein Wörterbuch bezeichnet. Wörterbücher enthalten eine Illustration der Gleichungen, die richtig auf die vorhandene Basis abgestimmt sind. Wörterbücher können verwendet werden, um ein intuitives Verständnis dafür zu liefern, warum alle Variablen die Basis betreten und verlassen.