Каноническая задача линейного программирования

Для построения общего метода решения ЗЛП разные формы ЗЛП должны быть приведены к некоторой стандартной форме, называемой канонической задачей линейного программирования (КЗЛП).

В канонической форме

1. все функциональные ограничения записываются в виде равенств с неотрицательной правой частью;

2. все переменные неотрицательны;

3. целевая функция подлежит максимизации

Таким образом, КЗЛП имеет вид

(3.10)

, (3.11)

(3.12)

или в векторно-матричной форме

(3.13)

(3.14)

(3.15)

КЗЛП является частным случаем общей ЗЛП при m₁=0, p=n

Любую ЗЛП можно привести к каноническому виду, используя следующие правила:

а) максимизация целевой функции = c₁x₁+…+c_nx_n равносильна минимизации целевой функции - =-c₁x₁ -…-c_nx_n;

б) ограничение в виде неравенства, например, 3Х₁+2Х₂-Х₃£6, может быть приведено к стандартной форме 3Х₁+2Х₂-Х₃+Х₄=6, где новая переменная Х₄ неотрицательна. Ограничение Х₁ -Х₂+3Х₃³10 может быть приведено к стандартной форме Х₁ -Х₂+3Х₃-Х₅=10, где новая переменная Х₅ неотрицательна;

в) если некоторая переменная Х_k может принимать любые значения, а требуется, чтобы она была неотрицательная, ее можно привести к виду , где ³0 и ³0.