Лекции Методы оптимальных решений

3.2. Линейные неравенства

рассмотрим подробнее системы линейных неравенств и покажем, что решение их тесно связано с понятиями выпуклого многоугольника и выпуклого многогранника.

Для начала рассмотрим неравенство с одной переменной величиной x₁, например x₁4. Если на плоскости провести прямую х₁=4, то она разделит всю плоскость на две части - полуплоскости: в одной из них, а именно слева от прямой х₁=4, лежат точки, абсциссы которых меньше 4, а справа от прямой - точки, абсциссы которых больше 4. Таким образом, неравенство x₁4 геометрически определяет полуплоскость (Рис.1). Рассмотрим теперь неравенство с двумя переменными типа 3х₁+4х₂  12. Построим прямую линию 3х₁+4х₂=12. Разделим обе части уравнения на 12:

из которого видно, что прямая отсекает по осям отрезки, равные 4 и 3.

Неравенство 3х₁+4х₂  12 определяет собой совокупность всех точек плоскости, лежащих ниже прямой, т.е. в заштрихованной части (Рис. 2).

Чтобы легче было понять, какую именно полуплоскость определяет то или иное неравенство, мы в левую часть неравенства подставим координаты начала координат, т.е. х₁=0 и х₂=0. Если неравенство удовлетворяется, то оно определяет ту полуплоскость, в которой лежит начало координат, в противном случае - другую полуплоскость. Пользуясь геометрическими соображениями, найти возможные решения системы:

3х₁+4х₂  12

x₁2

х₁ 0 и х₂  0

Каждое из неравенств системы определяет полуплоскость, отмеченную на Рис.3 штрихами.

Полученный многоугольник является выпуклым, ибо вместе с любыми двумя точками содержит весь соединяющий их отрезок. таким образом, мы видим, что выпуклый многоугольник можно задать аналитически, с помощью системы линейных неравенств. Линейное уравнение с тремя переменными: a₁₁x₁+a₁₂x₂+a₁₃x₃=b₁ определяет в пространстве некоторую плоскость, которая рассекает все пространство на два полупространства.

В связи с этим неравенство a₁₁x₁+a₁₂x₂+a₁₃x₃  b₁ определяет одно из полупространств, к которому принадлежит также и сама граничная плоскость. В общем случае, когда система неравенств совместна, пространство решений образует некоторый выпуклый многогранник - многогранник решений. Частным случаем его могут быть: отдельная грань, ребро или точка. Последнее имеет место, когда система неравенств имеет одно единственное решение. Дальнейшие обобщения приводят нас к рассмотрению m линейных неравенств с n неизвестными. Каждое уравнение a_i₁x₁+a_i₂x₂+ ... +a_inx_n=b_i является уравнением некоторой гиперплоскости в n-мерном пространстве, которая как бы рассекает все пространство на два полупространства.

Содержание