Simplex-Verfahren

Duale Information im Tableau

Aus dem Simplextableau lässt sich auch die Information zur Lösung des zu dem linearen Programm (LP) gehörigen dualen linearen Programms entnehmen. Zu einer gegebenen Basis B kann man neben der zugehörigen Primallösung x = b = A^-1_B b, die in der rechten Spalte des Tableaus steht, auch eine Duallösung berechnen. Diese beiden Vektoren x und erfüllen immer die Bedingung

,

die für Optimallösungen notwendig ist. Der Vektor x bleibt nach Konstruktion der einzelnen Simplexiterationen immer zulässig für das primale LP, während der Vektor Bedingungen des dualen LPs verletzen kann. Sind zu einer Basis sowohl die zugehörige Primallösung x als auch die entsprechende Duallösung zulässig (man spricht dann von einer primal und dual zulässigen Basis), dann sind beide optimal für das primale bzw. duale lineare Programm. Man kann zeigen, dass dies genau dann der Fall ist, wenn der reduzierte Kostenvektor c nichtpositiv ist. Obwohl das Ziel des Simplex-Verfahrens eigentlich nur die Berechnung einer optimalen Primallösung ist, fällt also am Ende auch eine optimale Duallösung nebenbei mit ab.

Eine Beispielrechnung zur Dualität befindet sich im Artikel Pivotverfahren.

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