= 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>.
Back to article page