Summary D0H45A_Linear Optimisation: Part 3: Duality Theory

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