This unit develops basic feasible solutions, simplex pivots and dual certificates for linear programs. We assume elementary matrix algebra and explain the optimization terminology as it arises.
Motivation
A compiler must decide how much of several divisible computational tasks to run within fixed processor and memory limits. If each task consumes resources at constant rates, both the limits and the performance score are linear expressions. The resulting optimization problem can have many feasible schedules. Solving a few equations produces candidates, but does not explain why no other feasible schedule performs better. Linear programming supplies both a search procedure and a short certificate of optimality.
The word linear describes the objective and the constraints, not the shape of the answer as data change. Intersections of half-spaces have corners; the preferred corner can change abruptly when a coefficient changes. Geometry makes these changes understandable. Algebra then extends the same reasoning to dimensions where a drawing is impossible.
Divisibility is a modeling assumption. A variable measuring processor time can plausibly take fractional values; a variable counting installed devices usually cannot. We first study the divisible model, because it is useful in its own right and supplies bounds for the integer models considered later. Every bound must be checked against the direction of optimization.
Definitions
Definition 1.1.1
(Feasibility, slack, and a primal-dual pair)
For real data , , and , consider
All inequalities are componentwise. A feasible point satisfies every constraint. An optimal point is feasible and attains the best objective among feasible points. The primal slack is ; the dual surplus is . The feasible set is a polyhedron, an intersection of finitely many closed half-spaces. A bounded polyhedron is a polytope.
Nonnegativity belongs to the model; it is not a default property of arbitrary variables. Replace a free variable by the difference of two nonnegative variables when standard form is required. Replace an inequality by an equality and a nonnegative slack. Multiplying a constraint by minus one reverses its inequality. These operations preserve the represented feasible decisions when carried out consistently.
For the simplex discussion, use equality standard form , , with of full row rank . A basis is a choice of linearly independent columns. Write after ordering the columns. The basic solution sets and . It is a basic feasible solution if the basic values are nonnegative. A zero basic value makes the solution degenerate. Degeneracy concerns a basis representation, so it must not be confused with having many optimal points.
A vertex is a feasible point that cannot be expressed as a nontrivial convex combination of two distinct feasible points. In equality standard form, basic feasible solutions are precisely the vertices. One can test this by looking at the columns corresponding to positive variables: dependence allows a small feasible move in both signs, while independence prevents such a decomposition.
Theorem/proposition
Theorem 1.1.2
(An attained optimum has a basic representative)
Let have full row rank. If has an attained finite optimum, then at least one optimal solution is basic feasible. In particular, a nonempty bounded feasible set has a basic optimal solution.
The attainment hypothesis is explicit. Boundedness of the feasible set gives compactness and attainment by continuity. An unbounded feasible set can also have a finite attained optimum; boundedness is sufficient, not necessary. The theorem does not say every feasible point or every optimal point is a vertex.
Counterexample mode
Without sign restrictions an optimum need not sit at a vertex
Claim: every linear program with an attained optimum has an optimal vertex. In , maximize subject only to . The maximum is attained on the whole line , yet no feasible point is a vertex, since . The theorem's standard form excludes this: means the feasible set contains no line. Writing with restores a vertex: is optimal and represents .
Theorem 1.1.3
(Dual bounds and the zero-gap certificate)
For primal-feasible and dual-feasible ,
Equality holds exactly when for every constraint and for every variable. If equality holds, both points are optimal. These product conditions are complementary slackness.
No boundedness assumption is needed for this certificate: feasible points with equal objectives already bound all competitors. The usual strong-duality theorem also guarantees equal-valued primal and dual optima when a primal finite optimum exists. Its general existence proof is beyond this unit; our computations construct and verify the needed dual point directly, so no unproved existence claim enters an example.
Proof sketch or proof idea
Choose an optimal standard-form solution with the smallest possible number of positive coordinates. This choice is possible because the support size is an integer between zero and the number of variables. Suppose its positive-support columns are dependent. There is a nonzero vector , supported on these coordinates, with . For sufficiently small positive , both and remain nonnegative and satisfy the equality constraints.
Optimality forces : otherwise one of those two small moves improves the objective. Choose the sign of so that at least one coordinate decreases, and increase the step until the first such coordinate reaches zero. All other coordinates stay nonnegative, the objective stays unchanged, and no coordinate outside the old support becomes positive. This contradicts minimal support. The positive-support columns are therefore independent. Extend them to a basis of ; the newly included basic coordinates are zero. This proves the first theorem, including degenerate cases.
Proof X-ray
How shrinking the support produces a vertex
The argument never searches for a vertex; it shrinks the support of an optimum. Attainment is used first, to have an optimum at all. Dependence of the support columns gives a direction with that touches only support coordinates, so small moves stay feasible in both signs. Optimality, not feasibility, gives , so moving along costs nothing. The real idea is the closing ratio step: pushing until the first coordinate reaches zero removes a coordinate from the support without creating one, contradicting minimality. Full row rank enters only at the end, to extend the independent columns to a basis.
For the second theorem, substitute the definitions of slack and surplus and expand. The terms involving cancel. Both remaining dot products are sums of nonnegative terms. Their sum vanishes precisely when each individual product vanishes. If a feasible pair has equal value, every primal competitor lies below that dual value, and every dual competitor lies above that primal value. Thus both are optimal without searching the rest of either feasible set.
Proof X-ray
Which assumptions make the gap a certificate?
The identity itself is algebra and holds even for infeasible vectors. The inequality needs four separate sign facts: primal slack, primal variables, dual multipliers, and dual surplus must all be nonnegative. Those facts make every product nonnegative. Only after checking them can zero total gap force every product to vanish. The last step compares all competitors using weak duality; it does not use the history of a simplex run or an assumed strong-duality existence theorem. A numerically small gap without feasibility is therefore not an optimality proof.
From a basis to a simplex step
The equations and objective in a chosen basis are
The entries of are reduced costs. At a feasible basis, if all reduced costs are nonpositive, increasing any nonbasic variables cannot improve a maximization objective. This is a global statement because every feasible point satisfies the displayed dictionary, not merely points close to the current vertex.
If a reduced cost is positive, increase that entering variable by . Put for its column. Each basic variable becomes . Rows with impose an upper bound on the step; choose the smallest ratio . Rows with nonpositive impose no upper bound. If none is positive, the dictionary supplies a feasible improving ray and the objective is unbounded. A zero minimum ratio produces a degenerate pivot with no immediate objective gain. Repeated zero pivots can cycle unless an anti-cycling rule such as Bland's rule is used. This unit explains pivot logic, rather than claiming that arbitrary tie-breaking always terminates.
Worked examples
Worked example 1.1.4
(A complete two-pivot calculation)
Consider two divisible computational workloads with objective and limits
Introduce slacks . At the initial slack basis,
Let enter. The ratios are four in the first row and two in the second; the third row does not restrict this direction. Thus leaves. Substitution gives
Let enter. With , the limiting values are two and three, so leaves. The final dictionary is
Every feasible solution has nonnegative , so its score is at most ten. Setting both to zero gives and . The dictionary has become an explicit optimality proof.
Worked example 1.1.5
(The dual certificate and its sensitivity range)
For the preceding model, let . Its components are nonnegative and
The primal point has value ten, so weak duality proves optimality independently of the pivot history. The unused third capacity has zero multiplier; the first two positive multipliers correspond to tight constraints. These observations are consequences of the products in complementary slackness, not a rule that every tight constraint must have a positive multiplier.
Now change only the first capacity from four to . The same basis gives , , and . It stays feasible exactly for . The unchanged dual point then certifies value . Outside that interval the dual vector still gives an upper bound whenever the model is feasible, but the proposed primal point fails nonnegativity. A multiplier describes the value change only over a range where its certificate remains exact.
Worked example 1.1.6
(Diagnosing infeasibility, unboundedness, and multiple optima)
The constraints and are incompatible; an optimizer must report infeasibility rather than invent a poor best point. By contrast, maximizing subject only to has feasible points but no finite maximum. The ray , , explains the failure.
Finally maximize subject to and . Both and are optimal vertices, and every point on their connecting segment is also optimal. The midpoint is optimal but not a vertex. Thus the basic-representative theorem is existential. A zero reduced cost may indicate a flat optimal direction, but degeneracy can prevent a particular zero-cost pivot from reaching a distinct point.
Common mistakes
A feasible point need not be optimal, and satisfying a collection of boundary equations need not even give a feasible point. After solving active equations, check every unused inequality and every sign restriction. A picture showing several intersections is a list of candidates, not a certificate that the list includes a feasible optimum.
Dual signs follow the chosen primal convention. The displayed dual belongs to a maximization problem with upper inequalities and nonnegative variables. An equality constraint gives a free dual multiplier; a free primal variable gives a dual equality. Reusing the displayed signs after changing the primal format can turn a claimed upper bound into an invalid expression.
Complementary slackness does not say slack and multiplier are both zero. A positive slack forces the multiplier to vanish; a tight constraint leaves its multiplier free to be zero or positive. Similarly, a zero decision variable does not force its dual inequality to be strict. Check feasibility before using any complementary products.
A simplex ratio test divides only by positive direction entries. Dividing by a negative entry incorrectly treats a growing basic variable as a threat to nonnegativity. Numerical implementations also need tolerances and stable linear solves; the exact algebra here does not establish numerical robustness for nearly singular bases.
Summary
Linear programming connects feasible polyhedra to algebraic bases. A pivot changes the basis while preserving feasibility; reduced costs identify possible improvement. The final dictionary and a feasible dual point provide two ways to certify the same bound. Always distinguish an infeasible model, an unbounded objective, an attained optimum, and a nonunique optimum. These are mathematically different outcomes with different evidence.
Exercises
Quick check
(Maximize subject to , , and . Find a feasible optimum and a dual certificate in the displayed primal convention.)
Solution · Answer
Take , with objective four. A dual vector is : its column inequalities are and , both equalities. Its objective is . Feasibility and equal objectives prove optimality. Directly, gives the same certificate in elementary form.
Quick check
(In the first worked model, change the objective to . Describe every optimum and give one dual optimum. Explain whether the previous primal point remains optimal.)
Solution · Answer
The maximum is four, reached exactly when with and . These bounds come from and . The point remains optimal but is no longer the sole optimum. The dual vector is feasible for the new objective and has value four.
Quick check
(In standard form, a current dictionary has basic values , and the entering column has with positive reduced cost. Compute the allowed step and the new basic values before the basis is relabeled. What changes if the direction is ?)
Solution · Answer
The first row imposes ; the second grows and imposes no bound. At , the old basic values are and the entering variable is two. For direction , both old basic values grow for all nonnegative steps. With positive reduced cost, this is a feasible improving ray, proving unboundedness of the current LP.
Quick check
(A proposed feasible pair has primal slack , dual multiplier , primal point , and dual surplus . Does it certify optimality? What if only the second multiplier changes to one, while all feasibility conditions are assumed rechecked?)
Solution · Answer
The gap is , so the original pair certifies both optima. With second multiplier one, the slack contribution is two. The gap is then positive, so equal-value certification fails. A positive gap alone does not determine which of the feasible points is suboptimal; it only shows that this pair does not certify equality.
Quick check
(Prove that two distinct optimal feasible points generate an entire optimal segment. Explain why this does not imply that every point on the segment is basic.)
Solution · Answer
If and are feasible, linear inequalities preserve feasibility of for . Linearity gives the same optimal objective on that segment. For , the point is a nontrivial convex combination of distinct feasible points, so it is not a vertex and hence not basic feasible. The endpoints may or may not themselves be vertices.