Every linear programme becomes Ax = b with all variables at or above zero by adding a slack to each ≤ row and subtracting a surplus from each ≥ row. The sign is not a convention: add a surplus instead and the variable is forced negative at every feasible point. Each new column measures something in the situation, which is why this is a modelling step and belongs here.
Core ideas
Four mechanical rules and one thing that is not mechanical: every column added has a meaning in the situation, and naming it is the work.
F + G ≥ 4 becomes F + G − e₁ = 4. At a point where the row holds, F + G is at least 4, so e₁ = F + G − 4 is at or above zero. Write + e₁ instead and e₁ = 4 − (F + G) is at or below zero at every feasible point, which breaks the sign restriction the whole form rests on.
The kiln's slack is unfired capacity, in pieces a day. The contract's surplus is deliveries beyond what was promised, in pieces. A column you cannot describe in a sentence about the pottery is a column you have not understood, and “Duality and Sensitivity Analysis” reads prices and ranges off exactly these columns.
A row is tight at a point exactly when its own added variable is zero there. That is what makes the corner table readable: a column of zeros is the list of rows used right up, and it is a computation rather than a claim about a diagram.
The material
The two signs and why they are forced, the columns a solver needs and the one it only needs for the search, and the negation that is usually forgotten.
A pottery fires pieces plain or glazed: F pieces fired and left plain and G pieces fired and glazed, both counted in pieces a day. A delivery contract wants at least 4 pieces, the kiln takes at most 10 firing units where a plain piece costs 2 and a glazed piece 1, and a licence allows at most 4 plain pieces. Plain costs 3 to make and glazed 5, and the pottery minimises cost.
A linear programme is in standard form when it reads maximise c·x subject to Ax = b and x ≥ 0. Every programme reaches it: add a slack to each ≤ row, subtract a surplus from each ≥ row, split each free variable into a difference of two non-negative ones, and replace a minimisation of f by a maximisation of −f.
The transformation is exact, not an approximation: the feasible points correspond one to one, and so do the objective values — up to the sign, which has to be put back.
The pottery in standard form carries three added columns with meanings: e₁, the pieces delivered beyond the four promised; s₂, the firing units the kiln has left; and s₃, the plain pieces the licence still allows. It carries a fourth column, a₁, which measures nothing about the pottery: an artificial variable, there to give the search a basis to start from, zero at every feasible point. The lab leaves it out of the table of corners for that reason and says how many it left out.
The region has four corners. Evaluating the three meaningful columns at each of them turns the phrase “tight if and only if the added variable is zero” into something to read rather than accept.
At (4, 0) the contract is met exactly and the licence is used right up, so two of the three rows are tight and the kiln has 2 firing units to spare. At (0, 10) the kiln is full and the contract is exceeded by 6 pieces. Reading down a column tells you which corners a row is tight at; reading across a row describes a corner completely.
Suppose the contract row had been written F + G + e₁ = 4. At (0, 10) that needs e₁ = −6, and at (4, 0) it needs e₁ = 0, so the only feasible points left are the ones where the contract is met exactly. The programme has silently acquired a new requirement, and every method that follows in this subject assumes x ≥ 0 and would carry the error forward without a murmur.
The engine maximises. So the pottery's cost is handed over as maximise −3F − 5G, the answer comes back as −12, and the page negates it to 12. That last step is the one that gets forgotten, and a cost reported as a negative number is a symptom worth recognising rather than a mystery. The lab prints both numbers with their signs for exactly that reason.
Flip the kiln row from a limit to a requirement — at least 10 firing units, perhaps because the kiln is uneconomic below that — and the form changes shape. That row now takes a surplus rather than a slack, the model needs a second artificial column, the number of added columns rises from four to five, and the cheapest plan moves from 12 at (4, 0) to 22 at (4, 2). One character in one relation, and both the columns and the answer move.
Interactive
Adding a surplus instead of subtracting it forces the variable negative
Method
Four steps, and a sentence per new column. The sentence is the part that makes this modelling rather than clerking.
a·x + s = b with s ≥ 0. Name what s is: unused hours, unfired capacity, shelf space still free — in the row's own unit.
a·x − e = b with e ≥ 0. Check the sign on a feasible point you know: if the variable comes out negative there, the sign is wrong and every later method will inherit the error.
Split a free variable into x⁺ − x⁻, both at or above zero. Convert a minimisation of f into a maximisation of −f, and write down now that the answer must be negated back.
One line per added variable saying what it measures. A column you cannot describe is either misunderstood or artificial — and an artificial column is zero at every feasible point, so it belongs in the search and not in the report.
The conversion is four lines. What takes the space is the meaning of each new column, which is the part “Duality and Sensitivity Analysis” reads.
Three added columns with meanings and one without: a₁ exists so that the search has somewhere to start, and it is zero at every feasible point, so a column of zeros beside the slacks would describe the algorithm rather than the pottery. That is why the lab tabulates three columns and says it left one out.
For a faded rehearsal, change the kiln row from ≤ 10 to ≥ 10. The supplied first move is the kind of column it now takes: a requirement takes a surplus, subtracted, so 2F + G − e₂ = 10. Work out how many added columns the form now has, which of them are artificial, and where the cheapest plan moves to — then check all three against the lab.
You should be able to convert a mixed-constraint minimisation to equalities with the right sign on every new variable, evaluate all of them at a given corner, say which rows are tight from the zeros, and negate the objective back.
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.