Лекция 11. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Выпуклые множества в n-мерном пространстве

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

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

Рис. 1

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

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

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

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

Особый интерес в ЗЛП представляют угловые точки.

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

На рис. 2 приведены примеры различных точек многоугольника: внутренней М, граничной N и угловых А, В, С, D, Е, Е Точка F угловая, так как для любого отрезка, целиком принадлежащего многоугольнику, например FP, она не является внутренней. Эта точка является внутренней для отрезка KL, но этот отрезок не принадлежит целиком многоугольнику.

Для выпуклого множества угловые точки всегда совпадают с вершинами многоугольника (многогранника), для невыпуклого множества это не обязательно.

Рассмотрим простейшее выпуклое множество - отрезок на плоскости.

Пусть Xj= (Xj(1), х2(1)) и Х2= (х/2), х2(2)) - точки плоскости ОХ]Х2, а X = (хр х2) - любая точка отрезка XjX2. Очевидно, что отношение а длин отрезков ХХ2 и XjX2 удовлетворяет условию 0<а<1. Запишем это отношение через координаты точек

откуда

X' = ax/0 + ( - a)x{{2), x2 = ax2l) + (-a)x22),

где 0

Полагая а1 = аиа2= 1 - а, условия (1) и (2) можно переписать в виде

х = а.х(|) + <х,х(2),

11 11 " 1 (3)

2 = а{х21)2х22 a>2>0, Oj + а, = 1. (4)

Равенство (3) можно записать в виде

X = ttjXj+a^X,, (5)

учитывая, что все операции здесь выполняются покоординатно.

Таким образом, отрезок можно определить как множество точек, удовлетворяющих условиям (5) и (4). В случае п-мерного пространства определение отрезка будет таким же, если под Х2 и X, понимаются точки n-мерного пространства.

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

Точка X называется выпуклой линейной комбинацией точек Хр Х2,..., X если выполняются условия

X = alX.+a,X7+... + a X , 112 2 n n?

a > 0, Ea. = 1. j j

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

Рассмотрим теорему о представлении выпуклого многогранника. Выпуклый n-мерный многогранник является выпуклой линейной комбинацией своих угловых точек.

ДОКАЗАТЕЛЬСТВО

Для простоты возьмем п = 2, а в качестве многогранника - треугольник XjX2X3 (рис. 3). Через произвольную точку X проведем отрезок XjX4. Так как точка X лежит на этом отрезке, то

X = ajXj+a^, где a^O, a4>0, a, + a4 =1.

Точка Х4 лежит на отрезке Х2Х3, следовательно, Х4 = a2X2+a3X3, где а,>0, а3>0, а, + а3= 1.

Подставив значение Х4 в выражение для X, получим

X = + a4(a,X,+a3X3) = + a,a4X2+ a3a4X3.

Обозначив p] = ap p2 = a,a4, p3 = a3a4, окончательно получим:

x = p1x1+p2x2+p3x3,

где Р>0, Р>0, р >0, р]+ р2+ рз= 1.

Таким образом, точка X есть выпуклая линейная комбинация угловых точек (вершин) треугольника Х]Х2Х3. ®

Из доказанной теоремы следует, что выпуклый многогранник порождается своими угловыми точками: отрезок двумя точками, треугольник тремя, тетраэдр - четырьмя и т.д. В то же время неограниченная выпуклая многогранная область не определяется однозначно своими угловыми точками.

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