How to Convert a Primal Linear Program to Its Dual

Converting a primal linear program to its dual is mostly a matter of organizing the coefficients and applying sign rules. The most common case has a maximization objective, upper-bound constraints, and nonnegative variables; mixed inequalities and unrestricted variables use the same principles with adjusted signs.

The standard primal–dual pair

Write the primal in the standard maximization form

$$\begin{aligned} \text{maximize} \quad & c^T x \\ \text{subject to} \quad & Ax \le b, \\ & x \ge 0. \end{aligned}$$

Here, each row of $A$ is one constraint, and each column corresponds to one variable. Its dual is

$$\begin{aligned} \text{minimize} \quad & b^T y \\ \text{subject to} \quad & A^T y \ge c, \\ & y \ge 0. \end{aligned}$$

The dimensions switch: if the primal has $m$ constraints and $n$ variables, the dual has $m$ variables and $n$ constraints. The entries of $b$ become the dual objective coefficients, the entries of $c$ become the right-hand sides of the dual constraints, and the constraint matrix becomes $A^T$.

A reliable conversion procedure

For a primal maximization problem:

1. Make one dual variable for each primal constraint.
2. Make one dual constraint for each primal variable.
3. Set the dual objective coefficients equal to the primal right-hand side.
4. Transpose the primal coefficient matrix. The right-hand side of each dual constraint is the coefficient of the corresponding primal variable in the objective.
5. Determine signs and inequality directions from the rules below.

The objective direction reverses: a primal maximum gives a dual minimum. For a primal minimum, the dual is a maximum.

Sign rules for mixed forms

The table gives the rules for a maximization primal. A row constraint means one constraint in the primal; its dual variable appears in the dual objective. A primal variable bound determines the inequality in the corresponding dual constraint.

Maximization-primal feature	Corresponding dual feature
Constraint $\le$	Dual variable $\ge 0$
Constraint $\ge$	Dual variable $\le 0$
Constraint $=$	Dual variable unrestricted in sign
Variable $x_j \ge 0$	Dual constraint $j$ is $\ge$
Variable $x_j \le 0$	Dual constraint $j$ is $\le$
Variable $x_j$ unrestricted in sign	Dual constraint $j$ is an equality

For a minimization primal, reverse these signs and inequality directions: a primal $\le$ row gives a nonpositive dual variable, and a nonnegative primal variable gives a $\le$ dual constraint. Equality rows still give unrestricted dual variables, and unrestricted primal variables still give equality constraints.

These rules assume the objective and constraints are written consistently as a maximization or minimization problem. You can also multiply a constraint by $-1$ to reverse its inequality, but you must change the signs of every coefficient in that row, including its right-hand side.

Worked example

Consider the primal problem

$$\begin{aligned} \text{maximize} \quad & 3x_1 + 2x_2 \\ \text{subject to} \quad & x_1 + x_2 \le 4, \\ & 2x_1 + x_2 \le 5, \\ & x_1, x_2 \ge 0. \end{aligned}$$

There are two primal constraints, so introduce dual variables $y_1$ and $y_2$. The primal is a maximization with $\le$ rows, so $y_1,y_2\ge 0$. The dual objective uses the primal right-hand sides, 4 and 5:

$$\text{minimize } 4y_1 + 5y_2.$$

There are two primal variables, so the dual has two constraints. Read each dual constraint from the corresponding column of the primal matrix:

• The $x_1$ column has coefficients 1 and 2, and its objective coefficient is 3. Since $x_1\ge 0$, its dual constraint is $y_1+2y_2\ge 3$.
• The $x_2$ column has coefficients 1 and 1, and its objective coefficient is 2. Since $x_2\ge 0$, its dual constraint is $y_1+y_2\ge 2$.

Thus the dual is

$$\begin{aligned} \text{minimize} \quad & 4y_1 + 5y_2 \\ \text{subject to} \quad & y_1 + 2y_2 \ge 3, \\ & y_1 + y_2 \ge 2, \\ & y_1, y_2 \ge 0. \end{aligned}$$

Why the standard signs make sense

If $x$ satisfies $Ax\le b$ and $y\ge 0$, then $y^TAx\le y^Tb$. If also $A^Ty\ge c$ and $x\ge 0$, then $c^Tx\le y^TAx$. Therefore every feasible primal objective value is at most every feasible dual objective value. This is the weak duality property, and it explains why the standard primal maximum pairs with a dual minimum.

Common mistakes

• Using $A$ instead of $A^T$. Each dual constraint comes from a column of the primal matrix, not a row.
• Keeping the same objective direction. The dual reverses maximum and minimum.
• Setting every dual variable nonnegative. That is true for $\le$ rows in a maximization primal, but not for $\ge$ or equality rows.
• Forgetting variable bounds. A free primal variable creates an equality in the dual; it does not create a one-sided inequality.
• Changing an inequality without changing its whole row. Multiplying by $-1$ also changes the right-hand side and all coefficients.