Lesson · Linear Programming Models · Standard form and corners

Basic Solutions and Corners

With m equalities in n + m variables, choose which n variables are zero and solve the rest by row reduction: the result is a basic solution. One with no negative entry is a basic feasible solution, and the basic feasible solutions are exactly the corners. That is what replaces the drawing, and there are at most C(n + m, m) bases to try.

Open the interactive lesson Practice

m equalities, n + m variables choose n of them to be zero, solve the rest by row reduction no negative entry → basic FEASIBLE solution = a corner some entry negative → a crossing outside the region the columns dependent → two parallel lines, no point at all bases to try: C(n + m, m) here C(5, 3) = 10

A basis, and the four things it can turn out to be

Core ideas

What this lesson establishes

The hard idea is the substitution of a computation for a picture. Everything else is the four outcomes that computation can have.

Choosing which variables are zero is choosing a point

Set n of the n + m variables to zero and the equalities pin the rest down. Each zero variable is a line the point lies on: a decision column set to zero gives an axis, a slack column set to zero gives its row's boundary. Two zeros in two dimensions is two lines, and two lines usually cross somewhere.

A basic solution is a corner exactly when nothing came out negative

The crossing of two boundary lines need not satisfy the other rows. When a basic variable solves to a negative value, the point violates that variable's own sign restriction and lies outside the region. Rejection is arithmetic on a solved value, not a glance at a diagram.

The count is why an algorithm is needed

There are at most C(n + m, m) ways to choose a basis, which is 10 for two decisions and three rows and grows far faster than any picture. Enumerating them all is possible here and hopeless at twenty variables, which is exactly the gap “The Simplex Method” exists to close.

The material

Bases, basic solutions, and which of them are corners

What a basis is, the four ways one can turn out, and the count that makes enumeration untenable.

Take the small workshop again, in equality form: C chairs and T tables, three packing rows with slacks s₁, s₂ and s₃. Three equalities, five variables. Choosing two of the five to be zero leaves three unknowns and three equations, which row reduction settles.

maximise 3C + 5T C + s₁ = 4 the carpentry shop 2T + s₂ = 12 the finishing shop 3C + 2T + s₃ = 18 the assembly line C, T, s₁, s₂, s₃ ≥ 0

Definition · Basic and basic feasible solutions

For Ax = b with m rows and n + m variables, choose m columns as the basis and set the other n variables to zero. If the chosen columns are independent, the equations determine the basic variables uniquely, and the result is a basic solution. A basic solution with no negative entry is a basic feasible solution.

A basic solution with a basic variable equal to zero is called degenerate: more boundaries pass through that point than the dimension requires, so several different bases describe it.

Every one of the ten choices is worth seeing once. Five of them are feasible and they are exactly the five corners of the picture; three solve to points outside it; and two are not points at all.

zero variables lines they put the point on point kind s₂, s₃ 2T = 12 with 3C + 2T = 18 (2, 6) feasible s₁, s₃ C = 4 with 3C + 2T = 18 (4, 3) feasible s₁, s₂ C = 4 with 2T = 12 (4, 6) infeasible T, s₃ T = 0 with 3C + 2T = 18 (6, 0) infeasible T, s₂ T = 0 with 2T = 12 — singular T, s₁ T = 0 with C = 4 (4, 0) feasible C, s₃ C = 0 with 3C + 2T = 18 (0, 9) infeasible C, s₂ C = 0 with 2T = 12 (0, 6) feasible C, s₁ C = 0 with C = 4 — singular C, T C = 0 with T = 0 (0, 0) feasible

What rejects a basic solution

(4, 6) is where the carpentry boundary meets the finishing boundary, and it scores 42 against the optimum's 36. It is rejected because solving its basis gives s₃ = −6: the assembly row is over by six hours, recorded as a negative slack. (0, 9) scores 45 and is rejected by s₂ = −6 in the same way. These are the crossings a picture discards by eye, and here discarding them is a number with a sign.

That matters because the picture is about to go away. A negative entry is available in any number of variables; “outside the shaded region” is available in two.

Two of the ten are not points

Setting T and s₂ to zero asks for the intersection of T = 0 and 2T = 12, which are parallel and never meet, and row reduction stops at rank 2 out of 3. The lab reports that as two parallel lines, named, rather than as “the matrix was singular” — the geometry is the explanation and the rank is the symptom.

Degeneracy, and why the counts stop matching

Example · Three boundaries through one corner

Push the assembly line from 18 hours to 24. Now C = 4, 2T = 12 and 3C + 2T = 24 all pass through (4, 6). Three different bases solve to that same point, each with a basic variable equal to zero, and the picture has four corners while the enumeration reports six basic feasible solutions. The extra ones are not extra points; they are extra descriptions of one point.

The count itself is the argument for an algorithm. C(n + m, m) is 10 here and the ten fit in a table. It is the number of bases to try, it comes from “Pascal's Triangle”, and it grows fast enough that a programme with ten decisions and ten rows has 184,756 of them. Enumerating bases is a definition of a corner, not a method for finding the best one.

Interactive

Every basis, solved and classified

A basic feasible solution is a corner; a basic solution need not be

Walk the bases while the picture is still there to check them

Choosing which variables are zero and solving the rest by row reduction gives a basic solution; one with no negative entry is a corner. Every basis here is reduced by the same row reduction the elimination lessons used, with the trace for whichever one you pick printed underneath. Push the assembly line up until three boundaries meet at one point and watch several bases collapse onto one corner.

bench hours available in the carpentry shop—

hours available in the finishing shop—

hours available on the assembly line—

which basis to reduce, step by step—

——

Method

Enumerating the basic solutions

Standard form first, then the choosing, then the classification. The classification is where the picture stops being needed.

Put the programme in equality form and count

m rows and n + m variables after the slacks and surpluses. Write the count C(n + m, m) down before starting: it tells you how long the enumeration is and whether it is worth doing at all.

Choose which variables are zero, and name the lines that puts you on

A decision column at zero is an axis; a slack column at zero is that row's boundary. Naming the two lines is what lets you predict the point before solving for it.

Solve the remaining system by row reduction

If the reduction does not reach full rank, the chosen columns are dependent: the two lines are parallel and there is no basic solution for this choice at all.

Classify from the solved values, not from the diagram

No negative entry is a basic feasible solution, which is a corner. A negative entry is a crossing outside the region. A zero among the basic variables is degenerate, and several bases will describe the same point.

Bases, corners and the count

Score 0 / 0

Choose the answer you can justify.

One basis, reduced by hand, and the entry that rejects it

The basis {C, T, s₃} sets s₁ and s₂ to zero, which puts the point on C = 4 and 2T = 12. The reduction is three rows wide and the sign at the end is the whole verdict.

the system C + s₁ = 4 2T + s₂ = 12 3C + 2T + s₃ = 18 the basis {C, T, s₃}, so s₁ = 0 and s₂ = 0 C T s₃ = operation 1 0 0 4 0 2 0 12 divide row 2 by 2 3 2 1 18 row 3 − 3(row 1) 1 0 0 4 0 1 0 6 0 2 1 6 row 3 − 2(row 2) 1 0 0 4 C = 4 0 1 0 6 T = 6 0 0 1 −6 s₃ = −6 verdict s₃ = −6 is negative, so (4, 6) is a basic solution that is NOT a corner: the assembly row is over by 6 hours objective there 3(4) + 5(6) = 42, which is more than the optimum 36

This is the crossing that would have won. It is rejected by one negative entry in a solved system, and that is the point of the whole lesson: at three variables there is no diagram to look at, and the rejection has to be arithmetic. The optimum 36 at (2, 6) comes from the basis {C, T, s₁}, whose solved values are all at or above zero.

For a faded rehearsal, take the basis {C, s₁, s₂}, which sets T and s₃ to zero. The supplied first move is the two lines: T = 0 is the horizontal axis and s₃ = 0 is the assembly boundary 3C + 2T = 18. Predict the point, reduce the system by hand, say which entry rejects it, and compare the objective value there with 36 before opening the lab's trace.

Common mistakes

Assuming every basic solution is a cornerThree of the ten here solve to points outside the region, and two of those score better than the optimum. What rejects them is a negative entry in the solved system, and that is the only form of rejection available once there is no diagram to look at.

Reading “singular” as a failure of the arithmeticDependent basis columns mean the two lines the zeros put you on are parallel. T = 0 and 2T = 12 never meet, so there is nothing for the reduction to find. The geometry is the explanation; the rank is only how the reduction reports it.

Treating the count of bases as a methodC(n + m, m) is 10 for this workshop and 184,756 for ten decisions and ten rows. Enumerating bases defines what a corner is and finds the best one only on problems small enough to be uninteresting, which is the whole argument for the algorithm that comes next.

Check your understanding

✓

Finish when you can reject a basic solution by its solved values rather than by its position on a drawing.

You should be able to count the bases of a small programme, name the two lines a choice of zeros puts the point on, solve one basis by row reduction, and classify it as feasible, infeasible, singular or degenerate with the entry that decided it.

Note: A corner is now an algebraic object, and one structural fact is still missing before an algorithm can use it: why stopping is allowed at all. That is convexity, and it is what “Convexity, and Why a Local Optimum Is Global” establishes.