Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Solve an LP with the Big-M method

Use when: a standard-form LP has at least one \ge or = constraint with no natural starting slack, and you want to solve it directly in one penalized simplex run

Goal: the optimal solution of the original LP, or a certificate (a positive artificial) that none exists

Taught in The Big-M method

Quick recipe

  1. Convert to standard max form with artificial variables
  2. Add the penalty term to the objective
  3. Run the ordinary simplex pivot recipe to completion
  4. Read the artificials in the final tableau
  1. 1

    Convert a minimize objective to maximize (multiply by -1). For a \ge row, subtract a surplus, then add an artificial; for an = row, add an artificial directly; a \le row keeps its ordinary slack, no artificial needed.

    Example

    \min\ 2x_1+3x_2 becomes \max\ -2x_1-3x_2; x_1+2x_2\ge10 becomes x_1+2x_2-e_1+a_1=10; 3x_1+x_2\ge15 becomes 3x_1+x_2-e_2+a_2=15.

    Why: setting every real and surplus variable to 0 and each artificial equal to its row's right-hand side makes that row feasible right away, giving simplex a starting corner to stand on.

  2. 2

    Augment the objective with -M times the sum of the artificials, for a constant M chosen large enough to dominate every other coefficient in the problem.

    Example

    \max\ -2x_1-3x_2-Ma_1-Ma_2, with M=1000 standing in for "sufficiently large."

    Why: an enormous M makes any solution with a positive artificial so costly that simplex's own greedy rule abandons it the moment a real alternative exists.

  3. 3

    Pivot exactly as Section 7's recipe describes -- most negative reduced cost enters, the ratio test decides who leaves -- until every z-row entry is \ge0.

    Example

    x_1 enters first (-3998 beats -2997), the ratio test sends a_2 out; one more pivot brings x_2 in and a_1 leaves; final tableau: x_1=4,\ x_2=3,\ a_1=a_2=0.

    Why: the penalty is already baked into the reduced costs, so no separate bookkeeping is needed -- the same pivot rule that solves an ordinary LP drives the artificials out on its own.

  4. 4

    Check whether every artificial variable equals 0 in the optimal tableau.

    Example

    Blend problem: a_1=a_2=0, so x_1=4,\ x_2=3, cost \$17 is the genuine optimum. Shipping example below: a_2=4>0 at the optimal tableau, certifying the dock-capacity and contract-minimum requirements are infeasible.

    • every artificial is 0 at the optimal tableau — this is a genuine optimum of the ORIGINAL problem; drop the artificial columns and report the real solution.
    • some artificial is still positive at the optimal tableau — the original LP is infeasible; the positive artificial is the algebraic certificate, not a computational failure.

    Why: a positive artificial in an otherwise-optimal tableau means no assignment of the real variables alone ever satisfied every constraint -- exactly the Big-M infeasibility certificate above.

Common mistakes

  • Forgetting the artificial on an = row -- it has no slack or surplus of its own, so without one there's no starting basic variable for that row.
  • Choosing an M that isn't actually large enough relative to the problem's other numbers, letting a real variable's column look falsely attractive.
  • Declaring "infeasible" from a positive artificial mid-computation instead of checking only at the optimal tableau.
  • Reporting the penalized objective value instead of the real one once the artificials are confirmed to be 0.