1611141234-c9398682b029dca593d2e7400e783f93 (824980), страница 64
Текст из файла (страница 64)
Лемма 1. Пересечение семейства граней, и грань грани выпуклого множества 5 явллется гранью 5. Доказательство. а) Пусть Т = ПТо Т, грани Я. Любои отрезок с концами в о', внутренняя точка которого принадлежит Т,, целиком лежит в Ть Значит, если его внутренняя точка лежит в Т, то он лежит в Т. б) Пу.сть Т1 С Т С Я, Т вЂ” грань множества Я. Любой отрезок с концами в 5, внутренняя точка которого лежит в Т„целиком лежит в Т, ибо Т грань Я. Значит, его концы лежат в Т, и потому он целиком лежит в Ты ибо Т1 -" грань грани Т.
П Лемма 2. Пусть 5 — многогранник, заданный неравенствами 11>О, 1=1,,,.,т, Тогда для любого индекса 1 многогранник Я,, = Я П (а ~ (,(а) = О) либо пуст, либо является гранью Я. Доказательство. Пусть Я, непуст, аы аа е Я и внутренняя точка Ла1 + (1 — Л) аг отрезка лежит в Яь Функция ЯЛа1+ (1 — Л)аг),. О < Л < 1, линойна по Л, обрашается в нуль для некоторого О < Ло < 1 и, кроме того, неотрицательна при Л = О и Л = 1. Поэтому она тождественно равна нулю, так что весь отрезок лежит в Яо П Лемма 3. Непостоянная аффинно-линейная функция 1 на многограннике Я = (а ! з',(а) > О; 1 < г < т) не может принимать максимальное значение в точке а ч Я, для которой все 1,(а) > О. Доказательство. Так как 1 непостоянна, то Ру ~ О.
Выберем в векторном пространстве 1г, ассоциированном с А, вектор ч е Е 'н', для которого Р)(ч) ф О. Можно считать, что Ру(и) > О, изменив в случае необходимости вектор и на противоположный. Если число е > О достаточно мало и а Е 5, то 1,(а + еи) > О для всех 1 = 1,...,пн достаточно взять е < ш1п,(1,(а)/~Р1,(ч)~).
Поэтому а + еч Е 5 для таких;.. Но 1(а + еч1 = 1(а) + еР) (и), так что 1(а) не является максимальным значением (. П Теперь мы можем доказать наш основной результат. Теорема. Предположим, что аффинно-линейная функция 1" ограничена сверху на многограннике Я. 320 Гл. 7. Приложения Тогда она принимает свое' максимальное значение во всех то м ках некопеорой грани 5, яв яющейся также многогранником. Если Е ограничен, то 7 принимает свое максимальное значение в некогпорой вершине много~ранника Е. Доказательство. Проведем индукцию по размерности пространства А. Случай с)1п1 А = О очевиден.
Пусть 31п1 А = и, и пусть для меньших размерностей теорема доказана. Пусть многогранник 5 задан системой неравенств 71 > О,...,7ш > О. Так как множество о' замкнуто, то ограниченная сверху функция 7 на нем принимает максимальное значение в некоторой точке а. Если 711а) > > О,..., 7" (а) > О, то по лемме 3 7' может быть только константой;, в частности, свое максимальное значение она принимает на всем 5. Считаем теперь, что Л(а) = О для некоторого 1.
Это значит, что 7 принимает максимальное значение в точке непустого многогранника Ем который является гранью о' и лежит в аффинном подпространстве (а ~ 7',1а) = О) размерности и — 1, ибо 71 непостоянна. По индуктивному предположению максимальное значение ограничения 7 на Ее принимается во всех точках некоторой грани многогранника 5,.
По леммам 1 и 2 она же будет гранью исходного многогранника Е, причем — многогранником, ибо к неравенствам., определяющим ее в Ем с левыми частями, продолженными на все пространство А, следует добавить равенство 71 = О. Теперь индукцией по размерности аффинной оболочки 5 покажем,что у любого ограниченного многогранника обязательно есть вершина.
В самом деле, для размерности нуль зто очевидно. Пусть размерность больше нуля. Мы можем считать, что аффинная оболочка многогранника 5 есть все А. Возьмем любую непостоянную аффинно-линейную функцию на А. Она должна принимать на Е максимальное значение, ибо 5 ограничен и замкну.т. Стало быть, у Е есть непустая грань, во всех точках которой зто значение принимается. Она является ограниченным многогранником, аффинная оболочка которого имеет строго меньшую размерность. По индуктивному предположению у нее есть вершина, являющаяся по лемме 3 также вершиной многогранника 5.
Окончательно, пусть 5 ограничен и Т многогранная грань Е, на которой исходная функция 7 принимает свое максиглальное значение. Тогда любая вершина Т, существование которой доказано, является искомой вершиной многогранника Е. П УНРЛ Ж1ГгсНИЯ 1. Доказать, что всякий ограниченный многогранник является выпуклой оболочкой множества своих вершин. 3. Исцояьзуя унр. 1 и теорему 13 из 1 3 гз. 1, доказать, что максимум яинейной функции на ограниченном многограннике достигается в одной из его вершин.
У 1. Неотрвяагнсльные магнрнны 321 3 4. Неотрицательные матрицы 1. Производственная мотивировка. Следуя [12, 15), изложим задачу планирования производства в достаточно известной экономической модели Леон!ноева!~!. Некий концерн владеет а фабриками Р, 1 < у < п. На фабрике Е производится продукт Р . Для производства единицы продукта Рь нужно использовать а а > 0 единип продукта Р, ! ф й (естественно полагать а = 0).
Для производства хь единиц продукта Рь при й = 1, 2,..., и концерну потребуется в итоге ~„" ! а ьхь единиц продукта Р!. Таким образом, для рынка остается у =х — ~а ьхь ь=! единиц продукта Р,. Задача планирования принимает следующий вид: при заданной рЫНОЧНОй ПОтрЕбНОСтИ у = (у!,...,ун) Е Но С у > 0 НужНО НайтИ вектор производства х = (хг,...,х„) с х > О, удовлетворяющий условию (1). Полагая А = (аль)., мы перепишем (1) в матричной форме; у = (Š— А)х. Теперь мы используем обозначение (2) х ) О, у ) О, А > О для векторов и матриц с неотрицательными вещественными компонентами (коэффициентами), называя их коротко неотрицательными. В случае строгих неравенств говорят о положптаельных векторах и матрицах (не смешивать с положительно определенными матрицами). Воспользуемся теперь элементарными результатами о спектральном радиусе матрицы (или отождествляемого с нею линейного оператора в Кн) из п. 6 9 1.
Если г (А) < 1, то, как следует из примера 3 из 9 1, матрица Š— А обратима, причем (Š— А) ! = 2 )о Аь. Так как матрица А по определению неотрицательна, то неотрицательна любая ее степень Аь, а в таков! случае нсотрицательна и матрица (Š— А) '. Поэтому нужное решение х > О, отвечающее матричному соотношению (1'), дается формулой х = (Š— А) 'у. Условие г(А) < 1 вряд ли интерпретируется в зкономических терминах, но к этому можно прийти, используя неравенство 3) из 9 1, п. 5: е! Василий Васильевич Леонтьен (!900 !999) вынугкник ~егербургского университета, впоследствии профессор Гарвардского университета, крупный окономист,лауреат Нобелевской премии.
щ А.И. Кострикин 322 Гл. 7. Прилолеенил г(А) < шахе 2 " а ы Следовательно, 2„", а ь < 1, к = 1, 2,..., п, является достаточным условием для разрешимости нашей задачи. Это условие уже допускает экономическую интерпретацию. Действительно, ~. азе издержки, которые несут на фабрике Рь при изготовлении единицы продукта Рь.
Требование 2 "' а я < 1 означает, следовательно, что фабрика Рь работает рентабельно. Таким образом, имеет место Теорема 1. Если все фабрики работают рентабельно, то задача планирования разрешима, причем единственным образом. 2. Свойства неотрицательных матриц. Согласно теореме 1 система (1) с матрицей А > О, удовлетворяющей условиям (2), имеет единственное решение при любом у > О, т.е. де1(Š— А) ~ О. Заметим теперь, что с<ли А > О и 1 > Л > О, то матрица ЛА > О удовлетворяет тем же условиям (2), так что с1еЦŠ— ЛА) фО, О< Л < 1. Определитель бес(Š— ЛА) положителен при Л = О и непрерывен по Л, а поэтому он положителен и при Л = 1, т.е.
имеет место Теорема 2. Пусть А = (а ь) ) О и 2 "., а,ь < 1 при к = 1,2,...,и. Тозда деЦŠ— А) > О. Неотрицательные матрицы -- важный и неотъемлемый инструмент исследования в теории игр, комбинаторике, задачах оптимизации, математической экономике (линейное и динамическое программирование), теории вероятностей, в генетике.
Пусть Р матрица, отвечающая некоторой перестановке к Е Яь (см., в частности, упр. 6 в [ВА 1, гл. 2, 3 3)). Например, при и = 3 и и = (1 2 3) имеем О О 1 1 О О О 1 О Понятно, что гР = Р '. Преобразование подобия А ь+ Р 'АР осуществллет перестановку одновременно строк и столбцов матрицы А е ЛХ„(й). О п р е д е л е н и е 1.
Пусть при и > 1 найдется матрица перестановки Р, для которой А11 Аш О Азз где Аы, Аяз квадратные матрицы порядка < и. Тогда А называется приводимой матрицей. Если такой матрицы Р не существует, то А - неприводимая матрица. Понятно, что матрица А > О всегда неприводима, поскольку при любой перестановке ее строк и столбпов угол нулей возникнуть не может. У 4. Неотрицательные матрицы 0 Аьз 0 ... 0 Р 'АР= 0 0 0 ... Аь.ць Аы 0 0 ... 0 где А дчы — и х п ьь-матрица и Аы —. пя х па-,матрица; 5) если а > 0 хотя бы длл одного ь то 1 = 1; 6) если найдется 1 ф- '1 с аоа, > О, то к.
( 2, Доказательство теоремы 3 довольно длинное и здесь не приводится [см. [14, 1о)). 3. Стохастические матрицы. Напомним [см. [ВА 1, гл. 2, 2 3, упр. 4)) следующее Определение 2. Матрица Р = [р,.) е ЛХ„[Щ называется стохастической, если ~ р, = 1, 1 = 1, 2,...,п. 1=1 Р>0, Есчи, кроме того, 2„',1 ро — — 1, у = 1,2,...,п, то матрица Р называется дважды стохастической.
Матрица перестановки - . один из частных видов дважды стохастической матрицы. Теорема 4. Стохастичность неотрицательной, матрацы Р имеет место тогда и только тогда, когда Ре = е для е = [1, 1,... 2р Основным результатом, относящимся к нсприводимым неотрицательным матрицам, является след уюпзая классическая теорема Перрона--Фробениуса [1907-1912), усовершенствованная впоследствии Виландом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
