Simplex method: Big-M and two-phase

Why it matters

Real production LPs have dozens of products and hundreds of constraints, far beyond a graph. The simplex method solves them by walking from corner to corner of the feasible region, improving the objective at every step. Big-M and two-phase are the two standard ways of starting simplex when the constraints include ≥ or = rows, which is the case in almost every cost-minimisation, blending and scheduling model.

Key ideas

Standard form. Every constraint is turned into an equation with a non-negative right-hand side:

• ≤ row: add a slack variable s ≥ 0 (unused resource).
• ≥ row: subtract a surplus variable s ≥ 0 (amount above requirement).
• If a bᵢ is negative, multiply the row by −1 first (this flips ≤ and ≥).

Basic feasible solution (BFS). With m equations and n variables, set n − m variables (non-basic) to zero and solve for the m basic ones. A BFS with all basic values ≥ 0 is exactly a corner point of the feasible region.

Simplex iteration (maximisation, Cj − Zj form).

1. Optimality test: compute the net evaluation Cj − Zj for every non-basic column. If all are ≤ 0, the tableau is optimal.
2. Entering variable: the column with the most positive Cj − Zj (largest per-unit improvement).
3. Leaving variable — minimum ratio test: divide the RHS by the positive entries of the entering column; the smallest ratio decides the leaving row. It keeps every variable non-negative.
4. Pivot: make the pivot element 1 and every other entry of its column 0 by row operations. Repeat. (For minimisation, use the most negative Cj − Zj to enter and stop when all are ≥ 0, or maximise −Z.)

Reading the final tableau.

• Unbounded: the entering column has no positive entry — no ratio exists.
• Alternative optima: a non-basic variable has Cj − Zj = 0 at optimality.
• Degeneracy: a tie in the ratio test, giving a basic variable equal to 0; it can cause cycling in theory.
• Infeasible: an artificial variable stays positive in the final solution.

Why artificial variables. A ≥ or = row has no slack with coefficient +1 to start the basis. An artificial variable R ≥ 0 is added to such rows purely to give an initial identity basis. It has no physical meaning and must be driven to zero.

Big-M method. Penalise artificials in the objective with a very large M: for Max Z, add −M·R; for Min Z, add +M·R. Then run ordinary simplex. Drawback: hand calculations carry M symbolically, and in a computer a numerical M causes round-off trouble.

Two-phase method.

• Phase 1: minimise r = sum of artificials subject to the constraints. If min r > 0, the original LP is infeasible. If min r = 0, the final basis is a BFS of the original problem.
• Phase 2: drop the artificial columns (keep any degenerate zero-valued artificial carefully), restore the original objective and continue simplex. Both methods reach the same optimum; two-phase avoids the large number and is what solvers effectively use.

Formulas

• Net evaluation: Cj − Zj, where Zj = Σ C_B,i · aᵢⱼ
• Objective value of a tableau: Z = Σ C_B,i · bᵢ
• Minimum ratio test: θ = min { bᵢ / aᵢₖ : aᵢₖ > 0 }
• Pivot row update: new pivot row = old pivot row / pivot element
• Other rows: new row = old row − (entry in pivot column) × new pivot row
• Big-M objective: Max Z = Σ cⱼxⱼ − M·ΣRᵢ or Min Z = Σ cⱼxⱼ + M·ΣRᵢ
• Phase 1 objective: Min r = ΣRᵢ

Symbols: Cj = objective coefficient of column j (₹/unit); C_B,i = objective coefficient of the i-th basic variable; aᵢⱼ = current tableau entry; bᵢ = current RHS (value of the i-th basic variable); k = entering column; M = large positive penalty; Rᵢ = artificial variables. These hold for any LP in standard form.

Worked examples

Example 1 (standard simplex). Max Z = 3x₁ + 5x₂ subject to x₁ ≤ 4, 2x₂ ≤ 12, 3x₁ + 2x₂ ≤ 18, x ≥ 0.

1. Add slacks s₁, s₂, s₃; initial basis (s₁, s₂, s₃) = (4, 12, 18), Z = 0. Cj − Zj: x₁ = 3, x₂ = 5.
2. x₂ enters (5 is largest). Ratios: s₂ row 12/2 = 6, s₃ row 18/2 = 9; s₁ row has 0 (no ratio). s₂ leaves.
3. After pivoting: x₂ = 6, s₁ = 4, s₃ = 6, Z = 30. Cj − Zj: x₁ = 3, s₂ = −5/2.
4. x₁ enters. Ratios: s₁ row 4/1 = 4, s₃ row 6/3 = 2. s₃ leaves.
5. After pivoting: x₁ = 2, x₂ = 6, s₁ = 2, Z = 36. Cj − Zj: s₂ = −3/2, s₃ = −1, all ≤ 0.
6. Optimum x₁ = 2, x₂ = 6, Z = 36, the same corner the graphical method gives. The magnitudes 3/2 and 1 under s₂ and s₃ are the shadow prices of those resources.

Example 2 (GATE-type, two-phase). Min Z = 4x₁ + x₂ subject to 3x₁ + x₂ = 3, 4x₁ + 3x₂ ≥ 6, x₁ + 2x₂ ≤ 4, x ≥ 0.

1. Standard form: 3x₁ + x₂ + R₁ = 3; 4x₁ + 3x₂ − x₃ + R₂ = 6; x₁ + 2x₂ + x₄ = 4 (x₃ surplus, x₄ slack, R₁, R₂ artificial).
2. Phase 1: Min r = R₁ + R₂. Initial basis (R₁, R₂, x₄) = (3, 6, 4), r = 9. Reduced costs: x₁ = −7, x₂ = −4, x₃ = +1.
3. x₁ enters; ratios 3/3 = 1, 6/4 = 1.5, 4/1 = 4 → R₁ leaves. Now x₁ = 1, R₂ = 2, x₄ = 3, r = 2; reduced cost of x₂ = −5/3.
4. x₂ enters; ratios 1/(1/3) = 3, 2/(5/3) = 1.2, 3/(5/3) = 1.8 → R₂ leaves. Now x₁ = 3/5, x₂ = 6/5, x₄ = 1, r = 0. Phase 1 ends: feasible.
5. Phase 2: original objective at this BFS: Z = 4(3/5) + 6/5 = 18/5 = 3.6. Reduced cost of x₃ is −1/5 < 0, so x₃ enters; the only ratios are 3 (x₁ row) and 1 (x₄ row) → x₄ leaves.
6. New BFS: x₁ = 2/5, x₂ = 9/5, x₃ = 1; all reduced costs ≥ 0.
7. Optimum x₁ = 0.4, x₂ = 1.8, Z = 3.4. Check: 3(0.4) + 1.8 = 3 ✓; 4(0.4) + 3(1.8) = 7 ≥ 6 ✓; 0.4 + 3.6 = 4 ≤ 4 ✓. Big-M with M = 1000 passes through the same bases and gives the same answer.

Common mistakes

• Choosing the leaving row by the largest ratio, or including zero or negative column entries in the ratio test.
• Using the wrong sign for M: it is −M in a maximisation and +M in a minimisation.
• Forgetting to update the objective row to account for artificials in the basis before the first iteration.
• Stopping when a non-basic Cj − Zj is zero and missing that alternative optima exist.
• Reporting a "solution" with an artificial variable still positive — that means infeasible.
• Mixing the Cj − Zj and Zj − Cj sign conventions in one tableau.

For GATE PI

• One-iteration questions: identify the entering and leaving variables, the pivot element, or Z after an iteration.
• Interpreting a given final tableau: optimal values, shadow prices, alternative optima, unboundedness, infeasibility.
• Conceptual MCQs on slack, surplus and artificial variables, and on what Phase 1 tells you.
• Practise one full tableau sequence by hand until pivot arithmetic is quick and error-free.

Quick check

1. In a maximisation tableau the entering column has entries −2, 0 and −1. What do you conclude?
2. What is the sign of the artificial-variable coefficient in Big-M for a minimisation problem?
3. Phase 1 ends with r = 2. What does this mean?
4. Which variable type is added to a ≤ constraint?

Answers: 1. The LP is unbounded. 2. +M. 3. The original LP has no feasible solution. 4. A slack variable.