Е.Б. Винберг - Теория к экзамену, страница 8

Пусть p′ =λ′i pi , p′′ =λ′′i pi - две линейных комбинации точекi=0i=0p0 , p1 , . . . , pk ∈ M (без ограничения общности можно считать, что это линейные комбинации одинакового набораточек). Пусть µ′ , µ′′ > 0, µ′ + µ′′ = 1. Тогда надо доказать, что µ′ p′ + µ′′ p′′ ∈ M.kPНо µ′ p′ + µ′′ p′′ =(µ′ λ′ + µ′′ λ′′ )pi - выпуклая комбинация точек p0 , p1 , . .

. , pk ∈ M. Q.E.D.i=0Def. Совокупность выпуклых линейных комбинаций точек из M называется выпуклой оболочкой множества M .Обозначается conv M. Это наименьшее выпуклое множество, содержащее M .Def. Выпуклая оболочка аффинно независимых точек p0 , p1 , . . . , pk называется k−мерным симплексом, натянутым на p0 , p1 , .

. . , pk . Нульмерный симплекс - это точка, одномерный - это отрезок. Двухмерный симплексназывается треугольником, трёхмерный - тетраэдром.40Полупространства. Выпуклые многогранники, их грани.Грани симплекса и параллелепипеда.Def. Полупространством называется множество, задаваемое линейным неравенством a1 x1 + · · · + + an xn > b,где не все ai = 0. При этом гиперплоскость, задаваемая соответствующим равенством a1 x1 + · · · + an xn = b,называется граничной гиперплоскостью данного полупространства. Полупространство a1 x1 + · · · + an xn 6 bназывается противоположным полупространством.С каждой гиперплоскостью связаны два полупространства.Утверждение.

Полупространство является выпуклым множеством.Доказательство. Линейное неравенство, задающее полупространство, на любой прямой превращается в нера→→+−→венство вида αt + β > 0 (если прямая имеет вид −x =−xa t). Пересечение полупространства с любой прямой0есть либо вся прямая, либо луч, либо оно пусто; то есть в любом случае это выпуклое множество. Значит,полуплоскость является выпуклым множеством. Q.E.D.Def. Выпуклым многогранником называется пересечение конечного числа полупространств.Иначе говоря, выпуклый многогранник есть множество решений системы линейных неравенств: a11 x1 + · · · + a1n xn > b1 ;...am1 x1 + · · · + amn xn > bm .(здесь и все aij могут быть нулями!).Def. Функция вида l(x) = a1 x1 + · · · + an xn + b называется аффинно-линейной функцией (здесь x1 , x2 , .

. . , xn координаты точки x).Можно переписать систему неравенств, задающую выпуклый многогранник: l1 (x) > 0 ;...lm (x) > 0.Def. Гранью выпуклого многогранника M называется любое непустое подмножество Γ ⊂ M , которое можетбыть получено заменой некоторых из неравенств, задающих многогранник M , на равенства.! Может оказаться, что какие-то из оставшихся неравенств выполняются всюду на этой грани как равенства.! Грань грани Γ - это то же самое, что грань многогранника M , содержащаяся в Γ. Таким образом, выпуклыймногогранник сам является своей гранью.Нульмерные грани называются вершинами, одномерные - рёбрами, (dim M − 1)-мерные грани называются гипергранями.25векториз→−−→Грани симплекса.

Рассмотрим симплекс PT , натянутый на репер (p0 ; −p−0 p1 , . . . , p0 pn ).Тогда T = {x = x1 p1 + · · · + x1 p1 : xi > 0, xi = 1}. Значит, неравенства:i = 1, . . . , n; xi > 0nPxi 6 1j=1→−−→задают симплекс T относительно репера (p0 ; −p−0 p1 , . . . , p0 pn ).Грани симплекса T , проходящие через p0 , суть пересечения координатных плоскостей с симплексом. Это будутсимплексы, натянутые на точку p0 и какие-то из точек p1 , p2 , . .

. , pn . Таким образом, все грани симплекса - этосимплексы, натянутые на всевозможные непустые подмножества множества {p0 , p1 , . . . , pn }. Их число 2n+1 − 1.Вершины этих симплексов - это какие-то из вершин исходного симплекса.Грани параллелепипеда. Пусть (e1 , . . . , en ) - базис пространства V . Параллелепипед - это множество()XP (p0 ; e1 , e2 , . . . , en ) = p0 + P (e1 , e2 , . . . , en ) = p0 +xi ei : 0 6 xi 6 1 .iТаким образом, параллелепипед задаётся неравенствами: 0 6 xi 6 1 (i = 1, . .

. , n).Найдем его грани. С точностью до нумерации координат, всякая грань размерности k задаётся соотношениями:0 6 xi 6 1, i = 1, . . . , k;xj = εj ,j = k + 1, . . . , n; εj ∈ {0, 1}.Число k−мерных граней равно Cnk · 2n−k . В частности, число вершин равно 2n .41Теорема о том, что всякий ограниченный выпуклыймногогранник есть выпуклая оболочка своих вершин.Задача линейного программирования.Def. Выпуклое множество M ⊂ S называется телесным (или выпуклым телом), если его аффинная оболочкасовпадает со всем пространством: aff M = S.Лемма.

Выпуклое тело содержит внутренние точки.Доказательство. Пусть p0 ∈ M. Тогда aff M = p0 + h−p→0 p : p ∈ M i = S.−→→−−→Значит, rk {p0 p : p ∈ M } = dim S = n ⇒ ∃ p1 , . . . , pn ∈ M, такие, что (−p−0 p1 , . . . , p0 pn ) - базис пространства V .Точки p0 , p1 , . .

. , pn аффинно независимы, и натянутый на них симплекс (в силу выпуклости M ) содержится вM . Но симплекс, очевидно, содержит внутренние точки. Q.E.D.Def. dim M + dim aff M.Всякое выпуклое множество M является телом в aff M. Допуская вольность речи, будем называть внутреннимиточками множества M точки, внутренние по отношению к aff M.Теорема (Минковского-Вейля). Всякий ограниченный выпуклый многогранник M совпадает с выпуклой оболочкой множества своих вершин.Доказательство.

Индукцией по n = dim M.При n = 0 доказывать нечего: M - это точка.Пусть n > 0. Заменив S на aff M , можно считать, что M - телесный выпуклый многогранник. Пусть p - какаялибо внутренняя точка M . Все определяющие M неравенства в точке p выполняются как строгие (иначе в любойокрестности точки p есть точки, в которых какое-либо из неравенств неверно). Проведём через p произвольнуюпрямую l. Её пересечение с M есть ограниченное выпуклое множество - отрезок qr. В точках q и r какие-то изнеравенств выполняются как равенства, значит, эти точки принадлежат собственным граням многогранника M .По предположению индукции, точки q и r принадлежат выпуклой оболочке множества вершин многогранникаM ⇒⇒ значит и qr, и точка p тоже принадлежат этой выпуклой оболочке.

Q.E.D.! На самом деле, верно и обратное (выпуклая оболочка конечного числа точек есть выпуклый многогранник) без доказательства.Задача линейного программирования. Требуется найти максимум аффинно-линейной функции на ограниченном выпуклом многограннике.Теорема. Максимум аффинно-линейной функции l на ограниченном выпуклом многограннике M достигаетсяхотя бы в одной из вершин (на самом деле, множество всех точек максимума аффинно-линейной функции естьгрань многогранника M - без доказательства).26PPPДоказательство. Воспользуемся тем, что l( λi pi ) = λi l(pi ) ( λi = 1) - это очевидно.iiiPPПусть p1 , .

. . , pk - все вершины M . Тогда ∀ p ∈ M : p = λi pi ( λi = 1; λi > 0 ∀ i).iPЗначит, l(p) = λi l(pi ) 6 max l(pi ). Q.E.D.iiМетод решения задачи линейного программирования - ”симплекс-метод”: Возьмём одну вершину, посмотрим,как изменяется функция по рёбрам, выходящим из этой вершины. Если по всем уменьшается, то это - вершинамаксимума. Если где-то увеличивается, то пойдём по этому ребру.42Аффинные отображения, их свойства.

Аффинныепреобразования. Существование и единственностьаффинного преобразования, переводящего одинзаданный репер в другой. Координатный признакравенства фигур в аффинной геометрии.Def. Пусть S и S ′ - аффинные пространства, ассоциированные соответственно с векторными пространствами Vи V ′ . Отображение f : S → S ′ называется аффинным, если существует такое линейное отображение ϕ : V → V ′ ,что f (p + x) = f (p) + ϕ(x) ∀ p ∈ S, x ∈ V.−−−−−→→Свойство: ϕ(−pq) = f (p)f (q) ∀p, q ∈ S.→→Действительно, f (q) = f (p + −pq) = f (p) + ϕ(−pq).Значит, ϕ однозначно определяется по f .

Линейное отображение ϕ называется дифференциалом аффинногоотображения f и обозначается df .−−−→Если выбрать в S и S ′ начала отсчёта o и o′ , то получим f (o + x) = f (o) + ϕ(x) = o′ + o′ f (o) + ϕ(x). Положим−′−−→o f (o) = b ∈ V ′ . Тогда в векторизованной формеPотображение f записывается в виде f (o + x) = f (x) = ϕ(x) + b.В координатной форме: если f (x) = y, то yi = aij xj + bi в некоторых базисах V и V ′ . В частности, аффинноjлинейные функции - это аффинные отображения из S в K.

В случае K = R понятие дифференциала аффинногоотображения согласуется с общим понятием дифференциала гладкого отображения.Свойства аффинного отображения:1. Если P ⊂ S - плоскость, то f (P ) ⊂ S ′ - тоже плоскость, причём если аффинное отображение f биективно,то dim f (P ) = dim P.Действительно, P = p0 + U ⇒ f (P ) = f (p0 ) + df (U ) - плоскость в S ′ .Если f биективно, то df тоже биективно (выберем согласованные начала отсчёта в S и S ′ , где f = df ) ⇒dim df (U ) = dim U.PPP2. fλi pi = λi f (pi ), гдеλi = 1.iiPP →По определению,λi pi = o + λi −opi .