Inhaltsverzeichnis:
Definition - Was bedeutet Simplex-Methode?
Die Simplex-Methode ist in der mathematischen Optimierung ein bekannter Algorithmus für die lineare Programmierung. Laut der Fachzeitschrift Computing in Science & Engineering gilt diese Methode als einer der zehn wichtigsten Algorithmen, die im 20. Jahrhundert entwickelt wurden.
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.
Das Verfahren ist auch als Simplex-Algorithmus bekannt.
Techopedia erklärt die Simplex-Methode
Die Simplex-Methode wird verwendet, um die Probleme bei der linearen Programmierung zu beseitigen. Dabei werden die benachbarten Scheitelpunkte der realisierbaren Menge nacheinander untersucht, um sicherzustellen, dass bei jedem neuen Scheitelpunkt die Zielfunktion zunimmt oder nicht beeinträchtigt wird. Im Allgemeinen ist die Simplex-Methode äußerst leistungsfähig. Sie benötigt in der Regel höchstens 2 bis 3 m Iterationen (hier bezeichnet m den Bereich der Gleichheitsbeschränkungen) und konvergiert in der erwarteten Polynomzeit für bestimmte Verteilungen der Zufallseingabe.
Die Simplex-Methode verwendet eine systematische Strategie, um mögliche Vertex-Lösungen für ein lineares Programm zu generieren und zu testen. Bei jeder Iteration wird die Variable ausgewählt, die die größte Änderung in Richtung der minimalen Lösung vornehmen kann. Diese Variable ersetzt dann eine ihrer Kovariablen, was sie am drastischsten einschränkt, wodurch die Simplex-Methode auf einen anderen Teil des Lösungssatzes und in Richtung der endgültigen Lösung verschoben wird.
Darüber hinaus kann mit der Simplex-Methode beurteilt werden, ob tatsächlich keine Lösung vorliegt. Es kann beobachtet werden, dass der Algorithmus gierig ist, da er sich bei jeder Iteration für die beste Option entscheidet, ohne dass Informationen aus früheren oder bevorstehenden Iterationen angefordert werden.
Manchmal wird die von der Simplex-Methode angewendete Hauptdatenstruktur als Wörterbuch bezeichnet. Wörterbücher enthalten eine Illustration der Gleichungen, die auf die vorhandene Basis abgestimmt sind. Mit Hilfe von Wörterbüchern können Sie intuitiv nachvollziehen, warum alle Variablen in die Basis eingehen und diese verlassen.
