назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [ 17 ] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]


17

§ 11. ВЫПУКЛЫЕ МНОЖЕСТВА

11.1. Приведем некоторые вспомогательные сведения о выпуютых множествах *).

Определение. Выпуклым множеством в векторном (линейном) пространстве называется такое множество что для любых U, V G: S и произвольного X G [О, 1) вьшолняется KU+ (1 - X) VS (см. рис. 1.6), т.е. вместе с любыми двумя своими точками и и V множество S содержит весь соединяющий их прямолинейный отрезок. □

Примерами вьшуклых множеств могут служить замкнутые полупространства т.е. множества всех векторов Ze для которых UZ с при заданных URn CGR.

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

Рис. 1.6

11.2.Если множество S - выпуклое, X,, .. ., Л S, и а,,. .. , ад - неотрицатель-

ные числа, для которых S а-= 1, то вектор £ а. Х, назьгоаемый выпуклой комбина-

1=11=1

цией векторов Xj,Xj, также принадлежит S. Совокупность всех вьшуклых

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

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

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

11.4.Имеет место следующая теорема об отделимости вьшуклых множеств. Если S и Т - два непересекающихся выпуклых множества, то существует разделяющая их гиперплоскость, т.е. такая гиперплоскость UZ = с, чю

UZ>c при ZS, VZ <с приZT.

11.5.Определение. Точка U назьшается крайней точкой вьшуклого множества S, если f/G .S и не найдется таких двух различных точек U,U" S, что U = = (U + U")/2. □

Справедлива следующая теорема Каратеодори ***).Если S - выпуклое замкнутое ограниченное подмножество R", то каждая его точка представима в виде выпуклой комбинации не более чем w + 1 его крайних точек.

*) Более обстоятельную информацию о вьшуклых множествах можно почерпнуть из книги Р. Рокафеллара "Вьшуклый анализ" (М., "Мир", 1973), а также из любого достаточно подробного учебника по линейному программированию.

**) Соответствующее доказательство читатель может найти в книге: Ашма-н ов С.А. Линейное программирование. - М.: Наука, 1982.

***) См., например: Рокафеллар Р. Вьшуклый анализ. - М.: Мир, 1973, с. 169. 4*51



11.6. Частным случаем выпуклого множества является выпуклый конус.

Определение. Выпуклым конусом в векторном пространстве называется такое множество С, что каковы бы ни были С/" G С и неотрицателЫ1ые X и \", имеет место X U + X"U" G С □

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

Определение. Если заданы векторы C/j, ..., Щ,то являющаяся выпуклым

конусом совокупность всех векторов вида 2 X. U, гце Х-> О при / = 1,.. ., А:, называется вьшуклым конусом, натянутым на векторы U, :.., U. □

§ 12. ЛЕММА О ДВУХ АЛЬТЕРНАТИВАХ

Лемма (о двух альтернативах). Какова бы ни была тХп-матрица А, имеет место одна из двух возможностей (альтернатив") :

1)существует такой вектор X GX, что XAj О для всех / = 1,... ,«;

2)существует такой вектор YG Y, 4ToAf Одля всех / = 1,... , т.

Доказательство. Составим выпуклую оболочку фундаментального симплекса X (т.е. всех векторов Ь),. .., Е) и всех векторов A.j и обозначим ее через М. Нам могут при этом представиться две возможности:

Рис. 1.7

а) 0 (рис. 1.7). В этом случае точка О (согласно п. 11.4) отделима от множества Л некоторой гиперплоскостью. Мы можем считать, что эта гиперплоскость проходит через точку О, а все множество М лежит по одну сторону от нее. Пусть UZ = О - уравнение этой гиперплоскости, и для любого Z G Л

UZT>0,(12.1)

В частности, должно быть UE >0 для каждого /= 1, ..., т. Рассмотрим числа UE -Щ (/= I, ... , т). Так как все эти числа положительны, их сумма также положительна:

и= 2w,.>0.

/ = 1

Составим теперь вектор

= (?l,...,?m)

Очевидно, что Z € X. 52



Поскольку w>0, из (12.1) следует, что и

для любой точки Z G Л. В частности, это будет и для всех точек A.f. XA.j > > О, и мы нашли требуемый вектор X.

б) О G (рис. 1.8). В этом случае (согласно п. 11.2) точка О может быть представлена в виде выпуклой комбинации вершин многогранника J/, , т.е. в виде выпуклой комбинации А. х,А., ),E(f). Пусть

1а,А.,+ s е,. =0.•(12.2) 1=1 /=1

Здесь а,,..., а„, ej,!.., О и

2а,. + 2 F. = l.(12.3) /=1 1=1

Равенство (12.2) являетсявекторным. Расписывая его покоординатно, получаем

2 сьгзг.-+е,. = 0.(12.4) / = 1

Ввиду того, что 6,- > о, должно быть

2 а.д.. 0.(12.5) / = 1

Дапее мы имеем

а= 2 а,.>0.(12.6)

Если бы было о: = О, то ввиду неотрицательности каждого из чисел а-все они должны бьши бы быть равны нулю: = О (/ = 1,...,«). Но тогда из (12.4) следовало бы, что и все числа ej равны нулю, а это противоречит равенству (12.3). Следовательно, в действительности в (12.6) имеет место знак строгого неравенства.

Положим .теперь 0/0: = т? и составим вектор У= (т?!, ..., г]„). Как

легко проверить, Y G Y.

Ввиду того, что о:> О, мы можем левую часть (12.5) разделить на а, не нарушив знака неравенства. В результате мы получим

2 rij =Ai. <0 для всех

/= 1,,.. ,m.

Следовательно, вектор Y является искомым. □

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [ 17 ] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]