Dualität
Die lineare Optimierung ist auch unter der Bezeichnung lineare Programmierung bekannt. Sie beschäftigt sich, wie der Name schon sagt, „mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist“1. Dabei wird die (Ziel-) Funktion minimiert oder maximiert, unter Beachtung der linearen Nebenbedingungen, die man auch Restriktionen nennt. Die Variablen (x1, x2, ... , xn) hingegen in der (Ziel-)funktion nennt man Entscheidungsvariablen.
Jedem linearen Optimierungsproblem lässt sich ein zweites lineares Optimierungsproblem zuordnen. Deshalb nennt man Originalproblem oft auch Primalproblem, während das zweite Problem Dualproblem genannt wird. Dabei ist das Dualproblem des Dualproblems wiederum das Primalproblem. Zu beachten ist dabei, dass beide Probleme zwar den selben Sachverhalt beschreiben, dies allerdings jeweils mit einer eigenen Sichtweise.
Um den Zusammenhang zwischen Primal- und Dualproblem verstehen zu können, muss man sich einige Sätze bewusst machen. Den Anfang bildet der schwache Dualitätssatz. Dieser lautet:
Für jeden primal zulässigen Punkt x und jeden dual zulässigen Punkt y gilt:cTx ≤ bTy
Darüber hinaus gibt es auch noch den starken Dualitätssatz der besagt:
Es seinen x* ein optimaler Punkt des Primalproblems und y* ein optimaler Punkt des Dualproblems. Dann gilt:
cTx* = bTy*
Eine wichtige Folgerung aus dem schwachen und starken Dualitätssatz ist der Satz vom komplementären Schlupf.