Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 35
Текст из файла (страница 35)
10. Исследовать возможность обобщения теорем 5А и 6.1, 6.2 иа случай задач (1.5), (1А5). 11. Требуется составить наиболее дешевую смесь, содержащую зе кексе Ь' единиц <-го вещества (» = 1, ..., »и) при условии, что для изготовления смеси имеется и видов продуктов, причем в одной единице рго продукта содержится аы единиц <-го вещества, а цена одной единицы 1-го продукта равна с» рублей (задача о смесях). Сформулировать зту задачу в виде аадачи (1.15). Глава 4 ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Прежде чом переходить к рассмотрению задач, болев сложных, чем задачи линейного программировании, остановимся на злементах выпуклого анализа — области математики, в которой изучеютск свойства выпуклых множеств и выпуклых функций, и которан играет фундаментальную роль н теории и методах решения зкстремзльных задач Н, 2, 7, 8, 11, 12, 15 — 19, 21, 24, 33, 41, 52, 66, 67, 92, 132, 137, 144, 146, 156, 186, 167, 195, 197, 255, 264, 283, 290, 321, 337, 338, 34Ц.
9 1. Выпуклые множества 1. Начнем с рассмотрения конкретных примеров выпуклых множеств. Сначала напомним О п р е д е л е н и е. 1. Множество У называется вы рклыж, если для любых и, и ж с7 точка и„= и+ а(и — и) = ии+ +(1 — сс) и принадлежит г7 при всех и (О < а < 1). Иначе говоря, множество У выпукло, если отрезок [и, и) = (и«. 'Ис = и+ 0 + а(и — п), 0 < а(1), соединяющий любые две точки и, и иа (7, целиком лежит в с7 (рис. 4.1).
Все пространство Е', очевидно, з образует выпуклое множество, Пу- стое множество и множество, состо- Р .41 Рис. ящее из одной точки, удобно считать выпуклыми. Тогда из определения 1 непосредственно следует, что пересечение любого числа выпуклых множеств является выпуклым множеством. Приведем другие примеры выпуклых множеств. Пример 1. Шар Я(и„В)=(п1 и ж Е, 1и — пе! ~И (1) радиуса В > 0 с центром в точке и, является выпуклым множеством.
В самом деле, если и, иенЯ(ию В), то, пользуясь нера- Вьшуклыв мнОжестВА 149 венством треугольника, имеем )аи+(1 — а)и — и,~ = ~а(и — и,)+(1 — а) (и — и,)»»( ~ а)и — и,! +(1 — а) )и — и,! (аЕ+(1 — а)Е =Е, т. е. и„= аи + (1 — а) и»и Я (и„В) для всех а ж [О, 11 Пример 2. Гипврплоспостью в Е" называется множество Г=Г(с, () (и: и~Е", <с, и>=(), (2) где с = (с„ ..., с„)Ф 0 — вектор из Е", ( — действительное число. Это множество всегда непусто: если, например, с, Ф О, то точка и, с координатами и' "(/с», и»= 0 (1=1, ..., и, Хчь») удовлетворяет равенству <с, и,> = (, т. е.
и,~ Г. Если и, — какая-либо точка из Г, т. е. <с, и,>= (, то гиперплоскость Г можно представить в виде Г = Г(с, и,) =(и: и ж Е", <с, и — и,>= 0). Напоминаем, что два вектора о, Ь жЕ", называются ортозональными, если <а, Ь>= О. Предыдущее представление для Г означает, что гиперплоскость состоит из тех и только тех точек и, для которых вектор и — и, ортогонален вектору с.
Вектор с называют нормальным вектором гиперплоскости Г. Возьмем произвольные точки и, иж Г, т. е. <с, и>=<с, и>= (. Тогда <с, аи+(1 — а)и>=а<с, и>+(1 — а)<с, и>='( при всех а»п О, 1). Следовательно, à — выпуклое множество. ример 3. Пусть Г=(и: <с, и>=() — некоторая гиперплоскость. Тогда множества Г+=(и: <с, и»(), Г (и: <с, и><'() называются отнрь»тыми полупространствами, а множества Г+ =(и: <с, и» (), Г =(и: <с, и>( () называются замкнутыми полупространствами. Нетрудно видеть, что Г+, Г, Г+, à — выпуклые множества. Например, если и, и»в Г+, то <с, аи+(1 — а)и>= сс<с, и>+(1 — а)<с, и»а(+ +(1 — а) ( "( для всех а»и [О, Ц.
Пример 4. Множество ЛХ, =(и»вЕ": и=асс+(1 — а)и =и+а(ги — и), ажЮ называется пр мой, проходящей через точки и, ю, и Ф ю. Прямую в Е» можно задать также и в виде ЛХ, =(и»и Е": и и+ г»(, Г ~ К), где вектор»(чь 0 называют направляющ м вектором прямой, и — фиксированная точка из Е". Множество ЛХ,+ = (иеп Е": и= и+ г»(, 1~~0) называют лучом, выходящим из точки и в направлении вектора»ге" О. Нетрудно видеть, что прямая и луч — выпуклые множества. Пример 5. Важным примером выпуклого множества являются аффинные множества (или линейные многообразия). Определение 2. Множество ЛХ из Е" называется аффинным, если аи+(1 — а)и»вЛХ при всех и, и»нЛХ, аж К, т. е.
ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА !ГЛ. А прямая, проходящая через любые две точки и, г»н М, целиком лежит в М. Все пространство Е" является аффинным множеством. Пустое множество и множество, состоящее из одной точки, удобно считать аффинными. Любое подпространство пространства Е" представляет собой аффинное множество. Множество М = Х + им получаемое сдвигом подпространства Х, на пропзвольный фиксированный вектор ип также является аффинным. Верно и обратное: всякое аффинное множество М может быть получено сдвигом некоторого подпространства Е на некоторый вектор и,. В самом деле, возьмем произвольную точку и» ж М и положим Е = М вЂ” и,.
Ясно, что Х вЂ” аффинное множество, причем 0 ш Х. Тогда для каждого и ш Х имеем»хи = с»и+ +(1 — а) 0 ш Е при всех а ш К. Кроме того, если и, »» ш Х, то (и+ г)/2 = и/2+(1 — 1/2)»» ж Х и, следовательно, и+ и 2((и+»»)/2)»и Х. Таким обрааом, сумма двух векторов из Е и произведение вектора из Е на любое число принадлежат Х, т. е.
Х вЂ” подпространство. Убедимся, что подпространство Е = М вЂ” и» не зависит ог выбора точки и, ш М. В самом деле, пусть Х,» М вЂ” и„где и, »и М. Возьмем любую точку и ~ Х. Поскольку и, — и, »и Х, то и+(и,— и,)~Х и, следовательно, ишХ вЂ” (и» вЂ” и,) (Х+ и,)— — и» = М вЂ” и» = Х,. Это значит, что Е ~ Х». Обратное включение Х, ~ Е доказывается совершенно так же. Следовательно, Х» =Х. Таким образом, всякое аффинное множество М из Е" представимо в виде М вЂ” Х,+и„ (3) где Х вЂ” подпространство, однозначно определяемое множеством М, и» вЂ” произвольная точка из М. Подпространство из етого представления называют параллельным аффинному множеству М. Опираясь на полученное представление (3), можно дать алгебраическое описание аффинных множеств из Е".
Как известно из линейной алгебры (93, 164], всякое подпространство Х из Е" представимо в виде Х =(и шЕ": Аи = 0)=(и»и Е' <а„и>= О, » =1, ..., т), где А — некоторая матрица размера т Х и, ໠— »чя строка матрицы А (например, в качестве векторов а» (» = 1, ..., я») можно взять базис ортогонального дополнения к Х в Е"). Отсюда и из (3) следует, что всякое аффинное множество из Е" может быть задано в виде М (Е~Е": Ап О)+и»=(пшЕ™' и но+»», Аэ=0) = =(и»н Е": А (и — и ) = 0)=(и»и Е": Аи = Ы= (и»вЕ": <ае и> Ь„( 1, ..., и)» (4) где Ь = Аи, =(Ь', ..., Ь"). Нетрудно проверить, что верно и обратное: всякое множество вида (4) является аффинным, В са- ВЫПУКЛЫЕ МНОЖЕСТВА мои деле, если и, о 1и М, т.
е. Аи = Ь, Ао= Ь, то А(аи+ +(1 — а) о) = аАи+(1 — а)АУ = Ь или, иначе, аи+(1 — а) ош ш М при всех а 1и К. Таким образом, множества вида (4) и только они являются аффиннымн. Согласно теореме Кронекера — Капелли 193, 1641 множество (4) непусто тогда н только тогда, когда матрица А и расширенная матрица В =(А, Ь) имеют один и тот же ранг.
Если гапд А ( гав3 В (например, А = О, Ь чь 0), то М вЂ” И. Если А = О, Ь = О, то М = Е". Рассмотрим случай А ~ О, гапй А ™ =гапйВ г. Тогда множество (4) состоит из тех и только тех точек, которые представимы в виде [93, 164] и = из+ ~ 11и1, (5) где и, — какое-либо частное решение неоднородной системы линейных алгебраических уравнений Аи = Ь, а и„..., и„, — линейно независимые решения однородной системы Аи = 0; )о ...
)„,— действительные числа. Векторы и„..., и„, обраау ют базис подпространства и-т 1-! З":А -О!-) Я! — Ь'1ьЬ 1), 1=1 так что размерность 5 равна и — г. С помощью введенного подпространства Ь равенство (5) можно переписать в виде М = и, + Š— мы снова пришли к представлению (3). Размерность аффиннозо множества М по определению при пинается равной размерности подпространства Е, параллельного М. Таким образом, размерность аффинного множества (4) равна и — г, где г гап3 А = гавй В. Аффинное множество размерности р часто называют зиперплоскостью размерности р. В тех случаях, когда нужно подчеркнуть размерность р аффинного множества М и соответствующего параллельного подпроства 5, будем писать М„Е,.
В частности, если в (4), (5) г и, то Е, =(0) и М, =(и,) состоит иэ одной точки. Если г = и — 1, то М, =(и ш Е": и = и, + )ио ) ш К) — прямая (см. пример 4). Далее, гиперплоскость (2) также является аффинным множеством: в этом случае в (4) нужно принять А с, Ь = ). Поскольку с чь О, то гана А = гапй(А, Ь) 1 и, следовательно, гиперплоскость имеет размерность и — 1. Согласно (5) тогда Г = ь-1 =М 1= иееЕ": и=и,+ ~11и1,11енК, где и„..., и„,— 1 1 базис параллельного подпространства Е„1= (и1нЕ": <с, и> = 0).
Как видим, вектор с ортогонален к Е„, и является базисом ортогонального дополнения к 5 1 до Е", а векторы и„..., и. „ с образуют базис в Е". (ГЛ. А <52 ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Заметим, что пересечение любого числа аффинных множеств само является аффинным множеством и, следовательно, представимо в виде (4). О и р е д е л е н и е 3. Пересечение всех аффинных множеств, содержащих множество У из Е", называется аффинной оболочкой множества У и обозначается через аН У; подпространство Ь, параллельное аН У, называется несущим подпространством множества У и обозначается через Ьш У.
Таким образом, аН У представляет собой минимальное аффинное множество, содержащее У. Пользуясь (3) — (5), нетрудно показать, что: 1) аН У= и,+ГАПУ, где и,— произвольная точка из У; 2) если 0 <н У, то аН У = Ьш У; 3) и = о — юж ЬшУ для всех о, ш<и аНУ, в частности, для и, ю<и У; 4) осли с<и1(ПУ, о<каНУ, то и=о+есшаНУ прн всех е <иК. Определение 4. Размерностью произвольного мнозсества У из Е" называется размерность его аффинной оболочки; размерность множества У обозначают дйш У. Согласно этому определению отрезок (и, о) =(и„= о+ + а(и — о), 0 < сг < 1), соединяющий две точки и, о <л Е" (и Ф о), имеет размерность 1, так как его аффинной оболочкой является прямая Г =(и<: ю о+»(и — о), — < г < сс).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
