Learning outcomes
- Explain why ≥ and = constraints need artificial variables.
- Apply the Big-M method and interpret its tableaus.
- Apply the two-phase method and know when to prefer it.
- Detect infeasibility, unboundedness, alternate optima and degeneracy from a tableau.
- Diagnose and repair a failing model.
Start here
Everything so far rested on one quiet convenience: when every constraint is ≤, doing nothing is allowed. Produce zero of everything and every resource simply sits unused, no rule broken. That do-nothing point is a corner of the feasible region, so simplex — which only ever walks from one corner to the next — always had somewhere legal to stand before taking its first step.
Real models are not so polite. A supply contract says deliver at least 30 units; a blend must total exactly 100 kg. Doing nothing now breaks a promise, so the origin sits outside the feasible region. And that is a genuine emergency for simplex: it has no first corner to walk from, so it cannot even begin. Not a slow answer — no answer.
So we cheat, deliberately and temporarily. We add a fake variable to the offending row — an artificial — chosen so that the row is satisfied on paper the moment we set everything real to zero. That gives simplex its first corner. The catch is that the fake variable is standing in for a broken promise: while it is positive we are solving an easier problem than the one we were asked. Driving it back to zero is the whole game.
There are two ways to force it back down. Big-M bribes the algorithm: it hangs a colossal price tag M on every artificial, and simplex then expels them the way it flees any ruinously expensive activity. Two-phase is more disciplined: Phase I forgets the real objective entirely and does nothing but shrink the artificials. If they reach zero, we have a genuine corner and Phase II optimises for real; if they cannot, no such corner exists — the model is infeasible, and what is left over measures exactly how badly.
1. Why a ≥ or = constraint leaves no starting point
Simplex begins from a basic feasible solution: choose as many variables as there are constraint rows — the basis — set every other variable to zero, and solve. For that to be easy, each row needs to own one variable that appears in it with coefficient +1 and in no other row at all. Then the owner's value is just the number on the right-hand side, read straight off.
When every constraint is ≤ with bᵢ ≥ 0, the slacks hand us such a basis for free: zero the real variables and read sᵢ = bᵢ ≥ 0. Every owner is non-negative, so the origin is feasible and we are away.
A ≥ constraint destroys exactly this. Written in standard form, 3x₁ + x₂ ≥ 6 has to subtract the amount by which the left side overshoots the right:
Try the same trick and the row bites back. Setting x₁ = x₂ = 0 forces s₁ = −6, which breaks s₁ ≥ 0 — so that is not a feasible solution at all, and there is nothing to start from. The culprit is the sign, not the size: a row's owner needs a +1 coefficient, and the surplus has −1, so the surplus can never be it. An equality is worse still. The row 3x₁ + x₂ = 3 has no extra variable of any kind, so it owns nothing whatsoever.
Since the row will not supply an owner, we supply one ourselves — and that is all an artificial variable is.
A variable Aᵢ ≥ 0 added with coefficient +1 to a ≥ or = row purely to supply a basic variable for that row. It has no meaning in the original model, which is recovered only when every artificial equals zero.
Check that it works: set x₁ = x₂ = s₁ = 0 and the first row gives A₁ = 6, the second gives A₂ = 3. Both are non-negative, both rows are satisfied, and simplex has its corner.
But notice what we have actually done. A₁ = 6 says the first row is being propped up by six units of nothing; the point (0, 0) does not satisfy 3x₁ + x₂ ≥ 6. We bought a starting point by changing the problem, and any solution that still carries a positive artificial solves the augmented system, not the one we were asked about.
2. The Big-M method
We now have a starting corner and a debt to repay: every artificial must be driven to zero. Big-M repays it by making the debt unbearable. Rather than adding a rule that says "get rid of the artificials", we make them so expensive that the ordinary objective already wants them gone. Attach a penalty M to each artificial, with M larger than any number that could otherwise arise in the problem:
Because M dominates every genuine coefficient, any solution carrying a positive artificial is catastrophically worse than one that does not. Simplex therefore expels the artificials first, for its own reasons, without a special instruction — which is the entire trick. Note the condition on M: it must be big enough that no combination of real coefficients can ever make keeping an artificial look worthwhile. Too small an M and the bribe fails silently.
The three outcomes
| At optimality | Conclusion |
|---|---|
| All Aᵢ = 0 | optimal for the original problem ✓ |
| Some Aᵢ > 0 | the original problem is INFEASIBLE |
| Z unbounded with all Aᵢ = 0 | the original problem is UNBOUNDED |
The second row is the one that bites. Simplex does not crash on an infeasible model: it terminates normally, with an artificial still basic at a positive value. Fail to check, and you report a solution that violates a constraint.
Handling M inside the tableau
One practical nuisance follows. The row that tests optimality — the zⱼ − cⱼ row, whose entries say how much the objective changes per unit of each non-basic variable brought in — no longer holds plain numbers. Its entries become expressions such as −7M + 4, two numbers of wildly different scale glued together, and at every iteration you must decide which of several such expressions is the most negative.
There are two ways to cope. Symbolic: keep M as a symbol and compare the coefficients of M first, using the constants only to break ties. Numeric: commit to one large number for M, safely above any coefficient in the problem. These notes use M = 1000.
The two conventions never disagree, and it is worth seeing why. Suppose two entries read −7M + 4 and −4M + 1. Which is more negative? Their difference is −3M + 3, so for any M above 1 the first one wins — and M is by construction enormous. The constants 4 and 1 are along for the ride; they matter only when the M-coefficients tie. Drag the slider below from 0 upward and watch the two lines cross once, early, and then diverge for good.
3. The Big-M method at work
One problem, one of each awkward constraint:
Convert to a maximisation of Z′ = −4x₁ − x₂. The equality row needs one artificial, the ≥ row needs a surplus and an artificial, and the ≤ row supplies its own slack:
4x₁ + 3x₂ − s₂ + A₂ = 6
x₁ + 2x₂ + s₃ = 4max Z′ = −4x₁ − x₂ + 0s₂ + 0s₃ − MA₁ − MA₂
The geometry explains the difficulty before any arithmetic does. The equality is a line, not a half-plane, so every feasible point must lie exactly on it; the two inequalities then trim that line to a short segment. The segment is the whole feasible region — and the origin, where simplex would like to start, is nowhere near it.
How to read each stage
Four iterations follow, and every one of them is the same three decisions. Before stepping through, fix what each part of a tableau is telling you:
- The Basis column names the variables currently allowed to be non-zero; the RHS column gives their values. Everything not named in the Basis column is zero.
- The bottom zⱼ − cⱼ row rates each column: it is the change in Z′ per unit of that variable brought into the basis. We converted to a maximisation, so a negative entry means "bringing this in still improves things". Optimal means every entry ≥ 0.
- Entering variable: the most negative zⱼ − cⱼ. Leaving variable: the smallest ratio RHS ÷ (entering column entry), counting only positive entries — a zero or negative entry means that row never runs out, so it cannot stop the entering variable from rising. Their crossing point is the pivot; divide that row by the pivot, then clear the rest of the column.
The one thing to keep an eye on that is special to this lesson: watch the labels A₁ and A₂ in the Basis column, and note the exact iteration at which each disappears.
Verification. 3(0.4) + 1.8 = 3, the equality holds exactly; 4(0.4) + 3(1.8) = 7.0 ≥ 6 with surplus s₂ = 1; 0.4 + 2(1.8) = 4.0 ≤ 4, binding, so s₃ = 0; and Z = 3.4 ✓.
4. The two-phase method
Big-M worked. So why is there a second method at all? Look back at what the trace cost us. Every entry in that objective row was two numbers of utterly different size glued together — −7M + 4, then 4992/5 — and the small halves never once changed a decision. A computer storing both parts in one floating-point number simply loses the small one. And notice when the model's feasibility was finally settled: at the very end, after every scrap of optimisation work had already been done. On an infeasible model that whole effort is wasted.
Two-phase fixes both complaints at once by refusing to mix the two questions. It asks them separately, in the order that makes sense: is there a feasible point at all? first, and only if the answer is yes, which feasible point is best? No symbol M ever enters the arithmetic.
Phase I — feasibility. Throw the real objective away and replace it with
W is the total size of the artificials, so minimising it is a direct attempt to wipe them out. If W* > 0 they cannot all be driven out, which means no point satisfies every constraint: the problem is infeasible, and you stop here without ever costing anything. If W* = 0 every artificial has reached zero, so the tableau now describes a genuine basic feasible solution of the original problem — exactly the starting corner we could not find by hand.
Phase II — optimality. Drop the artificial columns, restore the original objective, and continue from the final Phase I tableau. One step is easy to forget: the zⱼ − cⱼ row you inherit rates columns against W, not against Z, so it must be recomputed against the current basis before you pivot again. The tableau body carries over untouched, so no pivoting work is repeated.
Run Phase I on the worked example and the pivots are identical to Big-M: x₁ then x₂ entering, A₁ then A₂ leaving. That is no coincidence, and the numbers show why. Phase I starts at W = 3 + 6 = 9 with objective row (−7, −4, +1, 0, 0, 0) — and those are precisely the M-coefficients of Big-M's iteration 0, where Z′ = −9M and the row read (−7M + 4, −4M + 1, M, 0, 0, 0). Since M is huge, every Big-M comparison was settled by those coefficients alone; the constants 4 and 1 never got a vote. The two methods were comparing the same numbers all along, and Phase I is simply Big-M with the M stripped out.
Phase I therefore ends at the same place, iteration 2, with W* = 0 and the BFS (0.6, 1.2). Phase II restores max Z′ = −4x₁ − x₂, recomputes the objective row, finds the same −1/5 under s₂, and that one pivot reaches the same optimum (0.4, 1.8) with Z = 3.4.
Why every real solver chooses two-phase
That is why Big-M never reached production code: the failure is not a crash but a wrong answer delivered confidently. It survives in textbooks because it fits on paper in one pass.
5. The four special cases, read off the tableau
We have just met a nasty habit of simplex: on an infeasible model it does not crash or complain — it terminates normally and leaves the evidence sitting in the tableau for you to notice. The same is true of every other way a model can misbehave. Nothing raises an alarm; each fault simply leaves a fingerprint, and there are exactly four of them to learn.
| Case | Tableau signature | Action |
|---|---|---|
| Infeasible | some Aᵢ > 0 at optimality, or W* > 0 in Phase I | relax a constraint |
| Unbounded | the entering column has no positive entry | add the missing constraint |
| Alternate optima | a non-basic variable has zⱼ − cⱼ = 0 | pivot to find the second optimum |
| Degenerate | a basic variable equals 0 | continue; watch for stalling |
The unbounded case is the one most often mistaken for an arithmetic slip. With no positive entry in the entering column the minimum-ratio test has no candidates, so no row limits how far the entering variable can rise: the objective improves forever along a ray.
6. Solved problems
x₁ + x₂ + s₁ = 4 and x₁ + x₂ − s₂ + A₁ = 8, with max Z = 3x₁ + 2x₂ − MA₁. The ≤ row brings its own slack; only the ≥ row needs an artificial.
The basis {s₁, A₁} has c_B = (0, −M), so Z = 0(4) + (−M)(8) = −8M. Building the objective row from that basis: under x₁, z₁ = 0(1) + (−M)(1) = −M and c₁ = 3, giving z₁ − c₁ = −M − 3; under x₂ the same sum with c₂ = 2 gives −M − 2. So zⱼ − cⱼ = (−M−3, −M−2, 0, M, 0). x₁ is the more negative, so it enters; the ratios 4/1 = 4 and 8/1 = 8 send s₁ out on pivot 1.
Row 1 is already divided by its pivot, so the only operation is R₂ − R₁, which turns the A₁ row into (0, 0, −1, −1, 1 | 4):
| Basis | c_B | x₁ | x₂ | s₁ | s₂ | A₁ | RHS |
|---|---|---|---|---|---|---|---|
| x₁ | 3 | 1 | 1 | 1 | 0 | 0 | 4 |
| A₁ | −M | 0 | 0 | −1 | −1 | 1 | 4 |
| zⱼ − cⱼ | 0 | 1 | M+3 | M | 0 | 12 − 4M |
The entries M + 3 and M are positive because M is huge, and the remaining ones are 0 and 1, so every zⱼ − cⱼ is non-negative: the optimality test passes and the algorithm halts, perfectly normally. Nothing has gone visibly wrong. But look at the Basis column — A₁ is still there, at the value 4. That single fact invalidates the whole answer, because A₁ = 4 means the ≥ row is still being propped up by four units of nothing.
That the model is impossible is obvious once stated: the constraints demand x₁ + x₂ ≤ 4 and x₁ + x₂ ≥ 8 at the same time, and 4 < 8. What is not obvious is that the tableau tells you more than "impossible". The final Z = 12 − 4M carries the term −4M, which is M times the surviving artificial: the model is short by exactly 4 units. That is the minimum total constraint violation — the smallest amount by which any constraint must be bent to make the model solvable, and therefore how much extra capacity, or how much demand reduction, would restore feasibility. Modern solvers report exactly this number.
Both constraints are ≥, so both need a surplus and an artificial: x₁ + x₂ − s₁ + A₁ = 5 and x₁ + 2x₂ − s₂ + A₂ = 6. The starting basis is {A₁, A₂}, so W = A₁ + A₂ = 5 + 6 = 11 — that is how far from feasible the propped-up start is.
The Phase I objective row has a shortcut worth understanding rather than memorising. Phase I is max −A₁ − A₂, so c_B = (−1, −1) for the two artificial rows and every real variable has cⱼ = 0. Then zⱼ − cⱼ = zⱼ = −(sum of that column down the artificial rows). In other words: add the artificial rows together and flip the sign.
Drop the A₁ and A₂ columns; they have done their job. The rest of the tableau carries over unchanged, but the objective row cannot: it currently rates columns against W, and W is not our objective any more. Recompute it against c_B = (2, 3), the real costs of the two basic variables:
zs₁ = 2(−2) + 3(1) = −1, and cs₁ = 0, so zs₁ − cs₁ = −1. Likewise zs₂ = 2(1) + 3(−1) = −1, so that entry is −1 too.
| Basis | c_B | x₁ | x₂ | s₁ | s₂ | RHS |
|---|---|---|---|---|---|---|
| x₁ | 2 | 1 | 0 | −2 | 1 | 4 |
| x₂ | 3 | 0 | 1 | 1 | −1 | 1 |
| zⱼ − cⱼ | 0 | 0 | −1 | −1 | Z = 11 |
Here both entries are −1 ≤ 0, so no column improves Z: Phase I happened to land straight on the optimum, and Phase II needs no pivot at all.
4 + 1 = 5 ≥ 5 and 4 + 2(1) = 6 ≥ 6, both binding ✓. Graphically the corners are (6, 0) with Z = 12, (4, 1) with Z = 11 and (0, 5) with Z = 15 — the smallest is 11 at (4, 1), which is what the tableau said.
Both constraints are ≤, so the basis starts at {s₁, s₂} with no artificial. Iteration 0 has zⱼ − cⱼ = (−2, −1, 0, 0); x₁ enters and the ratios 10 and 20 send s₁ out on pivot 1. Iteration 1 has −3 under x₂, column (−1, 1)ᵀ, and the single ratio 20 sends s₂ out.
| Basis | c_B | x₁ | x₂ | s₁ | s₂ | RHS |
|---|---|---|---|---|---|---|
| x₁ | 2 | 1 | 0 | −1 | 1 | 30 |
| x₂ | 1 | 0 | 1 | −2 | 1 | 20 |
| zⱼ − cⱼ | 0 | 0 | −4 | 3 | 80 |
The −4 says s₁ should enter, so we look for the row that will stop it — and there is none. The ratio test only counts positive column entries, because those are the rows where a basic variable is being driven down towards zero. Here the column is (−1, −2)ᵀ, both negative, so raising s₁ makes both basic variables larger. No row runs out, there is no ratio to take, and nothing can stop s₁ rising.
The tableau even hands you the direction. Basic values update as RHS minus t times the entering column, so setting s₁ = t gives x₁ = 30 − (−1)t = 30 + t and x₂ = 20 − (−2)t = 20 + 2t, with Z = 80 − (−4)t = 80 + 4t → ∞. It stays feasible: x₁ − x₂ = 10 − t ≤ 10 for every t ≥ 0 ✓ and 2x₁ − x₂ = 60 + 2t − 20 − 2t = 40 ≤ 40, always binding ✓. Both constraints read (something) − x₂ ≤ constant, so raising x₂ loosens both, yet x₂ pays. Every LP claiming unbounded profit has a missing constraint, and the ray names the culprit.
x₁ is non-basic — it is not one of the labels in the Basis column, so its value is 0 — yet z₁ − c₁ = 0. Read that literally: bringing x₁ in changes Z by zero per unit. It does not improve the objective, which is why the tableau is optimal, but it does not worsen it either, which means there is a second optimal corner sitting somewhere along that column. The current optimum is x₁ = 0, x₂ = 4, Z = 4(4) = 16.
Pivot as usual. The x₁ column is (1/2, 3/2)ᵀ, giving ratios 4 ÷ 1/2 = 8 and 2 ÷ 3/2 = 4/3; the minimum 4/3 sends s₂ out on pivot 3/2. Row 2 ÷ (3/2) is (1, 0, −1/3, 2/3 | 4/3); row 1 minus half of that new row is (0, 1, 2/3, −1/3 | 10/3).
Z = 2(4/3) + 4(10/3) = 48/3 = 16, identical as required, so every point between is optimal too: x(λ) = λ(0, 4) + (1 − λ)(4/3, 10/3), λ ∈ [0, 1]; at λ = 1/2 that is (2/3, 11/3) with Z = 16 ✓. Note s₂ also shows zⱼ − cⱼ = 0, but s₂ is basic, as every basic variable is by construction. Only non-basic zeros count.
Nothing subtle is needed here. The two contracts must be honoured, and honouring them at the bare minimum already consumes 2(30) + 3(25) = 60 + 75 = 135 machine hours, while only 100 exist. The model is infeasible by 35 machine hours, and Phase I would confirm it by terminating with W* = 35. Solvers also report the Irreducible Infeasible Subsystem — the smallest set of constraints that is already contradictory on its own — which here is all three, since dropping any one of them restores feasibility.
Raise machine hours from 100 to 135, an extra 35, and both contracts survive untouched. At ₹200 per overtime hour that costs 35 × ₹200 = ₹7,000.
Keep capacity at 100 and break one promise instead. Relaxing x₂ ≥ 25 to x₂ ≥ q needs 2(30) + 3q ≤ 100, so 3q ≤ 40 and q ≤ 13.33 — product 2 falls to 13 whole units, a cut of (25 − 13)/25 = 48 %. Relaxing x₁ ≥ 30 to x₁ ≥ p instead needs 2p + 3(25) ≤ 100, so 2p ≤ 25 and p ≤ 12.5, i.e. 12 units, a cut of (30 − 12)/30 = 60 %. Product 2 is the cheaper promise to break, because each unit of it frees 3 hours rather than 2.
Better still, stop making the model choose for us. Soften both contracts into targets that may be missed at a price, using deviation variables d⁻ (shortfall) and d⁺ (excess):
This model is always feasible — any shortfall can be absorbed by a deviation variable — so instead of the word "infeasible" it returns the least-cost way to break the promises. With penalties p₁ = ₹500 and p₂ = ₹300 per unit short, the right comparison is not the penalty per unit but the penalty per machine hour saved, since hours are what we are short of: ₹500/2 = ₹250 per hour for product 1, ₹300/3 = ₹100 per hour for product 2. Product 2 is the cheaper source of hours, so cut it. Saving all 35 hours from product 2 means cutting 35/3 = 11.67 units, giving x₁ = 30, x₂ = 25 − 11.67 = 13.33 and d₂⁻ = 11.67, which checks out as 2(30) + 3(13.33) = 60 + 40 = 100 ✓. The penalty is 11.67 × ₹300 = ₹3,500. Taking the same 35 hours out of product 1 would need 35/2 = 17.5 units cut, costing 17.5 × ₹500 = ₹8,750.
7. Where this is used
Blending and diet models
Full of "at least" specifications plus one exact "the batch totals 100 %". Phase I tells the blender whether the specification can be met at all.
Contract-bound production
Minimum deliveries are ≥ constraints. When capacity falls short, Phase I returns the gap in the units management cares about.
Solver infeasibility reports
Minimum total violation and the Irreducible Infeasible Subsystem both descend from the Phase I objective.
Goal programming for policy
Budget and service-level targets conflict by design; penalised goals guarantee feasibility and price each broken promise.
Model debugging
An unbounded result almost always means a forgotten capacity row, and the ray names the variables that grow.
Alternate optima as freedom
A whole segment of equally optimal plans lets a secondary criterion be applied for free.
8. Common mistakes
- Stopping when the artificials leave. The worked example was feasible at (0.6, 1.2) with Z = 3.6 and still needed a pivot to reach 3.4.
- Not checking the artificials. Big-M terminates normally on an infeasible model; if an Aᵢ is basic and positive, the answer is worthless.
- Forgetting the surplus. A ≥ row needs both −sᵢ and +Aᵢ; an = row needs the artificial only.
- Choosing M too small. An artificial can then look cheap enough to stay in the basis, and the method quietly fails.
- Reading alternate optima off a basic variable. Every basic variable has zⱼ − cⱼ = 0; only a non-basic zero counts.
- Calling a no-positive-entry column an arithmetic slip. It is the unboundedness signature: write the ray and find the missing constraint.
- Not recomputing zⱼ − cⱼ for Phase II. That row belongs to W, not Z.
9. Practice problems
- Set up the Big-M tableau for min 3x₁ + 5x₂ subject to x₁ + x₂ ≥ 4 and 2x₁ + x₂ = 6.
- Solve Problem 2 above by Big-M and confirm the same answer.
- A Phase I ends with W* = 3. What do you conclude? [Ans: infeasible, minimum total violation 3]
- Column entries in the pivot column are (0, −2, −5)ᵀ. Diagnose. [Ans: unbounded]
- Why is Big-M numerically dangerous on a computer?
- In a minimisation tableau, state the optimality condition. [Ans: every zⱼ − cⱼ ≤ 0]
- A final tableau has a basic variable equal to 0 and all zⱼ − cⱼ > 0. Is it optimal? [Ans: yes — optimal and degenerate]
10. What you can now do
- Recognise when simplex cannot start, and say why. A ≥ row's surplus enters with −1 and an = row brings nothing at all, so neither row owns a basic variable and the origin is infeasible. You can add an artificial Aᵢ with coefficient +1 to fix that, knowing you have bought the start by changing the problem.
- Run Big-M end to end. You can attach the penalty (−M for a maximisation, +M for a minimisation), build the zⱼ − cⱼ row from c_B and the columns, compare entries like −7M + 4 by their M-coefficients first, choose the entering and leaving variables, and pivot.
- Refuse to stop early. Given a tableau with no artificial left in the basis, you can still check the objective row and keep pivoting — the mistake that turns 3.4 into 3.6 in the worked example.
- Run two-phase and justify preferring it. Phase I minimises W = Σ Aᵢ and settles feasibility before a rupee of cost is considered; if W* > 0 you stop and report infeasibility, and if W* = 0 you drop the artificial columns, recompute the objective row against the real costs, and finish. You can also explain why solvers use it: no giant M to swamp small coefficients in floating point.
- Diagnose any of the four special cases from a tableau alone — infeasible (some Aᵢ > 0, or W* > 0), unbounded (no positive entry in the entering column), alternate optima (a non-basic variable with zⱼ − cⱼ = 0), degenerate (a basic variable at 0) — and say which of them is an error and which is not.
- Turn "infeasible" into a decision. You can read the size of the violation off the tableau (4 units in Problem 1, 35 machine hours in Problem 5), rank the repairs by cost per unit of the scarce resource, and reformulate the hard constraints as penalised goals so the model prices the broken promise instead of refusing to answer: ₹3,500, ₹7,000 or ₹8,750 here, depending on which promise you break.
Next: L07 — duality and sensitivity analysis, where the penalties we invented by hand turn out to be the shadow prices of the constraints.