Dual Simplex Method

Applies when a tableau is optimal (objective row satisfies the optimality criterion) but infeasible (some RHS is negative). Common after adding a new constraint to an already-optimal tableau.

Iteration Steps

Select Leaving Variable

The basic variable with the most negative RHS.

Select Entering Variable

Among columns with a negative entry in the leaving row, the one minimizing the ratio:

If no negative entry exists in the leaving row, the problem is infeasible. Stop.

Pivot

Same as the primal simplex algorithm’s pivot step.

Repeat until every RHS is $\ge 0$, at which point the tableau is both optimal and feasible.

Worked Example

Take the optimal tableau from the simplex algorithm example ($z = 3x_1 + 5x_2$, optimum $x_1 = 2$, $x_2 = 6$, $z = 36$) and add the constraint $x_1 + x_2 \le 5$, which the current optimum violates ($2 + 6 = 8$).

Adding slack $s_4$ gives $x_1 + x_2 + s_4 = 5$. Substituting the $x_1$ and $x_2$ rows to eliminate the basic variables leaves $-\tfrac{1}{6}s_2 - \tfrac{1}{3}s_3 + s_4 = -3$. The objective row is unchanged, so the tableau is still optimal but now infeasible.