циентами) вдоль п попарно ортогональных осей, проходящих через некоторую точку аоеА; б) движения, оставляющего неподвижным точку ао; в) сдвига.

Доказательство. Заменив / его композицией с подходящим сдвигом, как в доказательстве теоремы п. 5, мы можем считать, что уже / имеет неподвижную точку ао. Отождествив А с L и ао с нулем, мы можем разложить f = Df в композицию положительно определенного симметрического оператора и ортогонального оператора. Приведя первый из них к главным осям и перенеся эти оси в А, получим требуемое.

9. Заметим в заключение, что в этом параграфе мы широко пользовались линейными подмногообразиями в А (прямыми, плоскостями), определяя их конструктивно как прообразы линейных пространств в L при разных отождествлениях А с L, зависящих от выбора начала координат. Следующий параграф посвящен более систематическому исследованию связанных с этим понятий.

§ 3. Аффинные подпространства

1. Определение. Пусть (Л, L) - некоторое аффинное пространство. Подмножество В с: Л называется аффинным подпространством в А, если оно пусто или если мноясество

M = {bt-b2eL\bi, b2eB}czL является линейным подпространством в L и tm {В) cz В для всех теМ.

2. Замечания, а) Если выполнены требования онределения и В непусто, то пара (В, М) образует аффинное пространство, что оправдывает терминологию (подразумевается, что сдвиг В посредством вектора из М получается ограничением на В этого же сдвига на всем Л). В самом деле, просмотр условий в определении п. 1 § 1 сразу же показывает, что они выполнены для {В,М). В частности, выбрав любую точку be В, получаем В = = {Ь-\-т\теМ}.

б) Будем называть линейное подпространство M={bi - 62 ?1, 62 е В) направляющим для аффинного подпространства В. азмерностью В называется размерность М. Очевидно, из Bi с: В2 следует, что Му cz М2 и, значит, dim By dim В2. Назовем два аффинных подпространства одинаковой размерности с общим направляющим пространством параллельными.

3. Предложение. Аффинные подпространства одинаковой размерности By, B2CZA параллельны тогда и только тогда, когда существует такой вектор leL, что B2 = ti{By). Любые два вектора с таким свойством отличаются на вектор из направляющего пространства для By и В2.

Доказательство. Если B2=ti{By) и Мг, М, -направляющие Вг и В, соответственно, то

М2{а-Ь\а, 6еВ2} = {(а'-Ь0-(бЧ-/)а', Ь' еВу) = Му, так что By и Вг параллельны.

Наоборот, пусть М -общее направляющее для Bi и Вг. Выберем точки 6ieB и ЬчВч. Имеем В^ = {Ь; -\- t\l М}, Вг = = {b2-i-l\lM}, откуда Bi = th-bAi)- Наконец, легко видеть, что /г, (Bi) = / jj (Вг) тогда и только тогда, когда li - /г е М.

4. Следствие. Аффинные подпространства в L (с аффинной структурой) - это линейные подмногообразия L в смысле определения п. 1 § 6 ч. \, т. е. сдвиги линейных подпространств.

5. Следствие. Параллельные аффинные подпространства одинаковой размерности либо не пересекаются, либо совпадают.

Доказательство. Если 6 е Bi ПВг, то по предыдущему В, = {Ъ -\-т\т М) = Вч, где М - общее направляющее Bi и Вг.

6. Аффинные подпространства В, и Вг не обязательно одинаковой размерности называются параллельными, если одно из их направляющих содержится в другом. Слегка изменяя предыдущие доказательства, легко получить следующие факты. Пусть Bi и Вг параллельны и dim Bi dim Вг. Тогда существует такой вектор lL, что /г(В1)с::Вг, и два вектора с этим свойством отличаются на элемент из М\. Кроме того, либо В, и Вг не пересекаются, либо Bi содержится в Вг.

7. Предложение. Пусть (Bi, Mi), (Вг, Мг)-два аффинных подпространства в А. Тогда В, П Вг либо пусто, либо является аффинным подпространством с направляющим М, П Мг.

Доказательство. Пусть В1ПВг непусто и & е В. П Вг. Тогда В, = {6-b/i/eM,}, B2={b-\-h\lM2), откуда В, П Вг = - {6 -j- / /е Ml П Мз}, что доказывает требуемое. (Следствие п. 5, очевидно, вытекает отсюда.)

8. Аффинные оболочки. Пусть S сг Л - некоторое множество точек в аффинном пространстве А. Наименьшее аффинное подпространство, содержащее S, называется аффинной оболочкой S. Оно существует и совпадает с пересечением всех аффинных подпространств, содержащих S. Мы можем описать аффинную оболочку в терминах барицентрических линейных комбинаций (предложение п. 11 § 1).

9. Предложение. Аффинная оболочка множества S совпадает с множеством барицентрических комбинаций элементов из S:

где {si, ..., s } с= 5 пробегает всевозможные конечные подмножества S.

Доказательство. Покажем преже всего, что барицентрические комбинации образуют аффинное подпространство в Л. В самом деле, обозначим через McL линейное подпространство, натянутое на всевозможные векторы s - t; s, t.(S. Любые две бари-н,ентрические комбинации точек S можно представить в виде

п п

Yj XtSf, Е fi С ОДНИМ И тем же множеством {sj, взяв

(=1 (=1

объединение двух исходных множеств и положив лишние коэффи-206

циенты равными нулю. Поскольку Z - г ~ Z У1=-у разность этих

(=1 (=1

комбинаций можно представить в виде

п

и потому она лежит в М. Наоборот, любой элемент из М вида Z Xl (si - ti) есть разность точек Е XiSi + 1 - Е Xij s, и jc,/, +

+ 1 - YjXiSi из 5. Поэтому М= {b\ - бг!!, 62:5}. Это же

соображение показывает, что tm{S)dS для всех теМ. Следовательно, S является аффинным подпространством с направляющим пространством М. Ясно, что SczS.

Наоборот, пусть В =э S - любое аффинное подпространство,

п

{si.....s ) с: S. Тогда для любых Xi.....х„еЖ, Z 1, имеем

п п

Е XiSi = S, -f YuXi (Si - Si). t-1 i=i

Поскольку s,.....s eB, вектор Xi(S{-Si) лежит в направляющем пространстве В и потому сдвиг 5i на него лежит в В. Значит, SczB а 5 действительно является наименьшим аффинным подпространством, содержащим S.

10. Предложение. Пусть f: Ai-Aa - аффинное отобраоюение двух аффинных пространств; BycAi и BiCzAi -аффинные подпространства. Тогда f{Bi)czA2 и f~{B2)czAi являются аффинными подпространствами.

Доказательство. Пусть Bi = {6 -f е Mi}, где Mj - направляющее пространство для В|. Тогда f{Bi)= {f{b)-\-Df(l)\le е Ml} = {/{6)-f Г /е ImZ)/}. Следовательно, /(Bi)-аффинное подпространство с направляющим пространством 1т Df.

В частности, f{Ai) есть аффинное подпространство в Л2, ВгП n/(/4i) есть аффинное подпространство и f~42) = /~42n/(i)) в силу общих теоретико-множественных определений. Заменив А^ на f{Ai) и В2 на Вг 0/(1), мы можем ограничиться случаем, когда / сюръективно. Пусть Мг - направляющее пространство для 62. Тогда Ba={b-{-m\mGMi} и /- (Вг) = {6-Ь т'/(6) = Df(m)eM2}, Справа можно ограничиться одним значением Ь'е е f-ib): остальные получатся из него сдвигами на KerD/. Отсюда следует, что / (г) имеет вид {Ь'+ т\т е Df-iMi)} и потому является аффинным подпространством с направляющим подпространством (£>/)-(M2l.

11. Следствие. Множество уровня любой аффинно линейной функции является аффинным подпространством.

Доказательство. В самом деле, множества уровня аффинно линейной функции /: Л->Х' суть прообразы точек в ЖК Но любая точка в аффинном пространстве является аффинным подпространством (с направляюпхим {0}).

12. Предложение. Пусть fi...../ - аффинно линейные функции на аффинном пространстве А. Тогда множество {аеЛ /i(fli)== = ... =/n{fln) = 0} является аффинным подпространством в А. Если Л конечномерно, то всякое его аффинное подпространство имеет такой вид.

Доказательство. Указанное множество является конечным пересечением множеств уровня аффинно линейных функций. Поэтому оно аффинное в силу следствия п. 11 и предложения п. 7. Наоборот, пусть В cz А - аффинное подпространство в конечномерном аффинном пространстве А, М cz: L - соответствующие линейные пространства. Если В пусто, его можно задать уравнением / = 0, где / - постоянная функция на Л с ненулевым значением (очевидно, любая такая функция аффинно линейна, Df = 0). Иначе, пусть gi = ... =gn = 0 - система линейных уравнений на L, задающая М; в качестве g\, gn можно взять, например, базис подпространства MczL*. Выберем точку Ь^В к построим аффинно линейные функции ft: Л->-Х' с условиями fi{b) = 0, Dfi= = gi, /=!,..., . Очевидно, ti{b-\-1)~gi{l). Поэтому точка £) -f / е Л обращает в нуль все функции Д- тогда и только тогда, когда Z е М, т. е. тогда и только тогда, когда 6 + / е Б. Это завершает доказательство.

13. Назовем конфигурацией в аффинном пространстве Л конечную упорядоченную систему аффинных подпространств {Bi, ...

Вп). Две конфигурации {В .... BJ и {В\, В^} назовем

аффинно конгруэнтными, если существует такой аффинный автоморфизм /еАГГЛ, что /(Вг)= Вь 1=1, и. Возможны варианты этого понятия, когда / разрешается выбирать лишь из некоторой подгруппы Aff Л, например, группы движений, когда Л евклидово. В последнем случае будем называть конфигурации метрически конгруэнтными. Важные понятия и результаты аффинной геометрии связаны с отысканием инвариантов конфигураций относительно отношения конгруэнтности. Заметим, что оно является аффинным вариантом понятия одинаковой расположенности , которое мы изучали в § 5 ч. 1.

Докажем несколько основных результатов о конгруэнтности.

Пусть Л - аффинное пространство размерности п. В соответствии с результатами пп. 8-11 § 1 назовем конфигурацию {яо, . я } из п + 1 точки в А координатной, если ее аффинная оболочка совпадает с Л.

14. Предложение, а) Любые две координатные конфигурации конгруэнтны и переводятся друг в друга единственным отображением f е Aff Л.

б) Координатные конфигурации [а^, , а„} и {а', <п) в евклидовом пространстве А метрически конгруэнтны тогда и только тогда, когда d {а^, Яу) = d [а\, а^) для любых i, j el, п.

Доказательство, а) Положим ei = ai - а^, е\ == - а^. Системы {ej и (eJ образуют базисы в L. Пусть g: LL - ли-нейное отображение, переводящее в е' Построим аффинное отображение /: Л->Л со свойством Df = g и f{ao) = a. Оно существует по утверждению п. И § 1 и лежит в Aff Л, ибо g обратимо. Кроме того,

f (fl.) = f (Go).-f g {a, - flp) = fl; -b e. = a; -f (a; - fl) = a;

для всех /= 1, п. Эта же формула показывает, что / единственная, ибо Df должно переводить в и / (я ) = а'.

б) В силу доказанного выше достаточно проверить, что / является движением тогда и только тогда, когда d (а fly) = d (я, а^) для всех i, j. В самом деле, й{яг, Яу-) = яг -Яу = ег -е/, где eo = flo -flo==0, и аналогично (Яр Gy) = e -е^]. Если / - движение, то Df ортогонально и сохраняет длины векторов, так что условие необходимо. Наоборот, пусть оно выполнено. Тогда = el I для всех / == 1, ..., п и далее из равенств е^ ~ р == - elf получаем, что (е., ej) = {e., ej) для всех t, /.Значит, матрицы Грама базисов {е.} и (ej совпадают. Но тогда отображение g, переводящее ej в \е', является изометрией, так что / является движением. Доказательство окончено.

Рассмотрим теперь конфигурации (6, В), состоящие из точки и аффинного подпространства. В евклидовом случае назовем расстоянием от 6 до В число

dip, B) = inf{/6-b/,eB}.

15. Предложение, а) Конфигурации (Ь, В) и {Ь', В') аффинно конгруэнтны тогда и только тогда, когда dim В = dim В' и либо одновременно ЬфВ, Ь' ф. В', либо одновременно be В, Ь' е В'.

б) Конфигурации (Ь, В) и (Ь', В') метрически конгруэнтны тогда и только тогда, когда dimS dim В' и d{b, B) = d{b, В'),

Доказательство, а) Сформулированные условия, очевидно, необходимы. Пусть они выполнены. Обозначим через М, М' направляющие В, В' соответственно и выберем линейный автомор- физм g: LL, для которого g{M)=M. Если беВ и Ь'е В^, построим аффинное отображение /: Л->-Л с условиями D/ = g й f{b) = b. Очевидно, /(6 + 0 = так что f(B) = B.

Если b фВ и Ь' ф.В', наложим на g дополнительные условиЯу Выберем по точке аеВ, а' еВ я потребуем, чтобы g переводил вектор b - а в вектор Ь' - а'. Оба вектора ненулевые и лежат вне М, М' соответственно, поэтому стандартная конструкция, исходящая из базисов L вида {базис М, b - а, дополнение} и

{базис М', b - а', дополнение}, показывает сунхествование g. После этого снова построим аффинное отображение /: Л->-Л с Df==g и l{b) = b. Проверим, что f{B) = B. В самом деле, прежде всего, Ца) = а', потому что

f{a) = f{b-{b-a)) = f{b)-g(b-a) = b-{b-a)a.

Далее, f{а-\-1) = f(а)g(1), и условие 1тМ равносильно условию g{l)M, так что f(B) = B.

б) Необходимость условия снова очевидна. Для доказательства достаточности подчиним выборы, сделанные в предыдущем рассуждении, дополнительным требованиям. Прежде всего, отождествим Л с L, выбрав начало координат в В. Тогда В отождествится с М, b станет некоторым вектором в L. Пусть а - ортогональная проекция b на М. В линейном варианте мы уже знаем, что d{b, B) = \b - а\. Аналогично определим точку а' на М' или в нашем отождествлении на В\ В качестве g возьмем изометрию L, переводящую М в М' и b в Ь'. Она существует: дополним ортонормированные базисы в М и М' соответственно до ортонормиро-ванных базисов в L, содержащих {b - a)/\b - а\ и (Ь' - а')/ /\Ь - а\, и определим g как изометрию, переводящую первый базис во второй. После этого аффинное отображение f: Л->Л с Df = g и f{b) = b будет движением, переводящим (Ь, В) в (Ь', В').

16. Рассмотрим, наконец, конфигурации, состоящие из двух подпространств Вь Вг- Полная классификация их с точностью до аффинной конгруэнтности может быть нроведена с помощью соответствующего результата для линейных подпространств, доказанного в п. 5 § 5 ч. 1. Полная метрическая классификация довольно громоздка: она требует рассмотрения расстояния между Bi и Вг и серии углов. Мы ограничимся обсуждением единственного метрического инварианта - расстояния, которое, как обычно, определим формулой

d(Bu B2) = inf{6i-62llbieB ЬгВг}.

Назовем общим перпендикуляром к Bi, Вг такую пару точек 6ieBi, biBi, что вектор Ьх - 6г ортогонален к направляющим Bi и Вг. (Точнее было бы называть общим перпендикуляром отрезок {if6,-f (1 -0b20<if< 1}.)

17, Предложение, а) Общий перпендикуляр к Bi и Вч всегда существует. Множество общих перпендикуляров биективно пересечению направляющих By и Вч.

б) Расстояние между В] и Вг равно длине любого общего перпендикуляра \bi - 621 к ним.

Доказательство, aj Пусть Ми Мг - направляющие Bi и Вг и пусть Ь[ G Bp b s Bj. Спроектируем вектор b[ - b2 ортогонально на Ml -f Мг и представим проекцию в виде nii -\- т^, mi е S Mi. Положим 6, i=6, -/Пр б2 = 2 + 2- Очевидно, b.eBiZ

6, 6 = 6; - 6; - (m, + /712) е (М, -Ь Мг) Значит, {bi, bz} есть общий перпендикуляр к В Bj. 210

Пусть 62} и {Ь\, Ь') - авя общих перпендикуляра.Тогда by - Ь[е М^, 62 - К^- и, кроме того,

6, -Ь,е{М, + М,у, Ь\ - 6; е (М, + Al2)-L.

Значит, разность (6, - 6{) - (bg - b), лежит одновременно в + 4-Мг и (Mi + a). Поэтому она равна нулю. Следовательно, 6, - Ь[ = Ь. - Ь' е М, П 12- Наоборот, если [by, 62} - фиксированный общий перпендикуляр и га е П Л^г, то {61 -Ь га, 62 + i} тоже является общим перпендикуляром. Это завершает доказательство первой части предложения.

б) Пусть (Ьь 62} -общий перпендикуляр к В Bg и bl i, Ь'еВ - любая другая пара точек. Достаточно доказать, что

6, - ftjlli ~~2- самом деле,

Ъ\-ь;={Ь,-Ь,) + {Ь\-Ь,) + {Ь, - Ь',).

Но {Ь\ - 6,) -Ь (6.2 - 62) + Ig, а вектор bi - 62 ортогонален Ml 4- М2. Значит, по теореме Пифагора

\b-b\f = \b-b,f + \b-b, + b2-b,fb,-b,\\

что завершает доказательство.

Установим в заключение один полезный результат, характеризующий аффинные подпространства.

18. Предложение. Подмножество ScA является аффинным подпространством тогда и только тогда, когда вместе с любыми двумя точками s, teS оно содержит всю прямую, проходящую через эти точки, т. е. их аффинную оболочку.

Доказательство. Прямая, проходящая через точки s, ife5, - это множество {xs-\-{l-x)t хеЖ}. Поэтому необходимость условия следует из предложения п. 9. Наоборот, пусть оно выполнено. Поскольку в силу того же предложения аффинная оболочка S состоит из всевозможных барицентрических комбинаций

п

точек S, мы должны проверить, что такие комбинации Е iSi лежат в S. Проведем индукцию по п. При п = 1, 2 результат очевиден. Пусть и > 2 и для меньших значений п результат доказан.

Представим Yj ii виде

п-2 п

где </1 = Е- л У2 = Хп-1-\- Хп (мы можем считать, что обе эти

п

суммы не равны пулю, иначе Е XiSi е S по индуктивному

предположению). Очевидно,

г=1 /=п-1

п-2 п

X, г-\ X,

Значит, -Si и X! ~Т^ лежат в S, и потому их барицен-

трическая комбинация с коэффициентами t/i, у2 лежит в S. Это завершает доказательство.

УПРАЖНЕНИЯ

1. Назовем t-й медианой системы точек а, Ur.A отрезок, соединяющий точку Oi с центром масс остальных точек {с1,Цф1}. Доказать, что все медианы пересекаются в одной точке -центре масс Сь .., а„.

2. Угол между двумя прямыми в евклидовом аффинном пространстве А - это угол между их направляющими. Доказать, что две конфигурации из двух прямых в А метрически конгруэнтны тогда и только тогда, когда углы и расстояния между прямыми в обеих конфигурациях совпадают.

3. Угол между прямой и аффинным подпространством размерности > 1 - это угол между направляющей прямой и ее проекцией на направляющую подпространства. Пользуясь этим определением, обобщить результат упражнения 2 на конфигурации, состоящие из прямой и подпространства.

§ 4. Выпуклые многогранники и линейное программирование

1. Постановка задачи. Основная задача линейного программирования ставится следующим образом. Дано конечномерное аффинное пространство А над полем вещественных чисел R и m + 1 аффинно линейных функций /ь ..., f: Требуется отыскать точку (или точки) а е Л, удовлетворяющие условиям fj (а) О, ...

/ш(а)0, для которых функция f принимает наибольшее возможное значение при этих ограничениях.

Вариант, в котором некоторые из неравенств направлены в обратную сторону, fi{a) О, и/или требуется отыскать точки, в которых f принимает наименьшее возможное значение, сводится к предыдущему случаю заменой знака соответствующих функций. Условие /,(а) = 0 равносильно совокупности условий А(а)0 и -f((fl) 0. Все функции fi можно считать непостоянными.

2. Мотивировка. Рассмотрим следующую математическую модель производства. Пусть имеется предприятие, использующее т видов различных ресурсов и производящее п видов различных продуктов. Ресурсы и продукты измеряются в своих единицах неотрицательными вещественными числами (случай, когда это целые числа, например, количество штук автомобилей, мы не рассматриваем; при больших объемах производства и потребления ресурсов он хорошо аппроксимируется непрерывной моделью).

План производства - это вектор {Ху, jt )eR , указывающий количество Х/ у'-го продукта, которое необходимо произвести. Принимается следующая линейная модель потребления ресурсов:

если на производство единицы /-го продукта расходуется количество щ/ единиц /-Г0 ресурса, то для выполнения плана (х\,. ..,Хп)

п

Требуется Е iXj единиц i-ro ресурса. Ресурсы, отпускаемые предприятию, определяются вектором {by, bm): дается bi единиц t-ro ресурса. Следовательно, план (хи Хп) выполним, только если выполняется система ограничений

fl {xi.....Xn) = bi - aijXj > О,

/= 1, .... т.

Мы будем всегда считать, что эти неравенства совместны.

Предположим, что предприятие реализует выпущенную им продукцию по цене d за единицу i-ro продукта. Тогда прибыль от реализации произведенного продукта будет равна

п

f{Xi.....Х„)=(1Х{.

План производства {xi, .... х„) называется оптимальным по прибыли, если f{x) достигает наибольшего возможного значения при ограничениях 0, XiO (г = 1, п) (последнее условие означает, что предприятие не добывает производимых им продуктов на стороне - для продажи или для запчастей).

Мы видим, что задача составления оптимального плана является частным случаем задачи, сформулированной в п. 1.

Разумеется, практические приложения линейного программирования связаны с разработкой конкретных алгоритмов отыскания оптимального плана, которые можно применять вручную или на ЭВМ. Мы ограничимся в этом параграфе изложением геометрических аспектов задачи, лежащих, конечно, в основе всех алгоритмов.

3. Основные геометрические понятия. Фиксируем конечномерное аффинное пространство А над полем R. Буквы / с индексами будут обозначать аффинно линейные функции на А.

Полупространством называется множество точек вида {а е еЛ/(а)0}, где /-непостоянная аффинно линейная функция. Многогранником называется пересечение конечного числа полупространств.

Напомним, что подмножество 5с:Л выпуклое, если из Qi, agsS и Oxl следует, что кау-\-{I - х)а2е S. Поскольку f{xai-\--х)ai) = xf(ау)-\-{{ - х)f(ai), все полупространства выпуклы. Так как пересечение любого семейства выпуклых множеств выпуклое, все многогранники вьшуклые. Мы будем говорить, что любая точка хау +(1 -х)а2, О <; х <: 1, является внутренней точкой отрезка с концами а, и ai.

Пусть S - выпуклое множество. Выпуклое подмножество TczS называется гранью S, если любой отрезок с концами в S, некоторая внутренняя точка которого лежит в Т, целиком лежит в Т.

Все множество S является своею гранью. Грань S, состоящая из одной точки, называется вершиной S. Читателю следует представить себе куб, октаэдр и многогранный угол в трехмерном пространстве, чтобы иметь наглядную картину основной ситуации, важной для линейного программирования. Грани этих фигур в смысле нашего определения - это грани, ребра и вершины школьной геометрии плюс сама фигура. Вершины шара - это все точки его поверхности.

Важнейший результат этого параграфа будет состоять в том, что максимум аффинно линейной функции на ограниченном многограннике (в приложениях этот случай наиболее распространен) достигается на одной из его вершин; последних конечное число. Но прежде нам придется разобраться в структуре многогранников и их граней подробнее.

4. Лемма. Пересечение семейства граней и грань грани выпуклого множества S является гранью S.

Доказательство, а) Пусть Г= []Т Г, -грани S. Любой отрезок с концами в S, внутренняя точка которого принадлежит Ti, целиком лежит в Tt. Значит, если его внутренняя точка лежит в Т, то он лежит в Т.

б) Пусть T\CzTczS, Т - грань S. Любой отрезок с концами в S, внутреняя точка которого лежит в Ti, целиком лежит в Т, ибо Т -грань S, значит, его концы лежат в Г и потому ои целиком лежит в Ti, ибо Ту - грань Т.

5. Лемма. Пусть S - многогранник, заданный неравенствами

т. Тогда для любого i многогранник Sj = = Sn {flfi(fl) = 0} либо пуст, либо является гранью S.

Доказательство. Пусть 5,- непуст, а- г S и внутренняя точка отрезка хау- х)ач лежит в St. Функция fi(xay-\--х)а9), О X 1, линейна по х, обращается в нуль для некоторого О < дсо < 1 и, кроме того, неотрицательна при л: = О и ж= 1. Поэтому она тождественно равна нулю, так что весь отрезок лежит в Si.

6. Лемма. Непостоянная аффинно линейная функция f на многограннике S= {a\fi(a)0} не может принимать максимальное значение в точке о е 5. для которой все fi{a) > 0.

Доказательство. Так как f непостоянна, Df Ф 0. Выберем в векторном пространстве L, ассоциированном с Л, всГктор

L для которого Df{l)0. А'ожно считать, что Df(l)> О, изменив знак I в случае нужды. Если число е > О достаточно мало и aeS, то f,(a-be/)>0 для всех г= 1, т: достаточно взять

е < т\п-щ^щу- Поэтому а Ц- е/е S для таких е. Но f{a + бО =

= f{)4-eZ)f(0 > f(fl), так что f(o) не является максимальным значением f.

Теперь мы можем доказать наш основной результат.

7. Теорема. Предположим, что аффинно линейная функция f ограничена сверху на многограннике S. Тогда она принимает свое максимальное значение во всех точках некоторой грани S, являю-