Приведение задачи линейного программирования к каноническому виду

Предмет: Линейное программирование

Раздел: Приведение задачи линейного программирования к каноническому виду

Задача линейного программирования состоит в нахождении максимального или минимального значения линейной функции (целевой функции) при ограничениях в виде линейных неравенств и равенств. Данная задача имеет следующую постановку:

Целевая функция: \[ Z(X) = x_1 + 2x_2 - 2x_3 \to \max \]

Ограничения: \[ \begin{cases} 5x_1 - 5x_2 + 2x_3 \leq 20, \\ 3x_1 - 2x_2 + x_3 = 12, \\ 2x_1 - 4x_2 - x_3 \geq 8, \\ x_j \geq 0, \quad j=1, 2, 3. \end{cases} \]

Для приведения задачи к каноническому виду, нам нужно, чтобы все ограничения были представлены в виде уравнений. Решим это следующим образом.

1. Преобразуем ограничения таким образом, чтобы избавиться от неравенств:

Для первого ограничения: \[ 5x_1 - 5x_2 + 2x_3 \leq 20 \]

Добавим неотрицательную переменную \( s_1 \geq 0 \) (переменную свободного члена или "свободную переменную") для превращения неравенства в равенство: \[ 5x_1 - 5x_2 + 2x_3 + s_1 = 20 \]

Для второго ограничения: \[ 3x_1 - 2x_2 + x_3 = 12 \]

Оно уже имеет вид уравнения и дополнительной переменной не требует.

Для третьего ограничения: \[ 2x_1 - 4x_2 - x_3 \geq 8 \]

Введем неотрицательную переменную \( s_2 \geq 0 \), представляющую свободный член: \[ 2x_1 - 4x_2 - x_3 - s_2 = 8 \]

Теперь мы можем переписать задачу линейного программирования в следующем виде:

Целевая функция: \[ Z(X) = x_1 + 2x_2 - 2x_3 \to \max \]

Ограничения: \[ \begin{cases} 5x_1 - 5x_2 + 2x_3 + s_1 = 20, \\ 3x_1 - 2x_2 + x_3 = 12, \\ 2x_1 - 4x_2 - x_3 - s_2 = 8, \\ x_j \geq 0, \quad j=1, 2, 3; \\ s_k \geq 0, \quad k=1, 2. \end{cases} \]

Таким образом, приведенная нами задача в каноническом виде состоит из целевой функции, которая остается без изменений, и системы уравнений вместо неравенств, благодаря введению дополнительных свободных переменных \( s_1 \) и \( s_2 \).