LP Duality

Interactive visualizations for Chapter 5 of the Ricerca Operativa notes

The Primal-Dual Pair

Every LP has a companion dual problem. The primal seeks the best feasible solution; the dual seeks the tightest upper bound on that solution’s value.

For the furniture workshop LP, the primal (canonical form) is:

\[ \begin{aligned} & \text{maximize} && 30\,x_1 + 50\,x_2 \\ & \text{subject to} && 2\,x_1 + 5\,x_2 \leq 40 && \text{(wood)} \\ & && 4\,x_1 + 2\,x_2 \leq 32 && \text{(labour)} \\ & && x_1, x_2 \geq 0. \end{aligned} \]

The dual is obtained by introducing multipliers \(u_1 \geq 0\) (wood) and \(u_2 \geq 0\) (labour), then minimising the tightest upper bound:

\[ \begin{aligned} & \text{minimize} && 40\,u_1 + 32\,u_2 \\ & \text{subject to} && 2\,u_1 + 4\,u_2 \geq 30 && \text{(chair bound)} \\ & && 5\,u_1 + 2\,u_2 \geq 50 && \text{(table bound)} \\ & && u_1, u_2 \geq 0. \end{aligned} \]

The dual optimal solution is \(u^* = (35/4,\; 25/8) = (8.75,\; 3.125)\) with \(w^* = 450\).

Strong duality guarantees \(z^* = w^* = 450\) — the primal and dual optima are equal, with no duality gap.

Visualization 1: Primal and Dual Feasible Regions

The primal feasible region is a polygon in \((x_1, x_2)\)-space. The dual feasible region is a polygon in \((u_1, u_2)\)-space. Both have unique optimal vertices; strong duality says their objective values at those vertices are equal.

  • Primal optimal vertex: \((x_1^*, x_2^*) = (5, 6)\) with \(z^* = 30(5) + 50(6) = 450\).
  • Dual optimal vertex: \((u_1^*, u_2^*) = (8.75, 3.125)\) with \(w^* = 40(8.75) + 32(3.125) = 450\).

Both optima achieve the same value \(z^* = w^* = 450\). The dual optimal vertex \((8.75, 3.125)\) is where both dual constraint boundaries meet — exactly the “tightest” upper-bound multipliers. The primal optimal vertex \((5, 6)\) is where both primal constraints are active. This perfect correspondence is the content of strong duality.

Visualization 2: Weak Duality — Closing the Gap

Weak duality states that any dual-feasible solution gives an upper bound on any primal-feasible objective value: \(c^\top \bar{x} \leq b^\top \bar{u}\) for all feasible \(\bar{x}, \bar{u}\).

As we move toward the optimum from both sides, the duality gap \(b^\top \bar{u} - c^\top \bar{x}\) shrinks to zero. The plot below shows:

  • Blue dots: primal-feasible points along a path toward \((5, 6)\), with their objective values.
  • Orange dots: dual-feasible points along a path toward \((8.75, 3.125)\), with their objective values.
  • The gap between the two sequences narrows until the optima meet at \(z^* = w^* = 450\).

Weak duality says the gap is always \(\geq 0\) (dual value \(\geq\) primal value). Strong duality says that for LP, the gap at optimality is exactly zero. The right panel shows the gap collapsing to zero as both sides approach their respective optimal vertices.

Visualization 3: Complementary Slackness

Complementary slackness gives a structural test for optimality. For the optimal pair \(x^* = (5, 6)\) and \(u^* = (8.75, 3.125)\):

  • Dual complementarity (one condition per primal constraint \(i\)): \(u^*_i \cdot s_i = 0\), where \(s_i = b_i - (Ax^*)_i\) is the primal slack.
  • Primal complementarity (one condition per dual constraint \(j\)): \(x^*_j \cdot \bar{c}_j = 0\), where \(\bar{c}_j = (A^\top u^*)_j - c_j\) is the dual slack.

At optimality, all four conditions hold with equality. The visualization below displays the full complementary slackness table.

All four complementary slackness conditions hold:

  • Wood (\(i=1\)): the constraint is tight (\(s_1 = 0\)), and correspondingly \(u^*_1 = 8.75 > 0\) (wood has positive shadow price — every unit of wood is binding).
  • Labour (\(i=2\)): the constraint is tight (\(s_2 = 0\)), and \(u^*_2 = 3.125 > 0\) (labour is also fully used).
  • Chair (\(j=1\)): \(x^*_1 = 5 > 0\), so the dual constraint must be tight — and indeed \(\bar{c}_1 = 0\).
  • Table (\(j=2\)): \(x^*_2 = 6 > 0\), so the dual constraint must be tight — and indeed \(\bar{c}_2 = 0\).

The shadow prices \(u^*_1 = 8.75\) and \(u^*_2 = 3.125\) measure the marginal worth of each resource: one extra unit of wood yields €8.75 additional profit; one extra hour of labour yields €3.125.