Simplex-Verfahren
aus www.iwiki.de, der freien Wissensdatenbank
Inhaltsverzeichnis |
Allgemein
Der Simplex ist ein Verfahren zur linearen Optimierung und Lösungsfindung bei komplexen Aufgabenstellungen. Das Simplex-Verfahren löst ein lineares Optimierungsproblem nach endlich vielen Schritten exakt oder stellt die Unlösbarkeit des Problems fest. Eine Gleichung wird durch mehrere Ungleichungen umschrieben.
Vorteihaft ist die Einfachheit und Ãœbersichtlichkeit des Verfahrens. Ein Nachteil ist, dass es bei mehreren Restriktionen sehr rechenaufwendig wird.
Das Simplex-Verfahren ist eine Art Kombination zwischen Eckenauswertungsverfahren und grafischer Lösung.
Lösungsschritte
Schritt 1: Ungleichungen umformen und Schlupfvariablen einfügen
Schritt 2: Aufstellen der ersten Simplextabelle
Schritt 3: Ermitteln des Pivot-Elements
Schritt 4: Berechnung nach dem Simplex Algorithmus, wodurch die neue Tabelle erzeugt wird.
Schritt 5: Prüfen, ob Abbruchbedingung erfüllt ist, falls nicht, die Schritte 2-5 wiederholen
Dualitätstheorem
Zu jedem linearen Optimierungsproblem (Primalproblem) existiert ein duales Problem und umgekehrt. Dadurch werden auf einem Lösungsweg zwei Aufgaben gelöst. Man kann ein Dualproblem auch wieder zurück wandeln in ein Primalproblem, zum Beispiel nach der Bearbeitung einer Rechenaufgabe. Dies ist besonders hilfreich bei der Bearbeitung von minimal-Aufgabenstellungen, da mit dem Simplex-Verfahren nur Maximal-Aufgabenstellungen bearbeitet werden können.
Sonderfälle
- Entartungen
- Unbegrenzte Lösung
- Probleme mit unzulässiger Ausgangslösung liegen vor, falls die Schlupfvariablen kleiner 0 sind
- Gleichungen als Restriktionen
- Duale Simplex-Methode
