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

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

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

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

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

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

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

(1.10)

, (1.11) (1.12)

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

(1.13) (1.14) (1.15)

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

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

а) максимизация целевой функции равносильна минимизации целевой функции - ;

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

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