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

Любую задачу линейного программирования можно привести к канонической форме по следующему правилу:

1) если знак неравенства , то балансовая переменная вводится со знаком плюс;

2) если знак неравенства , то балансовая переменная вводится со знаком минус;

3) в целевую функцию балансовые переменные не вводятся;

4) если на какую либо исходную переменную не наложено условие неотрицательности (например, на ), то ее можно представить в виде разности двух положительных переменных () и выполнить соответствующую замену в исходной задаче.

Пример 3. Привести к каноническому виду задачу линейного программирования

, , .

Решение. Первое уравнение системы ограничений оставим без изменения. Во второе неравенство системы ограничений введем балансовую переменную со знаком плюс , а во второе неравенство переменную со знаком минус . В целевую функцию эти переменные не вводятся. Так как на переменную не наложено условие неотрицательности, то заменим ее разностью двух положительных переменных . Выполним соответствующую замену в целевой функции.

Каноническая форма исходной задачи будет иметь вид:

, , .