A column that is not in the model is priced by what it earns less what it would consume at the prices you already have, and a row that is not in the model is tested by evaluating it at the plan you already have. Both questions are answered from the final tableau, and only a favourable price or a broken rule costs anything further. A profitable product can still be the wrong thing to make, and that is the point of the lesson.
Core ideas
One hard idea, which is that profit is not the test. The second panel is the same trick applied to a row instead of a column.
The prices already say what each resource is worth in the plan you have. A new activity consuming aₙₑw would take yᵀaₙₑw worth of that out of other activities, so the only figure that matters is cₙₑw − yᵀaₙₑw. Positive means it pays for what it displaces; negative means making it would lower the total, however profitable it looks on its own.
A proposed constraint either the current plan satisfies or it does not. If it does, the plan is still feasible and still optimal — adding the rule changes nothing, costs nothing and needs no arithmetic beyond the substitution. If it does not, the current basis is still a basis of the new problem and only feasibility has to be restored.
Both questions are one dot product against numbers already computed. The work only begins when a column prices favourably — one pivot — or a row is broken, which is the next lesson. Deciding cheaply whether to do any work is most of what sensitivity analysis is for.
The material
The pricing formula and the two ways it comes out, the substitution test for a row, and why a rule can only ever cost.
For a proposed activity with column aₙₑw and objective coefficient cₙₑw, its reduced cost at the current optimum is cₙₑw − yᵀaₙₑw, where y is the price vector already in the final tableau. For a maximisation the activity is worth introducing exactly when that number is positive.
Nothing about this formula requires the column to have been in the model when it was solved. The prices are properties of the basis, and any column at all can be valued against them.
That is the same expression as the objective-row entry over a column that is in the model, which is why this lesson needs no new machinery. What is new is the use: a product nobody has ever made, a machine nobody has bought, a contract nobody has signed — all of them can be valued before anything is committed, from numbers a single solve already produced.
The workshop's prices are y = (0, 3/2, 1): cutting is worth nothing, glazing 3/2 an hour, assembly 1 an hour. Propose a third product taking one hour of each and earning 4.
It would consume (0)(1) + (3/2)(1) + (1)(1) = 5/2 worth of what the plan is already short of, and it earns 4, so its reduced cost is 4 − 5/2 = 3/2 a unit. It enters, and a single pivot — not a re-solve — takes the total from 36 to 39.
Propose instead a product taking one hour of cutting, two of glazing and three of assembly, also earning 4. Now it consumes (0)(1) + (3/2)(2) + (1)(3) = 6, and its reduced cost is 4 − 6 = −2.
Making it would cost 2 a unit. Every unit of it would displace work worth 6 to make 4, and the plan you already have is still optimal with this column present in the model. Profit is not the test. Profit beyond what the ingredients are already worth is the test, and the break-even point for this column's lighter cousin is at earnings of exactly 5/2, where the reduced cost is zero and the lab reports that it does not enter.
The reason this is the misconception worth naming is that the wrong answer is the one a reader arrives at by a perfectly sound-sounding argument: the product makes money, so make it. It does make money, and it makes less money than what it would have to stop making. The prices are what convert that sentence into arithmetic, and they are already on the screen.
The second question has a shorter answer. A proposed constraint is a statement about plans, so evaluate it at the plan you have. If it holds, nothing at all follows: the plan is still feasible for the enlarged problem and still optimal, since adding a constraint cannot create a better plan. If it fails, the plan is no longer feasible, and the work of restoring feasibility is the next lesson's.
The workshop's plan is (2, 6). The proposed rule x1 + x2 ≤ 5 reads 8 there, so it is broken by 3, and something has to change; the lab reports that restoring feasibility from the tableau in hand takes two pivots and lands at 25.
The proposed rule x1 + x2 ≤ 10 also reads 8, which leaves 2 spare. It is satisfied, so it changes nothing whatever: no pivot, no re-solve, and the same plan and the same total. That is a real answer to a real question, arrived at by one substitution.
And a rule can only ever cost. A constraint removes points from the feasible region and never adds any, so the new optimum is at most the old one: 36 becomes 25 in the first case and stays 36 in the second. If a proposed constraint appears to raise the objective, the arithmetic is wrong. That is a useful check, and it is the mirror image of the one for a new column, which can only ever help.
One warning about the row test. It says whether the plan you have is still feasible, and that is all. A satisfied rule is genuinely free; a broken rule tells you that work is needed but not how much, and the amount by which it is broken is not the amount the objective will fall. On the workshop the rule is short by 3 and the objective falls by 11.
Interactive
what a product you have never made is worth, and whether a new rule matters
Method
Take the prices and the plan off the tableau first. Both questions are then one line each.
A new product, machine or contract that consumes resources is a column, with one entry per existing constraint. A new rule, limit or requirement is a row, with one entry per existing activity. They are answered by different tests and confusing them is the first thing to rule out.
yᵀaₙₑw, one product per row, added up. Then subtract that from what it earns. Positive for a maximisation means it enters; zero means it is exactly break-even and the plan you have is still optimal.
Substitute and compare with the proposed right-hand side. Satisfied means nothing follows at all, and that is the answer rather than a step towards one. Broken means the plan has to change, and the shortfall is not the size of the change in the objective.
A favourable column costs one pivot, performed from the tableau you already have. A broken row costs a dual simplex run from the same tableau. Neither costs a fresh solve, and most proposals cost nothing at all.
Everything below comes from a single finished solve of the workshop. Nothing is re-solved until the last two lines, and those are one pivot and two pivots respectively.
Column B is the one to keep. It earns money, it earns the same money as column A, and it is the wrong thing to make — because it displaces 6 worth of glazing and assembly to produce 4. Nothing about the model changed between A and B except the recipe.
Notice too that the row test gives no estimate of the damage. Row P is short by 3 and the objective falls by 11. Those two numbers are not related by anything simple, and the lesson's answer to how far it falls is the next lesson's method.
For a faded rehearsal, use the three-activity programme, whose prices are y = (3, 2, 0) and whose plan is (2, 6, 0) at 46. The supplied move is that a proposed fourth activity taking one unit of each resource consumes 3 + 2 + 0 = 5. Decide whether it is worth making if it earns 6, if it earns 5, and if it earns 4; then propose the rule x1 + x2 + x3 ≤ 7 and say whether it bites before you check.
You should be able to price a proposed activity against the current prices and decide, evaluate a proposed rule at the current plan and decide, say what each answer costs — nothing, one pivot, or a dual simplex run — and state without checking which direction the objective can move in each case.
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.