Canonical Form for a Basis

Take a standard-form program $min{c}^{\mathsf{T}}x$ subject to $Ax=b$, $x\ge 0$, and a basis $B$ of $m$ independent columns. Partition the columns into basic and nonbasic, writing $x=(x_B,x_N)$ and $A=(A_B,A_N)$. The constraints become

and since $A_B$ is invertible, solving for the basic variables gives

Substituting that into $c^{\mathsf{T}}x=c_B^{\mathsf{T}}{x}_B+c_N^{\mathsf{T}}{x}_N$ gives

The program written this way, every basic variable and the objective expressed in terms of the nonbasic variables alone, is the canonical form for the basis $B$.

Three quantities are now visible as coefficients rather than as calculations.

The basic solution. Setting $x_N=0$ gives $x_B=A_B^{-1}b$, which is the basic solution for this basis. It is feasible exactly when $A_B^{-1}b\ge 0$.

The objective value there. With $x_N=0$ the objective is $z_0=c_B^{\mathsf{T}}{A}_B^{-1}b$, the constant term.

The reduced costs. The row vector ${\overline{c}}_N^{\mathsf{T}}=c_N^{\mathsf{T}}-c_B^{\mathsf{T}}{A}_B^{-1}{A}_N$ holds the coefficient of each nonbasic variable in the rewritten objective: the net change in $z$ per unit increase of that variable, once the basic variables move to keep $Ax=b$.

The canonical form is relative to a basis. A different basis gives a different constant, different coefficients, and a different reading, of the same program.

For a basis $B$ with $A_B$ invertible: $x_B=A_B^{-1}b-A_B^{-1}{A}_N{x}_N$ and $z=z_0+{\overline{c}}_N^{\mathsf{T}}{x}_N$, where $z_0=c_B^{\mathsf{T}}{A}_B^{-1}b$ and ${\overline{c}}_N^{\mathsf{T}}=c_N^{\mathsf{T}}-c_B^{\mathsf{T}}{A}_B^{-1}{A}_N$. The basic solution is $x_B=A_B^{-1}b$, $x_N=0$; it is feasible when $A_B^{-1}b\ge 0$.