Simplex-Algorithmus

Rechenverfahren der linearen Programmierung. Ausgangsbasis ist ein mathematisches Problem, das eine Entscheidungssituation abbildet. Eine lineare Zielfunktion ist unter Beachtung von Restriktionen sowie von Nichtnegativitätsbedingungen zu maximieren.            


           


           


        


           


           


Die allgemeine Lösung des Entscheidungsproblems mit Hilfe des S. nutzt die Erkenntnis, daß die optimale Lösung des Problems der linearen Programmierung in einem Eckpunkt des zulässigen Lösungsraumes liegt, indem sog. Basis-Lösungen konstruiert werden, die jeweils in den Eckpunkten des Lösungsraumes liegen. Ausgehend vom Koordinatenursprung wird in mehreren Rechenschritten (Iterationen) die Basislösung gesucht, die die Zielfunktion maximiert. Das Verfahren kann aus Platzgründen hier nicht beschrieben werden. Dieses heißt S. Der Name stammt von einer geometrischen Interpretation des Algorithmus, in der spezielle Teilmengen des IRn auftreten, die Simplices (oder Simplexe) heißen. Hier ist lediglich ein Flußdiagramm angegeben (s. Abb.) mit einem Simplex-Algorithmus zur Lösung eines linearen Maximumproblems, dessen Normalform eine zulässige kanonische Form des Problems ist.