![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
На практике ограничения в задаче линейного программирования часто задаются не уравнениями, а неравенствами.
Покажем, как можно перейти от задачи с ограничениями-неравенствами к основной задаче линейного программирования.
Пусть имеется задача линейного программирования с переменными, в которой ограничения, наложенные на переменные, имеют вид линейных неравенств. В некоторых из них знак неравенства может быть а других (второй вид сводится к первому простой переменой знака обеих частей). Поэтому зададим все ограничения-неравенства в стандартной форме:
Будем считать, что все эти неравенства линейно независимы (т. е. никакое из них нельзя представить в виде линейной комбинации других).
Требуется найти такую совокупность неотрицательных значений которая удовлетворяла бы неравенствам (4.1), и, кроме того, обращала бы в минимум линейную функцию:
От поставленной таким образом задачи легко перейти к основной задаче линейного программирования. Действительно, введем обозначения:
где — некоторые новые переменные, которые мы будем называть «добавочными». Согласно условиям (4.1), эти добавочные переменные так же, как и должны быть неотрицательными.
Таким образом, перед нами возникает задача линейного программирования в следующей постановке: найти такие неотрицательные значения переменных чтобы они удовлетворяли системе уравнений (4.3) и одновременно обращали в минимум линейную функцию этих переменных:
Как видно, перед нами в чистом виде основная задача линейного программирования (ОЗЛП). Уравнения (4.3) заданы в форме, уже разрешенной относительно базисных переменных которые выражены через свободные переменные Общее количество переменных равно, из них «первоначальных» и «добавочных». Функция L выражена только через «первоначальные» переменные (коэффициенты при «добавочных» переменных в ней равны нулю).
Таким образом, задача линейного программирования с ограничениями-неравенствами сведена нами к основной задаче линейного программирования, но с большим числом переменных, чем первоначально было в задаче.
Пример 1 Имеется задача линейного программирования с ограничениями-неравенствами: иайти неотрицательные значения переменных удовлетворяющие условиям
и обращающие в минимум линейную функцию
Требуется привести эту задачу к виду ОЗЛП.
Решение. Приводим неравенства (4.4) к стандартной форме;
Вводим дополнительные переменные:
Задача сводится к тому, чтобы найти неотрицательные значения переменных
удовлетворяющие уравнениям (4.6) и обращающие в минимум линейную функцию (4.5).
Мы показали, как от задачи линейного программирования с ограничениями-неравенствами можно перейти к задаче с ограничениями-равенствами (ОЗЛП). Всегда возможен и обратный переход — от ОЗЛП к задаче с ограничениями-неравенствами. Если в первом случае мы увеличивали число переменных, то во втором случае будем его уменьшать, устраняя базисные переменные и оставляя только свободные.
Пример 2. Имеется задача линейного программирования с ограничениями-равенствами (ОЗЛП):
и минимизируемой функцией
Требуется записать ее как задачу линейного программирования с ограничениями-неравенствами.
Решение. Так как, то выберем какие-то две из переменных в качестве свободных. Заметим, что переменные в качестве свободных выбирать нельзя, так как они связаны первым из уравнений (4 7): значение одной из них полностью определяется значением другой, а свободные переменные должны быть независимыми
По такой же причине нельзя в качестве свободных выбрать переменные (их связывает второе уравнение). Выберем в качестве свободных переменные и выразим через них все остальные:
Так как условия (4 9) могут быть заменены неравенствами:
Рис. 2.18
Перейдем в выражении линейной функции L к свободным переменным Подставляя в L вместо и их выражения (4.9). получим:
Таким образом, задача сведена к задаче линейного программирования с ограничениями-неравенствами. Ее геометрическая интерпретация показана на рис. 2.18. Основная прямая параллельна той стороне ОДР, где V достигает минимума. Следовательно, все точки участка АВ дают оптимальное решение. Беря в качестве решения, например, координаты точки А, получим:
При таких значениях переменных линейная функция L достигает минимума, равного
Таким образом, мы можем по произволу переходить от ОЗЛП к задаче линейного программирования с ограничениями-неравенствами и обратно. Если в числе ограничений задачи есть как уравнения, так и неравенства, рекомендуется произвести унификацию и перейти в какой-либо единообразной форме, например ОЗЛП.
Пример 3. Рассматривается задача линейного программирования с переменными и ограничениями вида
Минимизируется функция
Требуется привести задачу к ОЗЛП.
Решение. Введением добавочных переменных приведем условия (4.12) к виду ОЗЛП:
Минимизируемая функция остается в виде (4.13).
Дата публикования: 2015-02-03; Прочитано: 459 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!