Adjacent basic solutions
Adjacent Basic Solutions
Adjacent basic solutions are basic feasible solutions connected by one pivot. Geometrically, they are neighboring vertices joined by an edge.
Adjacent Bases
Two bases are adjacent if they differ by one column.
One nonbasic variable enters, and one basic variable leaves.
New Basis
If $x_j$ enters and $x_{B(\ell)}$ leaves, then
\[\bar B=[A_{B(1)}\ \cdots\ A_j\ \cdots\ A_{B(m)}].\]Edge Direction
The direction for entering $x_j$ is
\[d_j=1,\qquad d_B=-B^{-1}A_j,\]with other nonbasic components zero. Points on the edge have form $x+\theta d$.
Leaving Variable
The leaving variable is the basic variable that reaches zero first as $\theta$ increases. It is found by the minimum ratio test.
Degenerate Exception
If $\theta^*=0$, the basis can change without moving to a different geometric point.
Checklist
You should be able to describe entering, leaving, and the one-column basis replacement.
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.