Canonical Form for a Basis

A basic solution sits at a corner with the nonbasic variables held at zero. Raising one of them moves off that corner, and the objective changes by an amount the original program does not state anywhere.

It does not state it because raising $x_j$ forces the basic variables to move in compensation, and their costs are part of the answer. Working that out for one variable is a short calculation. Working it out for every nonbasic variable, at every corner the method visits, is the calculation the canonical form does once and then reads off.

After the rewrite the program carries its own answers: the basic solution and the objective value appear as constants, and each nonbasic variable carries the net rate at which it changes the objective. Deciding optimality becomes a matter of reading signs.

This unit assumes standard form, what a basis is, and the column reading of $A$.

At a basic solution the nonbasic variables sit at zero. The only moves available are to raise one of them, and the question that decides the next step is what each such move does to the objective.

The original program does not answer that. Raising $x_j$ by one unit breaks $Ax=b$ unless the basic variables move to compensate, and the cost of that compensation is part of the answer. So the full accounting has three parts: what the new variable costs directly, how far the basic variables must move, and what their movement costs.

The substitution does that accounting once, for every nonbasic variable simultaneously. What survives is one number per variable:

After the rewrite the program states its own situation. The constant is where the objective stands. Each coefficient is the rate at which one available move changes it. Nothing further needs computing to decide what to do next.

Why the constant plays no part in the decision. Every nonbasic variable is at zero and can only increase, so a negative coefficient is an available improvement and a nonnegative one is not. That comparison is between the coefficient and zero. The constant shifts $z$ up or down equally whatever move is chosen, so it cannot distinguish between them. A basis with an excellent objective value and a negative coefficient is not optimal; a basis with a poor value and no negative coefficient is.

Why it must be redone each iteration. The compensation term depends on $A_B^{-1}$, so it is a fact about the current basis rather than about the program. Change the basis and every coefficient changes. That recomputation is not overhead attached to the method; it is the method.

Four objects come out of the rewrite, and the later material refers to each by name.

On $y$. Writing the compensation term as $y^{\mathsf{T}}{A}_j$ rather than $c_B^{\mathsf{T}}{A}_B^{-1}{A}_j$ is the same quantity grouped differently, and it is worth the change: $y$ is computed once per basis, after which each reduced cost costs one dot product. The revised simplex method is built on exactly that regrouping.

Feasibility is separate. The derivation needs $A_B$ invertible and nothing more. A basis whose $A_B^{-1}b$ has a negative entry still has a canonical form; what it does not have is a basic feasible solution. Deriving the form and checking $A_B^{-1}b\ge 0$ are two steps, and only the second decides feasibility.

Optimality is a statement about signs. For a minimisation in standard form, the basis is optimal when every ${\overline{c}}_j\ge 0$. For a maximisation converted by negating $c$, the test applies to the converted program; applying a minimisation test to an unconverted maximisation reverses the verdict.

The form is not unique to a point. At a degenerate basic feasible solution several bases describe the same point, each with its own canonical form and its own reduced costs. Two of them can disagree about whether an improving direction exists, which is why degeneracy is treated as its own topic rather than as an edge case of this one.

Start from the standard-form program and a basis $B$ of $m$ independent columns.

Split the constraints. Every column belongs to the basis or not, so $Ax=b$ separates into

Nothing has changed yet; the terms have only been grouped.

Solve for the basic variables. $A_B$ has $m$ independent columns and is square, so it is invertible:

This is the step that makes the form useful. The basic variables are no longer unknowns to be solved for later; they are stated as a function of the nonbasic ones, so a choice of $x_N$ determines the whole point.

Substitute into the objective. With $c^{\mathsf{T}}x=c_B^{\mathsf{T}}{x}_B+c_N^{\mathsf{T}}{x}_N$, replacing $x_B$ gives

Name the parts. The first term is a constant, $z_0=c_B^{\mathsf{T}}{A}_B^{-1}b$. The bracket is a row vector with one entry per nonbasic variable,

and entry $j$ is the reduced cost of $x_j$.

Read what the algebra says. Each term $c_j-c_B^{\mathsf{T}}{A}_B^{-1}{A}_j$ has two parts. The first is what a unit of $x_j$ costs directly. The second is what it costs indirectly: $A_B^{-1}{A}_j$ is how much each basic variable must move to absorb one unit of $x_j$ while keeping $Ax=b$, and $c_B^{\mathsf{T}}$ prices that movement. The reduced cost is the direct cost net of the compensation, which is why raising a variable with lowers the objective.

Why a basic variable has reduced cost zero. Apply the same expression to a basic column: $A_B^{-1}{A}_j$ is then a unit vector, and $c_B^{\mathsf{T}}$ times it returns $c_j$ exactly, leaving $c_j-c_j=0$. A variable already in the basis has no unexploited effect on the objective, so the optimality test concerns the nonbasic variables only.

The program.

So $c=(-3,-2,0,0{)}^{\mathsf{T}}$ and

---

Basis $B=\{3,4\}$.

$A_B=I$, so $A_B^{-1}=I$ and the partition is immediate:

With $c_B=(0,0{)}^{\mathsf{T}}$ the constant is $z_0=0$ and the reduced costs are the cost coefficients themselves:

The canonical form is

Reading it. The basic solution is $x=(0,0,12,12{)}^{\mathsf{T}}$, feasible because $A_B^{-1}b=(12,12{)}^{\mathsf{T}}\ge 0$, with objective $0$. Both nonbasic coefficients are negative, so this basis is not optimal and either variable improves. Taking the most negative, $x_1$ enters.

The step. The direction is $u=A_B^{-1}{A}_1=(2,1{)}^{\mathsf{T}}$, and the ratio test over positive components gives $12/2=6$ and $12/1=12$. The minimum is $6$, so $\theta =6$ and $x_3$ leaves.

---

Basis $B=\{1,4\}$.

Now

which checks: $A_B{A}_B^{-1}=I$.

so the basic solution is $x=(6,0,0,6{)}^{\mathsf{T}}$, again feasible. With $c_B=(-3,0{)}^{\mathsf{T}}$,

and $y^{\mathsf{T}}=c_B^{\mathsf{T}}{A}_B^{-1}=(-1.5,0)$. The nonbasic columns are $A_3=(1,0{)}^{\mathsf{T}}$ and $A_2=(1,2{)}^{\mathsf{T}}$, giving

The canonical form is

Reading it. The objective has fallen from $0$ to $-18$, as the step promised. Re-entering $x_3$ would raise the objective by $1.5$ per unit, which is why the method does not undo its own move. But , so this basis is not optimal either and $x_2$ enters next.

What changed between the two forms. The program did not. The constant, the coefficients and the verdict all did, because all three are properties of the basis rather than of the program. The same point can be described by more than one canonical form, and every iteration of the simplex method installs the next one.

The worked example carried out every step. Here the support is removed a piece at a time. Work on

First, with the steps named. Take $B=\{3,4\}$.

1. Write $A_B$ and $A_N$, with the nonbasic columns in the order $(x_1,x_2)$.
2. $A_B$ is the identity here, so $A_B^{-1}b$ is immediate. What is the basic solution, and is it feasible?
3. $c_B=(0,0{)}^{\mathsf{T}}$, so what is $z_0$, and what does that make ${\overline{c}}_N^{\mathsf{T}}$?
4. Write $z$ in the form $z_0+{\overline{c}}_N^{\mathsf{T}}{x}_N$. Is this basis optimal? If not, which variable would you bring in, and why that one?

Then, with the steps only implied. Take $B=\{2,4\}$ in the same program.

Derive the canonical form. You will need $A_B^{-1}$ for a matrix that is not the identity; multiply it back against $A_B$ before using it. Report the basic solution, whether it is feasible, the objective value, and the reduced costs. State the optimality verdict and name the quantity that decides it.

Last, with nothing named. Still the same program, $B=\{1,2\}$.

Put the program in canonical form for this basis and say what the result tells you about the point it describes.

---

Checks you can run without the answers. $A_B{A}_B^{-1}$ must be the identity. Every basic variable must have reduced cost zero, compute one and confirm it. The constant $z_0$ must equal $c^{\mathsf{T}}x$ evaluated at the basic solution you reported; if the two disagree, the substitution went wrong rather than the arithmetic.

The rewrite produces three readings, and they answer different questions. Treating one as an answer to another is the recurring error.

Feasibility and optimality are independent. A basis can be infeasible and have every reduced cost nonnegative; it can be feasible with a strongly negative one. The first is not an optimum of anything, because the point is not in the feasible set. The second is a perfectly good corner with a better neighbour.

A low objective value is not optimality. In the worked example the second basis reaches $z_0=-18$ and is still not optimal: ${\overline{c}}_2=-0.5$ says another move lowers the objective further. A learner comparing constants across bases is answering "which of these corners is better" when the method is asking "is there anything better than this corner".

The reduced costs say which way, not how far. makes $x_j$ worth raising, and says nothing about the limit. That limit comes from $A_B^{-1}b$ and $A_B^{-1}{A}_j$ through the ratio test, which is a different reading of the same form. An answer that names the entering variable and stops has done half the step.

What all three share. Each is computed from $A_B^{-1}$ and is therefore a fact about the basis. None of them is a property of the program, and none survives a basis change unexamined.