Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 38 ยท Duality and Sensitivity

Duality Theorems and Complementary Slackness

Understand weak duality, strong duality, the primal-dual outcome table and complementary slackness conditions, and verify them numerically with Python and linprog.

The dual problem is more than a clever rewrite: primal and dual solutions are tied together by exact relationships. This lesson states them, proves the easy one, and checks all of them numerically. They give you optimality certificates and a way to recover one solution from the other.

We use the symmetric pair throughout:

TEXT
Primal (P):  max c.x   s.t.  A x <= b,   x >= 0
Dual   (D):  min b.y   s.t.  A^T y >= c, y >= 0

Weak duality

For any primal-feasible x and any dual-feasible y: c.x <= b.y.

Proof in two lines. Because y >= 0 and Ax <= b: y^T A x <= y^T b. Because x >= 0 and A^T y >= c: x^T A^T y >= x^T c. Chain them: c.x <= y^T A x <= b.y.

So every feasible dual solution is an upper bound on every feasible primal value, and every feasible primal solution is a lower bound for the dual. If you ever find feasible x and y with c.x = b.y, both must be optimal: there is no room between them. That is an optimality certificate you can check with simple arithmetic.

Python Weak duality on random feasible points

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The best random primal value is below 2600 and the best random dual value is above 2600: the optimum is squeezed between them.

Strong duality

If the primal has an optimal solution, so does the dual, and the optimal values are equal: max c.x = min b.y.

There is no duality gap in linear programming (unlike integer programming, as you will see later in the track). Strong duality can be proved from the simplex method: at the final tableau the objective-row entries under the slack columns give a dual-feasible y whose value equals the primal objective, because that is what the optimality condition says.

The outcome table

For any primal/dual pair exactly one of these four combinations occurs:

Primal \ Dual Optimal Infeasible Unbounded
Optimal Yes (equal values) Impossible Impossible
Infeasible Impossible Possible (both infeasible) Possible
Unbounded Impossible Possible Impossible

The key rules: if one problem is unbounded, the other is infeasible (weak duality leaves no feasible partner, since the partner would give a finite bound). If one is optimal, so is the other. It is possible, but rare, for both to be infeasible.

Python Unbounded primal, infeasible dual

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complementary slackness

At optimal solutions x* and y*, the inequalities in weak duality's chain must be equalities. That forces a precise pairing between slack and positivity:

x* and y* are both optimal if and only if

  1. y*_i (b_i - a_i . x*) = 0 for every constraint i, and
  2. x*_j (a_j . y* - c_j) = 0 for every variable j,

with both solutions feasible.

In words:

  • If a constraint is not tight (has slack) at the optimum, its dual price is zero.
  • If a dual price is positive, its constraint is tight (the resource is fully used).
  • If a variable is positive (a product is made), its dual constraint is tight (resource values equal the profit).
  • If a dual constraint has slack (the resources are worth more than the profit), the variable is zero (do not make it).
Python Check complementary slackness on the bakery

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both product vectors are zero, as the theorem says.

Using complementary slackness

To verify a proposed solution. Given a candidate x, find which constraints are tight and which variables are positive; solve for the y that is zero on non-tight constraints and makes the dual constraints tight for positive variables. If that y is feasible (non-negative with A^T y >= c), then x is optimal.

To recover the dual from the primal (or vice versa). For the bakery, x = 20, y = 60 are both positive, so both dual constraints are tight: 2y1 + y2 + y3 = 40 and y1 + y2 = 30. The flour constraint has slack, so y3 = 0. Then 2y1 + y2 = 40 and y1 + y2 = 30 give y1 = 10, y2 = 20. No simplex needed.

Python Recover the dual from complementary slackness

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The recovered y = (10, 20, 0) is dual feasible and its value b.y = 2600 equals c.x, which proves optimality of (20, 60) using only arithmetic.

Farkas' lemma (a glimpse)

The infeasibility side of duality is captured by Farkas' lemma: either Ax = b, x >= 0 has a solution, or there is a y with A^T y >= 0 and b.y < 0, but never both. That vector y is a certificate of infeasibility: a weighted combination of the constraints that produces a contradiction. Solvers can hand it to you to explain why a model is infeasible.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Weak duality says that for feasible x (primal max) and y (dual min)

    Every dual-feasible value is an upper bound on every primal-feasible value.
  2. 2. You find feasible x and y with c.x = b.y. What can you conclude?

    Weak duality leaves no gap, so neither can be improved.
  3. 3. If the primal is unbounded, the dual is

    A feasible dual would bound the primal objective, contradicting unboundedness.
  4. 4. Complementary slackness: a constraint with positive slack at the optimum has dual price

    y_i * slack_i = 0, so with slack > 0 the price must be 0.

Summary

  • Weak duality: c.x <= b.y for all feasible pairs; equality certifies optimality.
  • Strong duality: if one problem has an optimum, so does the other, with equal value (no LP duality gap).
  • Unbounded primal implies infeasible dual and vice versa; both can be infeasible.
  • Complementary slackness: y_i * slack_i = 0 and x_j * reduced_cost_j = 0.
  • Use these relationships to verify solutions and recover duals without re-solving.

Next: Shadow Prices and Sensitivity Analysis