Every linear programme carries a second one with a variable for each of its constraints and a constraint for each of its variables. The transformation is not a table to memorise: each direction and each sign restriction is forced by the single requirement that the prices, multiplied through the rows and added up, must bound the objective. Take the dual twice and the programme you started with comes back.
Core ideas
The transpose is the easy half and nobody gets it wrong. The three ideas here are about the half that decides the directions and the signs.
A programme with m constraints and n variables has a dual with n constraints and m variables, and the pairing is fixed: the i-th row creates yᵢ, the j-th column creates the j-th dual constraint. The dual's objective coefficients are the primal's right-hand sides, and its right-hand sides are the primal's objective coefficients — the two vectors swap places.
Multiply each row by a number of its own and add the results. For that to be a valid bound on cᵀx, two things must hold: the multipliers must have signs that preserve the inequality when they multiply through, and the resulting combination must dominate c on every variable that can be positive. Those two requirements produce the whole table, row rules and column rules alike.
A dual variable's units are the objective's units divided by its row's units: pounds per hour for an hours row, pounds per kilogram for a kilograms row. A price whose units you cannot state out loud is a price you have paired with the wrong constraint, and that is the commonest construction error there is.
The material
One derivation, then the four row rules and the three column rules it produces, then the cases that are not the textbook case.
Given a maximisation max cᵀx subject to Ax ≤ b and x ≥ 0, its dual is the minimisation min bᵀy subject to Aᵀy ≥ c and y ≥ 0. The original programme is called the primal. There is one dual variable for each primal constraint and one dual constraint for each primal variable.
The dual variables are called prices throughout this course, because that is what their units make them: a quantity of objective per unit of right-hand side.
That definition is the clean case, and reading it as a recipe is how the mixed-form cases go wrong. So here is where it comes from, on the workshop programme above: three resources, two products, and the question of how large 3x1 + 5x2 could possibly be.
Every line of that is forced. y ≥ 0 is needed at the first step, because a negative multiplier would turn each ≤ into a ≥ and the sum would bound nothing. x ≥ 0 is needed at the second step, because (y1 + 3y3)x1 ≥ 3x1 requires x1 not to be negative. And the dual is a minimisation because a bound is only worth having as small as it can be made. The dual is not the transpose of the primal; it is the cheapest certificate the primal admits, and the transpose is what that turns out to look like.
Let the primal be a maximisation. Then each row contributes a price whose sign its direction fixes: a ≤ row gives y ≥ 0, a ≥ row gives y ≤ 0, and an = row gives a y with no sign restriction at all. Each column contributes a dual constraint whose direction its variable's sign fixes: x ≥ 0 gives a ≥ row, x free gives an = row, and x ≤ 0 gives a ≤ row.
If the primal is a minimisation every one of those turns over: now ≥ rows give y ≥ 0, ≤ rows give y ≤ 0, x ≥ 0 gives a ≤ dual row, and the dual is a maximisation.
Each rule is the derivation above run on that shape. A ≥ row in a maximisation is a floor; relaxing a floor cannot improve a maximum, so its price cannot be positive. An = row binds in both directions, so nothing restricts the sign of its price. A free variable can be made negative, so the domination step must hold as an equality rather than as an inequality.
The primal reads max 3x1 + 5x2 subject to x1 ≤ 4 (cutting), 2x2 ≤ 12 (glazing), 3x1 + 2x2 ≤ 18 (assembly), x ≥ 0. Its dual reads min 4y1 + 12y2 + 18y3 subject to y1 + 3y3 ≥ 3 (the x1 column), 2y2 + 2y3 ≥ 5 (the x2 column), y ≥ 0.
Read the first dual row aloud: the cutting and assembly capacity that one unit of x1 consumes must be worth at least the 3 that unit earns. That sentence is the dual constraint, and it is why the direction is ≥ rather than ≤.
A programme with only ≤ rows and only non-negative variables is the one every textbook prints, and it is the one that teaches least, because in it the rules are invisible. The lab ships a preset with a cap, a floor, a quota and a variable free to go negative precisely so that all three of the awkward rules have to be applied at once.
max 4u + 3v subject to 2u + v ≤ 10 (capacity), u − v ≥ 1 (balance), u + v = 4 (quota), u ≥ 0 and v free. The dual is min 10y1 + y2 + 4y3 subject to 2y1 + y2 + y3 ≥ 4 (the u column) and y1 − y2 + y3 = 3 (the v column), with y1 ≥ 0, y2 ≤ 0 and y3 free.
Three separate rules did that. The ≥ row turned y2 non-positive, the = row left y3 unrestricted, and the free v turned its dual row into an equality. The lab prints the sentence that fixed each one on the link joining the pair, and the programme solves to z* = 18 at u = 6, v = −2 — a negative variable at the optimum, which is what declaring it free was for.
Take the dual of that dual and the original programme comes back, sign for sign and direction for direction. That is not a special case of the tidy shape: it is a property of the four rules, and it holds on the minimisation, on the floor, on the quota and on the free variable alike. The lab's last control runs the construction twice and reports whether the result agrees with what it started from — and on every preset it does.
min 2x + 3y subject to x + y ≥ 4 (protein), x ≤ 3 (supply), y ≥ 1 (oats), x, y ≥ 0 has the dual max 4y1 + 3y2 + y3 subject to y1 + y2 ≤ 2 (the x column) and y1 + y3 ≤ 3 (the y column), with y1 ≥ 0, y2 ≤ 0, y3 ≥ 0.
Everything has flipped and nothing has been memorised. In a minimisation the requirement to be met is the ≥ row, so that is the row with a non-negative price; the ≤ row is now the cap whose relaxation cannot help, so its price is non-positive; and the dual constraints say that what a unit is worth must not exceed what it costs.
Interactive
the dual built pairing by pairing, and the dual of the dual returning the primal
Method
Count first, then transpose, then apply one rule per row and one per column. The units are the last step and they catch the pairing errors.
m rows means m dual variables; n variables means n dual constraints. If your dual has a different count in either direction you have paired a price with a variable, which is the error the count catches for free.
The primal's b becomes the dual's objective coefficients and the primal's c becomes the dual's right-hand sides. A maximisation becomes a minimisation and the other way round.
In a maximisation: ≤ gives y ≥ 0, ≥ gives y ≤ 0, = gives y free. Reach for the reason rather than the table — a floor you would like to relax cannot be worth a positive amount — because the reason survives a minimisation and the table does not.
The j-th dual row has the j-th column of A as its coefficients and cⱼ as its right-hand side. A non-negative variable gives ≥ in a maximisation's dual; a free variable gives =.
State each price's units aloud: objective units per unit of that row. Then run the construction on what you have written. If it does not return the programme you started from, the error is in the sign or direction of whichever row or column has changed.
Nothing below is taken from a table. The two dual constraints appear as the conditions under which the combination of rows is a bound at all, and the objective appears as the wish to make that bound small.
The two needs annotations are the whole content of the sign rules. Drop y ≥ 0 and the first line stops being an inequality in the right direction; drop x ≥ 0 and the domination step stops being valid. Everything else is bookkeeping.
For a faded rehearsal, do the same on the bakery: max 5x + 4y subject to 6x + 4y ≤ 24, x + 2y ≤ 6, x + y ≥ 2, x, y ≥ 0. The supplied first move is that the third row, being a floor in a maximisation, gets the price the derivation cannot allow to be positive. Write both dual rows, state the sign of all three prices, and then check your answer against the lab's bakery preset before opening the quiz.
If you want the harder rehearsal, take the dual of the minimisation preset and then take the dual of your answer. Everything reverses twice, which is the only way to be sure you applied rules rather than recalled a shape.
You should be able to take the dual of a maximisation and of a minimisation, apply the ≥ and = row rules and the free-variable column rule from the reason rather than from recall, state the units of every price, and take the dual of your own answer to get back what you started with.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.