Беклемишев - Дополнительные главы линейной алгебры (947281), страница 53

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 53)

Векторы, координаты которых удовлетворяют системе (4), называются внутреннил!и векторами конуса Ж, а множество всех внутренних векторов — его внутренностью. В соответствии с предложением 2 любой конус в некотором подпространстве определяется системой нежестких неравенств. Соответствующая система строгих неравенств имеет решения, лежащие в упомянутом подпространстве. Множество этих решений называется относительной внутренностью конуса. П р едл о ж е н и е 4. Каждый внутренний лектор конуса ьк" принадлежит конусу вл!есте с некоторой своей окреспгносглыо относительно произвольной нормы. Поскольку все нормы эквивалентны (теорема 1 5 4 гл. 1), достаточно доказать это утверждение для с-нормы ) х ), = гп ах ~ х' ~.

Рассмотрим вначале одно неравенство и вектор х„для которого а,х,'+...+аихь =г! О. Положим (Число е определено, так как среди коэффициентов а„,.„аи есть отличные от нуля: неравенство с нулевыми коэффициентами является жестким). Если вектор х таков, что 11 х — х, ~1, - з, то он, как и х„удовлетворяет строгому неравенству. Действительно, обозначив х,' — х' через б!, имеем и и и и .У', а!л' = ,У, 'а!кй — '~' а,б! ) Ь вЂ” ~ ~; а!б! . ! = ! с = ! Е=! Но ! и и и ~" а;б' ~ ~~ !б!,'1а!, '-- шах,'б!~ ~ ~аг',(г!. 1=! Отсюда мы заключаем, что и а!х!> О, г=! как и требовалось. Рассмотрим теперь систему неравенств (4) и вектор хи- решение этой системы.

Каждое из неравенств системы по формуле (5) $ С ОДНОРОДНЫЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ 239 определяет радиус такой окрестности вектора х„любой вектор которой удовлетворяет этому неравенству. Минимальная из этих окрестностей состоит из векторов, удовлетворяющих системе (4). Теперь нетрудно доказать следующее П р е д л о ж е н и е 5. Если конус Яс" в пространстве Ж„определяется систел!ой линейных неравенств, которая не содержит жестких неравенств, то разл!ерность З' равна ролл!ерности пространства Для доказательства рассмотрим какой-нибудь внутренний вектор х, конуса Ю. Пусть его координаты равны х,', ..., х„", а е есть радиус окрестности вектора х„состоящей из внутренних векторов аЗ'.

Рассмотрим векторы с координатами о ' о' х' — т! х' х" х', х' — т1, ..., х", л', м ! м где ! т! ! ~а и т! отлично от характеристических чисел матрицы, все строки которой совпадают со строкой х,',, х,". Легко видеть, что этн векторы линейно независимы и принадлежат З'. Предложение доказано. Отс!ода и нз предыдущих предложений следует П р е д л о ж е н н е 6. Размерность конуса Ю, определяемого системой линейных неравенств (1), равна и — р, где р — ранг матрицы, составленной из коэффициентов жестких неравенств. 2.

Строение выпуклого многогранного конуса. Пусть З' — конус, задаваемый системой неравенств (1). Рассмотрим подмножества конуса Ю, получаемые заменой некоторых нежестких неравенств системы (1) на равенства. Легко видеть, что эти подмножества — конусы меньшей размерности. Они называются гранями конуса З'. Частным случаем грани является подпространство, определяемое системой линейных уравнений а!х'+... + а„'х" = О, (б) аых'+...+а'"х" = 0 Эта грань называется минимальной гранью конуса.

Название связано с тем, что какова бы ни была грань А', она содержит в себе минимальную грань. Размерность минимальной грани равна и — г, где г — ранг матрицы А из коэффициентов системы (Ц, Рассматривая грань Ю' конуса Ю как самостоятельный конус, мы можем определить грани АЗ' . Очевидно, что они являются гра- 240 гл.

Р системы неРАВенстВ и линеиное ПРОГРАммиРОВАниВ нями конуса Л'. Минимальная грань конуса Л" является минимальной гранью любой его грани. Минимальная грань конуса может оказаться нулевым подпространством. В этом случае конус называется заостренным. Для того чтобы конус был заостренным, необходимо и достаточно, чтобы 1«й А = и. Если Вй А ~ и, то конус называется тупым. (Употребляется также термин «клины) Удобно будет ввести следующее определение.

Пусть д«„..., д' множества векторов в линейном пространстве Я„. Сумлюй д', + ...+ + У«этих множеств мы будем называть множество всех векторов вида х = х,+...+х„где х; ~ д'ь ( = 1, ..., ц. Отметим, что сумма подпространств в смысле обычного определения является их суммой в указанном выше смысле. Теперь мы можем сформулировать и доказать следующее П р едл о же н и е 7, Каждь«й выпуклый лиюгограннь«й конус Л' является суммой некоторого заостренного конуса Л' и своей минимальной грани Ж'. Каждая грань Л' конуса Л' есть сулсиа Х« и некоторой грани конуса Л'.

Обратно, каждая такая сульяа есть грань конуса Л. Д о к а з а т е л ь с т в о. Пусть Ж' — такое подпространство, что Х„= Х«+ Ж' и Х" ()Х' = О. Рассмотрим множество векторов З' = о' () Л'. Оно определяется системой неравенств, получаемой объединением системы неравенств (1) конуса Л' и системы уравнений подпространства Ж'. Следовательно, Л вЂ” конус.

Минимальная грань Л' определяется системой уравнений, которая получается заменой на равенства всех неравенств в системе (!) и добавлением уравнений подпространства Ж'. Но это как раз система уравнений для о«() Х', и она имеет только тривиальное решение. Следовательно, конус Ю' заостренный. Далее, для любого х ее.'с„имеет место разложение х =х, + +х„где х,ееХ«и х, ее Ж'. Если х ее Л', то вектор х, как сумма векторов х и — х, нз Л' также принадлежит Л'. Таким образом, х, я Л"'. Легко видеть, что и, обратно, из х, ее Ж«и х, ее Л' следует х, + х, ее Ж.

Это заканчивает доказательство первого утверждения. Для доказательства второго утверждения достаточно заметить, что пересечение «З" () :о' является гранью конуса Л.". Но это очевидно, потому что система неравенств для З"' () Х' получается из системы для Л' = Ю (! Х' заменой на равенства некоторых неравенств, а именно тех, которые обращаются в равенства на грани Л" конуса Л', Обратное утверждение доказывается столь же просто.

Важные заключения о строении многогранных конусов могут быть сделаны из следующего предложения. П р е дл о ж е н и е 8. Пусть З' — заостренный вьтуклый многогранно«й конус размерности ~2. Тогда каждый вектор х, ~ Л' представим как сумма двух векторов, принадлежащих граням Л. $1. ОднОРОдные системы линейных неРАВенств 241 До к а з а тел ь от в о. Для вектора, принадлежащего грани, утверждение очевидно. Пусть х, не принадлежит ни одной грани. Обозначим через а', ..., а'" строки матрицы системы нера- венств, задающей Л', и рассмотрим вектор х, из Л", не коллинеар- ный вектору х,. Будем предполагать, что нежестким неравенствам системы соответствуют номера 1 ( в.

Тогда для таких номеров 1 выполнены строгие неравенства а'х, ) О. Рассмотрим числа а'х, Х, = —., 1=1 а'х ' а и докажем, что среди них есть хотя бы два различных. В самом деле, если существует тзкое число Х, что для всех 1(в Х (а'х.) — а'х1 = О, то вектор )ха — х, удовлетворяет всем нежестким неравенствам как равенствам. Кроме того, для всех 1) в имеем а1х,=О и а'х,=О. Поэтому Хха — х, удовлетворяет также и всем жест- ким неравенствам.

Это означает, что Хха — х, принадлежит мини- мальной грани конуса Л' н, следовательно, равен нулю, так как конус заостренный. В этом случае вектор х, коллинеарен ха вопреки предположению. Итак, среди чисел )н существуют различные между собой мак- симальное !н и минимальное Хр Для Аа имеем Х~(аах,) — (а'х,) =:О, 1-~1, 1а=в, ) а(а ха) — (а1хг) = О Кроме того, Ц (а'ха) — (а'х,) = О, 1 ~ в, так как х, и х, удовлетворя1от жестким неравенствам. Все эти соотношения означают, что вектор у=1,ха — х, прннадлегкит грани конуса Ю.

Аналогично доказывается, что другой грани конуса Л' принадлежит вектор н=х, — )1ха. Теперь доказываемое легко следует из равенства у + е = ()1 — Х~) х,. Грани выпуклого многогранного конуса обладают следующим свойством. П р е дл о ж е н и е 9. Если вектор х грани Л" предстослен как сумлаа нескольких векторов конуса, то все вти векторы принадлежат Л'. Действительно, пусть а' — строка коэффициентов одного из неравенств системы, обращающихся в равенства для грани Л", а х = х1 + ...

+ ха — то разложение, о котором идет речь. Тогда а'Х=а'Хг+...+ааХа =О, а сумма неотрицательных чисел может равняться нулю, только если все они равны нулю. Поэтому а'ху = О для всех 1 = 1, „1, откуда и следует доказываемое. 242 ГЛ Ч, СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Одномерные грани конуса получаются абра)цением в равенства и — 1 линейно независимых неравенств системы, задающей конус. Если при этом остается еще одно независимое нежесткое неравенство, то одномерная грань является лучом. Одномерные грани- лучи называются ребрами многогранного конуса. В заостренном конусе одномерная грань — обязательно луч.

П р едл о же н и е 10. Заостренный комус есть сумма своих ребер. Докажем сначала, что каждый вектор х заостренного конуса можно представить в виде х=а)х1+...+ачхч, где все а; ~ О, а х) — ненулевые векторы, принадлежащие ребрам конуса. Доказательство проведем индукцией по размерности конуса. У двумерного заостренного конуса гранями являются ребра, и потому доказываемое совпадает с утверждением предложения 8. Для конуса размерности п в силу того же предложения 8 каждый вектор х может быть разложен в сумму х=х,+х„где хг и х, принадлежат граням. Грани — заостренные конусы меньшей размерности, и, согласно предположению индукции, существуют разложения х1 — — а1у1+...

Характеристики

Список файлов книги