Every LP has a twin. Here is how to build it.
Chapter: 0 — LP theory · lesson id lp-duality-construct · theory lesson
For every LP there is another LP — the $dual$ — whose variables, constraints, and objective are mechanically determined by the original (the $primal$). The dual is one of the great surprises of linear programming: it is not a contrivance, it is something you discover when you ask "what is the best bound I can prove for the primal optimum, using only its constraints?"
Suppose you want a $lower\ bound$ on the value of the primal LP $\min c^{\top} x$ s.t. $A x \geq b$, $x \geq 0$. The only tools you have are the constraints themselves. So you try the most natural thing: take a non-negative combination of the constraints and see what falls out.
Pick weights $y_{1}, \ldots, y_{m} \geq 0$ and form $y^{\top}(A x) \geq y^{\top} b$, which is $(y^{\top} A) x \geq y^{\top} b$. If every coordinate of $y^{\top} A$ is at most the corresponding coordinate of $c^{\top}$, then because $x \geq 0$ we get $$c^{\top} x \geq (y^{\top} A) x \geq y^{\top} b.$$ Read that left-to-right: any non-negative weighting $y$ with $y^{\top} A \leq c^{\top}$ gives a valid lower bound $y^{\top} b$ on the primal optimum. Which $y$ gives the strongest bound? The one that maximises $y^{\top} b$.
Definition (Dual of a canonical-form LP). For the primal $\min c^{\top} x$ subject to $A x \geq b$, $x \geq 0$, the dual is $$\max y^{\top} b \quad \text{subject to} \quad y^{\top} A \leq c^{\top}, ; y \geq 0.$$ Equivalently (transposing), $\max b^{\top} y$ s.t. $A^{\top} y \leq c$, $y \geq 0$. The dual variables $y_{i}$ are sometimes called $multipliers$ or $shadow\ prices$.
There is one dual variable per primal constraint, and one dual constraint per primal variable. The roles of $A$, $b$, $c$ swap. Inequalities flip. The sense flips from min to max. The dual of the dual is the primal — duality is involutive.
Example (Primal and dual side by side). Take the primal $\min\ 2 x_{1} + 3 x_{2}\ $ s.t. $\ x_{1} + x_{2} \geq 4,\ x_{1} + 2 x_{2} \geq 6,\ x_{1}, x_{2} \geq 0$. Two constraints means two dual variables, $y_{1}, y_{2}$. Two primal variables means two dual constraints. The dual is $\max\ 4 y_{1} + 6 y_{2}\ $ s.t. $\ y_{1} + y_{2} \leq 2,\ y_{1} + 2 y_{2} \leq 3,\ y_{1}, y_{2} \geq 0$.
Quick check. How many constraints does the dual of an LP with $n = 5$ variables and $m = 8$ inequality constraints have?
For LPs with mixed senses, the dualisation rules are mechanical and worth memorising. For each $primal$ constraint, the $dual$ variable's sign is determined:
For each $primal$ variable, the $dual$ constraint's sense is determined:
A useful mnemonic: a $tight$ primal feature ($=$ constraint or free variable) gives a $loose$ dual feature (free variable or $=$ constraint). Tight vs. loose swaps under duality.
Recap.
Read this through MCP: read with path: "lessons/lp-duality-construct", or resource hlpl://lessons/lp-duality-construct.