Dual Simplex Method | Sahithyan's Notes

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 of objective row coefficient to that entry (absolute value).

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.

1 /

entering column leaving row pivot element updated this step

Basic	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	$s_4$	RHS
$z$	$0$	$0$	$0$	$3/2$	$1$	$0$	$36$
$s_1$	$0$	$0$	$1$	$1/3$	$-1/3$	$0$	$2$
$x_2$	$0$	$1$	$0$	$1/2$	$0$	$0$	$6$
$x_1$	$1$	$0$	$0$	$-1/3$	$1/3$	$0$	$2$
$s_4$	$0$	$0$	$0$	$-1/6$	$-1/3$	$1$	$-3$

Most negative RHS is $-3$ , so $s_4$ leaves. Negative entries in that row are under $s_2$ ( $-\tfrac16$ ) and $s_3$ ( $-\tfrac13$ ). Ratios of objective row coefficient to entry magnitude: $\tfrac{3/2}{1/6} = 9$ and $\tfrac{1}{1/3} = 3$ . Minimum is $3$ , so $s_3$ enters. Pivot on $-\tfrac13$ .

Basic	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	$s_4$	RHS
$z$	$0$	$0$	$0$	$1$	$0$	$3$	$27$
$s_1$	$0$	$0$	$1$	$1/2$	$0$	$-1$	$5$
$x_2$	$0$	$1$	$0$	$1/2$	$0$	$0$	$6$
$x_1$	$1$	$0$	$0$	$-1/2$	$0$	$1$	$-1$
$s_3$	$0$	$0$	$0$	$1/2$	$1$	$-3$	$9$

Still infeasible: $x_1 = -1$ . The only negative entry in that row is under $s_2$ ( $-\tfrac12$ ), so $s_2$ enters. Pivot on $-\tfrac12$ .

Basic	$x_1$	$x_2$	$s_1$	$s_2$	$s_3$	$s_4$	RHS
$z$	$2$	$0$	$0$	$0$	$0$	$5$	$25$
$s_1$	$1$	$0$	$1$	$0$	$0$	$0$	$4$
$x_2$	$1$	$1$	$0$	$0$	$0$	$1$	$5$
$s_2$	$-2$	$0$	$0$	$1$	$0$	$-2$	$2$
$s_3$	$1$	$0$	$0$	$0$	$1$	$-2$	$8$

Every RHS is $\ge 0$ and the objective row is still non-negative. Optimal at $x_1 = 0$ , $x_2 = 5$ , $z = 25$ .

.simplex [data-live] { display: none; } .simplex .stack { display: block; } .simplex .stack > .step { opacity: 1; visibility: visible; margin-top: 16px; } .simplex .stack .step > .tableau { display: table; } .simplex .foot { display: none; }