Каноническая форма задач ЛП
Задача ЛП представлена в канонической форме, если в ее модели все функциональные условия имеют вид равенств и все переменные ограничены по знаку. Направление цели не имеет существенного значения, для однозначности канонического представления будем иметь в виду максимизацию критерия. Модель задачи:
Векторно-матричные представления: L =
С– вектор коэффициентов целевой функции; Aj - векторы условий, j = Любую задачу ЛП можно привести к каноническому виду. Возможны 3 случая несоответствия исходной модели каноническому представлению. 1.Если в исходной постановке критерий минимизируется, то изменив знак критерия на обратный, приходим к задаче максимизации, т.е. если 2.В исходной модели есть неравенства. При этом способ преобразования зависит от знака неравенства. В случае неравенства 3.Некоторые переменные исходной модели не имеют ограничения на знак. Исключение таких переменных производится следующим способом. Пусть Таким образом, последние два случая преобразования к каноническому виду приводят к увеличению числа переменных, и поэтому всегда Исходная модель: Каноническая модель:
|