Различные формы записи задачи линейного программирования

В зависимости от вида используемого математического аппарата различают следующие формы записи ЗЛП [5]: векторная, матричная, каноническая.

Векторная форма записи ЗЛП

max (min) f (х₁, х₂,…, х_n) = f(x) = СХ,

А₁х₁ + А₂х₂ +…+ А_nх_n = В,

Х ≥ 0,

где    С = (с₁, с₂,…, с_n), Х = (х₁, х₂,…, х_n),

СХ – скалярное произведение векторов С и Х;

А₁, А₂,…, А_n, В – вектор – столбцы

    …

Матричная форма записи ЗЛП

max (min) f(x) = СХ,

АХ = В,

Х ≥ 0,

где    С = (с₁, с₂,…, с_n) - матрица-строка,

Х и В –матрицы -столбцы

                                                       А – матрица размерности m*n

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

Будем считать, что ЗЛП записана в канонической форме, если:

 -ее целевая функция максимизируется,

- ограничения имеют вид равенств с неотрицательной правой частью

 -  все переменные неотрицательны.

Как привести ЗЛП к каноническому виду:

1) Функциональные ограничения должны быть записаны с использованием знака «=». Если другие знаки, то добавляется вспомогательная переменная.

Если в ограничении знак < или ≤, то в левую часть ограничения добавляется  переменная со знаком «+»,

Если ограничение со знаком > или ≥, то добавляется переменная со знаком «-».

2) Должны быть положительными правые части функциональных ограничений (в противном случае уравнение умножить на «-1»).

3) Должны быть положительными переменные (в противном случае отрицательную переменную заменить разностью двух положительных переменных).

Каноническая форма используется при решении ЗЛП симплексным методом.