От нее к ОЗЛП и обратно

На практике ограничения в задаче линейного программирования часто задаются не уравнениями, а неравенствами.

Покажем, как можно перейти от задачи с ограничениями-неравенствами к основной задаче линейного программирования.

Пусть имеется задача линейного программирования с n переменными х₁,х₂,…,х_n, в которой ограничения, наложенные на переменные, имеют вид линейных неравенств. В некоторых из них знак неравенства может быть ≥, а других ≤ (второй вид сводится к первому простой переменой знака обеих частей). Поэтому зададим все ограничения-неравенства в стандартной форме:

(4.1)

Будем считать, что все эти неравенства линейно независимы (т.е. никакое из них нельзя представить в виде линейной комбинации других). Требуется найти такую совокупность неотрицательных значений х₁,х₂,…,х_n, которая удовлетворяла бы неравенствам (4.1), и, кроме того, обращала бы в максимум линейную функцию:

(4.2)

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

(4.3)

где у₁,у₂,…,у_m –некоторые новые переменные, которые мы будем называть «добавочными». Согласно условиям (4.1), эти добавочные переменные так же, как и х₁,х₂,…,х_n, должны быть неотрицательными.

Таким образом, перед нами возникает задача линейного программирования в следующей постановке: найти такие неотрицательные значения n+m переменных х₁,х₂,…,х_n; у₁,у₂…,у_m, чтобы они удовлетворяли системе уравнений (4.3) и одновременно обращали в максимум линейную функцию этих переменных:

Как видно, перед нами в чистом виде основная задача линейного программирования (ОЗЛП). Уравнения (4.3) заданы в форме, уже разрешенной относительно базисных переменных у₁,у₂…,у_m, которые выражены через свободные переменные х₁,х₂,…,х_n. Общее количество переменных равно n+m из них n «первоначальных» и m «добавочных». Функция L выражена только через «первоначальные» переменные (коэффициенты при «добавочных» переменных в ней равны нулю).

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