Back to the on-screen lesson ·
One dual variable per constraint, one dual constraint per variable, the limits as the new objective.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write the dual of a linear program by transposing its constraint matrix and exchanging its right-hand side with its objective, count the dual's variables and constraints from the primal's, apply the sense rules for equality constraints and free variables, and say why dualising twice returns the original problem.
You can write a program as $A$, $b$ and $c$ and run the simplex method on it. The dual is built from the same three objects, rearranged — and the rearrangement is worth knowing before any theorem about it.
The problem you started with is the primal; the problem built from its transpose is the dual. A dual variable belongs to a primal constraint and prices its resource. The rules for building one are the transposition rules, and they pair constraints with variables in both directions.
The dual of $\max c^{T}x$ subject to $Ax \le b$, $x \ge 0$ is $\min b^{T}y$ subject to $A^{T}y \ge c$, $y \ge 0$. Four exchanges, and nothing else: one dual variable per primal constraint, one dual constraint per primal variable, the limits become the objective, and the sense flips.
Read it as pricing. The primal chooses a plan; the dual chooses a price for each resource, low enough to be worth quoting and high enough that no product is worth making for less than its inputs cost. That reading is why $y_i$ turns out to be what one more unit of resource $i$ is worth, which is the next lesson but one.
The sense rules cover the cases the standard shape leaves out. An equality constraint gives a free dual variable; a free primal variable gives a dual equality. Strictness on one side is freedom on the other, in both directions.
And the relation is symmetric: dualise twice and you are back where you started.
Another way: steps
Another way: example
Workshop: $\max 30x_1 + 50x_2$, $2x_1 + 5x_2 \le 100$, $3x_1 + 2x_2 \le 60$. Dual: $\min 100y_1 + 60y_2$, $2y_1 + 3y_2 \ge 30$, $5y_1 + 2y_2 \ge 50$, $y \ge 0$ — a price for wood and a price for labour.
A dual constraint is built from a row of $A$ instead of a column, which produces a problem of the right shape and the wrong content whenever $A$ is not symmetric. The second error is counting the dual's variables from the primal's variables: it is the primal's constraints that supply them.
$\min 3x_1 + 2x_2$ subject to $x_1 + x_2 \ge 4$ and $x_1 - x_2 = 1$, $x \ge 0$.
One $\ge$ row, one equality.
Two dual variables: $y_1 \ge 0$ from the inequality, and $y_2$ free from the equality.
The sense rule for an equality.
Dual: $\max 4y_1 + y_2$ subject to $y_1 + y_2 \le 3$ and $y_1 - y_2 \le 2$.
Columns become rows.
One dual constraint per primal variable.
Variables become constraints.
So $5$ constraints, in $3$ dual variables.
The primal maximises $4x + 7y$ subject to $4x + 2y \le k$ and $6x + 7y \le m$, $x, y \ge 0$. Its dual has variables $u$ and $v$. Fill in the dual's two constraints.
| Coefficient of $u$ | Coefficient of $v$ | At least | |
|---|---|---|---|
| The constraint belonging to $x$ | |||
| The constraint belonging to $y$ |
The primal's constraint matrix has rows $6$, $2$ and $6$, $3$. Write the dual's constraint matrix.
This task has no paper form; do it on a device.
A primal program has $2$ variables and $4$ constraints besides non-negativity. How many variables does its dual have?
Answer:
A primal maximisation has $3$ constraints. Match each of its features to what it becomes in the dual.
| A dual variable | A dual constraint | The dual's objective coefficients | A minimisation | |
|---|---|---|---|---|
| One of the $3$ primal constraints | ||||
| A primal decision variable | ||||
| The primal's right-hand side | ||||
| The primal's maximisation |
Is this right: the dual has one variable for each primal constraint?
Select every statement that correctly translates a primal feature into its dual.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The primal maximises $9x + 3y$ subject to $3x + 5y \le k$ and $6x + 4y \le m$, $x, y \ge 0$. Its dual has variables $u$ and $v$. Fill in the dual's two constraints.
| Coefficient of $u$ | Coefficient of $v$ | At least | |
|---|---|---|---|
| The constraint belonging to $x$ | |||
| The constraint belonging to $y$ |
You can form the dual of a linear program and say what each of its variables and constraints came from. Say in your own words why a dual constraint is built from a column of the matrix rather than a row.
7. Your turn: how many constraints does the dual of a program with $5$ variables and $3$ constraints have?, step 2