Lineare Optimierung

Dualität

Jedem linearen Programm (dem primalen Problem) ist ein anderes lineares Programm zugeordnet: das duale Problem. Zwischen dem primalen und seinem dualen Problem gibt es enge Zusammenhänge, die sowohl beim Beweis von Sätzen der linearen Optimierung als auch bei der praktischen Lösung linearer oder ganzzahlig-linearer Programme ausgenutzt werden können. Einige dieser Zusammenhänge sind Spezialfälle der entsprechenden Sätze aus der konvexen Optimierung.

Einem primalen LP in Standardform

ist das duale LP

zugeordnet, bei dem die Zeilen und Spalten gegenüber dem Ausgangsproblem vertauscht sind. Jeder Ungleichung des primalen Problems ist dabei eine sogenannte Dualvariable y_i zugeordnet, und jeder Variable x_j des primalen Problems entspricht eine duale Ungleichung. Das duale Problem des dualen Problems ist wieder das Ursprungsproblem. Besonders hervorgehoben wird die Symmetrie beider Aufgaben, wenn wir das primale Problem in die alternative Grundform allgemeiner Pivotverfahren bringen.

Die Zusammenhänge zwischen dem primalen und dualen Problem werden durch die sogenannten Dualitätssätze beschrieben, die alle auf dem Lemma von Farkas basieren. Nach dem schwachen Dualitätssatz der linearen Optimierung gilt für alle zulässigen Lösungen x und y des primalen bzw. dualen Problems

,

d. h. der Wert jeder dualen Lösung ist mindestens so hoch wie der Wert jeder primalen Lösung.

Der starke Dualitätssatz verschärft diese Aussage: wenn eines der beiden LPs eine beschränkte Optimallösung besitzt, dann auch das andere, und die optimalen Zielfunktionswerte sind in diesem Fall gleich. Für jede optimale Lösungen x^* des primalen und jede optimale Lösung y^* des dualen Problems gilt also

c^T x^* = b^T y^* .

Man kann zeigen, dass folgende Zusammenhänge gelten:

• Das duale Problem hat genau dann eine beschränkte Optimallösung, wenn das primale Problem eine beschränkte Optimallösung besitzt.
• Wenn das primale Problem keine zulässige Lösung hat, ist das duale Problem unbeschränkt oder hat auch keine zulässige Lösung.
• Wenn das primale Problem unbeschränkt ist, hat das duale Problem keine zulässige Lösung.

Diese und weitere Sätze bilden die Grundlage für alle Verfahren, die mit primalen und dualen Schranken für den Wert einer Optimallösung arbeiten, wie beispielsweise Branch-and-Cut und Schnittebenenverfahren.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Lineare Optimierung 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