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