1611141239-59b1d3750d66507674a4c54de8111ebf (824983), страница 49

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 49)

Мы ограничимся обсуждением единственного метрического инварианта — расстояния, которое, как обычно, определим формулой а (Вь Вг) = !П1 (1 Ь! — Ьг ( ~ Ь! е= В~ у Ьг ев Вг). Назовем общим перпендикуляром к Вь Вг такую пару точек 6| еяВь Ьг~Вм что вектор Ь| — Ьг ортогонален к направляющим В, и Вг. (Точнее было бы называть общим перпендикуляром отрезок (! Ь| + (1 — 1) Ьг ~ б ( 1 = 1) . ) !7. Предложение. а) Общий перпендикуляр к В, и В, всегда существует. Множество общих перпендикуляров биекгивно пересечению направляющих В~ и Вь б) Расстояние между В~ и Вг равно длине любого общего перпендикуляра ~6~ — Ьг~ к ним. Доказательство, а! Пусть Мь Мг — направляющие В, и Вг и пусть Ь', е= В„Ь'ея В.

Спроектируем вектор Ь', — Ь; ортогонально на И~+ Мг н представим проекцию в виде а+ те, т, яв еяМь Положим Ь, ' Ь',— т„6,=6,'+т,. Очевидно, Ь,ев В, н Ь, — Ь, Ь; — Ь; — (т, + т ) ~ (М, + М )х. Значит, (Ьь Ьг) есть общий перпендикуляр к Вь Вг, Пусть (Ь„Ьт) и (Ь;, Ь;) — два общих перпендикуляра.Тогда Ь! — Ь;~ М„Ь, — Ь,'ен М и, кроме того, Ь, — Ь., ~ (М + Мг) х, Ь, — Ь ен (М, + М )х. Значит, разность (Ь, — Ь;) — (Ь, — Ь',), лежит одновременно в М! + +Ма и (М!+Ма)-".

Поэтому она равна нулю. Следовательно, Ь,— Ь;=Ьт — Ь',~ М, ПМт Наоборот, если (Ь|, Ьг) — фиксирован- ный общий перпендикуляр и т~ М!(!Мм то (Ь|+ т, Ьг+ т) тоже является общим церпепдикуляром. Это завершает доказа- тельство первой части предложения. б) Пусть (Ь|, Ьг) — обп1ий перпендикуляр к Во В, н Ь', ~ В„ Ь,'евВ,— любая другая пара точек. Достаточно доказать, что ~!Ь! — Ь ~(~Ь; — Ь;'!. В самом деле, Ь,— Ь,=(Ь, — Ь,)+(Ь, — Ь,)+(Ь,— Ь,). Но (Ь! — Ь,)+(Ьт — Ь,') ен М, +М„а вектор Ь! — Ьт ортогонален М!+ Ма Значит, по теореме Пифагора !Ь! — Ьг 1 ~ Ь! — Ьг ~ + ~ Ь! — Ь! + Ьт — Ьт~~ ~) ~ Ь! — Ьт~~, что завершает доказательство. Установим в заключение один полезный результат, характеризующий аффинные подпространства. !8.

Предложение. Подмножество 5 ~ А является аффинным подпространством тогда и только тогда, когда вместе с любыми двумя точками з, 1ен5 оно содержит всю прямую, проходяи(ую через эти точки, т. е. их аффинную оболочку. Д о к а з а т е л ь с т в о. Прямая, проходящая через точки з, !ен5,— это множество (хг+(! — х)!!х~Л). Поэтому необходимость условия следует из предложения п. 9. Наоборот, пусть оно выполнено. Поскольку в силу того же предложения аффипная оболочка 5 состоит из всевозможных барицентрических комбинаций л точек 5, мь! должны проверить, что такие комбинации ~ х!з! ле! ! жат в 5. Проведем индукцию по и.

При п = 1, 2 результат очевиден. Пусть и ) 2 и для меньших значений и результат доказан. и Представим ~'„х!з! в виде !-! у! ~' — з! + уч ~~~ — зо ! ! !-ь-! где у! —— Х х„ут=х„!+ х„(мы можем считать, что обе эти г=! л суммы не равны пулю, иначе ~ х,з, ~ 5 по индуктивному 311 предположению). Очевидно, л — 3 з Х вЂ” =Х Х1 Ч-~ Х =У1+Уэ= 1 р1 рт 1-1 1-~-1 я-э и Х х Значит, у — зг и у — зг лежат в 5, и потому их бариценр~ р~ 1=1 1-я-1 трическая комбинация с коэффициентами п1, пз лежит в 3. Это завершает доказательство.

УПРАЖНЕНИЯ 1. Назовем 1-й медианой системы точек а, ..., а„,~мА отрезок, соединяюпгий точку сч с центром масс остальных точек (оЯ Ф 1). Доказать, что все лседианы'пересекаются в одной точке — центре масс ап, а,. 2. Угол между двумя прямыми в евклндовом аффинном пространстве А— это угол между их направляющими. Доказать, что две конфигурации из двух прямых в А метрически конгруэитны тогда и только тогда, когда углы в расстояния между прямыми в обеих конфигурациях совпадают.

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

Основная задача линейного программирования ставится следующим образом. Дано копечномерное аффинное пространство А над полем вещественных чисел К и т+ 1 аффинно линейных функций П, ..., ~; ~: А — К Требуется отыскать точку (или точки) а ен Л, удовлетворяющие условиям ~,(а) =» О, ... (а) ) О, для которых функция ( принимает наибольшее возможное значение при этих ограничениях. Вариант, в котором некоторые из неравенств направлены в обратную сторону, Ца) ( О, и/или требуется отыскать точки, в которых ( принимает наименьшее возможное значение, сводится к предыдущему случаю заменой знака соответствующих функций. Условие (1(а)=О равносильно совокупности условий (1(а) ) О и — (1(а) ) О.

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

План производства — это вектор (хь ..., х„)ен зс", указывающий количество 21 /-го продукта, которое необходимо произвести. Принимается следующая линейная модель потребления ресурсов: 212 если на производство единицы 1чго продукта расходуется количество ап единиц Ого ресурса, то для выполнения плана (хь..., х,) требуется ~ а, х~ единиц 1-го ресурса. Ресурсы, отпускаемые пред/ ! приятию, определяются вектором (Ьь ..., Ь ): дается Ь; единиц 1-го ресурса.

Следовательно, план (хь ..., х„) выполним, только если выполняется система ограничений ~~ (хп ..., х„) = Ь, — ~ апхг) О, 1= 1, ..., пь ! 1 Мы будем всегда считать, что эти неравенства совместны. Предположим, что предприятие реализует выпущенную им продукцию по цене с~ за единицу Ьго продукта. Тогда прибыль от реализации произведенного продукта будет равна л )(хо ..., х„)= ~ с,хи 1-1 План производства (хь ..., х„) называется оптимальным по прибыли, если 1(х) достигает наибольшего возможного значения при ограничениях )~ О, х;) 0 (1= 1, ..., п) (последнее условие означает, что предприятие не добывает производимых им продуктов на стороне — для продажи или для запчастей).

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

Основные геометрические понятия. Фиксируем конечномерное аффинное пространство А над полем 11. Буквы 1 с индексами будут обозначать аффинно линейные функции па А. Полупространстеом называется множество точек вида (а ~ еп А !1(а) > О), где !' — непостоянная аффинцо линейная функция. Многогранником называется пересечение конечного числа полупространств. Напомним, что подмножество 5 ~ А выпуклое, если из аь азя5 и 0(х(1 следует, что ха~+(! — х)ахеп5. Поскольку 1(ха, + + (1 — х) аг) = хг (а1 ) + (1 — х) 1(ах), все полупространства выпуклы. Так как пересечение любого семейства выпуклых множеств выпуклое, все многогранники выпуклые. Мы будем говорить, что любая точка ха~+(! — х) ам О ( х ( 1, является внутренней точкой отрезка с концами а, и а,.

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

Важнейший результат этого параграфа будет состоять в том, что максимум аффинно линейной функции на ограниченном многогранннке (в приложениях этот случай наиболее распространен) достигается на одной из его вершин: последних конечное чисчо. Но прежде нам придется разобраться в структуре многогранников и их граней подробнее. 4. Лемма. Пересечение семейства граней и грань грани выггуклого мнозсества 5 является гранью 5. Д о к а з а т е л ь с т в о. а) Пусть Т = ! ! Т,, Тг — грани 5. Любой отрезок с концами в 5, внутренняя точка которого принадлежит Т„целиком лежит в Тг.

Зггачит, если его внутренняя точка лежит в Т, то он лежит в Т. б) Пусть Тг с Тс5, Т вЂ” грань 5. Любой отрезок с концами в 5, внутреняя точка которого лежит в Ть целиком лежит в Т, нбо Т вЂ” грань 5, значит, его копны лежат в Т и потому он целиком лежит в Т„ибо Тг — грань Т. б. Лемма. Пусть 5 — многогранник, 'заданный неравенствами 1~ ) О, г = 1, ..., т. Тогда длЯ любого г' многогРанник 5г —— =5!! (а!)г(а)=0) либо пуст, либо является гранью 5. До к аз а тел ь ство. Пусть 5; непуст, аь а, е= 5 и внутренняя точка отрезка хаг+(1 — х)ат лежит в 5г. Функция (г(хаг+ +(1 — х)аД, 0 ( х ( 1, линейна по х, обращается в нуль для некоторого 0( хо( ! и, кроме того, неотрицательна при х = 0 и х = !.

Поэтому опа тождественно равна нулю, так что весь отрезок лежит в 5ь 6. Лемма. Непостоянная аг1гфинно линейная 4ункцггя 1 на многограннике 5 = (а!)г(а) ) О) не может принимать максилгальное значение в точке и ен 5, для которой все 1г(а) ) О. Доказательство. Так как 1 непостоянна, 01 пи О. Выберем в векторном пространстве (., ассоциированном с Л, вектор 1е- =г., для которого 01(1) 4= О. Можно считать, что 0111) ) О, изменив знак 1 в случае нужды. Если число е ) 0 достаточно мало и а ею 5, то 1г(а+ е1)') О для всех г = 1, ..., т: достаточно взять е<ппп . Поэтому а+г1еи5 для таких е. Но 1(а+е1)= =1(а)+е01(1)~1(а), так что 1(а) не является максимальным значением 1.

Теперь мы можем доказать наш основной результат. 7. Теорема. Предположим, что аграгинно линейная функция ограничена сверху на многограннике 5. Тогда она принимает свое максимальное значение во всех точках некоторой грани 5, являю- 214 щейся также многогранником. Если 5 ограничен, г принимает свое максимальное значение в некоторой вершине 5. Доказательство.

Проведем индукцию по размерности А. Случай б(тА = О очевиден. Пусть йп>А = и и для меньших размерностей теорема доказана. Пусть 5 задан системой неравенств (> ) О, ..., ) ~ О. Так как множество 5 замкнуто, ограниченная сверху функция ) на нем принимает максимальное значение в некоторой точке а. Бели ~>(а) ) О, ..., ) (а) ) О, то по лемме п. 6 ) может быть только константой; в частности свое единственное значение она принимает на всем 5.

Иначе (>(а) = О для некоторого й Это значит, что ) принимает максимальное значение в точке непустого многогранника 5н который является гранью 5 и лежит в аффинном подпространстве (а ~)>(а) = О) размерности и — 1, нбо (> непостоянна. По индуктивному предположению максимальное значение ограничения ( на 5; принимается во всех точках некоторой многогранной грани 5ь По лемме и. 4 она же будет гранью 5. Она будет многогранником, ибо к неравенствам, определяющим ее в 5ь с левыми частями, продолженными на все А, следует добавить равенство г> = О.

Характеристики

Список файлов книги