Каноническая форма задач ЛП

Задача ЛП представлена в канонической форме, если в ее модели все функциональные условия имеют вид равенств и все переменные ограничены по знаку. Направление цели не имеет существенного значения, для однозначности канонического представления будем иметь в виду максимизацию критерия. Модель задачи:

Векторно-матричные представления: L = max

или

С– вектор коэффициентов целевой функции; A_j - векторы условий, j = В– вектор ограничений (свободных членов); А– матрица условий; Х– вектор переменных; – число переменных в канон. форме, >= числа переменных в исходной модели

Любую задачу ЛП можно привести к каноническому виду. Возможны 3 случая несоответствия исходной модели каноническому представлению.

1.Если в исходной постановке критерий минимизируется, то изменив знак критерия на обратный, приходим к задаче максимизации, т.е. если то

2.В исходной модели есть неравенства. При этом способ преобразования зависит от знака неравенства. В случае неравенства очевидно, что разность правой и левой части будет неотрицательной и неизвестной величиной, которую можно принять за новую переменную: Отсюда получаем следующее равенство: Аналогично при неравенстве Новая переменная (дополнительная, >=0)- разность левой и правой части и равенство записывается в виде

3.Некоторые переменные исходной модели не имеют ограничения на знак. Исключение таких переменных производится следующим способом.

Пусть – переменная, которая может иметь любой знак. Введем две неотрицательные переменные и во всей модели заменяем их разностью:

Таким образом, последние два случая преобразования к каноническому виду приводят к увеличению числа переменных, и поэтому всегда

Исходная модель: Каноническая модель: