Duality

Every linear program (the primal) has an associated linear program (the dual) built from the same data.

Consider a primal in standard form, with $x \in \mathbb{R}^n$, an $m \times n$ matrix $A$, $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$. It has $n$ variables and $m$ constraints.

The dual has $m$ variables and $n$ constraints. One variable $y_i$ per primal constraint. $y \in \mathbb{R}^m$:

By index:

Same data $(A, b, c)$, rearranged: $A$ transposed, $b$ and $c$ exchanged, objective sense flipped, and the constraint and variable counts swapped ($n$ constraints, $m$ variables). The correspondence table lists every swap; the direction rules cover constraints that are not $\le$.

Primal-Dual Correspondence

• Objective flips
  Maximize primal $\leftrightarrow$ minimize dual (or vice versa).
• Primal constraint $\leftrightarrow$ dual variable
  1 dual variable per primal constraint.
• Primal variable $\leftrightarrow$ dual constraint
  1 dual constraint per primal variable.
• RHS and objective coefficients swap
  Primal RHS becomes dual objective coefficients; primal objective coefficients become dual RHS.
• Constraint matrix transposes
  Dual constraint coefficients are the transpose of the primal’s.

Constraint Direction Rules

For a maximization primal with non-negative variables:

• Primal $\le$ constraint $\to$ dual variable $\ge 0$
• Primal $\ge$ constraint $\to$ dual variable $\le 0$
• Primal $=$ constraint $\to$ dual variable unrestricted in sign

For a minimization primal with non-negative variables, the two inequality rules swap. The equality rule is unchanged.

• Primal $\ge$ constraint $\to$ dual variable $\ge 0$
• Primal $\le$ constraint $\to$ dual variable $\le 0$
• Primal $=$ constraint $\to$ dual variable unrestricted in sign

The canonical constraint direction, the one giving a non-negative dual variable, is $\le$ for a max primal and $\ge$ for a min primal. A deviation from it forces the opposite sign.

The variable-to-constraint mapping mirrors this. A non-negative primal variable gives a $\ge$ dual constraint for a max primal, a $\le$ dual constraint for a min primal.

Mnemonics

• MOTS
  Max flips to Min. Objective coefficients swap with RHS. Transpose $A$. Sizes swap ($m$ constraints give $m$ variables, $n$ variables give $n$ constraints).
• Max is under, min is over
  The canonical constraint direction is $\le$ for a max primal, $\ge$ for a min primal.
• Same, equal, opposite
  Compare a primal constraint to the canonical direction. Same gives dual variable $\ge 0$. Equality gives it unrestricted. Opposite gives it $\le 0$.
• Same, equal, opposite (variable side)
  Take the max primal case, where a non-negative variable gives a $\ge$ dual constraint. A free variable gives an $=$ dual constraint. A non-positive variable gives a $\le$ dual constraint. For a min primal every direction flips.
• Pay only for what you use up
  A non-binding primal constraint has dual value $0$. A positive dual value forces its primal constraint to bind. See complementary slackness.

Theorems

Weak Duality Theorem

For a maximization primal and its minimization dual, every primal feasible objective value is $\le$ every dual feasible objective value.

Consequences:

• If the primal is unbounded, the dual is infeasible, and vice versa.
• If a primal feasible $x$ and a dual feasible $y$ satisfy $c^T x = b^T y$, both are optimal.
• Dual infeasible does not imply primal unbounded; both problems can be infeasible.

Strong Duality Theorem

If the primal has an optimal solution, the dual also has an optimal solution, and their optimal objective values are equal.

Only four primal-dual outcome pairs are possible:

Complementary Slackness

Primal feasible $x$ and dual feasible $y$ are both optimal if and only if for every matched pair one side is 0: either a constraint is binding (0 slack/surplus) or its corresponding variable in the other problem is 0, never both non-zero.

Proof sketch: strong duality makes both $\le$ in the weak duality chain equalities; each gap is a sum of non-negative terms equal to 0, so every term is 0.

Used to recover one problem’s optimal solution directly from the other’s, without re-solving.

Reading Dual Values from the Primal Optimal Table

The optimal dual variable values appear in the primal’s optimal simplex tableau, in the objective row under the columns of the corresponding primal slack/surplus variables (with sign adjusted for the constraint direction).

Each $y_i^*$ is the shadow price of primal constraint $i$: the rate $z^*$ changes per unit increase of $b_i$, valid over the range that keeps the current basis optimal.

Worked Example

Primal, the same LP as the simplex worked example:

3 constraints give 3 dual variables $y_1, y_2, y_3$; 2 primal variables give 2 dual constraints. All primal constraints are $\le$, so all $y_i \ge 0$. Transposing the constraint matrix and swapping RHS with objective coefficients:

The primal’s final tableau has objective row entries $0, \tfrac{3}{2}, 1$ under $s_1, s_2, s_3$, so $y_1 = 0$, $y_2 = \tfrac{3}{2}$, $y_3 = 1$. Then $w = 4(0) + 12(\tfrac{3}{2}) + 18(1) = 36 = z^*$, confirming strong duality.

Complementary slackness holds at $x^* = (2, 6)$, $y^* = (0, \tfrac{3}{2}, 1)$:

• Primal constraint 1 has slack $4 - 2 = 2 > 0$, so $y_1 = 0$.
• $y_2, y_3 > 0$, so primal constraints 2 and 3 are binding: $2(6) = 12$, $3(2) + 2(6) = 18$.
• $x_1, x_2 > 0$, so both dual constraints are binding: $0 + 3(1) = 3$, $2(\tfrac{3}{2}) + 2(1) = 5$.