Verifying a Given Vector as BFS
Verifying a Given Vector as BFS
A vector is a basic feasible solution only after the problem is in standard form.
Algorithm
Given $\bar x$ in original variables:
- Convert the LP to standard form.
- Compute all slack and surplus variables at $\bar x$.
- Form the full vector $\hat x$.
- Check $A\hat x=b$ and $\hat x\ge0$.
- Find a basis $B$ of $m$ independent columns such that all nonbasic variables are zero.
- If such a basis exists, $\hat x$ is a BFS.
Key distinction
Feasible does not always mean BFS.
A feasible point can fail to be BFS if its active/positive-column structure does not give a valid basis.
Mini example
For
\[\begin{aligned} 3x_1-2x_2+x_3 &=10,\\ x_2+2x_3+s_1 &=5,\\ 3x_1+5x_2+x_3-s_2 &=10, \end{aligned}\]at $(x_1,x_2,x_3)=(3,0,1)$, we get
\[s_1=3, \qquad s_2=0.\]So
\[\hat x=(3,0,1,3,0).\]This is feasible, but the positive columns $A_1,A_3,A_{s_1}$ are dependent, so it is not a BFS.
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.