Basic feasible solution (source code)

= Basic feasible solution
{wiki}

For a full-row-rank system $Ax=b$ with $m$ rows and variables $x\ge0$, choose $m$ <linearly independent> columns as a <simplex basis>. Set all <nonbasic variables> to zero and solve $x_B=A_B^{-1}b$. If $x_B\ge0$, 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 $A$ has row rank $m$. The extension may have zero-valued <basic variables>; this is <degeneracy in linear programming>.

For $x_1+x_2=1$ and $x_1,x_2\ge0$, the two basic feasible solutions are $(1,0)$ and $(0,1)$. The feasible midpoint $(1/2,1/2)$ 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>.