Tableau Simplex on 2-Variable Problems

Execute the full simplex algorithm on a 2-variable maximization linear program using the tableau form: select the entering variable via the most-negative-coefficient rule, select the leaving variable via the minimum ratio test, perform a pivot, and iterate until the objective row contains no negative entries.

Step 1 of 157%

Tutorial

Choosing the Entering Variable

Once a simplex tableau has been set up, we use the objective row (the bottom row) to test for optimality and to decide where to pivot next.

Optimality test. If every entry in the bottom row to the left of the RHS is $\ge 0$ , the current basic feasible solution is optimal and the algorithm terminates.

Otherwise, we must pivot. The entering variable -- the variable about to enter the basis -- is chosen by locating the most negative entry in the bottom row. The column containing that entry is the pivot column.

For example, consider the tableau

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

The bottom row has two negative entries: $-7$ under $x_1$ and $-4$ under $x_2$ . Since $-7 < -4$ , the most negative entry is $-7$ , so the pivot column is the $x_1$ column and the entering variable is $x_1$ .