Беклемишев - Дополнительные главы линейной алгебры (947281), страница 58
Текст из файла (страница 58)
Обозначим через р„..., Р, фундаментальную систему решений системы (4) н предположим нумерацию такой, что в столбцах Р„...,Р, последняя компонента положительна, а в столбцахР„„...,Р, равна нулю. При этом можно даже считать, что в первых 1 столбцах последняя компонента равна 1, так как любой из столбцов может быть заменен на ему пропорциональный с положительным множителем пропорциональности. Если система (1) совместна, то г ) 1.
Действительно, в противном случае для любых х и х"+' из Ах — х "' Ь.== О следует х"" =. О, и в частности, для решения х системы (1) из Ах — о =- О вытекает 1 = О. Все решения системы (4) и только онн могут быть представлены формулой Ч=а*Ръ+" +и~Р~+гчРм+" +(),-Ф, (5) с неотрицательными коэффициентами а, и Рн При этом в силу наших предположений столбец д имеет последнюю компоненту, равную 1, тогда и только тогда, когда а,+...+а,=1. Полученное равенство необходимо и достаточно для того, чтобы первые н компонент столбца (5) были решением системы (!).
При этом условии, отбросив последние элементы ' всех столбцов в формуле (5), мы получим общее решение системы линейных неравенств (1). Геометрически добавление вспомогательной переменной х"+' означает переход к (и + 1)-мерному пространству, в котором исходное п-мерное пространство содержится в качестве гиперплоскости с уравнением х"+' = 1, Система однородных неравенств (4) опреде- г х нзодиоеодиыв системы линвиных ивгкввнств 261 ляет выпуклый многогранный конус Л'.
Множество решений системы (1) — это пересечение конуса Уь" и гиперплоскости х"ы = 1. При х"+' = 0 система (4) превращается в однородную систему Ах~О. (6) Решения этой системы мы будем представлять себе как векторы. Так как последняя компонента каждого из этих векторов равна нулю, они лежат в направляющем подпространстве гиперплоскости х"+' =1. Система (6) определяет в этом подпространстве выпуклый многогранный конус ЛГ. Легко видеть, что р„„..., р, — координатные столбцы векторов остова Ю Столбцы р„..., рг будем рассматривать как координатные столбцы точек Р„...„Р,.
Тогда первая группа слагаемых в формуле (5) представляет собой произвольную выпуклую комбинацию точек Р,, ..., Р„а вторая группа — произвольный вектор из конуса лг Таким образом, мы можем сформулировать следующую теорему, которая является переводом формулы (5) на геометрический язык. Т е о р е м а 1. Пусть Ж вЂ” выпуклое многогранное множество. Тогда найдутся выпуклая оболочка конечного числа точек У и выпуклый многогранный конус%такие, что все точки лг и только они получаются откладыванием веюпоров из гпГ от точек из У. Пусть система (6) имеет только тривиальное решение. Тогда конус Ю состоит из нулевого вектора, множество ыз совпадает С У И ПОтОМу ОГраНИЧЕНО. НаО6Орст, ЕСЛИ юГ СОдЕржИт НЕНуЛЕ- вой вектор, то, умножая его на достаточно большой коэффициент, можно получить точку множества гг, среди координат которой будут сколь угодно большие по абсолютной величине.
Следовательно, имеет место С л е д с т в и е. Выпуклое многогранное множество, определяемое системой (1), является многогранником в том и только том случае, когда соответствующая однородная система неравенств имеет только тривиальное решение, Другой предельный частный случай получается при 1 = 1. Тут множество У состоит из одной точки, и тогда гс — выпуклый многогранный конус, рассматриваемый как точечное множество. Докажем теорему, обратную теореме !. Т е о р е м а 2. Пусть множество У вЂ” линейная оболочка конечного числа точек, Ю вЂ” выпуклый многогранный конус, а лЬ— множество точек, получаемых откладыванием векторов из Ю от точек из У. Тогда ль — выпуклое многогранное множество.
Д о к а з а т е л ь с т в о. Координатный столбец произвольной точки Х из Ф имеет вид х = жгхг+ ° ° + ссьхг+ ргег+" + ()лил Здесь хг,..., х~ и 1„..., 1ь — координатные столбцы соответственно точек, на которые натянуто У, и -векторов, порождающих Ю. Раз Гл ч системы неРАВенстВ и линеннОе пРОГРАммиРОВАние Все коэффициенты неотрицательны, н о, + ... +и, = 1. Обозна-' чим через р„( =1, ..., 1, столбцы, получаемые из х; дописыванием снизу единиц, а через ст~, 1 = 1, ..., Ь, — столбцы, получаемые яз 1с дописыванием снизу нулей.
Произвольные неотрицательные линейные комбинации столбцов р, и д~ вида х = агрс+" ° + очрс+ исус+ ° ° + Гсьуь составляют выпуклый многогранный конус Ю в (и + 1)-мерном линейном пространстве. По теореме 3 й ! найдется набор строк а', ..., ан длины и+! таких, что х ев йс' тогда и только тогда, когда аьх~О для всех й = 1, ..., У. Запишем эти неравенства подробнее и учтем, что сумма коэффициентов а; равна единице. с'(ы получим А а "х = Р , 'ас (а'х;) + Р , 'сс;а'„+, + ~~ Р, (аь(с) = а'х+ а А+ с =: О, с-с с=с с=с Но Л ен сь тогда и только тогда, когда х ен сй. Таким образом, Х ~ сь тогда н только тогда, когда ее координатный столбец удовлетворяет системе неоднородных линейных неравенств А и х+ а„+ с =.- О, у=1, ..., Лс.
Теорема доказана. С л е д с т в и е. Выпуклая оболочка произвольного конечного множества точек является выпуклым мноюгранником. 3. Грани выпуклого многогранного множества. Говорят, что непустое выпуклое многогранное множество имеет размерность й, если оно лежит в й-мерной плоскости и не лежит ни в какой плоскости меньшего числа измерений. Неравенства, входящие в неоднородную систему вида (1), могут быть разделены на жесткие и нежесткие так же, как это было сделано в з 1 по отношению к однородным неравенствам. Под жесткими неравенствами мы понимаем такие, которые для решений данной системы могут быть выполнены только как точные равенства. П р е д л о ж е н и е 5, Размерность выпуклою многогранною множества сь, определяемого системой (1), равна и — р, где р— ранг матрицы, составленной иэ коэффициентов жестких неравенств.
Доказательство основывается на рассуждениях, аналогичных приведенным при доказательстве предложений 2 — 5 $ 1. Во-первых, заменив в жестких неравенствах знаки ~ на =, мы получим уравнения плоскости Ж„Р размерности и — р, в которой лежит многогранное множество МР. Если мы выразим из этих уравнений р % г неодногодныв системы линвпных негкввнств 263 переменных и подставим их в оставшиеся (нежесткие) неравенства, то получим систему нежестких неравенств, с помощью которой в определяется в плоскости 8„ Далее, рассматривая Ж„р как самостоятельное пространство, покажем, что множество, определяемое системой нежестких неравенств, не лежит ни в какой гиперплоскости. С этой целью покажем сначала, что соответствующая система строгих неравенств имеет решение х,.
Действительно, каждое неравенство в некоторой точке множества;й выполнено как строгое. Нужным нам решением х, будет любая выпуклая комбинация этих точек с ненулевыми коэффициентами. Нетрудно доказать, что х, будет внутренней точкой множества в том смысле, что принадлежит ему вместе с некоторой (и — р)- мерной окрестностью. Отсюда аналогично доказательству предложения 5 5 1 можно вывести доказываемое утверждение. О п р е д е л е н и е. Гранью выпуклого многогранного множества, определяемого системой (!), называется выпуклое многогранное множество решений системы, которая получается из (1) заменой некоторых нежестких неравенств на равенства.
Одномерные грани называются ребрами, О-мерные грани— вершинами выпуклого многогранного множества. Каждое одномерное выпуклое многогранное множество — это либо прямая линия, либо луч, либо отрезок. Поэтому, если ребра существуют, они могут быть только трех перечисленных выше типов. У ограниченного выпуклого многогранника ребра могут быть только отрезками. й-мерное многогранное множество лежит в й-мерной плоскости и (если оно не пустое и не совпадает со всей плоскостью) задается в ней системой неравенств, которая содержит нетривиальные нежесткие неравенства.
Поэтому и-мерное многогранное множество имеет (й — 1)-мерные грани, получаемые обращением в равенство одного из этих неравенств. Заметим, что все грани пустыми быть не могут. Если бы так случилось, многогранное множество состояло бы из решений системы строгих неравенств. Тогда рассуждением, аналогичным доказательству предложения 4 5 1, мы доказали бы, что это множество открытое, тогда как, будучи пересечением замкнутых множеств, оно должно быть замкнутым. Более подробно сейчас это обосновывать не стоит, так как это следует из доказываемой ниже теоремы 7.
Итак, непустое и не совпадающее с й-мерной плоскостью й-мерное выпуклое многогранное множество должно иметь (й — 1)-мерные грани, но нельзя утверждать, что оно имеет грани меньших размерностей, так как (й — ! )-мерная грань вполне может оказаться (/г — !)-мерной плоскостью. Точнее, имеет место П р е д л о же н не 6. Выпуклое многогранное множество, задаваемое системой линейных неравенств с матриией А ранга г, не можаи иметь граней размерностей, меныиих чем и — г. 264 ГЛ, У. СИСТЕМЫ НЕРАВЕНСТВ и ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Действительно, для того чтобы грань имела размерность й, на ней должны обращаться в равенства и — й линейно независимых неравенств системы, Но общее число линейно независимых равенств, получаемых из системы (!), Ее больше чем Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
