Simplex-Verfahren

Die lineare Programmierung ist ein klassisches Teilgebiet der Optimierung und verfolgt die Aufgabe, lineare Zielfunktionen unter Berücksichtigung linearer Nebenbedingungen zu minimieren. Unter der Annahme, dass alle Variablen reell sind, liefert das Simplex-Verfahren einen gängigen Algorithmus zur Lösung derartiger Probleme. In Abschn. 1.1 definieren wir lineare Programme in Standardform sowie in allgemeiner Form und präsentieren Anwendungsbeispiele, welche wir in den folgenden Abschnitten aufgreifen. Anschließend zeigen wir in Abschn. 1.2, dass lineare Programme in allgemeiner Form in Standardform überfuührt werden können, sodass wir die folgenden Lösungsverfahren nur für lineare Programme in Standardform herleiten werden. In Abschn. 1.3 schaffen wir dank der Definition von Basislösungen die wesentliche Grundlage aller Simplex-Varianten und geben damit auch ein Optimalitätskriterium an. Mit diesen Vorbereitungen sind wir in Abschn. 1.4 schließlich in der Lage, das primale Simplex-Verfahren im Detail herzuleiten und zu beschreiben. Dabei gehen wir auch ausführlich auf das Finden einer zulassigen Startlösung ein und greifen einige Anwendungsbeispiele aus der Einleitung wieder auf. In den folgenden beiden Abschnitten präsentieren wir mit dem dualen Simplex-Verfahren eine weitere Simplex-Variante, welche je nach Eingabedaten im Vergleich zum primalen Simplex-Verfahren deutlich effizienter sein kann. Hierzu fassen wir in Abschn. 1.5 wichtige Ergebnisse der Dualitätstheorie zusammen, welche wir anschließend in der Herleitung des dualen Simplex-Verfahrens in Abschn. 1.6 benötigen. Wir beenden auch diesen Abschnitt mit der Lösung eines Anwendungsproblems aus der Einleitung.