Basis updates
Basis Updates
A basis update replaces the leaving basic column with the entering column.
Replacement
If $x_j$ enters and $x_{B(\ell)}$ leaves, replace $A_{B(\ell)}$ by $A_j$ in $B$.
New Values
$x_j^{new}=\theta^$, $x_{B(\ell)}^{new}=0$, and $x_{B(i)}^{new}=x_{B(i)}-\theta^u_i$ for $i \ne \ell$.
Objective Change
$c^Tx^{new}=c^Tx+\theta^*\bar c_j$.
Degenerate Pivot
If $\theta^*=0$, the basis changes but the point may not move.
Checklist
Write the new basis and new basic variable values.
See Also
Exam checkpoint
For simplex questions in minimization form, negative reduced costs indicate possible improvement. Use $u=B^{-1}A_j$, apply the ratio test only to positive components of $u$, then update the basis.