canonical form
Concept
Basis
- similar to the traditional definition in linear algebra
a non-singular matrix is one with independent columns
Basic variables
- basic variables are the ones corresponding to the independent columns
Basic solution
non-basic variables are zero
basic solutions are feasible if all values are non-negative
Uniqueness of basic solution
Canonical form
- choose basic variables that form an identity matrix, so they can be expressed in terms of non-basic variables
Every linear program has a canonical form
- feasible solutions have the same objective value
Converting to canonical form
- make the desired basis submatrix an identity
- remove basis variables from the objective function
Application
Finding a basic solution
Canonical form with different basis
recall that matrix transpose swaps the operands over matrix multiplication
Extra
Column sub-matrix notation
Working to derive the objectvie function rewrite step
Extra
Octave function to convert an LP into canonical form
octave
function [Ac, bc, cc, z0] = canonical_lp(c, A, b, B)
% Canonical form of:
% maximize c' * x
% subject to A*x = b, x >= 0
%
% B: indices of the basic variables.
%
% Output:
% Ac*x = bc
% z = z0 + cc'*x
%
% Ac(:, B) is the identity; cc(B) is zero.
c = c(:);
b = b(:);
B = B(:)';
[m, n] = size(A);
if length(c) != n || length(b) != m
error("Dimensions of c, A, and b do not match.");
endif
if length(B) != m || length(unique(B)) != m ...
|| any(B < 1) || any(B > n) || any(B != fix(B))
error("B must contain m distinct valid column indices.");
endif
AB = A(:, B);
if rank(AB) < m
error("The selected basis matrix is singular.");
endif
Ac = AB \ A;
bc = AB \ b;
cB = c(B);
cc = c - Ac' * cB;
z0 = cB' * bc;
% Remove numerical noise in the basis columns.
Ac(:, B) = eye(m);
cc(B) = 0;
endfunction