A ≥ row's surplus column is -1, and an = row has no extra column at all, so neither offers the identity column a starting basis needs. An artificial variable is added to supply one, and minimising the sum of the artificials is itself a linear programme. Its optimum is either zero, which hands over a genuine basic feasible solution, or positive, which proves the original programme has no feasible point and carries the proof as a number.
Core ideas
One hard idea: a phase of the method whose objective is not the programme’s objective, and whose answer is a yes-or-no about feasibility.
Turning x₁ + x₂ ≥ 4 into an equation gives x₁ + x₂ - e₁ = 4, and the column of e₁ is -1. Starting from that basis would read e₁ = -4, which is not feasible. An = row is worse: it contributes no new column at all. Either way there is nothing to start from, which is a different problem from the programme being hard.
A slack measures something real — the unused part of a resource — and may well be positive at the optimum. An artificial is put into a row purely to occupy an identity column, it corresponds to nothing in the situation, and any positive value it still has at the end of the first phase means the equations were satisfied only by cheating.
Minimise the sum of the artificials from the all-artificial basis. Reach zero and every artificial is out or at zero, so what is left is a genuine basic feasible solution of the original constraints and the second phase starts from it with the real objective. Stop above zero and the minimum amount of cheating required is positive, which is a proof that no feasible point exists.
The material
Where the artificial columns go, what the first phase minimises, the handover, and the certificate a positive optimum hands you.
Everything so far started at the origin because every row was a ≤ row with a slack, and the slacks formed an identity. Standard Form, Slack and Surplus wrote the other two kinds of row, and neither helps: a ≥ row's surplus enters with coefficient -1, and an = row adds no column. So the tableau has no starting basis, and one has to be built.
An artificial variable is a non-negative variable added to one row with coefficient +1, for the sole purpose of giving that row an identity column. It has no meaning in the situation being modelled, and a solution of the original programme is exactly a solution in which every artificial is zero.
Take minimise 2x₁ + 3x₂ subject to x₁ + x₂ ≥ 4 (demand), 2x₁ + x₂ ≥ 5 (a quality floor) and x₁ ≤ 3 (capacity). The two ≥ rows get a surplus and an artificial each; the ≤ row gets an ordinary slack. The columns, in order, are x₁, x₂, e₁, A₁, e₂, A₂, s₃.
That starting reading is feasible for the enlarged system and meaningless for the original one: it satisfies the demand row by putting 4 units of nothing into it. The first phase’s job is to drive that quantity to zero if it can.
Phase I is the linear programme minimise the sum of the artificial variables, over the same constraints, started from the basis of identity columns. Its optimum is non-negative. If it is zero, drop the artificial columns and run Phase II: the original objective, started from the basis Phase I finished on. If it is positive, the original programme is infeasible.
On the programme above, Phase I takes two pivots — x₁ in and A₂ out, then x₂ in and A₁ out — and its optimum is 0 with neither artificial left in the basis. The basis it hands over is a genuine corner of the original region.
Phase II then needs one pivot and finishes at x = (3, 1) with 2(3) + 3(1) = 9. Three pivots in total, and the only unusual thing about them is that the first two were optimising a different objective.
Take the empty region that “Systems of Inequalities and Linear Programming” drew as a blank picture: x₁ + x₂ ≤ 1 together with x₁ + x₂ ≥ 4. Phase I stops at 3. That is not a failure to converge and not a numerical artefact; it is the smallest total amount of artificial quantity that makes the two rows simultaneously satisfiable, and it is positive.
If the minimum of the sum of the artificials is v > 0, the original constraints have no non-negative solution. The value v is exact, and the multipliers the final tableau carries turn it into a contradiction that can be checked row by row: a combination y of the rows with yᵀA ≤ 0 and yᵀb > 0.
On the empty region the multipliers are y = (-1, 1). Combining the rows that way gives 0 ≥ 3: the coefficient of every variable cancels and the right-hand sides do not. That is a complete argument, it fits on one line, and it is what a blank picture was standing in for. “Duality and Sensitivity Analysis” is where those multipliers get their name.
Phase I can finish at zero with an artificial still in the basis, at value zero. On x₁ + x₂ = 4 together with 2x₁ + 2x₂ = 8 — the same row doubled — and x₂ ≤ 3, the first phase reaches 0 in one pivot and leaves the second artificial basic at zero, because no real column can replace it: that row is redundant. This is a degenerate basic feasible solution, not a failure. Phase II runs from it and reaches 7, and the artificial is held at zero or driven out on the way.
The one-phase alternative is worth naming and not running. Big-M keeps the artificials in the real objective with a large penalty coefficient M, so that a positive artificial is never optimal unless it has to be. It reaches the same answers and it needs M to be chosen large enough relative to data you have not solved yet, which is the kind of decision this path avoids. Two phases need no such constant.
Interactive
Minimise the sum of the artificials: zero hands a basis to the real problem, positive is a certificate
Method
The bookkeeping is where this goes wrong, not the pivoting. Write the enlarged system out in full before starting.
A slack for a ≤ row, a surplus for a ≥ row, and an artificial wherever the row has no identity column of its own. Label them: a surplus and an artificial in the same row are two different variables doing two different jobs.
The first basis is whichever columns are +1 in one row and zero elsewhere — some slacks, and every artificial. The first phase objective is the sum of the artificials and nothing else; the real objective is not in the tableau yet.
Zero means feasible: drop the artificial columns and go on. Positive means infeasible, and the value is the answer rather than a symptom — report it, and read off the multipliers if you want the contradiction in one line.
Phase II starts from the basis Phase I finished on, with the original objective written into a fresh objective row. Recompute that row from the current basis; the first phase’s objective row is about a different objective and carrying it over is the commonest slip here.
An artificial at zero is degeneracy and is fine. One above zero after Phase I means the programme is infeasible; one above zero after Phase II means the handover was done wrong, because the second phase has no reason to raise it.
A minimisation with two ≥ rows, so two artificials. The first phase is a different programme on the same constraints, and its optimum is the only thing that decides whether the second phase happens at all.
The number 3 is the interesting one. It is not a residual and not a tolerance: it is the exact minimum amount of artificial quantity the two rows require, and it is positive, so no assignment of x₁ and x₂ satisfies both. The multipliers turn the same fact into an argument a reader can check in two lines without running anything.
Note also what the first phase did not do on the feasible programme: it did not look at 2x₁ + 3x₂ once. The two pivots that reached feasibility were chosen to remove artificials, and the point they arrived at, (0, 5) moving to (1, 3), has no claim to be good. Feasibility first, optimality second, and the objective is not consulted until the handover.
For a faded rehearsal, run the redundant preset in the lab: x₁ + x₂ = 4 with 2x₁ + 2x₂ = 8 and x₂ ≤ 3, maximising x₁ + 2x₂. The supplied first move is that the second row is the first one doubled, so one of the two artificials can never be replaced by a real column. Predict the first-phase optimum, predict which artificial is left basic and at what value, say whether that is a failure, and then check the optimum of 7 in the panel.
You should be able to enlarge a mixed-constraint programme with the right surpluses and artificials, name the starting basis, run the first phase, decide feasibility from its optimum, hand over a basis with a freshly computed objective row, and recognise an artificial left basic at zero for what it is.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.