Утверждение

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

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

1)

2) Пусть ,

значит и (точки x¹ и x² свойством S)

3) И пусть ,

Покажем, что ВЛК (т.е. докажем, что ).

,

значит x удовлетворяет условию S, то есть .

Таким образом - выпуклое множество. Ч.т.д.

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

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

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

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

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

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

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

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

(3)

Для любой точки обозначим через I(x) множество номеров тех неравенств из (3), которые в данной точке выполняются как равенства:

def Ограничения с номерами из I(x) называются активными в точке х.

def. Точка называется внутренней, если для нее все неравенства в (3) выполняются как строгие неравенства.

Для внутренней точки .

def Все точки множества Х, не являющиеся внутренним, являются граничными.

Для граничной точки

def. Точка называется вершиной (крайней точкой, экстремальной точкой), если она не может быть выражена в виде линейной комбинации других различных точек множества Х,

т.е.

Точка называется вершиной, если не существует точек таких, что

при 0< l< 1

Определим мощность множества I(x) вершины x*.

Утверждение. Точка x* будет вершиной многогранного множества Х вида (3), если и среди векторов (!!!!) имеется n линейно-независимых.

Утверждение Точка x* будет вершиной многогранного множества Х вида (3), если она является единственным решением системы уравнений

Таким образом, для вершины имеем

Самостоятельно № 4.

Разработать алгоритм нахождения всех вершин многогранного множества вида (11).

Теорема: Любое многогранное множество имеет не более конечного числа вершин.

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

Теорема. Непустое многогранное множество вида (3) имеет по крайней мере одну вершину в том и только том случае, если rang A = n.

Без доказательства.

def. Ограничение многогранного множества Х называется жестким, если любая точка Х удовлетворяет ему как точному равенству.

def. Размерность r многогранного множества определяется формулой: r =n -g, где g - ранг матрицы, составленной из жестких ограничений этого множества.

def 1. Подмножество Y многогранного множества X называется q-мерной гранью Х, если

а) размерность Y = q

б) из условий и следует, что

При q=0 приведенное определение превращается в определение вершины.

Определение грани может быть дано в терминах ограничений, определяющих Х.

def 2. q-мерной гранью множества Х является q -мерное многогранное множество, система условий которого образуется из ограничений (описывающих многогранник) путем замены некоторых знаков неравенства знаками равенства, при этом число линейно-независимых ограничений, выполняемых на грани как равенство, равно n-q.

def. Одномерная грань множества Х называется ребром.

Из следующей теоремы следует, что вершины многогранника полностью определяют этот многогранник

Теорема (о представлении многогранника): Множество точек многогранника совпадает с множеством любых выпуклых линейных комбинаций его вершин.

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

Теорема содержит два утверждения, если – вершины многогранника, то

а) каждая его точка х может быть представлена в виде:

(*)

б) каждая точка х, удовлетворяющая условиям (*), принадлежит многограннику с данными вершинами.

Утверждение б) мы уже доказали: каждая выпуклая линейная комбинация (*) определяет только точки k -угольника, порожденного данными k вершинами.

Ограничимся доказательством утверждения а) для случая n =2.

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

· При одной вершине (k =1) теорема содержит тривиальное утверждение: х=х¹;

· При k =2 многогранник представляет собой отрезок, соединяющий точки х¹ и х². Но, как известно, любая точка х этого отрезка может быть представлена в виде

И наоборот, если l будет принимать все значения от 0 до 1 включительно, то тогда точка х будет пробегать весь отрезок от х¹ до х² включительно. Таким образом, оба утверждения теоремы справедливы.

· Пусть k =3, то есть многогранник имеет три вершины: х¹, х², х³.

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