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