Беклемишев - Дополнительные главы линейной алгебры (947281), страница 59
Текст из файла (страница 59)
Из доказанного нами предложения следует, что для существования вершин у выпуклого многогранного множества необходимо равенство п = Г. Докажем, что это условие и достаточно, т. е. имеет место П р е д л о ж е и и е 7. Непустое выпуклое многогранное множество Ф, задаваемое системои (!), иаеет вершины тогда и только тогда, когда столбцы мшприцы системы линейно независимы.
Доказательство. Пусть г=п. 'Тогда конус Г, определяемый системой (4), заостренный, так как система уравнений Ах — х" НЬ =- О, Хп~ 1 — О имеет только тривиальное решение. Следовательно, каждый из столбцов р„..., р, в формуле (5) определяет ребро конуса Ж и потому обращает в равенства какие-нибудь и (число переменных без единицы) линейно независимых неравенств системы (4). Для столбцов р„..., р, в число обращаемых в равенства последнее неравенство не входит, так как для ннх х"" =- !. Значит, первые п элементов каждого из этих столбцов удовлетворяют и линейно независимым неравенствам системы (!) как точным равенствам.
Отсюда следует, что первые и элементов столбцов р,, ..., р, составляют координатные столбцы вершин многогранного множества ыв. Предложение доказано. В дальнейшем нам не придется изменять систему координат. Поэтому для облегчения словесных конструкций мы будем отождествлять точку или вектор с соответствующим координатным столбцом. Это фактически превращает аффнпное пространство в арифметическое пространетво, в котором мы будем рассматрнвать объекты аффннного пространства: точки, векторы, плоскости различного числа измерений н т.
д. Из свойств граней произвольной размерности докажем П р едл о ж е н не 8. Пусть .6' — грань многогранного множества ЕС. Если некоторал точка х е= Ф' представлена как выпуклая комбинация х = а~х1+... + аьхь с ненулевыми коэффициентами точек х,..., хл из ле, то все эти точки и ринадлеокат ыв'.
Для доказательства рассмотрим произвольное неравенство и'х~Ь' системы (!), обращающееся в равенство на грани ыв'. Мы имеем а'х = а1а'хт+... + села'хл. з е неоднОРОдные системы линеиных неРАвенств 265 Для всех !'здесь а'ху ~ Ь', Если при некотором !„выполнено а'хкч)Ь', то из а, ) О, ..., аг ) О и а, + .. + а„= 1 следует а'х ) Ь' вопреки предложению. Это заканчивает доказательство. О п р е де л е н и е. Точку х выпуклого множества мб мы назовемегокрайнейточкои,если изх=ах, + (1 — а)хеприО(а «1 и х„х, еи 'Ф следует х = х, = х,. Иначе можно сказать, что крайняя точка не является внутренней ни для какого отрезка, целиком лежащего в ..е, П р е д л о ж е н и е 9, Вершины выпуклого многогранного множества и только они явлюотся его крайними точками.
До к а з а те л ь ст в о. Если х — вершина, т. е. О-мерная грань множества .Ф, то, согласно предложению 8, из х=ах, + + (1 — а)х„О - а (1 и х„х, ~:Ф, следует, что х,и х, лежат в той же О-мерной грани и, значит, совпадают с х. Таким образом, каждая вершина — крайняя точка. Докажем, что каждая крайняя точка является вершиной. Проверим сначала, что из существования крайней точки следует п = Кя А. Действительно, если у — нетривиальное решение системы уравнений Ау=О, то каждое решение х системы (1) можно рассматривать как середину отрезка с концами х+у и х — у, которые также являются решениями системы (1). Далее, докажем, что в разложение крайней точки по формуле (5) не входят члены с номерами, большими Е Действительно, пусть х — крайняя точка. Тогда столбец а = !! хг, 1 ~!г может быть представлен по формуле (5) в виде Ч = а~рь+ .+ СНА+ ()хрнл+ ° ° + ()~НРю или а=и+и, где и=ар,+" +а~рн а е=!)~ры1+".
1 3 ...+р,,р,. Столбцы и+ — в и и+ — псоответствуют точкам множества ль', и точка а — середина отрезка, ограниченного этими точками, если только иФ О. Итак, для крайней точки мы имеем Ч = а1 Рх +... + агарь Отсюда следует, что а совпадает с одним из р„..., рь В самом деле, пусть, например, а, Ф О. Если а, +... + а, = О, то все доказано. В противном случае д = а,р, + (1 — а,)р„, где рг = (сс, +... + а,)-' (аз рг+...
+ и,Я, и из определения крайней точки следует, что а =р1 = рг. Но при доказательстве предложения 6 мы видели, что в том случае, когда существуют вершины, столбцы р„...,р~ определяют именно вершины. Это заканчивает доказательство. Сл едет в не. Число вершин выпуклого многогранного множества конечно. 266 гл, ч, системы неелвенств и лииепное пгогглммиеовлние Действительно, если существуют вершины, они являются край- ними точками, а крайние точки определяются столбцами р„..., рь Значит, все вершины определяются этими столбцами. Если выпуклое многогранное множество, задаваемое системой (1) ограничено, то однородная система (6) имеет только тривиальное решение, а значит, и = г, и потому выпуклый многогранник обя- зательно имеет вершины.
Мы получаем следующую теорему. Т е о р е м а 3. Выпуклый многогранник имеет вершины (край- ниг точка) и является выпуклой оболочкой своих вершин. Эта теорема — частный случай более общей теоремы„согласно которой каждое ограниченное выпуклое множество имеет крайние точки и является выпуклой оболочкой своих крайних точек. В об- щем случае множество крайних точек бесконечно. Например, крайними точками шара являются точки ограничивающей его сферы. Доказательство этой более общей теоремы можно найти, например, в книге Никайдо 124). Используем теорему отделимости для выпуклых многогранных конусов и сведение неоднородной системы неравенств к однородной для того, чтобы получить теорему отделимости для выпуклых много- гранных множеств.
Т е о р е м а 4. Пусть Ах (Ь. Тогда найдется такая строка и и число в, что ов+ш (О, а для всех решений система Ах-".-Ь выполнено ох+ш —. О. До к а з а те л ь от в о. Отметим, что столбец х, получаемый из в дописыванием снизу единицы, не принадлежит множеству решений однородной системы (4): Ах — Ьхмн ~ О, Согласно теореме 4 5 1 найдется строка й длины п + 1, для которой пв(0 и ох== 0 для всех решений системы (4), в частности для тех, которые имеют последнюю компоненту, равную 1. Первые и компонент каждого из таких решений удовлетворяют системе Ах)Ь.
Наоборот, если х — решение системы Ах) Ь, то х= = !~хг, 1 !!г — решение системы (4). Пусть о= — !!о, ш!!. Тогда ох= ох+ в(0 и ччк = ох+ -!- со =.-0 для всех решений системы Ах~ Ь, как это и .требова- лось. 4. Условие совместности. В отличие от однородных систем, неоднородные системы линейных неравенств могут быть несовмест- ными. Существует ряд условий совместности таких систем. Усло- вия, обобщающие теорему Кронекера — Капелли, можно найти в книге Черникова [40!. Здесь мы приведем одно из условий, обоб- щающих теорему Фредгольма. Т е о р е м а 5. Система линейных неравенств Ах~Ь % а наоцноьодныв системы лингпвых нвгьвенств 267 совместна тогда и только тогда, когда аз иА = О, и .:-» О следует, что иЬ =- О.
Д о к а з а т е л ь с т в о. Пусть система неравенств (1) совместна, т. е. существует столбец х высоты и, для которого АхзьЬ. Тогда для любой неотрицательной строки и длины т мы имеем иАх ~ иЬ, и потому из иА = О следует иЬ =. О. Обратное утверждение менее очевидно. Покажем, что для несовместной системы вида (!) найдется строка и.=-» О, для которой иА = О и иЬ ) О. С этой целью рассмотрим строки и„..., и, — фундаментальную систему решений системы уравненич иА = О и матрицу У, составленную из строк и„..., и,. Очевидно, что УА =О. Через У мы обозначим плоскость в пространстве гЯ', состоящую из всех столбцов вида Ах — Ь для всевозможных хенЮ„. Для всех у ~ Ж мы имеем и;у = — и;Ь (1= 1, ..., з). (7) Обратно, если уравнения (7) выполнены для некоторого у, то у+Ь удовлетворяет условию теоремы Фредгольма, и система Ах =у+ Ь совместна.
Таким образом, система уравнений (7) определяет плосность Ж. Чтобы записать эту систему в матричной форме, введем столбец «7= — УЬ. Тогда (7) примет вид Уу=д. (8) Система неравенств (1) несовместна в том и только том случае, когда плоскость $ не содержит столбцов с неотрицательными элементами, или, что то же самое, система (8) не имеет неотрицательных решений. В этом случае, согласно следствию из теоремы 2 й 1, должна быть совместна система неравенств гУ~ О, ги(0.
Пусть г — какое-то решение этой системы. Обозначим гУ через и. Тогда и ~ О, иА =вУА =О и еи= — гИт (О, т. е. иЬ) О. Таким образом, строка и — та, которая нам требовалась. Получим некоторые следствия из доказанной теоремы. П р е д л о ж е н и е 10. При 4аксированной матраце А множество столбцов Ь, для которых система (1) совместна, является замкнутым относительно произвольной нормы в вЯ', а множество столбцов Ь, для которых вта система несовместна, является открытым. Доказательство достаточно провести для последнего утверждения, так как дополнение открытого множества является замкнутым (см.
Кудрявцев [161, т. 1, стр. 305). Система (1) противоречива, если найдется такая неотрицательная строка и, что иА=О и иЬ) О. Если столбец Ь' отличается от Ь достаточно мало, та же самая строка и удовлетворяет условию иЬ') О, н отсюда следует несовместность системы Ахр: Ь'. лба ° Гл Р. системы неРАВенстВ и линеинОе ПРОГРАммиРОВАние Докажем это утверждение, оценив по с-норме возможную разность 1) =Ь вЂ” Ь. Если иЬ= О, то неравенство и (Ь+р) ) О заведомо выполнено, если ( и(3 ! (иЬ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
