## 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 asMaximise

\[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.