Dual Simplex Method: Explained + Worked Examples

Last updated: β€’ Sources β€’ Methodology

Dual Simplex Method: When the Tableau Is Optimal but Infeasible (Pivot Rules + Worked Examples)

The dual simplex method is a simplex variant used when your current tableau satisfies the optimality condition (dual feasible / reduced costs β€œlook optimal”) but violates feasibility (some RHS values are negative). It restores feasibility while maintaining optimalityβ€”often ideal for re-optimization after adding a constraint.

If you’re new to LPs, start with Linear Programming (LP) β€” Beginner Guide. To verify final answers, use the Linear Programming calculator. If your issue is β€œno obvious starting basis,” see Two Phase Simplex Method or Big M Method.

On this page

Quick takeaway: The dual simplex method is used when your tableau is dual feasible (reduced costs satisfy the optimality sign condition) but primal infeasible (some basic RHS values are negative). Dual simplex pivots to make all RHS values nonnegative while keeping reduced costs in the β€œoptimal” sign pattern. If it cannot pivot (no eligible entering variable for a negative RHS row), the LP is infeasible (see Unbounded vs Infeasible LP (Fix Checklist)).

When to use dual simplex (vs primal simplex)

Practical

Dual simplex is for β€œoptimal but infeasible” tableaus

A common situation: you solved an LP, then you add or tighten a constraint (new policy, new capacity limit, new demand requirement). The old basis can remain objective-optimal in reduced-cost terms, but it may violate the new constraint, making some RHS negative. Dual simplex is designed to repair feasibility fast without restarting.

If your issue is the opposite (feasible but not optimal), you’re in standard/simplex territory (see LP beginner guide). If you don’t even have a starting feasible basis because of = or β‰₯ constraints, use two-phase simplex or Big‑M after understanding slack/surplus/artificial variables.

Concept bridge: primal feasibility vs dual feasibility

Beginner β†’ intermediate

Two β€œhealth checks” on a tableau

In simplex-style methods, you typically track:

  • Primal feasibility: all basic RHS values are β‰₯ 0 (so the basic solution is feasible).
  • Optimality / dual feasibility (max case, Cjβˆ’Zj convention): all reduced costs satisfy the sign condition (often Cj βˆ’ Zj ≀ 0).

Primal simplex assumes feasibility first and moves toward optimality. Dual simplex assumes optimality (in reduced-cost signs) first and moves toward feasibility.

For the bigger picture (why reduced costs relate to the dual problem), see Primal–Dual Relationship in LP.

Dual simplex steps (the real pivot loop)

Algorithm

What the solver does repeatedly

  1. Check optimality signs (reduced costs already satisfy the optimality condition).
  2. Pick a leaving row: choose the basic variable with the most negative RHS (most infeasible).
  3. Pick an entering variable from columns that can fix that negative RHS (pivot rule below).
  4. Pivot to improve feasibility while maintaining optimality signs.
  5. Stop when all RHS values are β‰₯ 0 (feasible). Since optimality signs were preserved, the solution is optimal.

Pivot rules cheat sheet (leaving/entering)

Cheat sheet

Leaving row by RHS; entering column by a ratio that preserves reduced-cost signs

Below uses the common maximization tableau convention where the reduced-cost row is Ξ”j = Cj βˆ’ Zj and optimality requires Ξ”j ≀ 0.

Decision Rule Reason (plain English)
Leaving variable (row) Choose a basic row with RHS < 0 (often the most negative) That row violates feasibility the most; fix it first
Eligible entering columns In the leaving row r, consider columns with arj < 0 Only those pivots can increase that RHS toward β‰₯ 0
Entering variable (column) Choose j that minimizes ΞΈj = Ξ”j / arj over eligible columns Preserves optimality signs (keeps reduced costs in the β€œoptimal” direction)
Infeasibility detection If leaving row has RHS < 0 and no arj < 0, stop: infeasible No pivot can fix the negative RHS without violating nonnegativity
Different textbooks use different tableau sign conventions. The logic stays the same: dual simplex fixes RHS infeasibility while preserving reduced-cost optimality.

Questions people ask about the dual simplex method (PAA)

People ask

What is the dual simplex method?

The dual simplex method is a simplex variant that starts from a tableau that is β€œoptimal” in reduced-cost signs but not feasible (some RHS values are negative). It pivots to restore feasibility while keeping the tableau optimality condition intact.

People ask

When should you use the dual simplex method instead of primal simplex?

Use dual simplex when your current solution becomes infeasible after a change (like adding a new constraint), but the reduced costs still satisfy the optimality sign condition. This is common in re-optimization.

People ask

What is the dual simplex pivot rule?

Pick the leaving row from a negative RHS (infeasible basic variable). Then choose an entering variable from columns with negative coefficients in that leaving row, using a ratio rule designed to preserve reduced-cost optimality signs. The exact ratio expression depends on your tableau convention, but the eligibility logic is the same.

People ask

What does it mean if dual simplex has no eligible entering variable?

If the chosen negative-RHS row has no coefficients that allow a pivot (e.g., no negative coefficients under the relevant convention), dual simplex cannot repair feasibilityβ€”this indicates the LP is infeasible. Use Unbounded vs Infeasible LP (Fix Checklist) to debug.

People ask

Is dual simplex faster than simplex?

It can be faster in re-optimization settings because it starts β€œnear optimal” and only repairs feasibility. For solving from scratch, performance depends on problem structure and solver strategy.

People ask

How is the dual simplex method related to the dual problem in linear programming?

Reduced costs and the optimality condition are tied to dual feasibility and complementary slackness. For intuition (shadow prices, bounds), see Primal–Dual Relationship in LP.

Worked examples (fully solved)

Worked examples

Expand only the example you need

Each example below is collapsible (collapsed by default) to keep the page scannable while remaining fully indexable. You can verify final solutions in the LP calculator.

Example 1 β€” Dual simplex method worked example (optimal but infeasible tableau)

Original LP (maximize):

maximize   z = 3x1 + 2x2
subject to x1 +  x2 ≀ 4
           2x1 + x2 ≀ 3
           x1, x2 β‰₯ 0

Step 1: Convert to standard form with slacks

x1 +  x2 + s1 = 4
2x1 + x2 + s2 = 3
x1, x2, s1, s2 β‰₯ 0

Step 2: Start from a dual-feasible but primal-infeasible basis

Dual simplex needs a tableau that already satisfies the reduced-cost optimality sign condition but has some negative RHS. One way this can happen is after re-optimization or after changing constraints. Here we choose basis {x1, x2} to demonstrate the method cleanly.

Solve the two equalities for x1, x2 in terms of nonbasic slacks s1, s2: 

x1 βˆ’ s1 + s2 = βˆ’1
x2 + 2s1 βˆ’ s2 =  5

If we set the nonbasic variables s1 = s2 = 0, we get x1 = βˆ’1, x2 = 5. That violates x1 β‰₯ 0, so the basis is primal infeasible (negative RHS in the x1 row).

Step 3: Express the objective in terms of nonbasics (reduced-cost check)

z = 3x1 + 2x2
  = 3(βˆ’1 + s1 βˆ’ s2) + 2(5 βˆ’ 2s1 + s2)
  = 7 βˆ’ s1 βˆ’ s2

Increasing s1 or s2 reduces z, so the reduced costs for s1 and s2 are negative. That means the tableau is already β€œobjective-optimal” in reduced-cost signs.

Step 4: Dual simplex tableau (Cj βˆ’ Zj convention)

Optimality condition for this convention (max): all Ξ”j = Cj βˆ’ Zj ≀ 0.

Basis x1 x2 s1 s2 RHS
x1 10-11-1
x2 012-15
Ξ” = Cj βˆ’ Zj 00-1-1z = 7

Step 5: Dual simplex pivot (fix the negative RHS)

Leaving row: pick the most negative RHS β†’ row x1 (RHS = βˆ’1).

Eligible entering columns: in the leaving row, choose columns with negative coefficients. Row x1 has s1 coefficient βˆ’1 (eligible) and s2 coefficient +1 (not eligible). So s1 must enter.

Pivot on the element at (row x1, column s1) = βˆ’1.

Step 6: New tableau after pivot

Pivoting makes s1 basic. Dividing the leaving row by βˆ’1 gives: 

s1 βˆ’ x1 βˆ’ s2 = 1

Eliminate s1 from the other row (x2):

x2 + 2s1 βˆ’ s2 = 5
Substitute s1 = 1 + x1 + s2:
x2 + 2(1 + x1 + s2) βˆ’ s2 = 5
x2 + 2x1 + s2 = 3

Objective becomes (substitute s1 = 1 + x1 + s2 into z = 7 βˆ’ s1 βˆ’ s2):

z = 7 βˆ’ (1 + x1 + s2) βˆ’ s2 = 6 βˆ’ x1 βˆ’ 2s2
Basis x1 x2 s1 s2 RHS
s1 -101-11
x2 21013
Ξ” = Cj βˆ’ Zj -100-2z = 6

Now all RHS values are nonnegative, and the reduced costs satisfy the optimality sign condition. Therefore this tableau is optimal.

Optimal solution (Example 1): set nonbasic variables x1 = 0 and s2 = 0. Then x2 = 3, and z* = 6.

Example 2 β€” Dual simplex re-optimization example (adding a new constraint)

Dual simplex shines when you already have an optimal solution and then introduce a new constraint that breaks feasibility. We’ll do that in a small, checkable example.

Original LP (already solved)

maximize   z = 3x2
subject to x1 +  x2 ≀ 4
           2x1 + x2 ≀ 5
           x1, x2 β‰₯ 0

Because the objective depends only on x2, the optimal solution sets x1 = 0 and maximizes x2. The constraints imply x2 ≀ 4 and x2 ≀ 5, so: 

Old optimum: (x1, x2) = (0, 4),  z* = 12

New constraint added (policy change)

Add: x1 β‰₯ 1. This makes the old solution infeasible.

Standard-form row for the new constraint

x1 β‰₯ 1  ⇔  βˆ’x1 ≀ βˆ’1  ⇔  βˆ’x1 + s3 = βˆ’1,  s3 β‰₯ 0

Why dual simplex is appropriate here

We are β€œbreaking feasibility” (RHS = βˆ’1 in the new row), but we don’t want to restart the optimization. Dual simplex pivots to restore feasibility while keeping objective optimality signs.

Dual simplex repair (one pivot)

The new row is: 

βˆ’x1 + s3 = βˆ’1

RHS is negative, so this row must be fixed. The coefficient under x1 is negative (βˆ’1), so x1 is an eligible entering variable. Pivoting makes: 

x1 βˆ’ s3 = 1  β‡’  x1 = 1 + s3

Setting nonbasic s3 = 0 gives x1 = 1. Now use constraints to update x2: 

x1 + x2 ≀ 4   β‡’  1 + x2 ≀ 4 β‡’ x2 ≀ 3
2x1 + x2 ≀ 5  β‡’  2 + x2 ≀ 5 β‡’ x2 ≀ 3

So the best possible is x2 = 3.

New optimal solution (Example 2): x1 = 1, x2 = 3, and z* = 9. Dual simplex reaches this by β€œrepairing feasibility” after the new constraint is added.

You can verify the before/after solutions quickly in the Linear Programming calculator. If you want the graphical confirmation for 2 variables, use Graphical Method for LP.
Example 3 β€” Dual simplex infeasibility example (negative RHS row with no eligible entering variable)

Dual simplex declares infeasibility when it finds a negative-RHS leaving row that has no pivot-eligible columns. Here is a tiny example that produces that situation.

LP (infeasible by inspection)

maximize   z = 0
subject to x1 ≀ 0
           x1 β‰₯ 1
           x1 β‰₯ 0

The constraints require x1 ≀ 0 and x1 β‰₯ 1 simultaneously, which is impossible.

Standard form (show the contradiction as a negative RHS that cannot be fixed)

From x1 ≀ 0:

x1 + s1 = 0,  s1 β‰₯ 0

From x1 β‰₯ 1:

βˆ’x1 + s2 = βˆ’1,  s2 β‰₯ 0

Consider the second row: 

βˆ’x1 + s2 = βˆ’1

Because x1 β‰₯ 0 and s2 β‰₯ 0, the left-hand side satisfies: 

βˆ’x1 + s2 ≀ s2  (since βˆ’x1 ≀ 0)

But the row forces it to equal βˆ’1. That means we need s2 to be negative enough to reach βˆ’1 (impossible), unless we can pivot in a way that introduces a variable with a negative coefficient to increase the RHS.

In dual simplex terms: if a leaving row has RHS negative but no eligible entering variable under your tableau convention, the algorithm stops with infeasible.

Conclusion (Example 3): The LP is infeasible. Dual simplex detects infeasibility when a negative RHS cannot be repaired by any pivot. Use Unbounded vs Infeasible LP (Fix Checklist) for systematic debugging.

Check your answer (calculator + next guides)

Tooling + learning path

Fast verification + what to read next

Verify any final solution (or infeasible status) using the Linear Programming calculator. Dual simplex is mainly about how the solver pivots, not about changing the LP itself.

If you’re solving from scratch and don’t have a feasible basis, use two-phase simplex or Big‑M. If your model needs integer variables, simplex solves only relaxationsβ€”use ILP/MILP and expect branch-and-bound.

Troubleshooting checklist

Troubleshooting

Symptom β†’ likely cause β†’ fix

What you observe Likely diagnosis What to do next
RHS has negative entries but reduced costs look β€œoptimal” Ideal dual simplex situation Apply dual simplex pivot rules (leaving row by most negative RHS)
No eligible entering variable for a negative RHS row LP infeasible under current model Use infeasible checklist; check signs/units/bounds
You can’t even form a starting tableau cleanly Need artificials for = / β‰₯ constraints Review slack/surplus/artificial variables, then use two-phase
Solver returns β€œunbounded” after edits Missing realistic variable bounds or anchoring constraints See Upper Bounds in Linear Programming
Solver says β€œmultiple optima” Alternate optimal face exists See Multiple Optimal Solutions in LP

Glossary

Glossary

  • Primal feasible: current basic solution satisfies RHS β‰₯ 0 (and variable bounds).
  • Dual feasible (tableau sense): reduced costs satisfy the optimality sign condition for the chosen convention.
  • Reduced cost: marginal objective change of increasing a nonbasic variable from 0; used for optimality tests.
  • Leaving variable (dual simplex): a basic variable with negative RHS (infeasible) selected to exit the basis.
  • Entering variable (dual simplex): chosen to fix the leaving row’s infeasibility while preserving reduced-cost signs.
  • Pivot: row/column operation that changes the basis.
  • Re-optimization: resolving an LP after minor changes (new constraint, changed RHS, changed cost).

Disclaimer

This article and the associated calculators are provided for educational and informational purposes only. Optimization outcomes depend on modeling assumptions and input data and may not reflect real-world constraints unless you encode them correctly. This is not legal, financial, operational, or safety advice. For high-stakes decisions, validate results against domain requirements and consult a qualified professional. For details, read our full disclaimer.

Sources
  1. Wikipedia β€” Simplex algorithm (primal/dual simplex overview)
  2. Wikipedia β€” Dual simplex method
  3. Google OR-Tools β€” Linear Programming documentation
  4. COIN-OR CLP β€” LP solver documentation (simplex implementations)
  5. GNU GLPK β€” LP solver project documentation
  6. SCIP Documentation β€” LP/MIP foundations and solver components