A nonbasic variable's entry in the objective row is a rate: how much the objective changes per unit of that variable, with every basic variable adjusting to keep the equations true. When no rate improves the objective, the corner has no improving edge and is globally optimal. The improvement a column actually delivers is that rate times the step the ratio test allows, which is why the steepest column is routinely not the best one.
Core ideas
The hard idea here is a distinction, not a formula: a rate per unit and a total improvement are different quantities, and the rule most textbooks teach optimises the first one.
For a nonbasic column j the objective-row entry z_j answers: if x_j rises by one unit and every basic variable adjusts to keep the equations true, how does z change? It changes by -z_j. So a negative entry is an improving direction for a maximisation, its size is the rate, and the whole row is a price list on the columns currently sitting at zero.
If every z_j ≥ 0 then no edge leaving this corner raises the objective, and “Convexity, and Why a Local Optimum Is Global” upgrades that from a statement about the corner to a statement about the region. This is the licence to stop, and it is the reason the method can finish without ever seeing most of the corners.
A rate of 9 on a column the ratio test stops after 4 units moves the objective by 36. A rate of 3 on a column that can run to 20 moves it by 60. Both figures come from one tableau of one real programme, and they are why “take the most negative entry” is a heuristic about rates rather than a rule about improvement.
The material
The rate interpretation, the rule almost everyone uses and what it costs, the stopping test, and the one adjustment a minimisation needs.
In a tableau at basis B, the reduced cost of column j is its objective-row entry z_j = c_Bᵀ B⁻¹ A_j - c_j. Every basic column has z_j = 0. For a maximisation, column j is improving when z_j < 0, and the rate at which z rises per unit of x_j is -z_j.
The formula is worth seeing even though you never need it to run the method, because it says where the number comes from: c_j is what one unit of x_j earns directly, and c_Bᵀ B⁻¹ A_j is what the basic variables have to give up to make room for it. The reduced cost is the difference, which is why it can be negative for a profitable column. “The Tableau as a Matrix Product” is where that expression is computed rather than quoted.
In the initial tableau of a ≤-only programme the basis is the slacks, c_B = 0, and the reduced costs are just -c_j. That is the familiar row of negated objective coefficients from The Simplex Tableau, and it is a special case rather than the definition.
Any improving column may enter. The rules in common use are: Dantzig’s rule, take the most negative reduced cost, breaking ties by lowest column index; Bland’s rule, take the lowest-index improving column; and greatest improvement, compute the step for every improving column and take the largest rate times step. Each terminates at the same optimal value when it terminates at all; they differ in the path and in how many pivots it takes.
Take maximise 5x₁ + 9x₂ + 3x₃ subject to 3x₁ + 2x₂ ≤ 20, x₁ + 3x₂ ≤ 12 and 4x₁ + 4x₂ + x₃ ≤ 20. At the origin the three rates are 5, 9 and 3, and the ratio test allows steps of 5, 4 and 20 respectively. So the products are 25, 36 and 60.
x₂ is the steepest column and moves z by 36. x₃ has a third of that rate and moves it by 60, which is the entire optimum of the programme. Dantzig’s rule takes x₂ and needs three pivots; greatest improvement takes x₃ and needs one.
Dantzig’s rule survives anyway, for a reason worth being honest about: computing the step for every improving column to find the greatest improvement costs a ratio test per column per pivot, and on a real problem that is more arithmetic than the extra pivots it saves. The rule is a cheap approximation to the thing you want, and this page exists so that you know which is which.
If every reduced cost in a feasible tableau satisfies z_j ≥ 0, the basic feasible solution it reads is an optimal solution of the programme. The test looks only at the current tableau, and its conclusion is about every feasible point.
The two halves of that sentence are worth separating. That no edge leaving this corner improves the objective is arithmetic on one row. That therefore no point of the region improves it is the convexity result from “Convexity, and Why a Local Optimum Is Global”. Quote the second half when you stop; a tableau alone only ever tells you about its own corner.
minimise cᵀx is maximise -cᵀx with the answer negated at the end, and that is exactly what the lab does. Take minimise 2x₁ - 3x₂ subject to x₁ + x₂ ≤ 8 and 2x₁ + x₂ ≤ 10. The internal objective is -2x₁ + 3x₂, so the objective row starts at (2, -3) — the original coefficients — and the stopping rule is still “no negative entry”. One pivot brings x₂ in at 8, the tableau reads 24, and the answer to the question asked is -24.
So nothing about the test flips. What flips is the sign of the number you report, and the discipline is to write down which convention you are in before the first pivot rather than to reconstruct it from the answer. A minimisation whose optimum is negative is the case where guessing goes wrong.
One last reading of the row: a zero reduced cost on a column that is not basic satisfies the stopping test and still means something. It says a pivot on that column would move to a different corner at the same objective value, so the optimum is not unique. “Unbounded and Alternative Optima in the Tableau” is where that signature is read.
Interactive
A reduced cost is a rate per unit; the improvement is that rate times the step the ratio test allows
Method
Read the whole objective row before choosing anything. The decision to stop is made from the same numbers as the decision where to go.
Basic columns always hold zero there and carry no information. What is left is one number per nonbasic column, and each is a rate per unit of that variable.
No improving edge leaves this corner, and a linear objective on a convex region has no local optimum that is not global. Report the point, the objective value, and that second sentence — the tableau on its own does not licence the claim.
Dantzig takes the most negative entry; Bland takes the lowest index; greatest improvement runs the ratio test on every candidate first. Name the rule, because the pivot count and the path depend on it and the optimum does not.
The rate told you the direction; only the step tells you how far. This is where a steep column with a short step gets found out.
They are equal, exactly, at every pivot. It is a free check on both the ratio test and the pivot arithmetic, and it is the arithmetic that makes the rate-versus-improvement distinction concrete rather than a slogan.
One programme, one tableau, four entering rules. The rates and the steps are both read from the starting tableau, so the comparison needs no pivoting at all.
Every rule reached 60. That is not luck and it is not a property of this programme: the optimum is a property of the feasible region and the objective, and an entering rule chooses a route to it. What the rule buys or costs is pivots, and here the spread is one against four.
The reason x₃ wins is visible in the ratio column. It appears in only one constraint, so only one row limits it, and that row lets it run to 20. x₂ earns nearly three times as much per unit and is cut off after 4 by the finishing row. A rate with no room to move is worth nothing, which is the sentence the whole lesson is built on.
For a faded rehearsal, take minimise 4x₁ - 8x₂ - 6x₃ subject to 3x₁ + 2x₂ + x₃ ≤ 13, 4x₁ + 2x₃ ≤ 17 and 2x₁ + 4x₂ ≤ 21. The supplied first move is that the objective row starts as (4, -8, -6) — the original coefficients, because the solver negated the objective on the way in — so x₁ is not a candidate at all. Work out the rate, the step and the product for x₂ and x₃, say which column Dantzig takes and which greatest improvement takes, and then check the pivot counts and the optimum of -69 in the lab.
You should be able to identify the improving columns in a tableau, apply any of the three entering rules and say which you used, verify rate × step against the change in z, state the stopping test with the theorem that licences it, and report a minimisation with the right sign.
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.