With the entering column fixed, the question is how far the entering variable can rise before some basic variable hits zero. Row i limits it only when its entry in the column is strictly positive, and then the limit is b_i ÷ a_ij. The smallest of those limits is the step, and the row that produced it leaves the basis. A row with a zero or negative entry imposes nothing, and a column with no positive entry at all is a column nothing limits.
Core ideas
One idea, and it is a feasibility argument rather than an optimisation one: the objective plays no part in this lesson at all.
Let x_j rise from zero to θ and hold the other nonbasic variables at zero. Row i says x_{B(i)} = b_i - a_ij·θ, so each basic variable moves at the rate given by its entry in the entering column. That single formula is the whole lesson: everything else is reading the sign of a_ij.
If a_ij > 0 then b_i - a_ij·θ falls, and it reaches zero at θ = b_i ÷ a_ij. If a_ij = 0 the basic variable does not move, and if a_ij < 0 it rises. Neither of those two can ever go negative, so neither restricts θ, and including them in the minimum is not a harmless extra check — it produces a smaller-looking ratio that is meaningless.
Take θ to be the smallest of the eligible ratios. At that value the basic variable of the winning row is exactly zero, so it can be dropped from the basis and x_j put in its place — which is what pivoting on that row does. Go further and that variable is negative and the point has left the region.
The material
The one-line derivation, the two kinds of row that impose nothing, and what a column with no positive entry is telling you.
The entering column is chosen by the objective and Reduced Costs and the Optimality Test is where that choice comes from. Take it as given here: column j is coming in, every other nonbasic variable stays at zero, and x_j is going to rise from zero to some θ ≥ 0.
Row i of the tableau reads x_{B(i)} + a_ij·x_j = b_i once the other nonbasic terms are dropped, so x_{B(i)} = b_i - a_ij·θ. Feasibility is the requirement that every one of those stays at or above zero, and that is a set of inequalities in the single unknown θ.
With entering column j and a feasible tableau, the ratio of row i is b_i ÷ a_ij, defined only for rows with a_ij > 0. The step is the smallest such ratio, and the leaving variable is the basic variable of a row achieving it. If no row has a_ij > 0, the ratio test has no candidates and x_j is unlimited.
Let θ* = min { b_i ÷ a_ij : a_ij > 0 }. Then every basic variable stays at or above zero for 0 ≤ θ ≤ θ*, and some basic variable is negative for every θ > θ*.
Split the rows by the sign of a_ij. If a_ij ≤ 0 then -a_ij·θ ≥ 0 for θ ≥ 0, so b_i - a_ij·θ ≥ b_i ≥ 0 and that row never complains. If a_ij > 0 then b_i - a_ij·θ ≥ 0 is exactly θ ≤ b_i ÷ a_ij.
So the feasible values of θ are the intersection of the intervals [0, b_i ÷ a_ij] over the positive entries, which is [0, θ*]. For θ > θ* the row achieving the minimum has b_i - a_ij·θ < 0, so some basic variable is negative. Both halves follow from the sign split and nothing else.
□
A zero entry means the pivot leaves that row alone — the plants tableau’s row 1 was untouched by the pivot in “The Simplex Tableau” for exactly this reason — and its basic variable is unchanged however far x_j goes. A negative entry means b_i - a_ij·θ grows with θ: raising the entering variable makes that basic variable larger, and a variable getting larger is not about to become negative.
Neither row is excluded by convention or for tidiness. A negative entry would produce a negative ratio, which looks like the smallest of the set and is not a step at all; a zero entry would produce a division by zero. Writing the ratio column with the ineligible rows struck out and the reason beside them is the habit that makes this reliable.
The starting tableau has rows s₁, s₂, s₃ with right-hand column 4, 12, 18, and column x₂ is (0, 2, 2). Row 1 has a zero entry: no limit, s₁ will not move. Row 2 has 2, so its ratio is 12 ÷ 2 = 6. Row 3 has 2, so its ratio is 18 ÷ 2 = 9.
The minimum is 6, row 2 leaves, x₂ enters at 6, and the new point is (0, 6). Row 3's basic variable s₃ drops from 18 to 18 - 2(6) = 6, and s₁ stays at 4 — both exactly as b_i - a_ij·θ predicts.
Pivot on row 3 instead, taking the ratio 9 rather than 6. Then x₂ = 9, and s₂ = 12 - 2(9) = -6. The tableau is still a correct system and its bottom-right entry reads 45, higher than the true optimum of 36, because it is the objective value at a point outside the region: (0, 9) uses 18 of plant B's 12 hours. A negative right-hand entry is the signature, and the constraint that has been broken is the one whose slack went negative.
On maximise x₁ + x₂ subject to x₁ - x₂ ≤ 4 and x₁ - 2x₂ ≤ 6, one pivot brings x₁ in and then the column of x₂ has no positive entry anywhere. The ratio test has no candidates, and the honest reading is not that the tableau is broken: it is that x₂ can rise for ever with every basic variable staying non-negative, so the objective is unbounded. Unbounded and Alternative Optima in the Tableau turns that column into an explicit ray.
The last case is a tie: two rows achieving the same minimum. Both are legal choices and the step is the same either way, but whichever row you do not take is left with a basic variable at zero. That is degeneracy, it is the subject of Degeneracy, Cycling and Bland’s Rule, and it is the one place where the tie-break rule turns out to matter.
Interactive
Only the strictly positive entries limit the step, and the smallest of those limits is it
Method
Write the whole column down, including the rows that do not qualify. The ones you strike out are the ones that cause the error.
Two columns of numbers, one row per constraint. Everything in this lesson is a comparison between those two, and the rest of the tableau is not needed.
Strictly positive: eligible. Zero: no limit, the basic variable does not move. Negative: no limit, the basic variable grows. Write the reason next to the struck-out rows rather than just omitting them.
b_i ÷ a_ij for each eligible row. The smallest is the step θ, and the row achieving it is the leaving row. On a tie, either row is legal — note that it happened, because the next basis will be degenerate.
Every entry of the new right-hand column should be at or above zero. A negative one means an ineligible row was included or the minimum was taken the wrong way round, and the point is now outside the region.
Each old basic variable should have moved by exactly its entry in the entering column times the step. That check is independent of the pivot arithmetic, so it catches a slip in either one.
Column x₂ is entering. Three rows, one ineligible, and two candidates whose ratios differ by three.
The tableau after the override is not wrong arithmetic. Every row operation was legal and the system it represents is equivalent to the original one. What it has stopped doing is describing a point of the feasible region, and the -6 in the right-hand column is the announcement. The 45 is the objective evaluated at (0, 9), which is a real number about an unreal plan.
Note which constraint broke. s₂ is the slack of plant B hours, so a negative s₂ is that row and no other, by exactly 6 hours. This is why a slack is worth naming when the programme is written: the violation reads itself.
For a faded rehearsal, take the tableau at (0, 6) from “The Simplex Tableau” and run the ratio test on column x₁, whose entries are (1, 0, 3) against a right-hand column of 4, 6, 6. The supplied first move is that row 2 is the ineligible one this time. Compute both ratios, name the leaving variable, predict the new point from b_i - a_ij·θ before pivoting, and then pivot and compare.
You should be able to write the ratio column with the ineligible rows marked and explained, take the step, name the leaving variable, predict every new basic value from b_i - a_ij·θ, and say what a column with no positive entry means.
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.