Canonical form
Canonical Form
Canonical form writes a standard-form LP relative to a chosen basis.
It expresses the basic variables in terms of the nonbasic variables.
This is the algebraic form used inside the simplex method.
Starting Point: Standard Form
Start with:
\[\min c^Tx\]subject to:
\[Ax=b\] \[x\ge 0\]where:
\[A\in\mathbb{R}^{m\times n}\]and $A$ has full row rank.
Basis
Choose $m$ linearly independent columns of $A$.
These columns form a basis matrix:
\[B=[A_{B(1)}\ A_{B(2)}\ \cdots\ A_{B(m)}]\]The variables corresponding to these columns are the basic variables:
\[x_B\]The remaining variables are the nonbasic variables:
\[x_N\]Partitioned System
After reordering variables conceptually, the constraint system can be written as:
\[Bx_B+A_Nx_N=b\]Since $B$ is invertible:
\[x_B=B^{-1}b-B^{-1}A_Nx_N\]This is the canonical form of the constraints relative to $B$.
Basic Solution
A basic solution is obtained by setting:
\[x_N=0\]Then:
\[x_B=B^{-1}b\]So:
\[x=\begin{bmatrix}x_B\\x_N\end{bmatrix} = \begin{bmatrix}B^{-1}b\\0\end{bmatrix}\]If:
\[B^{-1}b\ge 0\]then the basic solution is a basic feasible solution.
Objective in Canonical Form
Partition the cost vector into:
\[c_B\]and:
\[c_N\]The objective is:
\[c^Tx=c_B^Tx_B+c_N^Tx_N\]Substitute:
\[x_B=B^{-1}b-B^{-1}A_Nx_N\]Then:
\[c^Tx=c_B^TB^{-1}b+(c_N^T-c_B^TB^{-1}A_N)x_N\]The vector:
\[c_N^T-c_B^TB^{-1}A_N\]contains the reduced costs of the nonbasic variables.
Full Reduced-Cost Form
For all variables, reduced costs are:
\[\bar{c}^T=c^T-c_B^TB^{-1}A\]Basic variables have zero reduced cost.
This is because:
\[B^{-1}B=I\]Optimality Connection
For a minimization problem in standard form, a basis is optimal if:
\[B^{-1}b\ge 0\]and:
\[\bar{c}\ge 0\]The first condition means feasibility.
The second condition means no nonbasic variable can enter and decrease the objective.
Example Structure
Suppose:
\[A=[B\ A_N]\]and:
\[x=\begin{bmatrix}x_B\\x_N\end{bmatrix}\]Then canonical form is:
\[x_B=B^{-1}b-B^{-1}A_Nx_N\] \[z=c_B^TB^{-1}b+\bar{c}_N^Tx_N\] \[x_B,x_N\ge 0\]Why Canonical Form Matters
Canonical form makes simplex steps visible.
It shows:
- current basic feasible solution
- nonbasic variables currently set to zero
- reduced costs
- which variables can enter the basis
- how increasing a nonbasic variable changes basic variables
Standard Form vs Canonical Form
| Form | Purpose |
|---|---|
| Standard form | common problem format: $\min c^Tx$, $Ax=b$, $x\ge 0$ |
| Canonical form | same problem expressed relative to a basis |
Standard form is basis-independent.
Canonical form depends on the chosen basis.
Checklist
You understand canonical form if you can:
- choose a basis matrix $B$
- split variables into $x_B$ and $x_N$
- derive $x_B=B^{-1}b-B^{-1}A_Nx_N$
- obtain the basic solution by setting $x_N=0$
- identify feasibility using $B^{-1}b\ge 0$
- write reduced costs
- state the minimization optimality test $\bar{c}\ge 0$
See Also
Exam checkpoint
For standard-form questions, use the course convention $\min c^Tx$ subject to $Ax=b$, $x\ge0$. Convert max objectives, add slack to $\le$, subtract surplus from $\ge$, and split free variables.