Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Утверждение






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

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

    1)

    2) Пусть ,

    значит и (точки x1 и x2 свойством 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).

     
     

    def. Вершину называют невырожденной, если , и вырожденной в противном случае.

     
     

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

    Самостоятельно № 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) теорема содержит тривиальное утверждение: х=х1;

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

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

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

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






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.