1611141258-ba3f4d18d0dc46f5f4fb0d4ab6cc4e12 (824991), страница 49
Текст из файла (страница 49)
По теореме 2 множество М (очевидно, что оно замкнуто) может быть задано линейными неравенствами. Следовательно, М=(рЕ В:У(р)) 0 Ч7 ЕМ*) =(рЕ В:у(р))0 при 1=1,..., т). Таким образом, М вЂ” выпуклый многогранник. П Определение 7. Гранью выпуклого многогранника М называется всякое непустое пересечение этого многогранника с некоторым числом его опорных гиперплоскостей.
(Сам многогранник М также считается своей гранью как пересечение с пустым множеством опорных гиперплоскостей.) 'г(ульмерная грань называется вершиной, одномерная — ребром, (и — 1)-мерная (где п = б1ща((М) — гингргранью. Пусть многогранник М задан формулой (9). Следующая теорема показывает, что для нахождения его граней можно ограничиться рассмотрением гиперплоскостей Н,..., Н . Теорема б. Всякая грань Г многогранника М имеет вид Г=Ма(Д Н,), (10) тьч где,7 с (1,..., т). Доказательство. Положим Пусть Г' — грань многогранника М. ,У = ((: Г' с Н~ ) с (1,..., т). Для каждого Е ф,7 существует такая точка р,.
Е Г', что 1;.(р,.) >О. Пусть р — центр тяжести системы этих точек. Тогда Яр) > 0 при всех т' ф,7. Определим теперь грань Г по формуле (10) и докажем, что Г'=Г. Ясно, что Г'с Г и что точка р является внутренней точкой грани Г. Следовательно, всякая опорная гиперплоскость, проходящая через р, содержит Г. Значит, Г'= Г. П 27! $2. ВЫПУКЛЫЕ МНОЖЕСТВА Таким образом, если выпуклый многогранник задан системой линейных неравенств, то его грани получаются заменой части этих неравенств равенствами (но так, чтобы при этом получилось непустое множество). Нужно, однако, иметь в виду, что на определенной таким образом грани некоторые другие неравенства могут автоматически обращаться в равенства.
ПРИМЕР 3. Грани и-мерного параллелепипеда, задаваемого неравенствами 0 < х; < 1 (з' =1,..., и), выделяются тем, что некоторые координаты равны 0 или 1. В частности, вершины — это точки, все координаты которых равны 0 или 1. ЗАЛАЧА 2. Найти грани сечения и-мерного параллелепипеда 0< х, < 1 (з =1,..., и) гиперплоскостью х, +...+ х„= —. ЗАДАНА 3. Найти грани и-мерного симплекса. ЗАдАчА 4. Доказать, что всякая грань многогранника соптг (ры..., Р,) есть выпуклая оболочка некоторых из точек р„,р, Изучение комбинаторного строения выпуклых многогранников — это увлекательная и важная область математики.
Вот два примера результатов нз этой области. 1. Назовем Г.вектором и-мерного ограниченного выпуклого многогранника по. следовательность (ао, а„..., а„~), где а — число й-мерных граней этого многогранника. Каковы необходимые и достаточные условия для того, чтобы данная последовательность и натуральных чисел была у-вектором некоторого и-мерного многогранника? При и = 3 это следующие условия (глаорема Шжайкяца); 2а ао — о1 ч.аз =2, 4 < оп, аз К <зь.
В общем случае ответ неизвестен. 2. Назовем вершины р и 4 выпуклого многогранника смежными, если отрезок рт является ребром этого многогранника. Легко видеть, что единственным 3-мерным выпуклым многогранником, у которого любые две вершины смежны, является тетраэдр. Совершенно иная ситуация в 4-мерном пространстве. Как показал Д.
Гейл, там существуют выпуклые многогранники с любым числом вершин, у которых любые две вершины смежные. Например, пусть М вЂ” выпуклая оболочка точек где ты..., Гн — Различные вещественные числа, Тогда 1) каждая из точек р, является вершиной многогранника М (и это все его вершины: см. задачу 4); 2) каждый из отрезков р,р. (4 та у) является ребром многогранника м. Докажите это самостоятельно. Предложение 6. Крайние точки вьгпуклого многогранника М вЂ” это в точности его вершины. Доказательство. Если точка р является внутренней точкой отрезка, целиком лежащего в М, то любая опорная гиперплоскость, проходящая через р, содержит этот отрезок и, следовательно, р не может быть вершиной.
Обратно, если точка р не является 272 Гл. 7. АФФинные и пРОектиВные пРОстРАнстВА вершиной, то она является внутренней точкой некоторой грани положительной размерности и, значит, не может быть крайней точкой. П Важнейшие применения выпуклых многогранников вне матема- тики связаны с линейным программированием. Основная задача линейного программирования формулируется таким образом: найти максимум (минимум) заданной аффинно-линейной функции на за- данном выпуклом многограннике. Очевидно, что задача о минимуме функции Г равносильна задаче о максимуме функции -г'; поэтому можно говорить только об одной из этих задач. В основе линейного программирования лежит следуюшая Теорема 6. Максимум аффинно-линейной функ|(ии,г' на огра- ниченном вь|пуклом многограннике М достигается в одной из его вершин.
Д о к а з а т е л ь с т в о. Согласно теореме 3 и предложению б, каждая точка р многогранника М представляется в виде выпуклой линейной комбинации его вершин р„..., р„: р= )" Л,р„~ Л! =1, Л! >О (т' =1,..., Ь). ! =! В силу предложения 1.2 ,г(р) = 2,' Л,~(р,) < шахУ(р,), ! =1 откуда и следует утверждение теоремы. С| Приведем два примера ситуаций, в которых возникает задача линейного программирования. ПРимЕР 4 (задача о получении максимальной прибыли). Не- которое предприятие располагает ресурсами Р„ ..., Р в количест- ве Ь„ ..., Ь„ соответственно и планирует произвести продукцию типов П„ ..., П„ в количестве х„ ...,х„ соответственно.
Пусть а, — количество ресурса Р!, нужное для производства единицы продукции П,, и с, — цена единицы продукции П . Очевидно, что должны выполняться неравенства 2,а,х,<Ь, (т=1,...,гп), хт)0 (З'=1,,п). !'= ! Они задают некоторый выпуклый многогранник М в и-мерном про- странстве с координатами х„..., х„. Для получения максимальной прибыли нужно выбрать точку (х„..., х„) Е М, в которой линейная фУнкциЯ 2 с,.хт (цена пРоизведенной пРодУкции) максимальна. |=! $3. АФФИННЫЕ ПРЕОБРАЗОВАНИЯ И ДВИЖЕНИЯ 273 П Ример 5 (транспортная задача). Имеются поставщики А„..., ..., А„, располагающие неким продуктом в количестве а„..., а„ соответственно, и потребители В„..., В„, которые должны получить этот продукт в количестве Ь„..., Ь„соответственно, причем 2„а, = 2; Ь,.
Пусть х„— количество продукта, которое предпола~=! ! ! гается доставить от А, к В,, и сп — стоимость доставки единицы продукта от А, к В,. Должны вйполняться условия !'=! =! Они задают некоторый выпуклый многогранник в тп-мерном пространстве с координатами х„ (( = 1,..., гп, ~' = 1, ,и), Задача состоит в минимизации линеййой у=пах функции 2 саха (обшей стоимости Р, с! перевозки) на этом многограннике. Основной метод решения задачи линейного программирования, на- Р зываемый симплекс-методом, со- 2 стоит в движении по ребрам многогранника М в направлении возрастания функции 7' до тех пор, пока это возможно.
Движение заканчивается в одной из вершин, в которых достигается максимум функции У (см. рис. 9). В 3. Аффинные преобразования и движения Пусть В и Я' — аффинные пространства, ассоциированные с векторными пространствами Ъ' и Ъ" соответственно (над одним и тем же полем). Определение 1. Аффинмым отображением пространства В в пространство о' называется всякое отображение У: Я вЂ” о', обладающее свойством 7(р+х) =7(р)+ у(х) (р Е л! х Е Ъ'), (11) где !р — некоторое линейное отображение пространства У в пространство Ъ". В частности, аффинно-линейные функции, определенные в В 1— это не что иное, как аффинные отображения пространства Я в поле К, рассматриваемое как аффинная прямая.
274 Гл. 7. АФФИННЫЕ И ПРОЕКТИВНЪ|Е ПРОСТРАНСТВА Из (11) вытекает, что ~р(рд) = 7(р)7(д) (р, д Е Я) (12) Тем самым линейное отображение |Р однозначно определяется по )'. Оно называется дифференциалом отображения У и обозначается через ЫУ. Векторизуем пространства Я и Я', приняв за начала отсчета какие-то точки о и о' соответственно. Полагая в (11) р = о, мы получаем следую|нее представление аффинного отображения 7 в векторизованной форме: /(х) = |с(х) + Ь (Ь Е У'), (13) где Ь = о'7(о).
Отсюда, в свою очередь, получается запись отображениями в координатах: у,. = 2, а,х, + Ь,. (4 = 1,..., гп), (14) |=! где х„ ...,х„ — координаты точки х, а у„ ..., у„ — координаты точки у=Их). Обратно, как легко проверить, для любого линейного отображения ~р: Ъ'- Ъ"' и любого вектора Ь Е У' отображение, определяемое формулой (13), аффинно и его дифференциал равен ~р. Пусть Я" — е|це одно аффинное пространство и д: Я'- Я"— аффинное отображение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
