Геометрический смысл системы неравенств

Пусть дана система линейных неравенств с двумя переменными:

a_HXj + а₁₂х₂

а₉₁х + а_?9х₉ <Ь₉

• 21 1 22 2 2 /ОХ
• - (3)

Лт1^Х1^+ап>2^Х2-^Ь_т

Геометрический смысл неравенства a_nXj+а₁₂Х2 <Ц - полуплоскость, все точки которой ему удовлетворяют. Уравнение a_nXj н-а^ = Ь, определяет на плоскости ОХ_хХ₂ прямую, которая называется граничной.

В том случае, если система неравенств (3) совместна, область ее допустимых решений (ОДР) есть множество точек, принадлежащих всем указанным полуплоскостям.

Множество называется выпуклым, если оно вместе со своими любыми двумя точками содержит весь отрезок, соединяющий эти точки. Или для любых двух точек Xj и х₂, принадлежащих множеству X, ему принадлежат также все точки х, для которых справедливо равенство

х = (1 —a)xj+скх₂, 0<а<1.

Рисунок 1 - К определению выпуклого множества

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

замкнутая (ограниченная)

открытая (неограниченная)

Рисунок 2 - Виды областей допустимых решений (ОДР)

Доказывается, что ОДР ЗЛП - всегда выпуклое множество точек.

Область допустимых решений задается с помощью системы неравенств (3).

Пример 1. Построить множество (область) ДР для системы неравенств:

• -5x_t + 4x2 < 20
• 2х₁ + Зх₂ < 24

Рисунок 3 - Область допустимых решений (ОДР)

Для определения полуплоскости, которая удовлетворяет соответствующему неравенству, удобно использовать координаты точки О (0;0). Если при их подстановке в неравенство, оно является истинным, то это неравенство определяет всю полуплоскость, содержащую начало координат.

0 + 0<20 (верно); 0 + 0<24 (верно); 0-0 <3 (верно).

Точки О, А, В, С, Д, Е - вершины области решений или угловые точки.

Геометрический смысл системы неравенств на плоскости - это выпуклая область (многоугольник), каждая точка которой является допустимым решением ЗЛП.

По аналогии заключаем, что ОДР в пространстве, определяемая системой неравенств с 3-мя переменными, может представлять выпуклый многогранник.

Если систему ограничений (3) привести к каноническому виду добавлением новых переменных х₃,х₄,...,Х2_+гп, например для рассматриваемой задачи

• -5х₁ + 4x2 < 20
• 2xj + Зх₂ < 24

< x_t - ЗХ2 < 3

Х₂ < 6

^Х1,2 ⁰

• -5Xj + 4x2 ^{+ Х}3 ⁼ 20
• 2х_г + Зх₂ + х₄ = 24

Xj - 3x2 + х₅ = 3

х₂ + ^х₆ = 6

^Х12>0

то подстановкой координат точек можно убедиться, что области ДР будут соответствовать только неотрицательные значения дополнительных переменных. При этом в угловых точках ОДР дополнительные переменные, соответствующие пересекающимся линиям, равны нулю. Например, в точке Д (см. рисунок 3), где пересекаются линии и -?₃, нулю равны переменные х₃ и х₅.