Recipe

Construct the dual of a linear program

Use when: you have a primal LP ( $\min\ c^\top x$ subject to linear constraints and $x\ge0$ ) and want the corresponding dual maximization program

Goal: the dual LP -- objective, constraints, and sign restrictions -- built from the same $A$ , $b$ , $c$

Taught in Constructing the dual of a linear program

Quick recipe

Put the primal into canonical $\ge$ form
Assign one dual variable per primal constraint
Build one dual constraint per primal variable from the columns of $A$
Swap objective and right-hand side; minimize becomes maximize

1
Check every constraint is already written as $\ge$ . If one is written as $\le$ , multiply both sides by $-1$ before doing anything else with that row.

Example

$2x_1-x_2\le6$ becomes $-2x_1+x_2\ge-6$ after multiplying by $-1$ .
- every constraint is already $\ge$ — skip straight to Step 2.
- a constraint is $\le$ — multiply that row by $-1$ on both sides, flipping it to $\ge$ , before reading anything off it.
Why: the construction below assumes canonical $Ax\ge b$ form -- reading a row's dual sign or variable directly off a $\le$ row, without converting first, is the single most common way this rule goes wrong.
2
$A$ has $m$ rows, so the dual has $m$ variables $y_1,\dots,y_m$ , one per primal constraint, each restricted to $y_i\ge0$ .

Example

Meadowbrook's two constraints give $y_1$ (protein) and $y_2$ (energy).

Why: each dual variable is the shadow price attached to one primal resource limit -- Section 2 makes that precise once both programs are solved.
3
$A$ has $n$ columns, so the dual has $n$ constraints. Read column $j$ straight down -- every coefficient attached to $x_j$ -- and use it as the left side of dual constraint $j$ , bounded above by $c_j$ .

Example

Column 1 of Meadowbrook's $A$ is $(1,3)$ , giving $y_1+3y_2\le4$ ; column 2 is $(2,1)$ , giving $2y_1+y_2\le3$ .

Why: a primal variable's own column tells you exactly how much of each resource one unit of that variable uses -- the dual constraint says the implied price of that bundle can never beat the variable's own cost.
4
The primal's cost vector $c$ becomes the dual's right-hand side; the primal's right-hand side $b$ becomes the dual's objective coefficients. A minimize primal produces a maximize dual.

Example

$b=(10,15)$ becomes the dual objective $10y_1+15y_2$ ; $c=(4,3)$ becomes the right-hand sides already used in Step 3.

Why: this trade turns "the cheapest way to meet a requirement" into "the most a competing seller could charge and still lose no business" -- the same numbers, read as prices instead of quantities.

Common mistakes

Reading a $\le$ constraint's row directly as a dual variable or sign, without converting it to $\ge$ first (Step 1).
Mismatching a column of $A$ with the wrong primal variable, so a dual constraint's coefficients don't come from one consistent column.
Forgetting that $y\ge0$ always holds in the dual, no matter what sign the original primal constraint carried before conversion.
Swapping $c$ and $b$ into the wrong slots -- $b$ becomes the dual OBJECTIVE, not the other way around.