Глава 6 выпуклые множества § 6.1. выпуклые множества в пространстве а". полупространство как выпуклое множество

Глава 6 выпуклые множества § 6.1. выпуклые множества в пространстве а". полупространство как выпуклое множество

Мы продолжаем знакомство с геометрией арифметических пространств. Среди геометрических понятий, связанных с А", важную роль в приложениях (особенно экономических) играет понятие выпуклого множества.

Определение 1. Множество М С Ап называется выпуклым, если вместе с любыми двумя точками АиВ оно содержит весь отрезок АВ.

Наиболее важным примером выпуклого множества в А" является полупространство.

116

Определение 2. Полупространством в А" называется множество всех точек X = (дг|, х2,.., х„), координаты которых удовлетворяют заданному неравенству первой степени:

fl|X, +а^2+ +anxn + D-(i' (6-І)

где в|,ап, b — фиксированные числа, причем at,ап не все равны нулю.

Теорема. Любое полупространство в А" есть выпуклое множество.

Доказательство. Пусть полупространство П задано с помощью неравенства (6.1). Рассмотрим какие-либо две точки

Х= [х[* х^А, Х= [х{2 .... х£2А из 77. Наша цель состоит в том,

12

чтобы показать, что любая точка X отрезка XX принадлежит П. По теореме об отрезке (см. § 4.2) имеем

OX = sOX+(l-s)OX, j€[0, 1]. Будем писать просто

X = sX+ (-s)X.

Это равенство запишется в координатах следующим образом:

х, =jx,(I) + (1-j)x,(2))

x„ = sxl> + (-s)x)fK Подставляя эти выражения в левую часть неравенства (6.1), получим

a, + (1-5)х,(2)) + ... + а„(sxW + (1-^„(2)) + Ь =

= s (alXlW + ... + ajM + b) + (1-,) (а,*,(2) + ... + оЛ(2) + b) .

i 2

Так как обе суммы, заключенные в скобки, > 0 (ведь ХЄПнХє /7), то неравенство (6.1) выполняется, т. е. Л" Є П.

Для дальнейшего нам понадобится лемма.

Лемма. Пересечение нескольких выпуклых множеств есть выпуклое множество.

Действительно, пусть М = М, П М2, где Л/,, Л/2вь,пУкльі. Докажем выпуклость А/.

Пусть А Є М и В Є Л/. Тогда Л Є М, и В Є М,. Так как М, выпуклое, то это означает, что отрезок АВ содержится в А/(. Аналогично покажем, что АВ содержится в М2. Значит, А В содержится в М, что означает выпуклость М.

Из леммы следует, что пересечение нескольких полупространств в А" является выпуклым множеством.

Определение 3. Пересечение М нескольких полупространств в А" называется выпуклой многогранной областью в А". Иначе говоря, выпуклая многогранная область в А" задается с помощью системы из нескольких линейных неравенств.

На рис. 6.2 изображены примеры выпуклых многогранных областей в А2. В этом случае вместо «многогранных» более естественно говорить «многоугольных».

Замечание. Любая плоскость в А" есть выпуклое множество: это следует из того, что уравнение alxl + ... + апхп + b = 0 равносильно системе из двух неравенств:

+...+a„xn + b<0.

Определение 4. Ограниченная выпуклая многогранная область М в А" называется выпуклым многогранником в А".

Отметим, что множество PC А" называется ограниченным, если существует такое положительное число с, что координаты любой точки X из Р по модулю не превосходят с:

хх\<с,х2 <с, ...,хп\<,с.