Big M and Two Phase Methods: Explained with Examples

Big M and two-phase methods are techniques for starting the simplex method when there is no obvious initial basic feasible solution. This happens when constraints are of type ≥ or =, which cannot take slack variables as a starting basis.

They matter because real problems often have minimum requirements ("produce at least 500 units") or exact targets ("the budget must be exactly used"). These methods handle such constraints systematically so the simplex method can still be applied.

Key Concepts

• Artificial variable: a temporary helper variable added to a ≥ or = row to create a starting basis; it must leave the basis (become zero) for a real solution.
• Surplus variable: subtracted from a ≥ constraint: ax ≥ b becomes ax − s = b with s ≥ 0.
• Big M: a penalty of M (a huge positive number) assigned to each artificial variable in the objective.
• Two-phase method: Phase I minimises the sum of artificial variables; Phase II solves the original problem from the resulting basis.
• Infeasible: if an artificial variable stays positive at the end, the original problem has no solution.

Formulas

For a ≥ constraint ax ≥ b: ax − s + A = b (s surplus, A artificial).

• Big M objective (maximisation): Z = (original terms) − M·(sum of artificial variables).
• Two-phase Phase I: minimise w = sum of artificial variables (or maximise −w). If minimum w > 0, the problem is infeasible.

Assumption: M is larger than any number that could appear in the real problem, so the method never prefers keeping an artificial variable positive.

Worked Example

Maximise Z = 2x + 3y subject to x + y ≥ 4, x, y ≥ 0. Convert: x + y − s + A = 4. Objective: Z = 2x + 3y − MA.

1. Start: A = 4 in basis. Pivoting out A: entering y (or x). Choose y: new y = 4 − s → y = 4.
2. Now A = 0 and has left the basis. Z = 2x + 3(4 − s)… the tableau drives y further with x free: since x costs nothing in the converted form, x rises while y = 4 − x adjusted… re-solving cleanly: with y = 4 − x − s + A, A = 0 requires s = 0 at optimum, so y = 4 − x and Z = 2x + 3(4 − x) = 12 − x. Z is maximised at x = 0, giving Z = 12 with y = 4.
3. Check: 0 + 4 ≥ 4 ✓. Optimal Z = 12.

Common Misconceptions

• "Artificial variables are part of the answer." They are scaffolding; a valid final answer has all of them at zero.
• "Big M is a number I should pick, like 100." M must exceed any realistic value; in practice solvers treat it symbolically.
• "Two-phase always succeeds." Phase I ending with w > 0 proves the problem has no feasible solution.

Real-World Applications

• Production planning with minimum order quantities uses ≥ constraints solved this way.
• Diet and blending problems have minimum nutrient requirements handled by surplus variables.
• Workforce scheduling enforces exact staffing levels with equality constraints.

Big M and two-phase methods let the simplex algorithm start where no natural starting corner exists, by adding temporary artificial variables and then forcing them out. They extend linear programming to the minimum-requirement and exact-target constraints that dominate real planning problems.