= Linear programming duality
<Linear programming duality> pairs the standard maximization problem
$$
\max\{c^Tx:Ax\le b,\ x\ge0\}
$$
with the minimization problem
$$
\min\{b^Ty:A^Ty\ge c,\ y\ge0\}.
$$
The <dual variables> form nonnegative combinations of primal inequalities. If $x$ and $y$ are feasible, then
$$
c^Tx\le x^TA^Ty=y^TAx\le b^Ty.
$$
This is <weak duality>, giving independently checkable bounds before any algorithm reaches an optimum.
For a feasible primal with finite optimal value, <strong duality> for finite-dimensional linear programs ensures attained primal and dual optima with equal values. Their objective difference decomposes into nonnegative products of variables and opposite slacks, yielding <complementary slackness>. The worked allocation in <linear programming> has primal point $(2,2)$ and dual multipliers $(2,1,0)$, both with value ten. Sign conventions change for minimization, equality rows and unrestricted variables; a dual formula belongs to its declared primal form.
Back to article page