For a full-row-rank system with rows and variables , choose linearly independent columns as a simplex basis. Set all nonbasic variables to zero and solve . If , the resulting vector is a basic feasible solution. Redundant equality rows can first be removed.
Equivalently, a feasible vector is basic when the columns indexed by its strictly positive coordinates are linearly independent. Those columns can be extended to a basis of the full column space because has row rank . The extension may have zero-valued basic variables; this is degeneracy in linear programming.
For and , the two basic feasible solutions are and . The feasible midpoint is not basic: its two positive columns are dependent. In this standard form, basic feasible solutions are exactly the extreme points of the feasible polyhedron, connecting basis algebra to the Fundamental theorem of linear programming.
A basic feasible solution is degenerate when one or more of its basic variables is zero. A simplex algorithm pivot may then change the basis without moving the feasible point or changing the objective. Assignment networks force many zero-flow basic tree arcs.
For a full-row-rank system with rows, choose linearly independent columns, set all remaining variables to zero, and solve the resulting square system. The resulting vector is a basic solution; it is feasible when it also satisfies the required nonnegativity constraints.
For a linear program in standard equality form , , a finite attained optimum has an optimal basic feasible solution. After deleting redundant equality rows, assume has full row rank. The nonnegative standard form is part of the statement: an arbitrary polyhedron containing lines can have an optimum and no extreme point.
Choose an optimal feasible vector with the fewest positive coordinates. If its positive-support columns are dependent, there is a nonzero vector supported there with . Both signs of a sufficiently small displacement remain feasible. Optimality forces , or one sign would improve the objective. Reverse if necessary so it has a negative coordinate, and increase until the first positive coordinate becomes zero. The objective is unchanged, contradicting minimal positive support. Thus those columns are independent and the solution is basic.
For contrast, minimizing the constant zero on the unrestricted real line has an optimum at every point, but no extreme points. Converting such a model to nonnegative standard form introduces a different polyhedron where the basis theorem applies. The theorem guarantees a place to find an optimum; it does not guarantee that every optimum is a vertex or that a particular pivot rule is fast.

Ancestors (5)

  1. Linear programming
  2. Mathematical optimization
  3. Area of mathematics
  4. Mathematics
  5. Home

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.