Part 3: Duality Theory
Dual: Associated with any LP there is another LP called the dual
Primal: When taking the dual of an LP, the give LP is called the primal.
We speak of primal-dual pairs. This theory will give us insights in how changes in an LP’s
parameter the LP’s optimal solution affects.
The primal and dual Problems in Canonical Form
Maximization LP
Primal Dual
Max cx min wb
s.t. Ax ≤ b s.t. wA ≥ c
x≥0 w≥0
Minimization LP
Primal Dual
Min cx max wb
s.t. Ax ≥ b s.t. wA ≤ c
x≥0 w≥0
If the primal is in canonical form, the dual is also in canonical form.
Constraint i from primal will be associated to 𝑤) in dual.
Theorem
“Dual of the Dual is the primal”
, Primal-Dual pairs
A constraint in Primal ⟺ Variable in Dual
A variable in Primal ⟺ a constraint in Dual
Min in Primal ⟺ max in Dual (and vice versa)
What happens when we have equality constraints Ax = b in the primal?
Equality constraint in Primal ⟺ corresponding variable free in Dual
Primal Dual
Min cx max wb
s.t. Ax = b s.t. wA ≤ c
x≥0 w free
What happens when we have free variables in the primal?
Free variable in Primal ⟺ Corresponding constraint is equality in Dual
Primal Dual
Max cx min wb
s.t. Ax ≤ b s.t. wA = c
x free w≥0
What happens when we have non-positive variables in the primal?
ð Will define a new variable y = -x
Primal Dual
Max cx max - cy min wb min wb
s.t. Ax ≤ b ⟹ s.t. - Ay ≤ b s.t. -wA ≥ - c ⟹ s.t. wA ≤ c
x≤0 y≥0 w≥0 w≥0
Dual: Associated with any LP there is another LP called the dual
Primal: When taking the dual of an LP, the give LP is called the primal.
We speak of primal-dual pairs. This theory will give us insights in how changes in an LP’s
parameter the LP’s optimal solution affects.
The primal and dual Problems in Canonical Form
Maximization LP
Primal Dual
Max cx min wb
s.t. Ax ≤ b s.t. wA ≥ c
x≥0 w≥0
Minimization LP
Primal Dual
Min cx max wb
s.t. Ax ≥ b s.t. wA ≤ c
x≥0 w≥0
If the primal is in canonical form, the dual is also in canonical form.
Constraint i from primal will be associated to 𝑤) in dual.
Theorem
“Dual of the Dual is the primal”
, Primal-Dual pairs
A constraint in Primal ⟺ Variable in Dual
A variable in Primal ⟺ a constraint in Dual
Min in Primal ⟺ max in Dual (and vice versa)
What happens when we have equality constraints Ax = b in the primal?
Equality constraint in Primal ⟺ corresponding variable free in Dual
Primal Dual
Min cx max wb
s.t. Ax = b s.t. wA ≤ c
x≥0 w free
What happens when we have free variables in the primal?
Free variable in Primal ⟺ Corresponding constraint is equality in Dual
Primal Dual
Max cx min wb
s.t. Ax ≤ b s.t. wA = c
x free w≥0
What happens when we have non-positive variables in the primal?
ð Will define a new variable y = -x
Primal Dual
Max cx max - cy min wb min wb
s.t. Ax ≤ b ⟹ s.t. - Ay ≤ b s.t. -wA ≥ - c ⟹ s.t. wA ≤ c
x≤0 y≥0 w≥0 w≥0
