Способы приведения к ним

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

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

Если использовать векторно-матричные представления, то получим

L = max

или

где верхний индекс T означает транспонирование; – вектор коэффициентов целевой функции; – векторы условий, j = – вектор ограничений или вектор свободных членов, иногда используют сокращение ССЧ (столбец свободных членов);

– матрица условий; – вектор переменных; – число переменных в канонической форме, оно не меньше числа переменных в исходной модели

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

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

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

Отсюда получаем следующее равенство:

Таким образом, чтобы привести рассмотренное неравенство к равенству, нужно к левой части неравенства прибавить новую переменную.

Аналогично поступаем с неравенством Но теперь новая переменная обозначает разность левой и правой части

и равенство записывается в виде

то есть чтобы неравенство типа “больше или равно” привести к равенству, следует из левой части вычесть новую переменную. В отличие от исходных переменных такие вновь вводимые переменные будем называть дополнительными. Нетрудно видеть, что они по определению являются неотрицательными, что соответствует каноническому представлению модели.

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

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

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

Пример 4.1. Исходная модель:

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

2.2. Стандартная форма задачи ЛП

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

Таким образом, стандатрная форма модели имеет вид

Та же модель в векторно-матричных обозначениях:

L = max

или

Здесь символ / означает “или”. Число переменных при отсутствии неограниченных по знаку переменных не больше Соответственно матрица и вектор имеют меньшие размеры, чем в канонической модели.

Поясним преобразование равенств в неравенства. Пусть в исходной модели имеется q равенств. Решив эту систему уравнений относительно первых q переменных, получим

Используя эти равенства, исключаем из целевой функции и ограничений, уменьшая тем самым количество переменных на q. Однако число ограничений не изменяется, так как для сохранения неотрицательности исключенных переменных должны выполняться неравенства

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

Дата добавления: 2014-01-11