В.А. Артамонов - Линейная алгебра для экономистов (1129135), страница 4
Текст из файла (страница 4)
Гранью ΓA точки Aв P называется Π ∩ P .Отметим, что каждая грань является полиэдром, посколькуона задается неравенствами (3) и неравенствами−f1 > 0, . . . , −fr > 0.Определение 1.23. Грань нулевой размерности называется вершиной. Грань размерности 1 называется ребром.Теорема 1.24. Пусть полиэдр P задается системой неравенствa11 x1 + · · ·+a1n xn 6 b1......................................(19)am1 x1 + · · ·+amn xn 6 bmx1 , . .
. ,xn> 0,b1 , . . . , bm > 0. Тогда начало координат O = (0, . . . , 0) является вершиной полиэдра P . Если b1 , . . . , bm > 0, то из Oвыходит ровно n ребер.Доказательство. Заметим сначала, что O удовлетворяетвсем ограничениям (19), поскольку b1 , . . . , bm > 0. Кроме того,в грани ΓO выполнены уравнения x1 = · · · = xn = 0. Отсюда всилу определения 1.23 получаем первое утверждение.Пусть b1 , . . . , bn > 0. Зафиксируем индекс 1 6 i 6 n.
Существует такое ε > 0, что aji ε < bj для всех j = 1, . . . , m.Тогда точка B = (0, . . . , 0, ε, 0, . . . , 0), где ε стоит на месте i,Линейные неравенства29удовлетворяет всем ограничениям (19), т. е. B ∈ P . Но в B выполнены уравнения x1 = · · · = xi−1 = xi+1 = · · · = xn . Поэтомугрань ΓB содержит все точки B с достаточно малых ε и потому dim ΓB = 1. Таким образом, изменяя i = 1, . . .
, n получаемn ребер. Так как каждое bj > 0, то вершина O не обращает вравенство не одно из первых m неравенств в (19).¤Следствие 1.25. Пусть полиэдр M задается системойуравнений и неравенствa11 x1 + · · · + a1n xn + xn+1 = b1................................................am1 x1 + · · · + amn xn + xn+m = bmx1 ,...xn> 0,(20)где b1 , . .
. , bm > 0. Тогда точка C = (0, . . . , 0, b1 , . . . , bm ) является вершиной полиэдра M . Если b1 , . . . , bm > 0, то из Cвыходит n ребер.Доказательство. Так как b1 , . . . , bm > 0, то точка C удовлетворяет всем условиям (20) и потому лежит в M .Заметим, что при естественной проекции An на An−r ,(x1 , . . . , xn+m ) 7→ (x1 , . . . , xn ), полиэдр M биективно проектируется на полиэдр P из теоремы 1.24.
Остается воспользоватьсяутверждением теоремы 1.24.¤Определение. Пусть x – точка полиэдра P и Π – наименьшая плоскость, содержащая P . Точка x называется (относительно) внутренней для P , если некоторая ее окрестность вΠ содержится в P .Теорема 1.26. В непустом полиэдре есть внутренниеточки.Доказательство. Пусть полиэдр P имеет размерность−−−→−−−→s и векторы A0 A1 , . .
. , A0 As линейно независимы, гдеA0 , . . . , As ∈ P. Тогда любая точкаA0 + (1 −sXi=1ssi=1i=1X −−−→−−−→ X −−−→λi )A0 A0 +λi A0 Ai = A0 +λi A0 Ai ,30В. А. АртамоновPsгде λ1 , . . . , λs > 0, иi=1 λi 6 1, лежит в P по предложению 1.8. Более того, эта точка является внутренней, если всеλi > 0.¤Предложение 1.27. Точка A ∈ P является внутреннейточкой ΓA .Доказательство. Пусть P задается неравенствами (3), агрань ΓA , где A ∈ P, задается уравнениями f1 = · · · = fr = 0.
Вэтом случае fr+1 (A) > 0, . . . , fm (A) > 0. Пусть U ⊂ An – множество всех таких точек B ∈ An , что fr+1 (B) > 0, . . . , fm (B) >0. Тогда U – открытое подмножество в An . Если Π – плоскость,задаваемая уравнениями f1 = · · · = fr = 0, то U ∩ Π ⊂ P , т. е.A – внутренняя точка ΓA .¤Теорема 1.28. Пусть аффинная функция f достигаетэкстремума в некоторой внутренней точке полиэдра P . Тогда f |P = Const.Доказательство. Можно считать, что начало координатO является точкой экстремума f . Кроме того, можно считать,что размерность P совпадает с размерностью всего аффинногопространства.Пусть в некоторой системе координат f (x) = a0 +Pnax.Таккак O – точка экстремума, тоi=1 i iaj =∂f(O) = 0∂xjдля любого j = 1, . .
. , m. Поэтому f (x) = a0 .¤Предложение 1.29. Пусть f – аффинная функция, принимающая неотрицательные значения на полиэдре P , причемf (A) = 0 для некоторой точки A ∈ P . Тогда f |ΓA = 0.Доказательство. Точка A является внутренней точкойΓA по предложению 1.27. Остается воспользоваться теоремой 1.28.¤Следствие. Определение грани полиэдра не зависит отсистемы неравенств, задающих полиэдр.Линейные неравенства31Предложение. Пусть полиэдр P задается системой аффинных неравенств (3), а грань ΓA , где A ∈ P, задается уравнениями f1 = · · · = fr = 0. Если ранг линейных частей системыf1 , . . . , fr равен k, то dim ΓA = dim P − k.Доказательство.
Можно считать, что все пространствоявляется минимальной плоскостью, содержащей P . Предположим, что ранг линейных частей системы f1 , . . . , fr равен k, и Π– плоскость, задаваемая системой уравнений f1 = · · · = fr = 0.Пусть U ⊂ An – множество всех таких точек B ∈ An , чтоfr+1 (B) > 0, . . . , fm (B) > 0. Тогда U ∩ Π ⊂ ΓA , причемdim ΓA = dimhU ∩ Πi = dim Π = dim P − k.¤Теорема 1.30. Пусть полиэдр P задан системой аффинных неравенств (3). Предположим, что f1 , .
. . , fr не равнытождественно нулю на P , и fr+1 |P = · · · = fm |P = 0. Обозначим через Πi , 1 6 i 6 r, гиперплоскость, задаваемую уравнением fi = 0. Тогда Πi ∩ P является гранью размерности dim P − 1в P для некоторого i.Доказательство. Без ограничения общности можно считать, что гиперплоскости Π1 , . . . , Πr различны. Пусть A – внутренняя точка в P . Из предложения 1.29 вытекает, что f1 (A) >0, . . . , fr (A) > 0.
Переходя к плоскости, порожденной P можноnсчитать, что эта плоскостьPn совпадает с A , и r = m. Предположим, что fi (x) = ai + j=1 aij xj . Обозначим через Bi проекциюA на Πi . Как известно,−−→|ABi | = p|fi (A)|a2i1(21)+ · · · + a2inПусть U – открытый шар в An с центром в точке A, целиком содержащийся в P . По (21) все точки X ∈ An , равноудаленные отгиперплоскостей Πi , Πj , i 6= j, образуют пару гиперплоскостей,задаваемых уравнениями|fi (X)|pa2i1+ ··· +a2in|fi (X)|=qa2j1+ · · · + a2jn.32В. А. АртамоновОбъединение всех этих гиперплоскостей по всем парам 1 6 i 6=j 6 n не покрывает все U .
Следовательно, в U существует такаявнутренняя точка B, расстояния от которой до Π1 , . . . , Πr различны. Без ограничения общности можно считать, что A = B−−→−−→−−→и |BB1 | < |BB2 | < . . . < |BBr |.Лемма. Точка B1 принадлежит P .Доказательство. Пусть B1 ∈/ P .
Тогда существует такоеi = 2, . . . , n, что fi (B1 ) < 0. Пусть, например, f2 (B1 ) < 0.ZZZZZZZΠ2¶ZZZtA = B¶¶¶Z¶tZ¶ B2 Z¶¶CZtZZZZZΠ1tB1Рис. 1.3Так как f2 (B) > 0, то на интервале (B, B1 ) найдется такаяточка C, что f2 (C) = 0. В этом случае C ∈ Π2 , причем (см.−→−−→−−→−−→−−→Рис. 1.3) |BС| > |BB2 |. Отсюда |BB1 | > |BC| > |BB2 |, чтопротиворечит предположению.¤Завершим доказательство теоремы. Заметим, что B1 ∈/ Πi ,если i > 2. Действительно, если бы B1 ∈ Πi для некоторого i >−−→−−→2, то, в частности, |BB2 | 6 |BB1 |, что неверно.
Таким образом,f2 (B1 ) > 0, . . . , fn (B1 ) > 0, т.е. ΓB1 = Π1 ∩ P . При этомdim ΓB1 = dim Π1 = n − 1 = dim P − 1.Линейные неравенства33¤Теорема 1.31 (Фань Цзы). Пусть полиэдр P задается вAn системой неравенств (3), причем ранг линейных частейf1 , . . . , fm равен r. Если A ∈ P , то dim ΓA > n − r и каждаягрань в P размерности d > n − r обладает гранью размерности d − 1. В частности, dim P > n − r, и в P имеется граньразмерности dim P .Доказательство.
Переходя к новому базису можно считать, чтоXf1 = x1 , . . . , fr = xr , fj =aji xi + cj , j > r.i6rОбозначим через U подпространство, задаваемое уравнениями x1 = · · · = xr = 0. Пусть A = (x01 , . . . , x0n ) ∈ P иrz }| {u = (0, . . . , 0, ur+1 , . . . , un ) ∈ U. ТогдаA + u = (x01 , . . . , x0r , x0r+1 + ur+1 , . . . , x0n + un ).При этом x0i > 0 при i = 1, . . . , r, иXfj (A + u) = cj +aji x0i > 0,j > r.i6rПоэтому A + U ⊆ P . Если fj (A) = 0 для некоторого j > r,то аналогично fj (A + U ) = 0, откуда ΓA ⊇ A + U , и поэтомуdim ΓA > dim U = n − r.Пусть ΓB – грань точки B в P , dim ΓB > n − r.
Тогда невсе функции x1 , . . . , xr тождественно равны нулю на ΓB . Потеореме 1.30 в ΓB имеется грань размерности dim ΓB − 1.¤Теорема. Пусть полиэдр P обладает вершиной и аффинная функция f на P достигает минимума. Тогда этот минимум достигается и в некоторой вершине.Доказательство. Пусть c = minP f и f (A) = c. ТогдаA – внутренняя точка грани ΓA по следствию 1.27. По предложению 1.29 функция f постоянна на ΓA . Заметим, что ΓAзадается неравенствами, линейные части которых те же, чтои в неравенствах, задающих P . Поэтому в силу теоремы Фань34В.
А. АртамоновЦзы ΓA имеет грань меньшей размерности, если ΓA не вершина.Отсюда вытекает утверждение.¤Теорема 1.32 (Г. Вейль). Конечнопорожденный конус является полиэдром.Доказательство. Пусть конус K ⊆ An с вершиной O порождается точками A1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
