Pivoting Between Adjacent Bases

The simplex method moves between basic feasible solutions (BFSs) by exchanging exactly one variable in the basis. The non-basic variable joining the basis is the entering variable, and the basic variable leaving the basis is the leaving variable. Two BFSs that differ by exactly one such swap are called adjacent.

We carry out the swap directly on the simplex tableau by a pivot operation, anchored at the pivot element:

• The pivot column is the column of the entering variable.
• The pivot row is the row of the leaving variable.
• The pivot element is the entry where the pivot row and pivot column meet.

For example, consider the tableau

$$\begin{array}{c|cccc|c} & x_1 & x_2 & s_1 & s_2 & \text{RHS} \\ \hline z & -4 & -3 & 0 & 0 & 0 \\ s_1 & 2 & 1 & 1 & 0 & 10 \\ s_2 & 1 & 2 & 0 & 1 & 12 \end{array}$$

If the entering variable is $x_1$ and the leaving variable is $s_1,$ then the pivot column is the $x_1$ column, the pivot row is the $s_1$ row, and the pivot element is $2$ — the entry at their intersection.