Basic Feasible Solution Problems
Basic feasible solution problems ask you to use a basis matrix to construct or verify a feasible vertex of the standard-form polyhedron.
Standard-Form Setting
Start from:
\[\min c^Tx\]subject to:
\[Ax=b, \qquad x\ge 0,\]where $A\in\mathbb{R}^{m\times n}$.
Basis Matrix
Choose $m$ linearly independent columns of $A$:
\[B=[A_{B(1)}\ A_{B(2)}\ \cdots\ A_{B(m)}].\]The variables corresponding to these columns are basic variables.
Compute the Basic Solution
Set all nonbasic variables to zero:
\[x_N=0.\]Solve:
\[x_B=B^{-1}b.\]Then assemble the full vector $x$.
Feasibility Test
The basic solution is feasible if:
\[x_B\ge 0.\]If any basic variable is negative, it is a basic solution but not a basic feasible solution.
Verifying a Given Vector
To verify a given vector $\bar x$:
- check $A\bar x=b$
- check $\bar x\ge 0$
- identify positive/basic candidate variables
- check whether the corresponding columns form a basis
- if yes, $\bar x$ is a BFS
Degeneracy
A BFS is degenerate if at least one basic variable is zero.
Equivalently, fewer than $m$ variables may be positive even though $m$ variables are basic.
Checklist
For exam answers, always state the basis, compute $B^{-1}b$, and explicitly conclude feasible or not feasible.
See Also
Added drill source
Use BFS and Reduced Cost Drill Set and Verifying a Given Vector as BFS.
Exam checkpoint
Practice under exam timing. Write the full pipeline: model, standard form if needed, BFS/reduced costs if asked, simplex iterations if asked, final objective value and interpretation.