previous: Naive Methode up: Der Simplex-Algorithmus next: Das Simplextableau

Der Algorithmus  

Eine zulässige Basislösung läßt sich sofort aus unserem linearen Gleichungssystem ablesen:

$x_1=0$, $x_2=0$, $s_1=100$, $s_2=80$ und $s_3=40$,

d.h. der Punkt $(0,0;100,80,40)$.

Die Idee des  Simplex-Algorithmus ist es nun, von dieser zulässigen Basislösung ausgehend durch geeignetes Umformen des Gleichungssystems von Eckpunkt zu Eckpunkt voranzuschreiten, wobei

• wir eine neue zulässige Basislösung leicht abgelesen können,
• der Wert der Zielfunktion verbessert wird,
• wir Überprüfen können, ob das Optimum erreicht ist, und
• das Verfahren nicht zu langsam ist.