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