Moving what a basic activity earns changes the total but not the corner, until the coefficient crosses a value at which some reduced cost hits zero. Moving what a nonbasic activity earns changes nothing at all until it has improved by exactly its reduced cost. Two different ratio tests, and which one applies depends only on whether the activity is in the basis — so the first question to ask about a coefficient is whether the plan currently makes any of that product.
Core ideas
One hard idea: the answer to a corner problem does not care about the objective until a sign changes. The rest is keeping the two cases apart.
The optimal plan is a vertex, and which vertex is best is decided by the signs of the objective-row entries rather than by their sizes. Move a coefficient a little and every one of those signs is unchanged, so the same vertex is still best and only the total moves. The answer changes at one value, not gradually.
If xⱼ is basic then cⱼ appears in c_B, so changing it changes every entry of c_BᵀB⁻¹A − c. Each nonbasic column gives one bound on the change, from its reduced cost divided by its entry in xⱼ's row of the tableau, and the binding ones are the two ends. Inside the interval the plan is unchanged and z* moves by Δcⱼ times how much of xⱼ the plan makes.
If xⱼ is not in the basis its reduced cost is yᵀaⱼ − cⱼ > 0, and only cⱼ's own entry changes when cⱼ moves. So the range is one-sided: anything downwards, and upwards exactly as far as the reduced cost, at which point the column is worth bringing in. Below that value nothing changes — not the plan, not the total, not any other range.
The material
Why the basis is the deciding question, what each ratio test looks like, and what changes at the end of each kind of interval.
The reduced cost of column j is yᵀaⱼ − cⱼ, the objective-row entry over that column at the optimum. For a maximisation it is zero on every basic column and non-negative on every other one.
Read as a sentence it is the amount by which what one unit of activity j would consume, valued at the current prices, exceeds what it earns. A nonbasic activity is not made because that number is positive.
Right-hand-side ranging asked how far the data could move while the basis stayed feasible. This lesson asks how far it can move while the basis stays optimal. Those are different questions about different halves of the tableau: b appears only in the right-hand column, and the objective coefficients appear only in the objective row. Which is why one is a ratio test down a column and the other is a ratio test along a row.
Let the simplex method finish with basis B, plan x, prices y and reduced costs rⱼ = yᵀaⱼ − cⱼ.
If xⱼ is basic, occupying row p of the tableau, then the basis stays optimal for cⱼ + Δ exactly while rₖ + Δ·(row p of B⁻¹A)ₖ ≥ 0 for every nonbasic k — one bound per nonbasic column, Δ bounded above by the smallest rₖ / (−a_pk) over negative entries and below by the largest over positive ones. Inside, the plan is unchanged and z* becomes z* + Δxⱼ.
If xⱼ is nonbasic, the basis stays optimal exactly while Δ ≤ rⱼ, with no lower bound at all. Inside, neither the plan nor z* changes.
c1 = 8 is basic, and the plan makes 2 of it. Its range is 5 ≤ c1 ≤ 10. Raise it to 9 and the plan does not move at all: still (2, 6, 0), and the total goes from 46 to 46 + 1(2) = 48. That is the whole of the inside of a basic range — a different number and the same decision.
At c1 = 10 something exact happens: a reduced cost is precisely zero, and (4, 2, 0) earns 50 as well. Both corners are optimal and one pivot moves between them. Past 10 the answer really is (4, 2, 0) and the plan has changed once, at a value the lab prints.
c3 = 3 is nonbasic with a reduced cost of 4, so its range is c3 ≤ 7. Raise it from 3 to 6 and nothing whatever happens: the plan is still (2, 6, 0) and the total is still 46. The third product got twice as profitable and it is still not worth making.
At c3 = 7 the reduced cost is exactly zero and (4, 0, 2) also earns 46. At c3 = 8 the answer moves: (4, 0, 2) with a total of 48. So the improvement needed before anything happens is exactly the reduced cost, and the range is one-sided because making the product even less profitable cannot make it worth starting.
Two things about that one-sidedness are worth saying out loud. An interval unbounded below is a complete answer, not a missing number — the lab prints it as such. And the value at which a nonbasic coefficient matters is cⱼ + rⱼ, which is yᵀaⱼ: the coefficient becomes interesting exactly when it reaches what the activity's ingredients are already worth. That is the next lesson's question asked about a column already in the model.
So the answer to any single stated change comes in two parts, and the commonest error is to give only one of them. Inside a basic range: the plan does not change and the value does, by Δcⱼ times the amount made. Inside a nonbasic range: neither changes. At the end of either: two plans tie, both optimal, one pivot apart. Past the end: the plan has changed, and the old range no longer describes anything.
min 2x + 3y subject to x + y ≥ 4, x ≤ 3, y ≥ 1 costs 9 at (3, 1). The first ingredient may cost anything from 0 to 3: at c = 3/2 the total is 15/2 with nothing tied, and at either end of the interval two plans tie, costing 3 at the bottom and 12 at the top.
The second ingredient's range is 2 ≤ c with no upper end, and at c = 2 the total is 8. Both are ranges in exactly the sense above; what has changed is only that the solver negates a minimisation on the way in, so a coefficient handed to it has to be negated too. A kit that skipped that would print intervals that look like intervals and endpoints that are not endpoints.
Interactive
the range of one objective coefficient, and the single pivot at its end
Method
Ask the basis question first. Everything after it depends on the answer, and the two computations look alike on the page.
If it is in the basis, you are ranging along its row of the tableau against every nonbasic column. If it is not, the answer is its reduced cost and you are nearly done. Getting this backwards produces an interval of the wrong shape, which is hard to notice.
The range is everything downwards and rⱼ upwards. Inside it, nothing changes at all — say so explicitly, because the expected answer is that a better coefficient must do something.
One bound per nonbasic column: that column's reduced cost divided by its entry in this activity's row. Negative entries bound the increase, positive entries bound the decrease, and a side with no entries at all is unbounded.
Does the plan move, and does the value move? Inside a basic range only the value moves, by Δcⱼ times how much is made. Inside a nonbasic range neither moves. At an endpoint two plans tie and both are optimal.
The same programme, the same tableau, two coefficients, and two computations with nothing in common but the object they are read off.
The trap line in case 2 is the error worth seeing once. The third column of this programme is (1, 2, 0), and reading (1, 1, 0) off the wrong row gives a reduced cost of 2 and a range ending at 5 — an interval that looks perfectly reasonable and that predicts, at c3 = 6, a change which does not happen. Nothing about the wrong answer announces itself; only checking the column against the original model does.
Notice also that c3 + r3 = 7 = yᵀa3: the coefficient starts to matter exactly when it reaches what the activity's ingredients are already worth at the current prices. That is the same test the next lesson applies to a column that is not in the model at all.
For a faded rehearsal, range c2 on the same programme. The supplied move is that x2 is basic, so this is the ratio test along x2's row. Find the interval, then answer three questions before checking: what happens at c2 = 6, what happens at c2 = 8, and which second plan ties there.
You should be able to decide which of the two computations applies from the basis alone, produce the interval either way — including a one-sided one — compute the new total inside a basic range, and describe what happens exactly at an endpoint: two plans, both optimal, one pivot apart.
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.