Simplex-Verfahren und Dualität

Mit drei Unbekannten liegt der Bereich im Raum und ist ein Vielflach mit Ecken, Kanten und Flächen. Bei vier oder mehr Unbekannten kannst du ihn nicht mehr zeichnen. Echte Aufgaben haben tausende oder Millionen Unbekannte. Trotzdem gilt das Eckenprinzip weiter, und darauf baut das Simplex-Verfahren auf. Es läuft von Ecke zu Ecke:

1. Starte in einer Ecke, zum Beispiel im Ursprung.
2. Prüfe die benachbarten Ecken, die über eine Kante erreichbar sind. Gibt es eine, in der die Zielfunktion größer ist, gehe dorthin.
3. Wiederhole Schritt 2. Gibt es keine bessere Nachbarecke, bist du fertig. Weil der Bereich keine „Dellen“ hat (er ist konvex: Die Verbindungsstrecke zweier Punkte des Bereichs bleibt im Bereich), ist diese Ecke schon das Optimum.

Das Verfahren wählt dabei oft die Kante mit dem größten Zuwachs je Einheit. Im Beispiel ist das die $y$-Richtung mit 50 € je Tisch statt 40 € je Regal.

Rechnerisch wandelt man jede Ungleichung durch eine Reservevariable (Schlupfvariable) in eine Gleichung um, zum Beispiel $2x+y+s=100$ mit $s\ge 0$. Ein Schritt von Ecke zu Ecke entspricht dann einem Schritt wie beim Gauß-Verfahren für Gleichungssysteme.

In der Praxis ist das Simplex-Verfahren meist schnell. Es gibt aber von Klee und Minty konstruierte Beispiele, bei denen die Zahl der Schritte exponentiell wächst. Dafür wurden andere Verfahren entwickelt: 1979 zeigte Leonid Khachiyan mit der Ellipsoidmethode, dass sich lineare Programme theoretisch in vertretbarer (polynomialer) Zeit lösen lassen, und 1984 stellte Narendra Karmarkar ein Innere-Punkte-Verfahren vor, das auch praktisch gut funktioniert.

Verlangt die Aufgabe ganze Zahlen, etwa ganze Regale, wird es schwieriger. Unser Ergebnis $(40|20)$ war zufällig ganzzahlig. Im Allgemeinen liefert das Verfahren Brüche, und Runden kann das Optimum verfehlen oder die Bedingungen verletzen. Dafür gibt es die ganzzahlige Optimierung.