tem__1__2__3(______) ru

то есть, используя тот факт, что точки x1 , x 2 удовлетворяют условиям S показать,что и их линейная выпуклая комбинация удовлетворяет тем же условиям.

Утверждение

Гиперплоскости является выпуклым множеством.

Доказательство

Самостоятельно №1. Показать, что шар является выпуклым множеством.

Теорема: Пересечение произвольного числа выпуклых множеств является выпуклым множеством.

Самостоятельно № 2. Доказать теорему.

def. Множество, образованное пересечением конечного числа полупространств и гиперплоскостей (если это пересечение не пусто) называется многогранным множеством.

Многогранное множество выпукло.

Самостоятельно № 3 Доказывать.

def. Многогранником называется ограниченное многогранное множество.

Многогранное множество Х может быть представлено как множество решений системы из конечного числа линейных неравенств:

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 вершинами.

Ограничимся доказательством утверждения а) для случая 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.

Продолжить доказательство самостоятельно.