## The Canonical Form of a Linear Programming Problem

The standard linear programming problem is in the form of a set of linear inequalities - constraints - and an objective function, also linear which is to be maximised. We write this system to a 'canonical form' by introducing 'slack variables', and writing all the inequalities as equations. The slack variables are used because a solution which maximises the objective function may be maximised for at least one of the inequalities being a strict inequality. Introducing slack variables allows a matrix method of solution.
Example: Convert the linear programming problem below to canonical form.
Maximise
$8x_1+15x_2+6x_3+20x_4$
subject to
$x_1+3x_2+x_3+2x_4 \leq 9$

$2x_1+2x_2+2x_3+3x_4 \leq 12$

$3x_1++2x_2+2x_3+5x_4 \leq 16$

$x_1, \: x_2, \:, \: x_3, \: x_4 \geq 0$
.
Introduce slack variables
$x_5, \: x_6, \: x_7$
and rewrite the system as
Maximise
$8x_1+15x_2+6x_3+20x_4$
subject to
$x_1+3x_2+x_3+2x_4 +x_5 = 9$

$2x_1+2x_2+2x_3+3x_4 +x_6= 12$

$3x_1++2x_2+2x_3+5x_4 +x_7= 16$

$x_1, \: x_2, \:, \: x_3, \: x_4, \: x_5, \: x_6, \: x_7 \geq 0$
.
The slack variables must all be greater than or equal to zero because there must be positive slack.