Dual Simplex Method: Steps, Solved Example and When to Use It

The dual simplex method is a version of the simplex algorithm that starts from a solution that is optimal but infeasible and moves towards feasibility. It is the natural choice for minimization problems with ≥ constraints, and it is the method solvers use when a new constraint is added to a problem that has already been solved.

This guide explains when to use the dual simplex method, gives its rules step by step, and solves a complete example by hand. You can check the final answer with the dual simplex method calculator.

Primal Simplex vs Dual Simplex

Every simplex tableau can be judged on two things:

• Feasibility: are all right-hand-side (RHS) values non-negative?
• Optimality: does the Cj − Zj row show that no variable can improve the objective?

The ordinary (primal) simplex method keeps the tableau feasible at every step and works towards optimality. The dual simplex method does the opposite: it keeps the tableau optimal at every step and works towards feasibility. Both stop at the same place, a tableau that is feasible and optimal at the same time. A longer comparison is in primal vs dual simplex method.

When to Use the Dual Simplex Method

Use it when the starting tableau satisfies the optimality condition but has one or more negative RHS values. This happens most often in three situations:

1. Minimization with ≥ constraints and non-negative costs. Multiplying each ≥ constraint by −1 turns it into a ≤ constraint with a negative RHS. A slack basis is then immediately available, without any artificial variables.
2. Adding a new constraint after solving. If the old optimal solution violates the new constraint, the tableau is still optimal but now infeasible, so a few dual simplex pivots repair it.
3. Sensitivity analysis. When a right-hand-side value changes and a basic variable becomes negative, the dual simplex method finds the new optimum quickly.

Avoiding artificial variables is the main practical advantage. Compared with the Big M method or the two-phase method, the dual simplex method usually needs fewer columns and fewer iterations for this kind of problem.

Dual Simplex Method Steps

1. Check optimality. For minimization, every Cj − Zj must be ≥ 0. If not, the dual simplex method cannot start.
2. Choose the leaving variable. Pick the row with the most negative RHS. If every RHS is ≥ 0, the current solution is optimal and feasible, so stop.
3. Choose the entering variable (dual ratio test). In the leaving row, look only at the negative entries. For each one, compute |(Cj − Zj) / entry|. The column with the smallest ratio enters.
4. Check for infeasibility. If the leaving row has no negative entries, the problem has no feasible solution.
5. Pivot exactly as in the ordinary simplex method, then return to step 2.

Notice that the order is reversed. The primal simplex method chooses the entering variable first; the dual simplex method chooses the leaving variable first.

Solved Example

Minimize Z = 2x1 + x2

Subject to

• 3x1 + x2 ≥ 3
• 4x1 + 3x2 ≥ 6
• x1 + 2x2 ≤ 3
• x1, x2 ≥ 0

Setting Up

Multiply the two ≥ constraints by −1 so that every constraint is ≤, then add slack variables s1, s2 and s3:

• −3x1 − x2 + s1 = −3
• −4x1 − 3x2 + s2 = −6
• x1 + 2x2 + s3 = 3

The objective coefficients 2 and 1 are both non-negative, so the starting tableau is already optimal for a minimization problem, but s1 = −3 and s2 = −6 are infeasible. This is exactly the situation the dual simplex method is designed for.

Basis	x1	x2	s1	s2	s3	RHS
s1	−3	−1	1	0	0	−3
s2	−4	−3	0	1	0	−6
s3	1	2	0	0	1	3
Cj − Zj	2	1	0	0	0	Z = 0

Iteration 1

• Leaving variable: s2, because −6 is the most negative RHS.
• Dual ratio test on the negative entries of the s2 row: x1 gives |2 / −4| = 1/2 and x2 gives |1 / −3| = 1/3.
• The smallest ratio is 1/3, so x2 enters. The pivot element is −3.

After pivoting:

Basis	x1	x2	s1	s2	s3	RHS
s1	−5/3	0	1	−1/3	0	−1
x2	4/3	1	0	−1/3	0	2
s3	−5/3	0	0	2/3	1	−1
Cj − Zj	2/3	0	0	1/3	0	Z = 2

All Cj − Zj values are still ≥ 0, so the tableau is still optimal, but s1 and s3 are both −1, so it is still infeasible.

Iteration 2

• Leaving variable: s1 and s3 tie at −1. Either can be chosen; here we take the first row, s1.
• Dual ratio test on the negative entries of the s1 row: x1 gives |(2/3) / (−5/3)| = 2/5 and s2 gives |(1/3) / (−1/3)| = 1.
• The smallest ratio is 2/5, so x1 enters. The pivot element is −5/3.

After pivoting:

Basis	x1	x2	s1	s2	s3	RHS
x1	1	0	−3/5	1/5	0	3/5
x2	0	1	4/5	−3/5	0	6/5
s3	0	0	−1	1	1	0
Cj − Zj	0	0	2/5	1/5	0	Z = 12/5

Every RHS is now ≥ 0, so the tableau is feasible, and every Cj − Zj is still ≥ 0, so it is optimal.

Answer

• x1 = 3/5 = 0.6
• x2 = 6/5 = 1.2
• Minimum Z = 2(0.6) + 1.2 = 12/5 = 2.4

Check: 3(0.6) + 1.2 = 3 ✓, 4(0.6) + 3(1.2) = 6 ✓, and 0.6 + 2(1.2) = 3 ✓. All three constraints hold with equality, which is why s3 = 0 in the final tableau.

Common Mistakes

• Applying the dual ratio test to positive entries. Only negative entries in the leaving row are used. Positive entries would make a basic variable more negative.
• Starting from a non-optimal tableau. If some Cj − Zj has the wrong sign, the dual simplex method is not valid. Use the primal simplex, Big M or two-phase method instead.
• Choosing the entering variable first. In the dual simplex method the leaving row is always chosen first.
• Forgetting to flip the inequality. When a ≥ constraint is multiplied by −1, both sides change sign, including the RHS.

Dual Simplex Method vs Solving the Dual Problem

These are different things that are often confused. Solving the dual problem means writing a new linear program (the dual LP) and solving it with the ordinary simplex method. The dual simplex method works directly on the original (primal) tableau. Both give the same optimal objective value because of the strong duality theorem, but the dual simplex method does not require writing a second problem.

Check Your Answer

Enter 2x1 + x2 as the objective, choose minimize, and type the three constraints on separate lines in the dual simplex method calculator. The calculator solves the problem with the standard simplex method and the Big M technique, so its intermediate tableaus differ from the dual simplex tableaus above, but it reaches the same optimal solution: x1 = 0.6, x2 = 1.2 and Z = 2.4. That makes it a quick way to confirm your final answer.