может быть выбрана различными способами. Размерность 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