LP: каноническая форма и стандартная форма

Контенус

Каноническая форма и стандартная форма

Линейные программы следуют определенным правилам при написании. А линейная программа который следует правилам, называется канонической формой. Алгоритм симплекс может применяться только к линейным программам в канонической форме.

Каноническая форма

Линейная программа в канонической форме:

Задача максимизации при ограничениях «меньше или равно», в которой все переменные строго положительны.
Проблема Минимизация, при больших или равных ограничениях, все переменные которых строго положительны.

Если линейная программа не соответствует этим критериям, ограничения или целевая функция должны быть преобразованы в соответствии со следующими операциями:

макс z = – мин -z
x + y ≥ b эквивалентно – x – y ≤ – b
x + y = b эквивалентно x + y ≥ b, x + y ≤ b

Каноническая форма часто представляется в виде матрицы:

вектор коэффициентов целевой функции: c размера n
матрица коэффициентов левой части ограничений: A размера m*n
вектор констант правой части ограничений: b размера m
вектор переменных: x размера n

Итак, следующая линейная программа:

Записывается в следующем виде:

стандартная форма

Для каждого ограничения неравенства канонической формы мы добавляем резервная переменная положительные и такие, что:

Ax ≤ b ⇔ Ax + e = b, e ≥ 0, здесь e — вектор размера m переменных пробела.

Таким образом, каноническая форма приводится к стандартной форме добавлением пробельных переменных в вектор переменных:

вектор коэффициентов целевой функции: c размера n+m (n вместо x и m вместо e, хотя последние не учитываются при расчете)
матрица коэффициентов левой части ограничений: Ã размера m*(n+m), правая часть матрицы представляет собой единичную матрицу размера m.
вектор констант правой части ограничений: b размера m
вектор переменных размера n+m

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

Вот правила, которым нужно следовать, чтобы наилучшим образом преобразовать симплекс в стандартную форму:

Ограничения «больше или равно» или «меньше или равно с отрицательным значением b»: сделайте b положительным и добавьте «– резервная переменная + искусственная переменная »
Ограничения «равенства»: добавить «+ искусственная переменная»
ограничения «меньше или равно с положительным b»: добавьте «+ переменная разницы», как показано ранее.