Dual Simplex Method: Concepts, Formulas and Examples

The dual simplex method is a variant of the simplex algorithm that starts from an infeasible but optimal-looking solution and works toward feasibility. Instead of beginning inside the feasible region, it begins at a corner where the optimality condition holds and fixes violated constraints one by one.

It matters because it is the fastest way to re-solve a problem after small changes: when a new constraint is added or a resource amount changes, the old optimal solution usually stays "optimal but infeasible" — exactly where dual simplex starts. This is the core of sensitivity analysis.

Key Concepts

• Primal simplex: feasible but not optimal → works toward optimality.
• Dual simplex: optimal (Zⱼ − Cⱼ ≤ 0 for maximisation) but infeasible (some basic value negative) → works toward feasibility.
• Leaving variable: the basic variable with the most negative value.
• Entering variable: chosen by min ratio (Zⱼ − Cⱼ)/aᵣⱼ over columns with aᵣⱼ < 0.
• Starting point: needs all Zⱼ − Cⱼ ≤ 0 (maximisation) with at least one negative right-hand-side value.

How It Works

1. Arrange the problem as a tableau that is optimal (net evaluations ≤ 0 for maximisation) but infeasible (some bᵢ < 0).
2. Pick the leaving row: the most negative right-hand-side value.
3. Pick the entering column: minimum of (Zⱼ − Cⱼ)/aᵣⱼ among columns where aᵣⱼ < 0.
4. Pivot on that element and repeat until every right-hand-side value is ≥ 0.
5. The final tableau is both feasible and optimal — optimality was preserved at every step.

Worked Example

Maximise Z = −x − y subject to −x − 2y ≤ −4, −x − y ≤ −3, x, y ≥ 0. The tableau starts with basic slacks s₁ = −4, s₂ = −3 (infeasible), but net evaluations are already ≤ 0.

1. Leaving row: s₁ = −4 (most negative). Entering: min ratio on row 1 over negative coefficients: column x gives 0/(−1) = 0 → x enters.
2. Pivot: new x = 4 − 2y + s₁…; tableau gives x = 4, s₂ = 1, net evaluations still ≤ 0 but RHS all ≥ 0? Check: with x = 4, y = 0: constraints −4 ≤ −4 ✓, −4 ≤ −3 ✓. Optimal Z = −4.
3. Verify by substitution: minimise x + y subject to x + 2y ≥ 4, x + y ≥ 3. At (4, 0): 4 + 0 ≥ 4 ✓, 4 ≥ 3 ✓, objective 4 is minimal since x + 2y ≥ 4 forces x + y ≥ 4 − y ≥ … any point needs x + y ≥ 4? At (0, 3): x + 2y = 6 ≥ 4 ✓, x + y = 3 ✓, objective 3 < 4! Continue: (0, 3) has x + y = 3, better. True optimum: the binding pair x + 2y = 4, x + y = 3 gives x = 2, y = 1, objective 3. So Zₘₐₓ = −3 at (2, 1): check −2 − 1 = −3 ✓, constraints: −2 − 2 = −4 ≤ −4 ✓, −3 ≤ −3 ✓.

The final feasible-and-optimal answer is Z = −3 at (x, y) = (2, 1).

Common Misconceptions

• "It solves the dual problem." It solves the primal problem using dual-style logic; the name refers to the method, not the problem.
• "Negative right-hand sides mean the data is wrong." They just mean the current corner is outside the feasible region — the method's job is to fix that.
• "It works from any tableau." It needs the optimality condition already satisfied; otherwise start with regular simplex.

Real-World Applications

• Solvers re-optimise instantly when a manager adds a new constraint to an existing plan.
• Cutting-plane algorithms add cuts that make the solution infeasible, then re-solve with dual simplex.
• Supply-chain software re-runs plans after demand forecasts change without restarting.

The dual simplex method is the tool of choice when a solution looks optimal but breaks a constraint: it repairs feasibility while holding onto optimality. That makes it the backbone of re-optimisation and sensitivity analysis in practice.