Canonical Form Model
In linear programming, a model expressed in canonical form with respect to a basis is given by: $$ \begin{cases} \min \: z(x) \: = \: c_B^T A_B^{-1}b + \bar{c}_N^T x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$
The Proof
To rewrite an optimization problem in canonical form, we begin with the standard form:
$$ \begin{cases} \min \: z(x) \: = \: c^T x \\ Ax = b \\ x \ge 0 \end{cases} $$
When looking for basic feasible solutions (BFS), the variables are split into basic (B) and non-basic (N) sets:
$$ \begin{cases} \min \: z(x) \: = \: c_B^T x_B + \bar{c}_N^T x_N \\ A_B x_B + A_N x_N = b \\ x_B,x_N \ge 0 \end{cases} $$
Let’s now solve for the basic component \(x_B\):
$$ A_B x_B + A_N x_N = b $$
$$ A_B x_B = b - A_N x_N $$
$$ x_B = \frac{b}{A_B} - \frac{A_N x_N}{A_B} $$
$$ x_B = A_B^{-1}b - A_B^{-1} A_N x_N $$
So the model can be rewritten as:
$$ \begin{cases} \min \: z(x) \: = \: c_B^T x_B + \bar{c}_N^T x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$
In a basic solution, the non-basic variables \(X_N\) are zero:
$$ x_B = A_B^{-1}b $$
Substituting this into the objective function while ignoring \(X_N\):
$$ \begin{cases} \min \: z(x) \: = \: c_B^T A_B^{-1}b + \bar{c}_N^T x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$
This is the optimization model in canonical form.
The first term in the objective function is a constant numerical value.
The second term represents the reduced costs of the non-basic variables, computed as:
$$ \bar{c}_N^T = c^T - c_B^T A_B^{-1} A $$
Thus, the canonical form can also be written as:
$$ \begin{cases} \min \: z(x) \: = \: c_B^T A_B^{-1}b + [ c^T - c_B^T A_B^{-1} A ] x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$
A Worked Example
Consider the following optimization problem:
$$ \begin{cases} \min z(x) = 4x_1 - x_2 \\ \\ x_1-x_2 \le 5 \\ 3x_1+x_2 \le 2 \\ \\ x_1 \ge 0 \\ x_2 \le 0 \end{cases} $$
Rewriting it in standard form gives:
$$ \begin{cases} \min z(x) = 4x_1 - x_2\\ \\ x_1-x_2 +x_3 = 5 \\ 3x_1+x_2 + x_4 = 2 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
The coefficient matrix is:
$$ A = \begin{pmatrix} 1 & -1 & 1 & 0 \\ 3 & 1 & 0 & 1 \end{pmatrix} $$
Note. The rank of the system is r(A)=r(A|B)=2, which satisfies the Rouché-Capelli theorem ensuring that solutions exist. Moreover, the number of equations (m=2) does not exceed the number of variables (n=4), so the conditions for identifying basic feasible solutions are met.
To express the system in canonical form, we need a basic feasible solution.
This requires selecting two linearly independent columns of matrix \(A\), i.e., columns with a non-zero determinant.
For example, taking columns [1,2] we obtain:
$$ A_B = \begin{pmatrix} 1 & -1 \\ 3 & 1 \end{pmatrix} $$
The non-basic variables \((x_3, x_4)\) correspond to the submatrix:
$$ A_N = \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} $$
The basic solution is:
$$ x_B = A_B^{-1} b $$
$$ x_B = \begin{pmatrix} 1 & -1 \\ 3 & 1 \end{pmatrix} ^{-1} \begin{pmatrix} 5 \\ 2 \end{pmatrix} $$
Computing the inverse matrix gives:
$$ x _B = \begin{pmatrix} 0.25 & 0.25 \\ -0.75 & 0.25 \end{pmatrix} \begin{pmatrix} 5 \\ 2 \end{pmatrix} $$
$$ x_B = \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} $$
This basis is feasible since \(x_1 \ge 0\) and \(x_2 \le 0\).
We can now rewrite the model in canonical form with respect to basis [1,3]:
$$ \begin{cases} \min c_B^T A_B^{-1}b + c_N^T x_N \\ x_B = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_B,x_N \ge 0 \end{cases} $$
$$ \begin{cases} \min c_B^T A_B^{-1}b + c_N^T x_N \\ \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
The basic cost vector \(c_B\) for \(x_1\) and \(x_2\) is (4 , -1):
$$ \begin{cases} \min (4 , -1 ) \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} + c_N^T x_N \\ \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = A_B^{-1}b - A_B^{-1} A_N x_N \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\ \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = A_B^{-1}b - A_B^{-1} A_N x_N \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
Next, we compute the remaining expressions:
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} - A_B^{-1} A_N x_N \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} - \begin{pmatrix} 0.25 & 0.25 \\ -0.75 & 0.25 \end{pmatrix} \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} x_3 \\ x_4 \end{pmatrix} \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} - \begin{pmatrix} -0.25 & 0.25 \\ 0.75 & 0.25 \end{pmatrix} \begin{pmatrix} x_3 \\ x_4 \end{pmatrix} \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1.75 \\ -3.25 \end{pmatrix} - \begin{pmatrix} -0.25x_3 & 0.25x_4 \\ 0.75x_3 & 0.25x_4 \end{pmatrix} \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
Which expands to:
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\ x_1 = 1.75 + 0.25 x_3 - 0.25x_4 \\ x_2 = -3.25 -0.75x_3 -0.25x_4 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
Equivalently,
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\ x_1 - 0.25 x_3 + 0.25x_4 = 1.75 \\ x_2 +0.75x_3 +0.25x_4 = -3.25 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
We now compute the reduced costs \(c_N\) for the non-basic variables \(x_3\) and \(x_4\):
$$ c^T - c_B^T A_B^{-1} A $$
$$ (4, -1, 0, 0) - (4, -1) \begin{pmatrix} 0.25 & 0.25 \\ -0.75 & 0.25 \end{pmatrix} \begin{pmatrix} 1 & -1 & 1 & 0 \\ 3 & 1 & 0 & 1 \end{pmatrix} $$
$$ (4, -1, 0, 0) - (4, -1) \begin{pmatrix} 1 & 0 & 0.25 & 0.25 \\ 0 & -1 & -0.75 & 0.25 \end{pmatrix} $$
$$ (4, -1, 0, 0) - (4, -1, 1.75, 0.75) $$
$$ (0, 0, -1.75, -0.75) $$
Thus, excluding the basic variables \((x_1, x_2)\), the reduced costs of the non-basic variables are:
$$ c_N = (-1.75, -0.75) $$
We can now write the final form of the system:
$$ \begin{cases} \min 10.25 + c_N^T x_N \\ \\ x_1 - 0.25 x_3 + 0.25x_4 = 1.75 \\ x_2 +0.75x_3 +0.25x_4 = -3.25 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 + (-1.75 , -0.75) \begin{pmatrix} x_3 \\ x_4 \end{pmatrix} \\ \\ x_1 - 0.25 x_3 + 0.25x_4 = 1.75 \\ x_2 +0.75x_3 +0.25x_4 = -3.25 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
$$ \begin{cases} \min 10.25 -1.75x_3 , -0.75 x_4 \\ \\ x_1 - 0.25 x_3 + 0.25x_4 = 1.75 \\ x_2 +0.75x_3 +0.25x_4 = -3.25 \\ \\ x_1, x_3, x_4 \ge 0 \\ x_2 \le 0 \end{cases} $$
We have therefore expressed the system in canonical form with respect to basis [1,2].
Note. The solution is feasible since \(x_1 \ge 0\) and \(x_2 \le 0\), but not optimal: at least one reduced cost for a non-basic variable is negative (-1.75 and -0.75).
And the process continues in the same way.
