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.

Add comment

Security code
Refresh