Simplex-Verfahren

Beispielrechnung

Einträge in Bruchzahlform

Das obige Beispiel wurde in algebraischer Notation gelöst,indem man im Gleichungssystem die Basisvariablen bezüglich der restlichen, unabhängigen Variablen freilegt.Um Rundungsfehler zu vermeiden, kann man mit Bruchzahlen arbeiten und einen gemeinsamen Nenner für das gesamte Gleichungssystem wählen (dass dieser Nenner oben immer 1 war, ist Zufall).Um in jedem Schritt den gemeinsamen Nenner für das Gesamtsystem zu finden, müssen wir die Einträge nicht zusätzlich analysieren. Falls das Startsystem ganzzahlig ist (was sich normalerweise durch Erweiterung erreichen lässt), gilt die Regel:

• Der Zähler des gewählten Pivotelements ist ein gemeinsamer Nenner für das darauffolgende System

Wenn wir die neuen Tableau-Einträge mit diesem gemeinsamen Nenner multiplizieren, erhalten wir stets ganzzahlige Zähler.Bei der Berechnung dieser Zähler für die neuen Tableau-Einträge wird dann ungeprüft durch den alten Nenner geteilt, wobei das Ergebnis ganzzahlig sein muss.

Als Beispiel für diese Vorgehensweise lösen wir dieselbe Aufgabe wie oben noch einmal mit Dantzigs Pivotauswahl; hierbei wird als eingehende Pivotvariable diejenige mit größtem Zielfunktionskoeffizienten gewählt:

Durch Erhöhung der unabhängigen Variable x₂ lässt sich die Zielfunktion z vergrößern;die erste der Basisvariablen, die in diesem Fall auf Null stößt, ist y_C . Folglich kann man x₂  anstelle von y_C freilegen und erhält folgendes System mit z = 30000:

Wenn man die unabhängige Variable x₁ erhöht, vergrößert man die Zielfunktion;die erste der Basisvariablen, die dann auf Null stößt, ist y_A . Folglich legt man x₁  anstelle von y_A frei und erhält folgendes System mit z = 45000:

Wenn man die unabhängige Variable y_C erhöht, vergrößert man die Zielfunktion;die erste der Basisvariablen, die dann auf Null stößt, ist y_B . Folglich legt man y_C  anstelle von y_B frei und erhält folgendes System mit z = 49000:

Die Zielfunktion hat Wert z = 49000 und lässt sich nicht mehr erhöhen;die Lösung ist wie oben x₁ = 130, x₂ = 20. Wir beobachten nebenher, dass Dantzigs Pivotauswahl im Vergleich zur anfangs gewählten Alternative einen Schritt mehr gebraucht hat, um zur Lösung zu gelangen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Simplex-Verfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung