Think of a primal-dual pair as two sides to the same linear program.

Note that $\min$ doesn’t have to be $(P)$. The Primal is the Dual of the Dual.

Question marks are placeholders. Replace them with the cell across from them in this table.

Weak Duality

If one of $(P)$ or $(D)$ is unbounded, then the other is infeasible.

If both have a feasible solution, $x$ for $(P)$ and $y$ for $(D)$,

• $b^Ty ≤ c^Tx$; i.e. the obj. val. for the Dual is the lower bound **of the obj. val. for the Primal.
• If they are equal, both are optimal for their respective LPs.

Strong Duality

If $(P)$ has an optimal solution, then so too does $(D)$, and their objective values are equal.

As an extension from weak duality,

Complementary Slackness

$\overline{x}, \overline{y}$ are optimal for their respective problems iff for every row $i$

• Constraint $i$ is tight for $\overline{x}$ or
• $y_i = 0$