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

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

aHXj + а12х2

а91х + а?9х99

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

Лт1Х1п>2Х2-Ьт

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • -5xt + 4x2 < 20
  • 1 + Зх2 < 24

1

_х '

+ JX

? гГ

II IV IA

« О 04

0

Уравнения линий:

-4 : 2х. +3х, = 24

Z 1 Z y

----- А1

0

12

х2

1,-. X,-3X2=3 Х1

  • 5
  • 0

0

з : х2 =6;

8

0

Х2

-1

о (5: X, =0; ?6: х2 =0.

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

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

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

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

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

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

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

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

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

< xt - ЗХ2 < 3

Х2 < 6

Х1,2 0

  • -5Xj + 4x2 + Х3 = 20
  • г + Зх2 + х4 = 24

Xj - 3x2 + х5 = 3

х2 + х6 = 6

Х12>0

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >