§ 6.3. выпуклая оболочка системы точек

§ 6.3. выпуклая оболочка системы точек

Представим себе, что в плоскость, имеющую вид бесконечного листа фанеры, в некоторых точках АХ,А2, Ар забиты колышки.

Дадим теперь строгое определение выпуклой оболочки.

Определение 1. Пусть Ах,А2,...,Ар — некоторый набор

точек из А". Любая точка А вида

A = sxAx +^2 + ... + SpAp ,

где sx > 0, s2 S 0,$ > О, sx + s2 + ... + sp = 1, называется выпуклой линейной комбинацией точек А х, А2,Ар.

Определение 2. Множество всех выпуклых линейных комбинаций точек Ах, А2, Ар называется выпуклой оболочкой системы точек Ах, А2, Ари обозначается

<Ах,А2,...,Ар>

(другое обозначение: сот (Ах, А2,Ар) от английского «convex» — выпуклый).

122

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

Теорема. Множество L = <AX,A2, —,А> есть наименьшее из всех выпуклых множеств, содержащих точки Ах, А2, ■■■,Ар.

Доказательство. Нам необходимо доказать три утверждения:

L содержит каждую из точек Ах, А2, Ар.

L выпукло.

Каково бы ни было выпуклое множество Л/, содержащее каждую из точек Ах, А2,Ар, справедливо включение L С М.

Утверждение 1 очевидно, поскольку Ах = АХ + 0-А2 + О-Ар, откуда следует Ах Є L; аналогично и А2 Є L, ...,Ар Є L.

Докажем утверждение 2. При этом для сокращения записей будем считатьр = 3, т. е. что имеются три точки Ах, А2, Ау Пусть какие-то точки В и С принадлежат L:

B = sx Ах +s2A2 + Ait С = tx Ах + t2A2 + t^Ay

sx,s2,53>0, ^|+j2 + j3=1,

tx,t2,t3>0, tx + t2 + t3=l.

Любая точка X отрезка ВС имеет вид X=sB + tC, где s, t>:$, s + t = l. Отсюда

X = s(sx Ax + s2A2 + s3A3) + t (tx Ax + Г2^2 + 'з^з) =

= (ssx + ttx)Ax+ (ss2 + tli)A2 + (ss^ + /ґ3) Аг .

Коэффициенты при Ах,А1,Ат) в последнем выражении неотрицательны, а их сумма равна 1:

(SSX + ltx) + (SS2 + tt2) + 0*3 + tty) = S (Sx + S2 + Sy) + t (tx + t2 + /3)= 1.

Следовательно, X Є L, что и доказывает выпуклость L.

Докажем утверждение 3. По-прежнему считаем р = 3. Пусть М — какое-либо выпуклое множество, содержащее каждую из точек АХ,А2,АЪ.

Рассмотрим любую точку из L:

st Л| +S2A2 + siAi,sl,S2,s3kO, st +^2 + 53= 1.

(

sxA | + S2A2 = (S + Jj)

Имеем

s2

it /1 л

S[+S2 1 j, +s2 L

s s2

Точка В = A1 + A2 принадлежит отрезку A XA2. Так как M

выпуклое множество, имеем В Є М. Далее,

B +

sxA + s2A2 + siA'i = (s + Si) В + s^A^ =

s+s2

$1 + s2 + .s3 + j2 + s3

где точка С принадлежит отрезку &43 и потому С Є М.

Мы показали, что любая выпуклая линейная комбинация точек А,А2,А$ принадлежит М, т. е. что LCM. Теорема доказана.

Геометрическую иллюстрацию к последней части доказательства теоремы дает рис. 6.7.

А,

В

Рис. 6.7

Примеры

|. Предприятие выпускает два вида товаров Тх, Т2В любой из дней

предприятие может работать по одной из трех технологий 1, 2, 3.

ПустьЛ, = a2^j—набор товаров, производимых задень работы

по і-й технологии (/= 1,2,3). Рассмотрим промежуток времени, состоящий из / дней. Пусть из них /| дней отведено технологии 1,12 дней

— технологии 2, 1Ъ дней — технологии 3. Тогда набор В товаров,

произведенных за промежуток /, будет следующий:

В = 1ХА, + t2A2 + ;3Л3 = ^в, + 'j-B2 + ^Въ,

гдеЯ,.= /Л,0= 1,2,3).

Мы видим, что точка В есть выпуклая линейная комбинация точек Д|, В2, By Следовательно, множество всех наборов, которые

предприятие может выпустить за период t, есть выпуклая оболочка точек Вх,В2,Ву Разумеется, аналогичный пример может быть

рассмотрен при любом ассортименте товаров Tt, Т2,Тп и любом

количестве технологий 1, 2,..., р. В этом случае получим выпуклую

оболочку точек Я|, В2,Вр в А".

2. Имеются три сплава золота с серебром и другими металлами. Пусть А1 = ^ а^, а2® ^, где — доля золота, а а2® — доля серебра в 1-м сплаве (/' = 1, 2, 3). Из данных сплавов составлен новый сплав и Jl'J2>J3 — доли данных сплавов. Тогда доля золота в новом

сплаве следующая: ах = sx + s2 af-2* + j3 д/3 а доля серебра —

а2 = si «2^ + s2 а2^+ siа2^Иначе говоря, точка Aia^a-^ представляется в виде выпуклой линейной комбинации точек Ах,А2,Ау

В частности, ответим на такой вопрос: пусть

Л, (0,9; 0,05), Л2(0,4;0,35), Аъ (0,1; 0,45);

можно ли из данных сплавов составить новый сплав с содержанием золота 55\% и серебра 30\%? Ответ можно получить графически

125 (рис. 6.8), если на бумаге в клетку построить выпуклую оболочку точек В| (18, 1), Вг (8, 7), Вз (2, 9) (масштаб увеличен в 20 раз).