Recipe
Solve an LP that needs artificial variables
Use when: a standard-form LP has at least one \ge or = constraint, so the all-slack starting basis isn't available
Goal: the optimal solution of the original LP, or a certificate that none exists
Taught in Two-phase simplex · extends Run the simplex method to completion
Quick recipe
-
1
Convert a minimize objective to a maximize (Section 2), and flip any row with a negative right-hand side by multiplying it by -1.
Example
\min\ 2x_1+3x_2 becomes \max\ -2x_1-3x_2; every right-hand side in this chapter's examples is already nonnegative.
Why: every later step assumes a maximize objective and \mathbf b\ge\mathbf0, exactly like the ordinary pivot recipe (Section 7, Step 1).
-
2
A \le row gets an ordinary slack, nothing more. A \ge row gets a surplus SUBTRACTED, then an artificial ADDED (the surplus alone leaves no nonnegative starting value). An = row gets only an artificial, added directly.
Example
A blend problem's three rows: 3x_1+x_2=3 gets 3x_1+x_2+a_1=3 (artificial only); 4x_1+3x_2\ge6 gets 4x_1+3x_2-e_2+a_2=6 (surplus and artificial); x_1+2x_2\le4 gets x_1+2x_2+s_3=4 (slack only, no artificial needed).
Why: only a row with no slack sitting alone in it (a \ge or = row) fails to start at a nonnegative value with everything else at 0 — a \le row's slack already does that job for free.
-
3
With every artificial variable in place, two equally valid routes reach the same optimum — pick one before pivoting.
- Big-M — build one augmented objective, original objective minus M\sum a_i, and run the ordinary pivot recipe (Section 7) once, straight through to optimality.
- Two-phase — run Phase 1 first (temporarily minimize \sum a_i alone) to completion; if it reaches 0, drop the artificial columns, restore the real objective, recompute its reduced costs from the current basis, and run the ordinary pivot recipe again for Phase 2.
⚡ Shortcut
Two-phase avoids ever choosing a concrete value for M — a real practical trap, since an M chosen too small silently fails to dominate (producing a wrong entering-variable choice) and one chosen too large makes hand arithmetic (or floating-point computation) unstable. Two-phase's only cost is running the pivot loop twice instead of once.
Why: both routes drive every artificial toward 0 as fast as the greedy entering-variable rule allows — Big-M by penalizing it directly in one combined objective, two-phase by making eliminating it the ONLY objective, temporarily, in its own separate run.
-
4
Check the relevant stopping point: Big-M's own final optimum, or Phase 1's own minimum value. If any artificial variable is still positive there, the original LP is infeasible (the Big-M infeasibility certificate, Section 8). Otherwise, drop every artificial column and report the optimal real-variable solution and objective value.
Example
Both worked examples below reach every artificial exactly 0 at their relevant stopping point — genuine optima of the ORIGINAL problem, not artifacts of the penalty or the two-run split.
Why: a positive artificial at the point that matters means no assignment of the REAL variables alone ever satisfied every constraint — the scaffolding never came down, so the building it was propping up was never actually standing on its own.
Common mistakes
- Forgetting the artificial on an = row — it has neither a slack nor a surplus of its own, so without one there's no starting basic variable for that row at all.
- In two-phase, leaving the artificial columns in the tableau for Phase 2 instead of dropping them — a stray artificial column can re-enter and undo Phase 1's work.
- In two-phase, copying Phase 2's reduced costs from the ORIGINAL objective instead of recomputing them from the basis Phase 1 actually finished on.
- Declaring "infeasible" from a positive artificial mid-computation, rather than checking only at the relevant stopping point.
- Picking a Big-M value that isn't actually large enough relative to the problem's other numbers.