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»: добавьте «+ переменная разницы», как показано ранее.
Делиться
ru_RURU