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


[Старт] [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] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


11

может быть выбрана различными способами. Размерность Q здесь равна 1.

PUC.2J

Так как Л" также является линейным многообразием (размерности п)

= О , то Z = Л всякое выпуклое множество X е Л" принадлежит линейному многообразию размерности п.

Назовем размерностью выпуклого множества X eR" минимальное из размерности линейных многообразий, содержащих X . Так размерность отрезка [АВ] (рис.2.5) равна 1, размерность выпуклого множества, состоящего из точки А, равна нулю, размерность треугольника ABC равна 2.

Если размерность выпуклого множества X равна к, то можно считать, что ХеТг и выбрать в g=x+/ систему координат вида х° +/i,x° +/2,...,х +/, где /р...,4 - система независимых векторов (базис) в L.

Так, на рисунке 2.7 можно взять за начало координат в Q точку х, а за базис вектор /, тогда Q превращается в Ri.

Отметим еще один факт, связанный с понятием размерности выпуклого множества. Пусть X имеет размерность к и X a,R, Тогда пересечение X с любой гиперплоскостью Р = х\{р,х) = , где РеЛ, имеет размерность не более, чем к-1. Действительно, пусть Z=x(/7,x) =о.

Тогда легко видеть, что размерность 1=к-\. Это следует из того, что PnXcx+Z и поэтому по определению имеет размерность не бо-

лее, чем к -1 40

х еРпХ



Доказательство теоремы 2.8. Доказательство проведем по индукции. Пусть к размерность множества X . Если А: = О, то X является точкой, и утверждение теоремы очевидно. Пусть для множества размерности меньше к утверждение доказано.

Пусть а - произвольная граничная точка множества X (граничные точки существуют, поскольку X - компакт). Тогда по теореме о разделяющей гиперплоскости существует такая гиперплоскость {р,х), что

(р,х)<{р,а) для любого х е X. Пересечение Х множества X и этой

гиперплоскости представляют собой непустое подмножество и выпуклое множество. Это следует из того, что гиперплоскость выпукла и содержит точку аеХ. Множество Х имеет размерность меньше к и, по предположению индукции, является выпуклой линейной оболочкой своих крайних точек. При этом всякая крайняя точка с множества Х является крайней точкой и множества X. Действительно, пусть это не так и c = axЧ(l-a)x 0<а<1, х\х еХ .

Так как с принадлежит гиперплоскости, то 0 = {р,с-а) = а(р,х -а" +(1-а)/?,х -а<0, то (р,х -а) = 0,

(р,х-а) = 0,т.е. xgX, хеХ.

Учитывая, что с - крайняя точка в Х , получили х = с, х = с.

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

Определение 2.8. Множество X называется выпуклым многогранником, если оно является выпуклой оболочкой конечного числа точек, т.е. X является выпуклым многогранником, если оно содержит конечное число таких точек х\х,...,х*, что любая точка хеХ представлена в

виде х = Ха,, 0<а, <1, =1.

/=1/=1

Теорема 2.9. Выпуклый многогранник компактен. Доказательство. Пусть X - выпуклый многогранник, являющийся выпуклой оболочкой своих точек xx...,x: x = c(xx...,x). Для

доказательства компактности множества X достаточно показать, что из произвольной последовательности х[т)еХ, w = l,2,... можно выбрать



Так как x{in)eX, /w = l,2,..., то x[m) = Y.X)x \ 0<a,(/w)<l;

Х2 > 0.

= 1. Каждая последовательностьограниченна, следовательно,

из нее можно выбрать сходящуюся последовательность. Так как последовательностей {«/(/«)} конечное число, то можно выбрать такую подпоследовательность номеров /Wp/W2- ™ последовательности aXirij)- а, > О,

очевидно Х, = 1 • Тогда последовательность]«/С".У, j = 1,2,..., сходит-/=1/=1

к. к .

СЯ и при этом х = ИтХ«/(«/У =Z<, • /=1/=1

Теорема доказана.

Из теоремы 2.8 и теоремы 2.9 вытекает, что выпуклый многогранник является выпуклой оболочкой своих крайних точек. Если Л/ = С(хх,) -

выпуклая оболочка своих точек S = (xx...,x*), то ясно, что крайними

точками в М могут бьггь лишь точки из S (юзможно не все).

Вернемся к системе линейных неравенств вида Ах<Ъ, где {а) -

матрица / = !,...,/«, 7=1,...,«, х = (х*,...,х*), Ъ = {Ъ,,.,,Ь), Как и ранее

будем обозначать через X - множество допустимых точек системы неравенств Ах<Ь, т.е. х = хе К"\Ах<Ьу

Определение 2.9. Назовем точку xq еХ внутренней, если для нее все неравенства вида Ах<Ь выполняются строго, т.е. Ах<Ь. Все точки не являющиеся внутренними, назовем граничными.

Определение 2.10. Носителем граничной точки xq назовем множество ограничений Ах<Ь, которым эта точка удовлетворяет в виде равенств, т.е. это множество гиперплоскостей вида а. = , которые содержат точку Xq . Например, есть система линейных неравенств

-Xl + Х2 < 2 3xi+5x2 <15 lOxi +7x2 35 Xl >0

[Старт] [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] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]