13.Определение выпуклой линейной комбинации точек

Множество точек G называется выпуклым, если наряду с двумя произвольными точками А₁, А₂, принадлежащими данному множеству, их выпуклая линейная комбинация так же принадлежит множеству: l А₁ + (1 – l)А₂ Î G, l Î [0; 1].

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

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

Точку А_о выпуклого множества G называют угловой (крайней) точкой этого множества, если не существует двух различных А₁, А₂ Î G, для которых

А_о = l А₁ + ( 1 – l )А₂ Î G, l Î (0; 1).

Понятие угловой точки можно сформулировать так: точка А_о Î G является угловой точкой данного множества, если она не является внутренней ни для какого отрезка, целиком лежащего в G.

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

Множество точек G называется замкнутым, если включает все свои граничные точки.

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

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

Геометрическая интерпретация определения множества выпуклых линейных комбинаций точек А₁, А₂ – это отрезок, соединяющий эти точки.

Рассмотрим произвольные точки плоскости А₁ (х₁⁽¹⁾, х₂⁽¹⁾), А₂ (х₁⁽²⁾, х₂⁽²⁾),

А(х₁, х₂), А Î (А₁, А₂) .

Координаты векторов:

®

А₁А = {х₁ – х₁⁽¹⁾, х₂ – х₂⁽¹⁾},

®

А₁А₂ = {х₁⁽²⁾ – х₁⁽¹⁾, х₂⁽²⁾ – х₂⁽¹⁾}.

Так как точки принадлежат одному отрезку, полученные векторы коллинеарные:

® ®

А₁А = l А₁А_2, 0 ≤ l ≤ 1.

х₁ – х₁⁽¹⁾ = l ( х₁⁽²⁾ – х₁⁽¹⁾), (1)

х₂ – х₂⁽¹⁾ = l ( х₂⁽²⁾ – х₂⁽¹⁾), (2)

Из (1) и (2):

х₁ = х₁⁽¹⁾ ( 1 – l ) + lх₁⁽²⁾ ,

х₂ = х₂⁽¹⁾ ( 1 – l ) + lх₂⁽²⁾ ,

Обозначим: 1 – l = l₁, l = l_2,

l₁ + l₂ = 1, l₁ ≥ 0, l₂ ≥ 0, (a)

х_i = l₁ х_i⁽¹⁾ + l₂ х_i⁽²⁾ , i = 1, 2

A = l₁ А₁ + l₂А₂, (b)

Точка А является выпуклой линейной комбинацией (ВЛК) точек А₁, А₂, если выполняются условия (а) и (b).

Точка А – ВЛК точек А₁, А₂, ..., А_n, если выполняются условия:

A = l₁ А₁ + l₂А₂ + … + l_nА_n,

l_j ≥ 0, l₁ + l₂ + … + l_n = 1, (1 ≤ j ≤ n)

14.Теорема о представлении выпуклого многоугольника через угловые точки

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

■ Доказательство:

Рассмотрим произвольный треугольник А₁А₂ А_3.

На стороне (А₂, А₃) выберем произвольную точкуА₄ Î (А₂, А₃), а на отрезке (А₁, А₄) точку А Î (А₁, А₄). Тогда точки А и А₄ являются выпуклыми линейными комбинациями соответственно точек А₁, А₄ и А₂, А₃ :

А – ВЛК А₁, А₄ Þ A = l₁ А₁ + l₄А₄, (*)

l₁ + l₄ = 1, l₁ ≥ 0, l₄ ≥ 0,

А₄ – ВЛК А₂, А₃ Þ A₄ = l₂ А₂ + l₃А₃, (**)

l₂ + l₃ = 1, l₂ ≥ 0, l₃ ≥ 0,

Подстановка равенства (**) в (*):

A = l₁ А₁ + l₄(l₂ А₂ + l₃А₃)

Обозначим: l₄l₂ = l₂^{^}, l₄l₃ = l₃^{^}, тогда A = l₁ А₁ + l₂^{^}А₂ + l₃^{^}А₃,

l₁ ≥ 0, l₂^{^} ≥ 0, l₃^{^} ≥ 0, l₁ + l₂^{^} + l₃^{^} = 1 Þ А – ВЛК А₁, А₂, А₃.

Если область решений – выпуклый ограниченный п - мерный многогранник, то его можно представить как п – 2 треугольника. Точка А окажется в одном из треугольников, например, в треугольнике А₁ А₂ А₃ . тогда остальные вершины войдут в разложение (ВЛК) точки А с нулевыми коэффициентами.

A = l₁А₁ + l₂А₂ + l₃А₃ + 0А₄ + …+ 0 А_n, l_j ≥ 0, l₁ + l₂ + … + l_n = 1

(1 ≤ j ≤ n) ■