The standard simplex method needs an obvious starting basic feasible solution (BFS) — typically the slack variables. But for LPPs with = or ≥ constraints, there is no immediate identity submatrix to use as the basis. To create one, we add artificial variables with a large penalty in the objective.
Two popular approaches use this idea:
Min \(Z = 5 x_1 + 4 x_2\) subject to \(2 x_1 + x_2 \ge 12,\;\; x_1 + 2 x_2 \ge 12,\;\; x_1, x_2 \ge 0\).
Introduce surplus \(s_1, s_2\) and artificials \(A_1, A_2\):
| cB | Basis | xB | x₁ (5) | x₂ (4) | s₁ (0) | s₂ (0) | A₁ (M) | A₂ (M) | θ |
|---|---|---|---|---|---|---|---|---|---|
| M | A₁ | 12 | 2 | 1 | −1 | 0 | 1 | 0 | 12/2 = 6 |
| M | A₂ | 12 | 1 | 2 | 0 | −1 | 0 | 1 | 12/1 = 12 |
| Zj | 24M | 3M | 3M | −M | −M | M | M | ||
| cj−Zj | 5−3M | 4−3M | M | M | 0 | 0 | |||
For Min, we want all \(c_j - Z_j \ge 0\). Both \(x_1\,(5 - 3M)\) and \(x_2\,(4 - 3M)\) are strongly negative for large \(M\), so either may enter; we bring in \(x_1\) (both choices reach the same optimum). Smallest θ ratio = 6 ⇒ row 1 leaves; pivot at (1, x₁) with element 2.
Normalise row 1 (divide by 2), then eliminate x₁ from row 2 (subtract row 1).
| cB | Basis | xB | x₁ (5) | x₂ (4) | s₁ (0) | s₂ (0) | A₂ (M) | θ |
|---|---|---|---|---|---|---|---|---|
| 5 | x₁ | 6 | 1 | 1/2 | −1/2 | 0 | 0 | 6/(1/2) = 12 |
| M | A₂ | 6 | 0 | 3/2 | 1/2 | −1 | 1 | 6/(3/2) = 4 |
| Zj | 30+6M | 5 | 5/2 + 3M/2 | −5/2 + M/2 | −M | M | ||
| cj−Zj | 0 | 3/2 − 3M/2 | 5/2 − M/2 | M | 0 | |||
Most negative is \(3/2 - 3M/2\) ⇒ x₂ enters; smallest ratio = 4 ⇒ A₂ leaves; pivot = 3/2.
After pivoting, the basis becomes \(\{x_1, x_2\}\) with values \(x_1 = 4, x_2 = 4\), Z = 5(4) + 4(4) = 36.
All artificials have left the basis ⇒ feasible. Check optimality: all \(c_j - z_j \ge 0\) ⇒ optimum.
Solution: \(x_1 = 4,\; x_2 = 4,\; Z_{\min} = 36\).
An alternative to Big-M that avoids the algebraic awkwardness of a large symbolic \(M\). It proceeds in two phases:
Min \(Z = 5 x_1 + 4 x_2\) s.t. \(2 x_1 + x_2 \ge 12,\; x_1 + 2 x_2 \ge 12,\; x_1, x_2 \ge 0\).
Minimise \(W = A_1 + A_2\) subject to the same constraints.
| cB | Basis | xB | x₁ (0) | x₂ (0) | s₁ (0) | s₂ (0) | A₁ (1) | A₂ (1) |
|---|---|---|---|---|---|---|---|---|
| 1 | A₁ | 12 | 2 | 1 | −1 | 0 | 1 | 0 |
| 1 | A₂ | 12 | 1 | 2 | 0 | −1 | 0 | 1 |
| cj−Zj | −3 | −3 | 1 | 1 | 0 | 0 | ||
x₁ enters (or x₂ — both tied). Choose x₁. Ratios 6, 12 ⇒ A₁ exits.
After two iterations the artificials are eliminated and \(W = 0\), giving BFS \((x_1, x_2) = (4, 4)\). Phase 1 successful.
Use the BFS \((x_1 = 4, x_2 = 4)\) with the original objective Min \(Z = 5 x_1 + 4 x_2\). Compute \(c_j - z_j\) ⇒ already all ≥ 0 ⇒ optimal.
Solution: Same as Big-M: \(x_1 = 4, x_2 = 4, Z_{\min} = 36\).
| Aspect | Big-M | Two-Phase |
|---|---|---|
| How handles artificials | Large penalty M in objective | Auxiliary objective W in Phase 1 |
| Numerical stability | Sensitive to choice of M | More stable; avoids large numbers |
| Pen-and-paper feel | One pass | Two passes |
| Used in software | Rare | More common |
A basic feasible solution is degenerate if one or more basic variables take the value zero. In the simplex method, degeneracy is detected by a tie in the minimum-ratio test.
Consider an LPP whose simplex tableau gives, at some iteration, two rows with identical ratios. Pick any one of them as the pivot row (or apply Bland's rule). The iteration may produce a BFS with one basic variable = 0 — that's degeneracy. Proceed with the next iteration; the algorithm should still terminate.
Detection: In the final simplex tableau, a non-basic variable has \(c_j - z_j = 0\). It can enter the basis without changing \(Z\), giving another optimal BFS.
The set of optimal solutions is the convex combination of these alternative BFSs.
Detection: The entering column has all non-positive entries. No row gives a positive ratio ⇒ the entering variable can be increased indefinitely without violating any constraint. \(Z\) is unbounded.
Detection: At optimality of the Big-M (or Phase 1 of Two-Phase), an artificial variable remains in the basis with a positive value. There is no feasible solution.
Detection: A basic variable in the optimum BFS equals zero, or a tie occurs in a minimum-ratio test.
| Indication in tableau | Meaning |
|---|---|
| Non-basic variable has \(c_j - z_j = 0\) at optimum | Alternative optima |
| Entering column has all ≤ 0 entries | Unbounded |
| Artificial variable basic at positive value at end | Infeasible |
| Tie in min-ratio test / basic variable = 0 | Degenerate |
The simplex method's pivoting machinery can solve a system of linear equations \(A\mathbf{x} = \mathbf{b}\) — treat the system as the equality constraints of an LPP with a dummy objective.
Solve \(2 x_1 + x_2 = 8,\;\; x_1 + 3 x_2 = 9\) using simplex (Phase 1).
Add artificials: \(2 x_1 + x_2 + A_1 = 8,\; x_1 + 3 x_2 + A_2 = 9\). Min \(W = A_1 + A_2\).
After two simplex iterations, \(W = 0\) with \(x_1 = 3, x_2 = 2\). Verify: \(2(3) + 2 = 8\) ✓; \(3 + 3(2) = 9\) ✓.