Back to the on-screen lesson ·
Artificial variables and phase one; why a strictly rising objective over finitely many bases has to stop.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to set up a phase-one problem with artificial variables and read its answer as feasible or infeasible, give the counting argument that the simplex method terminates, name the three facts that argument depends on, and explain what a zero ratio does to a pivot and to the guarantee.
You can run one iteration: choose a column, run the ratio test, pivot. Two questions are left over — where the run starts when the slacks are not feasible, and what guarantees it ever finishes.
An artificial variable is added to a row purely to make a starting basis available; it has no meaning in the model. Phase one minimises their total to find a feasible corner. A corner is degenerate when a basic variable sits at zero, and cycling is a run that returns to a basis it has already held.
Starting. When every row is a $\le$ with a non-negative limit, the slack columns are a feasible basis and the method begins at the origin for free. A $\ge$ row breaks that: setting the decisions to zero makes its surplus negative. So add an artificial variable to each awkward row, minimise the total of the artificials, and run the ordinary method on that. Reaching zero means a feasible corner has been found; failing to reach zero means the program is infeasible, which is a result rather than a breakdown.
Ending. A basis fixes one objective value; every pivot raises that value strictly; the bases are finitely many. So no basis can recur and the run must stop — at an optimal tableau, or at a column the ratio test cannot bound.
The gap in that argument. At a degenerate corner the ratio test can return zero, the basis changes without the objective moving, and 'strictly' fails. Cycling becomes possible. Bland's rule — always the lowest-indexed eligible column and row — restores the guarantee, and is used only when a run is suspected of cycling, because it is slow.
Another way: steps
Another way: example
$x_1 + x_2 \ge 4$ becomes $x_1 + x_2 - s + a = 4$ with $a \ge 0$. Setting $x = s = 0$ gives $a = 4$: a feasible start for phase one, whose job is to push $a$ down to $0$.
Degeneracy is read as an error in the arithmetic, when it is a fact about where the constraints meet. And a zero ratio is confused with no ratio at all: the first means a pivot that goes nowhere, the second means the program is unbounded. They are opposite verdicts arrived at from the same column.
$x \ge 5$ and $x \le 2$ in standard form: $x - s_1 + a = 5$ and $x + s_2 = 2$, minimising $a$.
One artificial.
$x$ can reach at most $2$, so $a$ can be pushed down only to $3$.
The minimum is not zero.
Phase one ends at $3 > 0$: no feasible point exists, and the two rows that fought are named by the artificial that survived.
Infeasible, with a diagnosis.
A total of zero means every artificial is zero, so the corner is feasible for the real problem even though some artificials are still basic.
Zero total is what matters.
Drop the artificial columns, restore the real objective, and continue from this corner.
A program with $4$ greater-than constraints has no obvious feasible basis. Put the steps of the two-phase method into order.
Number the steps in order (write the number in the box):
Phase one adds $7$ artificial variables and minimises their total. What must that total reach for the original program to be feasible?
Answer:
Select every fact the argument that the simplex method terminates actually relies on.
This task has no paper form; do it on a device.
The entering variable has reduced cost $3$ and the ratio test returns a minimum of $0$. The objective stands at $10$. What happens at this pivot?
The run starts at $18$ and three pivots gain $7$, then $8$, then $5$. Fill in the objective after each one.
| Objective | |
|---|---|
| At the start | 18 |
| After the first pivot | |
| After the second | |
| After the third |
A program has $8$ columns and every pivot raises the objective strictly. Build the proof that the method terminates.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A program with $2$ greater-than constraints has no obvious feasible basis. Put the steps of the two-phase method into order.
Number the steps in order (write the number in the box):
You can set up phase one, read its verdict, and give the argument that the method terminates. Say in your own words why a degenerate pivot breaks that argument.
7. Your turn: phase one ends with the artificial total at $0$ and two artificials still in the basis. What now?, step 2