В различных задачах линейного программирования допустимое множество может описываться различными способами: системами неравенств различных знаков, наборами равенств и, наконец, комбинациями равенств и неравенств.
Такое разнообразие описаний является, с точки зрения теории, определенным недостатком, так как вынуждает каждый тип описания рассматривать по-своему. Однако все варианты постановок могут быть сведены к задаче линейного программирования, содержащей лишь равенства и условие неотрицательности переменных:
$\displaystyle{min_{Ax = b, x \geq 0} cx}$
Такая формулировка называется канонической.
Сведения к канонической форме задачи линейного программирования осуществляются, в зависимости от первоначальной формулировки, с помощью несложных приемов, изложенных ниже.
Ограничение типа неравенства $ax \leq b$ сводится к равенству $ax+s=b$ добавлением искусственной (дополнительной) переменной $s \geq 0$.
В задаче линейного программирования иногда присутствуют переменные, которые могут принимать как положительные, так и отрицательные значения. Чтобы свести такую задачу к канонической, каждая такая переменная $x_i$ может быть представлена как разность
$x_i = u_i - v_i$ (*)
неотрицательных переменных $u_i , v_i$. В частности, например, можно положить
$x_i = \max(x_i , 0) - \max(-x_i ,0)$
Следует сразу отметить, что представление (*) не единственно и, соответственно, оптимальное решение становится также не единственным.
