One Iteration of the Simplex Method

A simplex iteration moves from one basic feasible solution to an adjacent one. A nonbasic variable with negative reduced cost enters the basis; the minimum ratio test decides how far it can increase before a basic variable reaches zero, and that variable leaves. The test is what keeps the new point feasible.

Definition

Given a basis $B$ with basic feasible solution $x$ , an iteration selects an entering variable $x_{j}$ with ${\bar{c}}_{j} < 0$ , computes the direction $u = A_{B}^{- 1} A_{j}$ , and finds the step $θ = min {x_{B (i)} / u_{i} : u_{i} > 0}$ . The basic variable attaining that minimum leaves the basis, $x_{j}$ enters at value $θ$ , and the remaining basic variables move to $x_{B (i)} - θ u_{i}$ .

Formal statement

With $u = A_{B}^{- 1} A_{j}$ , the new point is $x_{j} = θ$ and $x_{B (i)} \leftarrow x_{B (i)} - θ u_{i}$ , where $θ = min_{i : u_{i} > 0} x_{B (i)} / u_{i}$ . The objective changes by $θ {\bar{c}}_{j} \leq 0$ . If $u \leq 0$ no ratio exists and the program is unbounded.

Assumptions and scope

Only components with $u_{i} > 0$ enter the ratio test. A basic variable whose component is zero or negative does not fall as the entering variable increases, so it never limits the step.
If every component of $u$ is nonpositive, the entering variable can increase without limit while feasibility holds, and the program is unbounded. No leaving variable exists.
A tie in the minimum ratio means more than one basic variable reaches zero together. Either may leave, and the resulting basic feasible solution is degenerate.
When the minimum ratio is zero the step is zero: the basis changes but the point does not. This is stalling, and repeated stalling can cycle without an anti-cycling rule.

Worked material

Contrast

Which rows enter the ratio test

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 $u_{i} > 0$ 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

u = (\begin{matrix} 4 \\ - 2 \end{matrix}) .

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 $θ^{*} = 8 / 4 = 2$ and the first basic variable leaves.

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

x_{B (2)} - θ u_{2} = 3 - θ (- 2) = 3 + 2 θ .

It rises. It moves away from zero, never toward it, so no value of $θ$ 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 $θ^{*} = - 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 $u_{i} > 0$ is exactly the condition for falling.

Common errors

Common misconception

The minimum ratio test compares the ratio in every row, so a row whose direction component is zero or negative competes for the minimum like any other.

One Iteration of the Simplex Method

Assumptions and scope

Worked material

Which rows enter the ratio test

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history