One Iteration of the Simplex Method

One iteration: choose a variable to bring in, find how far it can rise before something breaks, and see which variable hit zero first. Everything else in the simplex method is repetition.

The previous unit supplied the stopping rule. This one supplies the step. Together they are the whole method: test for optimality, and if the test fails, move to an adjacent corner and test again.

The step that carries the real content is the minimum ratio test, which answers a question the reduced cost cannot: not whether to move, but how far you may move before leaving the feasible region.

This unit assumes you can compute reduced costs and identify a basis and its basic feasible solution.

A nonbasic variable sits at zero. Start raising it.

The constraints still have to hold, so the basic variables move in compensation. Some of them rise, some of them fall, and how fast each one moves is fixed by the arithmetic of the basis.

You are now walking along an edge of the feasible region, and the reduced cost told you this walk improves the objective. The only question left is when to stop.

The answer is: when the first falling basic variable reaches zero. One step further and it would go negative, which the nonnegativity restrictions forbid. So the walk ends exactly there, at the next corner.

Two things follow immediately.

A basic variable that is rising, or holding steady, never ends the walk. It is drifting away from zero, not toward it, so it places no limit at all. Only the falling ones matter, which is why the ratio test excludes rows with $u_i\le 0$.

And if nothing is falling, the walk never ends. The entering variable increases forever while every constraint stays satisfied, and the objective improves forever with it. That is what an unbounded program looks like from the inside.

Let $B=(B(1),\dots ,B(m))$ be a basis with basic feasible solution $x$, so $x_{B(i)}$ are the basic values and every other component is zero.

Entering variable. Choose a nonbasic $j$ with . Each unit of $x_j$ changes the objective by ${\overline{c}}_j$, so raising it improves a minimization.

Direction. Raising $x_j$ to $\theta$ forces the basic variables to move. Writing

the basic values become $x_{B(i)}-\theta u_i$. The component $u_i$ is the rate at which the $i$-th basic variable falls per unit of $x_j$.

Minimum ratio test. Feasibility requires $x_{B(i)}-\theta u_i\ge 0$ for every $i$. When $u_i\le 0$ that holds for every $\theta \ge 0$, so those rows impose nothing. When it requires $\theta \le x_{B(i)}/u_i$. Therefore

Leaving variable. A row attaining the minimum has its basic variable driven exactly to zero; that variable leaves the basis and $x_j$ takes its place.

The new point. $x_j={\theta }^{\ast }$, each remaining basic variable becomes $x_{B(i)}-{\theta }^{\ast }{u}_i$, and the objective falls by ${\theta }^{\ast }|{\overline{c}}_j|$.

Unboundedness. If $u_i\le 0$ for every $i$, the minimum is over an empty set. No variable ever reaches zero, $x_j$ increases without limit, and the program is unbounded.

Given a standard-form minimization program, a basis $B$, and its basic feasible solution:

Compute the reduced costs of the nonbasic variables. Form $y^{\mathsf{T}}=c_B^{\mathsf{T}}{A}_B^{-1}$, then ${\overline{c}}_j=c_j-y^{\mathsf{T}}{A}_j$ for each nonbasic $j$.

Test for optimality. If every ${\overline{c}}_j\ge 0$, stop: the current solution is optimal and no iteration is needed.

Choose an entering variable. Pick any $j$ with . Taking the most negative is the common rule; any negative one is valid, and the choice affects how many iterations follow, not their correctness.

Compute the direction. $u=A_B^{-1}{A}_j$. In practice solve $A_{B}u=A_j$ rather than inverting.

Check for unboundedness. If no component of $u$ is strictly positive, stop: the program is unbounded and there is no leaving variable.

Run the minimum ratio test on the positive rows only. For each $i$ with , form $x_{B(i)}/u_i$. Ignore rows with $u_i\le 0$ entirely: they do not constrain the step and their ratios are meaningless.

Identify the leaving variable and the step. ${\theta }^{\ast }$ is the smallest of those ratios; a row attaining it supplies the leaving variable. On a tie, either choice is valid and the new solution is degenerate.

Update. Replace the leaving index with $j$ in the basis. Set $x_j={\theta }^{\ast }$, set the leaving variable to zero, and replace each remaining basic value with $x_{B(i)}-{\theta }^{\ast }{u}_i$.

Check. The new point should satisfy $Ax=b$ with every component nonnegative, and the objective should have fallen by ${\theta }^{\ast }|{\overline{c}}_j|$.

Problem. In standard form:

Start from the slack basis $B=\{3,4\}$.

Goal. Iterate to optimality, reporting each entering and leaving variable.

---

Iteration 1.

$A_B=I$, so $x_3=12$, $x_4=12$, and $x_1=x_2=0$. The objective is $0$.

With $c_B=(0,0{)}^{\mathsf{T}}$ we get $y^{\mathsf{T}}=(0,0)$, so the reduced costs are just the cost coefficients:

Entering: $x_1$, the most negative.

Direction: $u=A_B^{-1}{A}_1=A_1=(2,1{)}^{\mathsf{T}}$.

Ratio test: both components are positive, so both rows count.

Leaving: ${\theta }^{\ast }=6$, attained in the first row, so $x_3$ leaves.

New point: $x_1=6$, $x_4=12-6(1)=6$, $x_2=x_3=0$. Objective $-18$, a fall of $6\times 3$ as predicted.

---

Iteration 2.

Basis $\{1,4\}$ with $x_1=6$, $x_4=6$.

Now $y^{\mathsf{T}}=(-3/2,0)$, giving

Entering: $x_2$, the only negative one.

Direction: $u=(1/2,3/2{)}^{\mathsf{T}}$.

Ratio test:

Leaving: ${\theta }^{\ast }=4$ in the second row, so $x_4$ leaves.

New point: $x_2=4$, $x_1=6-4(1/2)=4$, $x_3=x_4=0$. Objective $-20$, a fall of $4\times \frac{1}{2}=2$.

---

Iteration 3: the test.

Basis $\{1,2\}$ with $x_1=4$, $x_2=4$. Here $y^{\mathsf{T}}=(-4/3,-1/3)$ and

Both are positive, so no variable improves the objective and the method stops.

Check. $2(4)+4=12$ and $4+2(4)=12$: both constraints hold with equality, and all components are nonnegative.

Interpretation. The optimum is $x_1=x_2=4$ with objective $-20$, that is a maximum of $20$ for the original $3x_1+2x_2$. This is the same point and value the graphical unit reached by sliding a contour across the region. The two routes agree: the algebra reproduces what the picture showed, on problems too large to draw.

The ratio test looks like "divide and take the smallest", and applying it to every row is the most common way an iteration goes wrong. The restriction to is not a convention; it is what the test means.

Take a basis with $x_{B(1)}=8$, $x_{B(2)}=3$, and an entering direction

Incorrect. Compute both ratios: $8/4=2$ and $3/(-2)=-1.5$. Take the smaller, $-1.5$, and let the second basic variable leave.

Correct. Only the first row qualifies, because $u_2=-2$ is negative. So ${\theta }^{\ast }=8/4=2$ and the first basic variable leaves.

Why the second row cannot limit anything. As the entering variable rises to $\theta$, the second basic variable becomes

It rises. It moves away from zero, never toward it, so no value of $\theta$ ever makes it negative. A row like this places no restriction on the step, and its ratio is not a step length at all. It is a negative number with no interpretation.

Taking it as the minimum would set ${\theta }^{\ast }=-1.5$, moving backwards along the edge to a point that fails feasibility, and reporting a leaving variable that was never in danger.

A row with $u_i=0$ is excluded for the same reason. That basic variable does not move at all, so it cannot reach zero, and its ratio would require dividing by zero.

The reliable phrasing. The ratio test asks which basic variable hits zero first. Only variables that are falling can hit zero, and is exactly the condition for falling.