Two of the three awkward cases have a signature you can see. An improving column with no positive entry means the objective is unbounded, and that column is the direction it escapes along, so the ray can be written down and evaluated. A zero reduced cost on a nonbasic column at optimality means a second optimal corner one pivot away, with every point of the edge between them optimal. Neither diagnosis is a statement about the shape of the region.
Core ideas
Both diagnoses are single columns of a single tableau. The hard part is that each one is easily confused with a statement about the region, and one of them is easily confused with degeneracy.
The ratio test on such a column has no candidates: every basic variable either holds still or grows as the entering variable rises. So the point x + t·d, where d puts one unit on the entering variable and -(column) on the basic ones, is feasible for every t ≥ 0, and the objective rises along it at the column’s rate. The word “unbounded” and the ray are the same fact.
At optimality every reduced cost is at or above zero. If one of them is exactly zero on a column that is not basic, pivoting that column in changes the basis and leaves the objective unchanged — rate zero times any step is zero. Two corners at the same value, and because the objective is linear, every point of the segment between them is optimal too.
A region can run on for ever and still have a best point, if the objective falls in the directions the region escapes along. Unboundedness is a property of one column of one tableau — of the region and the objective together. “Covering and Diet Models” made this distinction with a picture; here it is arithmetic.
The material
Reading a direction off a column, sampling an optimal edge, and the two confusions this page exists to prevent.
A feasible tableau in which some column j has z_j < 0 and a_ij ≤ 0 for every row i certifies that the objective is unbounded. The ray is x(t) = x + t·d where d_j = 1, d is -a_ij on the variable basic in row i, and zero on the other nonbasic variables.
The proof is the ratio test read the other way round. Row i says x_{B(i)} = b_i - a_ij·t, and with a_ij ≤ 0 that value never falls, so no row stops t growing. The objective changes at rate -z_j per unit of t, which is positive. A feasible point for every t with an objective that rises without limit is exactly what unboundedness means.
Take maximise x₁ + x₂ subject to x₁ - x₂ ≤ 1 and -x₁ + x₂ ≤ 1. One pivot brings x₁ in and leaves the tableau with x₂’s column at (-1, 0) and reduced cost -2: improving, and no positive entry.
The ray is d = (1, 1, 0, 0) from the point (1, 0) with s₁ = 0 and s₂ = 2. At t = 1 it is (2, 1) with z = 3; at t = 10, (11, 10) with z = 21; at t = 100, (101, 100) with z = 201. Every one of those points satisfies both constraints, which is what turns the word into a proof.
An optimal tableau with z_j = 0 for some nonbasic column j has alternative optima. Pivoting x_j in reaches a second optimal basis at the same objective value, and every point of the segment joining the two basic feasible solutions is optimal.
The word nonbasic is doing all the work in that definition. A basic column always has reduced cost zero — that is how the tableau is held — so a zero in a basic column is the normal state of affairs and means nothing at all. The signature is a zero where an improving column could have been and is not.
Take maximise 3x₁ + 2x₂ subject to 3x₁ + 2x₂ ≤ 12, x₁ ≤ 3 and x₂ ≤ 5. The objective is a positive multiple of the first constraint’s left-hand side, so it is parallel to that boundary. The method stops at (3, 3/2) with z = 12, and the nonbasic column s₂ has reduced cost 0.
One pivot on that column moves to (2/3, 5), also with z = 12. Sampling the segment between them at t = 1/4, 1/3, 1/2, 3/4 gives (29/12, 19/8), (20/9, 8/3), (11/6, 13/4) and (5/4, 33/8), and the objective at every one of them is exactly 12.
Reporting this honestly matters more than it looks. A solver that prints one optimal corner has told you the truth and not the whole truth: any point of that edge is equally good for the objective, which usually means a second criterion is free to choose among them. Naming the second corner costs one pivot.
Take maximise 2x₁ - x₂ subject to x₁ - x₂ ≤ 1 and x₁ ≤ 6. The region runs on for ever: raise x₂ as far as you like and both constraints stay satisfied. The objective nevertheless has a best value, 7 at (6, 5), because it falls in exactly the direction the region escapes along. The method stops with every reduced cost non-negative and there is no ray to report.
So the two claims come apart in both directions. A bounded region always bounds the objective; an unbounded region bounds it or does not, depending on the objective. This is why the diagnosis is made from a column and never from the drawing — and why, in practice, an unbounded objective on a model of something real is nearly always a missing constraint rather than an interesting discovery.
Alternative optima and degeneracy are confused constantly, and the distinction is one word. Alternative optima are a zero reduced cost on a nonbasic variable: a second corner, same value. Degeneracy is a zero value on a basic variable: one corner, two bases, and a pivot that may move nothing. Degeneracy, Cycling and Bland’s Rule is the second, and it is the case that can stop the method finishing at all.
Interactive
The ray read off a column with no positive entry, and the edge every point of which is optimal
Method
Look at the column, not the picture. Each of these verdicts is a pattern of signs in one column and a number in the objective row.
If the column improves the objective and has no positive entry, stop pivoting: the ratio test has no candidates and the diagnosis is unboundedness. Nothing about the tableau is wrong and there is no other column worth trying.
One unit on the entering variable, minus the column on each basic variable, zero elsewhere. Evaluate at two or three values of t, check each point against the original constraints, and report the objective at each — that is the difference between asserting unboundedness and exhibiting it.
Every basic column holds zero and tells you nothing. A zero on a nonbasic column means the optimum is not unique, and one pivot on that column produces the second corner.
Take two or three points strictly between the two optimal corners and evaluate the objective at each. Constant means the whole edge is optimal, which is the claim worth making to whoever asked the question.
“The objective is unbounded” and “the region is unbounded” are different statements, and only the first is a conclusion of the method. A region that runs on for ever can have a perfectly ordinary optimum.
Two small programmes, one signature each. In both cases the diagnosis is a column and the evidence is arithmetic on the original constraints.
The ray is not an extrapolation. Each of the three points was put back into both original constraints and satisfies them, so there is no largest feasible t and no largest objective value. That is a proof, and it is the reason this course evaluates rays instead of describing them.
On the second programme, notice where the zero is and where it is not. The basic columns x₁, x₂ and s₃ all hold zero in the objective row, and none of them is a signature — that is simply how a tableau is maintained. s₂ is nonbasic and holds zero, and that is the whole diagnosis. Getting these two cases the wrong way round is the single commonest misreading of a final tableau.
For a faded rehearsal, run the third preset in the lab: maximise 2x₁ - x₂ subject to x₁ - x₂ ≤ 1 and x₁ ≤ 6. The supplied first move is that the region is unbounded — check it by raising x₂ in either constraint. Now predict whether the method reports a ray, find the optimum and the corner it sits at, and say in one sentence why the two facts are consistent.
You should be able to recognise an improving column with no positive entry, write down and evaluate the ray it defines, spot a zero reduced cost on a nonbasic column at optimality, produce the second corner and sample the edge, and say why an unbounded region settles nothing about the objective.
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.