Выпуклые множества точек

Е

Рис. 2.1

Например, многоугольник на рис. 2.1, а — выпуклый, а мно­гоугольник на рис. 2.1, б не является выпуклым (он расположен по обе стороны от прямой ВС).

Общим определяющим свойством, которое отличает выпук­лый многоугольник от невыпуклого, является то, что если взять любые две его точки и соединить их отрезком, то весь отрезок будет принадлежать этому многоугольнику. Это свойство может быть принято за определение выпуклого множества точек.

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

Согласно этому определению многоугольник на рис. 2.1, а яв­ляется выпуклым множеством, а многоугольник на рис. 2.1, б таковым не является, ибо отрезок MN между двумя его точками М и N не полностью принадлежит этому многоугольнику.

⁴У1

Выпуклыми множествами могут быть не только многоугольни­ки. Примерами выпуклых множеств являются круг, сектор, отрезок, многоугольная область, куб, пирамида (рис. 2.2, о— е), многогран­ная область, прямая, полуплоскость, полупространство и т.п.

Выпуклые множества обладают важным свойством, которое устанавливается следующей теоремой.

Теорема 2.2. Пересечение (общая часть) любого числа выпуклых множеств есть выпуклое множество.

П Пусть М и N — любые две точки пересечения двух¹ мно­жеств А и В (рис. 2.3). Так как точки М и vV принадлежат пересе­чению множеств, т.е. одновременно и выпуклому множеству А, и выпуклому множеству В, то согласно определению выпуклого множества все точки отрезка MN будут принадлежать как множе­ству А, так и множеству В, т.е. пересече­нию этих множеств. А это и означает, что пересечение данных множеств есть выпуклое множество. ■

Среди точек выпуклого множества можно выделить внутренние, граничные и угловые точки.

Точка множества называется внут­
ренней, если в некоторой ее окрестности²
содержатся точки только данного мно­
жества.
^с* *•' Точка множества называется граничной,

если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему.

Глава 2

Элементы линейной алгебры и геометрии 35

Особый интерес в задачах линейного программирования пред­ставляют угловые точки.

Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежаще­го данному множеству.

На рис. 2.4 приведены примеры различных точек многоуголь­ника: внутренней (точки М), граничной (точка N) и угловых (точки А, В, С, D, Е). Точка А — угловая, так как для любого от­резка, целиком принадлежащего многоугольнику, например, от­резка АР, она не является внутренней; точка А — внутренняя для отрезка KL, но этот отрезок не принадлежит целиком много­угольнику.

Для выпуклого множества угловые точки всегда совпадают с вершинами многоугольника (многогранника), в то же время для невыпуклого множества это не обязательно. Так, на рис. 2.5 точка А является вершиной невыпуклого многоугольника, но не угловой (она является внутренней для отрезка АХ, целиком принадлежа­щего этому многоугольнику).

Множество точек называется замкнутым, если включает все свои граничные точки. Множество точек называется ограничен­ным, если существует шар (круг) радиуса конечной длины с цен­тром в любой точке множества, который полностью содержит в себе данное множество; в противном случае множество называет­ся неограниченным.

Если фигура ограничена только прямыми или их отрезками, то число ее угловых точек конечно; в случае криволинейности границ фигура содержит бесконечно много угловых точек, что позволяет сделать следующее определение.

Выпуклое замкнутое множество точек пространства (плоскости), имеющее конечное число угловых точек, называется выпуклым много­гранником (многоугольником), если оно ограниченное, и выпуклой много­гранной (многоугольной) областью, если оно неограниченное.

До сих пор рассматривались выпуклые множества точек на плоскости и в пространстве. Аналитически такие точки изобра­жаются упорядоченной парой чисел (х\, xj) или упорядоченной тройкой чисел (xj, x-i, xi). Понятие точки можно обобщить, под­разумевая под точкой (или вектором) упорядоченный набор п чисел Х= (х\, *2, ■ ••> *л), ^в котором числа Х\, x-i,..., х„ называются координатами точки (вектора). Такое обобщение имеет смысл, так как если взять какой-либо экономический объект, то для его ха­рактеристики двух-трбх чисел обычно бывает недостаточно и не­обходимо взять я чисел, где п > 3.

Множество всех точек Х- (х\, *2> —> ^хп) образует n-мерное точеч­ное (векторное) пространство. При п > 3 точки и фигуры л-мерного пространства не имеют реального геометрического смысла и все ис­следования объектов этого пространства необходимо проводить в аналитической форме. Тем не менее оказывается целесообразным и в этом случае использовать геометрические понятия для облегчения представлений об объектах «-мерного пространства.