На практике ограничения в задаче линейного программирования часто задаются не уравнениями, а неравенствами.
Покажем, как можно перейти от задачи с ограничениями-неравенствами к основной задаче линейного программирования.
Пусть имеется задача линейного программирования с n переменными х1,х2,…,хn, в которой ограничения, наложенные на переменные, имеют вид линейных неравенств. В некоторых из них знак неравенства может быть ≥, а других ≤ (второй вид сводится к первому простой переменой знака обеих частей). Поэтому зададим все ограничения-неравенства в стандартной форме:
(4.1)
Будем считать, что все эти неравенства линейно независимы (т.е. никакое из них нельзя представить в виде линейной комбинации других). Требуется найти такую совокупность неотрицательных значений х1,х2,…,хn, которая удовлетворяла бы неравенствам (4.1), и, кроме того, обращала бы в максимум линейную функцию:
(4.2)
От поставленной таким образом задачи легко перейти к основной задаче линейного программирования. Действительно, введем обозначения:
|
|
(4.3)
где у1,у2,…,уm –некоторые новые переменные, которые мы будем называть «добавочными». Согласно условиям (4.1), эти добавочные переменные так же, как и х1,х2,…,хn, должны быть неотрицательными.
Таким образом, перед нами возникает задача линейного программирования в следующей постановке: найти такие неотрицательные значения n+m переменных х1,х2,…,хn; у1,у2…,уm, чтобы они удовлетворяли системе уравнений (4.3) и одновременно обращали в максимум линейную функцию этих переменных:
Как видно, перед нами в чистом виде основная задача линейного программирования (ОЗЛП). Уравнения (4.3) заданы в форме, уже разрешенной относительно базисных переменных у1,у2…,уm, которые выражены через свободные переменные х1,х2,…,хn. Общее количество переменных равно n+m из них n «первоначальных» и m «добавочных». Функция L выражена только через «первоначальные» переменные (коэффициенты при «добавочных» переменных в ней равны нулю).
Таким образом, задача линейного программирования с ограничениями-неравенствами сведена к основной задаче линейного программирования.