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

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

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

+ акук и хе=р)яг+" 1-р)ЕМ где все аь !3) ) О, а у) и г) — ненулевые векторы, прннцалежашие ребрам. Отсюда прямо следует доказываемое. Обратное утверждение очевидно. В самом деле, если х„..., хе)— направляющие векторы ребер, то любая их неотрицательная линейная комбинация принадлежит конусу согласно предложению 1. Для того чтобы от заостренных конусов перейти к конусам общего вида, докажем П р е д л о ж е н и е 11.

Г)-л)ерное подпространство Я является суммой д + 1 лучей. Д о к а з а т е л ь с т в о. Пусть и„..., е,-базис в Я . Положим у= — (е, + ... + еч). Тогда для любого 1 = 1, ..., у верно равенство — е;=у+ ~', е). !Ф) Произвольный вектор х из х", имеет разложение х= е)ет+ ...

... + Веет Если е) 0 при каком-то ), то заменим в разложении х слагаемое «)е) на ! ~) (~+ ~ е)). $ Ь ОДНОРОДНЫЕ СИСТЕМЫ ЛИНЕЙНЫХ НЕРАВЕНСТВ из После приведения подобных членов мы получим разложение х по векторам е„..., е„у о неотрицательными коэффициентами. Наоборот, легко видеть, что всякая линейная комбинация этих векторов с неотрицательными коэффициентами принадлежит о . Предложение доказано. Объединяя предложения 7, 10 и 11, мы получаем следующую теорему. Т е о р е м а 1. Каждый замкнутый выпуклый многогранный конус является сумлюй конечного числа лучей, или, что то же, совокупностью линейных комбинаций конечного числа векпюров с неотрицательными коэффии,центами.

Возможно, что для некоторых целей более удобным окажется представление, связанное с предложением 7: произвольный вектор конуса представим как сумма некоторой линейной комбинации базисных векторов минимальной грани и неотрицательной линейной комбинации ненулевых векторов ребер заостренного конуса. Теорема 1 может быть сформулирована и иначе: Т е о р е м а 1а. Общее решение системы однородных линейных неравенств может бьипь записано в виде х = алхл+... + анхн, еде х„...хн — некоторый набор решений, а коэффициенты аы ..., ам неотрицательны, Мы будем использовать следующую терминологию.

Конечное множество лучей, суммой которых является конуо, мы назовем системой образующих конуса и будем говорить, что они порождают конус. Про направляющие векторы этих лучей мы будем также говорить, что они порождают конус. Минимальная (по количеству) система образующих называется остовом конуса. Допуская вольность речи, мы будем называть остовом и множество направляющих векторов лучей, составляющих остов конуса. По отношению к системе линейных неравенств набор решений, упомянутый в теореме 1а, назовем полной системой решений, а минимальную (по количеству) полную систему решений — фундаментальной системой. Отметим, что существует весьма громоздкий, но в принципе приводящий к цели способ нахождения всех ребер заостренного конуса.

Именно, нужно перебрать все подсистемы системы линейных уравнений (6), ранг которых равен п — !. (Такие системы существуют, так как ранг системы (6) равен и, а вычеркивание одного уравнения уменьшает ранг пе болыпе чем на 1.) Каждая такая система имеет фундаментальную систему решений из одного решения. Если это решение х удовлетворяет системе (1), то оно определяет ребро конуса; если оно удовлетворяет системе (1) о противоположными знаками неравенств (:=), то — х определяет ребро конуса, В остальных случаях х не представляет интереса. 244 гл, ч.

систвмы нвькввнств и линвннов пгогэхммиговлнив Говоря о фундаментальных системах решений однородных систем линейных неравенств, следует помнить об одном нх существенном отличии от фундаментальных систем решений однородных систем уравнений. Именно, разложение решения системы неравенств по фундаментальной системе решений, вообще говоря, не единственно. Приведем соответствующий пример. Пусть четырехгранный конус определяется в трехмерном пространстве системой неравенств х'~0, х')О, хе~О, х'+х' — х'.--О. Легко видеть, что остов этого конуса можно составить, например, из векторов е„ в„ у= е, + еь и л'= е, + е„ где е„ е, и е,— базисные векторы.

Нетрудно также заметить, что принадлежащий конусу вектор е, +~ можно представить также и в виде е, + д'. Для того чтобы описать остов произвольного конуса, введем следующее определение. Крайним вектором конуса а," назовем вектор х ен Л', который не допускает представления в виде х1+хм где х, и х,— неколлинеарные векторы, принадлежащие МГ. Иными словами, вектор х крайний, если из х=х, + х, и х„х,ецЮ следует, что х, и х, коллинеарны. Очевидно, что вектор Хх, пропорциональный крайнему вектору х с неотрицательным множителем Х, также является крайним. Луч, состоящий из крайних векторов, назовем крайним лучом. П р едл о же н не 12. Если конус З' заостренный, то его ребра и только они являются его крайними лучами.

Действительно, вектор х ен Х, не принадлежащий ребру Ю, принадлежит или внутренности З', или внутренности его грани размерности ) 2. В этом случае он не является крайним, так как раскладывается в сумму двух векторов, принадлежащих граням того конуса, для которого он — внутренний. Таким образом, крайними лучами могут быть только ребра.

Но они действительно являются крайними лучами, как следует нз предложения 9, Предложение доказано. Каждый крайний луч конуса обязательно входит в его остов, так как векторы этого луча не могут быть получены как неотрицательные линейные комбинации векторов из других лучей. Поэтому прямым следствием предложений 10 и 12 является П р едл аж е н и е 13. Остов заостренного конуса содержит все его ребра и только их. Докажем теперь следующее П р е д л о ж е н и е 14. Остов произвольного конуса Ю является объединением остовов его минимальной грани Хь и заостренного конуса Ю, такого, что Уь = Хь+ Юи До к аз а тел ь от в о.

Согласно предложению 7 канув глГ имеет грани размерности п — г + 1, каждая из которых является суммой минимальной грани Хь конуса Ю и одного из ребер конуса А;. Пусть гь — одна из таких граней. Остов ль мы получим, $ Ь ОДНОРОДНЫЕ СИСТЕМЫ ЛИНЕЯНЫХ НЕРАВЕНСТВ 245 если к остову Яе присоединим направляющий вектор того ребра конуса Л"„которое содержится в ех. В самом деле, очевидно, что все векторы из ыв раскладываются в неотрицательные линейные комбинации этой системы из л — г + 2 векторов.

Остов ех не может состоять из меньшего числа векторов, так как совокупность неотрицательных линейных комбинаций и — г + ! векторов в (п — г + 1)- мерном пространстве является либо заостренным конусом (если эти векторы составляют базис), либо конусом меньшей размерности (если векторы линейно зависимы). Далее, в силу предложения 9 остов конуса ЛГ должен содержать в себе остовы всех его (н — г + 1)-мерных граней. й(инимальной системой, удовлетворяющей этому требованию, является система векторов, о которой идет речь в формулировке предложения. Это заканчивает доказательство. Доказанное предложение можно рассматривать как уточнение теоремы 1„позволяющее описать минимальную систему векторов, порождающую конус. Ниже мы докажем теорему, обратную теореме 1, ко сначала нужно будет рассмотреть линейные неравенства, являющиеся следствиями заданной системы линейных неравенств.

3. Неравенства — следствия системы линейных неравенств. Рассмотрим неотрицательную линейную комбинацию неравенств, составляющих систему (1). Это — линейное неравенство такого же вида, как и неравенства системы. Оно имеет строку коэффициентов иА, где и — строка!~ ин ..., и !! с неотрицательными элементами, а А — матрица системы. Очевидно, что неравенство иАх»0 является следствием системы Ах~ 0 в том смысле, что оно выполнено для всех ее решений. В этом пункте мы получим фундаментальный результат, который состоит в том, что каждое однородное линейное неравенство, являющееся следствием системы Ах ~ О, имеет вид иАх» 0 при и~ О.

Этот результат известен как теорема Фаркаша. Предварительно мы докажем следующее П р е д л о ж е н и е 15. Системы Ах» О и иА = О, и ~ 0 обладшот решениями х, и ие, для которых Ахе+ие )О (у) Докажем сначала, что найдутся решения, для которых положительна первая компонента левой части (7). После этого доказательство не будет составлять труда.

Если т = 1, т. е. матрица А состоит из одной строки, утверждение очевидно. В самом деле, если единственная строка а' нулевая, то положим х=О, а и = 1. В противном случае положим х=(а1)т а и О Допустим теперь, что утверждение доказано для матриц, состоящих из т — 1 строк, и докажем его для матрицы А из т строк а', ..., аы. Строки а', ..., а -' составляют матрицу А, к которой 246 ГЛ, Ю СИСТЕмм НЕРАВЕНСТВ И ЛИНЕИНОЕ ПРОГРАММИРОВАНИИ можно применить предположение индукции. Поэтому существуют столбец х высоты п и неотрицательная строка 11и1, ..., й-1 11, для которых Ах= О, иА=О, а'х+и')О. Если а"'х) О, то х н !!и1, ..., и -', О 1! являются требуемыми решениями, н утверждение доказано, Допустим, что а"х(0. Составим матрицу В размеров Ьн — 1) к и из строк Ь'=а! — и!а", 1=1 ... о! — 1 где а'х и = —.

а"х ' Очевидно, что столбец Вх состоит из элементов а!х+ а1а х и потому равен нулю. К матрице В применим предположение индукции и найдем столбец у и строку т! такие, что Ву ~ О, НВ = О, о =- О, Ь'у+ о') О. Рассмотрим строку т — 1 то=~о!, ..., о -', — ~, 'а!о! ~, Она неотрицательна, так как все о') О, а! ~ О в силу а'х ) О и а"'х ( О. Легко видеть, что тоА =НВ=О. Рассмотрим столбец в=у+ йх, где й выбрано так, чтобы а"'я= О.

Для этого должно быть й = — а'"у/а'"х. Мы имеем "=~Ф1=Ф'=~~71=' Здесь использовано доказанное выше равенство Вх=О. Далее, из (8) следует, что а!г= Ь'у. Кроме того, !о' = о'. Следовательно, а!г+!о! = Ь'у + о') О, и потому г и то являются искомыми столбцом и строкой для матрицы А. Докажем теперь, что можно найти такие столбецх, и строку и„ что Ах, ) О, и,А = О, и, ) О и Ах,-1- и, ) О. Для этого применим доказанное выше утверждение к матрице Р,А, где Р,— матрица перестановки, переставляющая 1-ю строку на первое место. Мы получим строку тн1и столбец Вн для которых положительна 1-я компонента левой части (7). Рассмотрим хо= ~ч', я! н ио- х тв! ° 1 1 1 1 з ь однояодныя системы лнняиных няяьвянств 247 Легко показать, что х, и и, удовлетворяют всем требуемым соотношениям. Этим заканчивается доказательство предложения. Докажем теперь теорему Фаркаша в следующей формулировке. Те о р е м а 2. Каковы бы ни были матрица А размеров т 74 и и строка Ь длины и, обязательно имеет решгние одна и только одна из систем Ах--О, Ьх(0 иА =Ь, и)0.

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

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