Basic feasible solutions
Basic Feasible Solutions
A basic feasible solution is a basic solution that also satisfies nonnegativity.
Definition
For
\[P=\{x\mid Ax=b,\ x\ge 0\},\]$x$ is a basic feasible solution if it is a basic solution and $x\ge 0$.
Construction
Choose a basis $B$, set $x_N=0$, compute
\[x_B=B^{-1}b.\]If $x_B\ge 0$, the resulting vector is a BFS.
BFS and Vertices
Under the usual full-rank assumptions,
\[\text{BFS}\Longleftrightarrow\text{vertex of }P.\]This is the reason simplex works with bases.
Degenerate vs Nondegenerate
A BFS is nondegenerate if
\[x_B>0.\]It is degenerate if at least one basic variable is zero.
Simplex Role
The simplex method starts from a BFS and repeatedly moves to adjacent BFSs with better objective value.
Checklist
You should be able to compute a basic solution, check $x\ge 0$, and identify whether it is degenerate.
See Also
Exam checkpoint
For BFS questions, convert to standard form before checking the point. A candidate in original variables must be lifted with slack and surplus variables before testing basis columns.