tem__1__2__3(______) ru
.pdfто есть, используя тот факт, что точки x1 , x 2 удовлетворяют условиям S показать,что и их линейная выпуклая комбинация удовлетворяет тем же условиям.
Утверждение
Гиперплоскости является выпуклым множеством.
Доказательство
|
|
|
|
|
|
1) H |
ab |
= |
x R n |
aT x = b |
|
|
|
|
14243 |
||
|
|
|
|
условие S |
|
|
|
|
|
|
2) |
Пусть x1 , x 2 H ab , |
|
|
значит aT x1 = b и aT x 2 = b (точки x1 |
и x2 свойством S ) |
3) |
И пусть x = λx1 + (1 − λ )x 2 , 0 ≤ λ ≤ 1 |
|
Покажем, что ВЛК x H ab (т.е. докажем, что aT x = b ). |
||
aT x = aT (λx1 + (1 − λ )x 2 )= aT λx1 + aT (1 − λ )x 2 = λb + (1 − λ )b = b , |
||
значит x удовлетворяет условию S, то есть x H ab . |
|
|
Таким образом H ab - выпуклое множество. |
Ч.т.д. |
Самостоятельно №1. Показать, что шар является выпуклым множеством.
Теорема: Пересечение произвольного числа выпуклых множеств является выпуклым множеством.
Самостоятельно № 2. Доказать теорему.
def. Множество, образованное пересечением конечного числа полупространств и гиперплоскостей (если это пересечение не пусто) называется многогранным множеством.
Многогранное множество выпукло.
Самостоятельно № 3 Доказывать.
def. Многогранником называется ограниченное многогранное множество.
Многогранное множество Х может быть представлено как множество решений системы из конечного числа линейных неравенств:
X = {x R n |
|
Ax ≤ b}= {x R n |
|
aT x ≤ b ,i = |
|
} |
|
|
|
|
|
|
|||||
|
1,m |
(3) |
||||||
|
|
|
|
i* |
i |
|
||
|
|
|
|
|
|
|
|
|
A = [m × n],b R m
Для любой точки x X обозначим через I(x) множество номеров тех неравенств из (3), которые в данной точке выполняются как равенства:
I ( x ) = {i , 1 ≤ i ≤ m aiT* x = bi }
def Ограничения с номерами из I(x) называются активными в точке х.
def. Точка x* X называется внутренней, если для нее все неравенства в (3) выполняются как строгие неравенства.
Для внутренней точки x : I( x*) = .
def Все точки множества Х, не являющиеся внутренним, являются граничными.
Для граничной точки x* : I ( x*) ≠
def. Точка x* X называется вершиной (крайней точкой, экстремальной точкой ), если она не может быть выражена в виде линейной комбинации других различных точек множества Х,
т.е.
Точка x* X называется вершиной, если не существует точек x1 , x 2 X таких, что x* = λx1 + ( 1 − λ )x 2 при x1 ≠ x 2 , 0<λ<1
Определим мощность множества I(x) вершины x*.
Утверждение. Точка x* будет вершиной многогранного множества Х вида (3), если x X и среди векторов ai* )) (!!!!) имеется n линейно-независимых.
Утверждение Точка x* будет вершиной многогранного множества Х вида (3), если она является единственным решением системы уравнений
aiT* x = bi ,i I ( x*)
Таким образом, для вершины x * имеем I ( x*) ≥ n
Самостоятельно № 4.
Разработать алгоритм нахождения всех вершин многогранного множества вида (11).
def. Вершину x * называют невырожденной, если I ( x*) = n , и вырожденной в противном
случае.
x* x*
Теорема: Любое многогранное множество имеет не более конечного числа вершин.
Самостоятельно № 4. Доказать теорему
Теорема. Непустое многогранное множество вида (3) имеет по крайней мере одну вершину в том и только том случае, если rang A = n.
Без доказательства.
def. Ограничение многогранного множества Х называется жестким, если любая точка Х удовлетворяет ему как точному равенству.
def. Размерность r многогранного множества X R n определяется формулой: r =n-g , где g- ранг матрицы, составленной из жестких ограничений этого множества.
def 1. Подмножество Y многогранного множества X называется q-мерной гранью Х, если а) размерность Y = q
б) из условий x = λx1 + (1 − λ )x 2 Y , 0 < λ < 1 и x1 , x 2 X следует, что x1 , x 2 Y .
При q=0 приведенное определение превращается в определение вершины.
Определение грани может быть дано в терминах ограничений, определяющих Х.
def 2. q-мерной гранью множества Х является q-мерное многогранное множество, система условий которого образуется из ограничений (описывающих многогранник) путем замены некоторых знаков неравенства знаками равенства, при этом число линейно-независимых ограничений, выполняемых на грани как равенство, равно n-q.
def. Одномерная грань множества Х называется ребром.
Из следующей теоремы следует, что вершины многогранника полностью определяют этот многогранник
Теорема (о представлении многогранника): Множество точек многогранника X R n
совпадает с множеством любых выпуклых линейных комбинаций его вершин.
Доказательство:
1 2 K k
Теорема содержит два утверждения, если x , x , , x – вершины многогранника, то
а) каждая его точка х может быть представлена в виде:
k |
k |
|
x = ∑λi xi , |
∑λi = 1, λi ≥ 0 |
( ) |
i =1 |
i =1 |
|
б) каждая точка х, удовлетворяющая условиям ( ), принадлежит многограннику с данными вершинами.
Утверждение б) мы уже доказали: каждая выпуклая линейная комбинация ( ) определяет только точки k-угольника, порожденного данными k вершинами.
Ограничимся доказательством утверждения а) для случая n=2.
Доказательство:
•При одной вершине (k=1) теорема содержит тривиальное утверждение: х=х1 ;
•При k=2 многогранник представляет собой отрезок, соединяющий точки х1 и х2. Но, как известно, любая точка х этого отрезка может быть представлена в виде
x = λx1 + ( 1 − λ )x 2 , 1 ≥ λ ≥ 0
И наоборот, если λ будет принимать все значения от 0 до 1 включительно, то тогда точка х будет пробегать весь отрезок от х1 до х2 включительно. Таким образом, оба утверждения теоремы справедливы.
• Пусть k=3, то есть многогранник имеет три вершины: х1, х2, х3.
Продолжить доказательство самостоятельно.