Пересечение выпуклых множеств. Выпуклые множества и функции

Примеры выпуклых множеств

1. E n .

2. Пустое множество.

3. Множество, состоящее из одной точки

,

где
.

4. Гиперплоскость

где
, a ≠ 0, иb – число. Приn = 3 это множество совпадает с обычной плоскостью, а приn = 2 – с прямой.

5. Полупространство

где
, a ≠ 0, иb – число.

6. Конус

а y (k) – заданные векторы
. Заметим, что часто рассматриваются конусы с вершиной не в нуле, а в какой-либо другой точке
, то есть множества типа

7. Выпуклая комбинация (оболочка) конечного числа точек

Такое множество геометрически представляет собой n -мерный выпуклый многогранник.

8. Пересечение конечного числа полупространств

где
. Такое множество называется многогранным выпуклым множеством. В том случае, когда оно ограничено, оно также является выпуклым многогранником. Таким образом, возможны два представления выпуклого многогранника – в виде выпуклой оболочки конечной совокупности точек и в виде пересечения конечного числа полупространств, заданных неравенствами.

9. Шар радиуса r ≥0 с центром в

.

В качестве примеров невыпуклых множеств можно назвать множество целых чисел или множество рациональных чисел.

2.1.2. Свойства выпуклых множеств

Пересечение любого числа выпуклых множеств является выпуклым множеством.

Объединение двух выпуклых множеств не обязательно выпукло.

Пример: объединение двух точек не есть выпуклое множество.

также является выпуклым множеством.

Эти утверждения следуют из определения выпуклого множества. Докажем, например, первое утверждение для пересечения двух множеств
и
. Пусть. Рассмотрим

Из выпуклости A иB получаем, что
и
при всех
. Отсюда
. Утверждение доказано.

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

В качестве примера приведем выпуклый многогранник. Его крайними точками являются его вершины.

Определение . МножествоSE n называетсястрого выпуклым , если оно выпукло и все его граничные точки являются крайними.

Примером строго выпуклого множества является замкнутый шар.

2.1.3. Опорная гиперплоскость

Рассмотрим важнейшее понятие опорной гиперплоскости . Прежде всего заметим, что любая гиперплоскость , где
, a ≠ 0, определяет в пространстве
два замкнутых полупространства

Гиперплоскость является пересечением этих полупространств и одновременно границей каждого из них.

Пусть имеется некоторое выпуклое множество S и его граничная точкаy .

Определение . ГиперплоскостьH , проходящая через точкуy и содержащая все точки множествоS в одном из определяемых ею замкнутых полупространств, называется гиперплоскостью,опорной к множествуS в точкеy .

Можно показать, что опорную гиперплоскость можно провести через любую граничную точку выпуклого множества. Иллюстрация опорной гиперплоскости приведена на рис. 3.1.

Рис. 3.1. Опорная гиперплоскость H к выпуклому множеству S в точке y .

Отметим, что опорная гиперплоскость может быть не единственна (см. рис. 3.2).

Рис. 3.2. Две опорных гиперплоскости H 1 и H 2 к выпуклому множеству S в точке y .

Пусть теперь задано два непустых множества A иB . ГиперплоскостьH называетсяразделяющей гиперплоскостью, если все точки множестваA лежат в одном из замкнутых полупространств, определяемых гиперплоскостьюH , а все точки множестваB лежат в другом из определяемых ею замкнутых полупространств. Можно доказать несколько теорем о разделяющих гиперплоскостях. Рассмотрим простейшую из них. Пусть
– совокупность внутренних точек множестваA .

Теорема 3.1. ПустьA иB – два непустых выпуклых множества, причем
Ø. Тогда существует гиперплоскостьH , разделяющая множестваA иB. 1

Примеры разделяющих гиперплоскостей приведены на рис. 3.3 и 3.4.

Рис. 3.3. Гиперплоскость H разделяет множества S 1 и S 2 , не имеющие общую точку

Рис. 3.4. Гиперплоскость H разделяет множества S 1 и S 2 , имеющие общую точку

Выпуклые и вогнутые функции

При исследовании экономических явлений математическими методами весьма значительным оказывается такое свойство многих множеств и функций, как выпуклость. Характер поведения многих экономических объектов связан с тем, что определенные зависимости, описывающие эти объекты, являются выпуклыми.

С выпуклостью функций и множеств часто связано существование или единственность решения экономических задач: на этом же свойстве основаны многие вычислительные алгоритмы.

Справедливость многих утверждений, относящихся к выпуклым множествам и функциям, совершенно ясна, они почти очевидны. В то же время их доказательство зачастую очень сложно. Поэтому здесь будут изложены некоторые основные факты, связанные с выпуклостью, без доказательств, в расчете на их интуитивную убедительность.

Выпуклые множества на плоскости .

Любая геометрическая фигура на плоскости может рассматриваться как множество точек, принадлежащих этой фигуре. Одни множества (например, круг, прямоугольник, полоса между параллельными прямыми) содержат и внутренние, и граничные точки; другие (например, отрезок, окружность) состоят только из граничных точек.

Множество точек на плоскости называется выпуклым, если оно обладает следующим свойством: отрезок, соединяющий любые две точки этого множества, целиком содержится в этом множестве.

Примерами выпуклых множеств являются: треугольник, отрезок, полуплоскость (часть плоскости, лежащая по одну сторону от какой-либо прямой), вся плоскость.

Множество, состоящее из одной-единственной точки, и пустое множество, не содержащее ни одной точки, по принятому соглашению, также считаются выпуклыми. Во всяком случае, в этих множествах невозможно провести отрезок, соединяющий какие-то точки этих множеств и не принадлежащий этим множествам целиком, - в них вообще невозможно выбрать две точки. Поэтому их включение в число выпуклых множеств не приведет к противоречию с определением, а для математических рассуждений этого достаточно.

Пересечение, т. е. общая часть двух выпуклых множеств, всегда выпукло: взяв любые две точки пересечения (а они - общие, т. е. принадлежат каждому из пересекающихся множеств) и соединив их отрезком, мы легко убеждаемся в том, что все точки отрезка являются общими для обоих множеств, так как каждое из них выпукло. Выпуклым будет и пересечение любого числа выпуклых множеств.

Важным свойством выпуклых множеств является их отделимость: если два выпуклых множества не имеют общих внутренних точек, то плоскость можно разрезать по прямой таким образом, что одно из множеств будет целиком лежать в одной полуплоскости, а другое - в другой (на линии разреза могут располагаться точки обоих множеств). Отделяющая их прямая в одних случаях оказывается единственно возможной, в других - нет.

Граничная точка любого выпуклого множества сама может рассматриваться как выпуклое множество, не имеющее с исходным множеством общих внутренних точек, следовательно, она может быть отделена от него некоторой прямой. Прямая, отделяющая от выпуклого множества его граничную точку, называется опорной прямой этого множества в данной точке. Опорные прямые в одних точках контура могут быть единственными, в других - не единственными.

Введем на плоскости систему декартовых координат х, у. Теперь у нас появилась возможность рассматривать различные фигуры как множества таких точек, координаты которых удовлетворяют тем или иным уравнениям или неравенствам (если координаты точки удовлетворяют какому-либо условию, будем для краткости говорить, что сама точка удовлетворяет этому условию).

Выпуклое множество - подмножество евклидова пространства содержащей отрезок, соединяющий любые какие две точки этой множества.

Определение

Другими словами, множество называется выпуклой, если:

То есть, если множество X вместе с любыми двумя точками, которые принадлежат этому множеству, содержит отрезок, их соединяющий:

В пространстве выпуклыми множествами будут прямая, полупрямой, отрезок, интервал, одноточечный множество.

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

• гиперплоскости H p? с нормалью p :

• полупространства на которые гиперплоскости разделяет пространство:

Все перечисленные множества (кроме пули) является частным случаем выпуклой множества полиэдры.

Свойства выпуклых множеств

• Пересечение выпуклых множеств является выпуклым.
• Линейная комбинация точек выпуклой множества выпуклая.
• Выпуклая множество содержит любую выпуклую комбинацию своих точек.
• Любую точку n -мерного евклидова пространства с выпуклой оболочки множества можно представить как выпуклую комбинацию не более n +1 точек этого множества

Рассмотрим n - мерное евклидово пространство и пусть  точка в этом пространстве.

Рассмотрим две точки и , принадлежащие .Множество точек , которые могут быть представлены в виде

(в координатах это записывается так:

отрезком , соединяющим точки и . Сами точки и называются концами отрезка . В случаях n =2 и n =3 это  отрезок в обычном понимании этого слова на плоскости или в пространстве (см. рис. 12). Заметим, что при  =0 , а при  =1 , т.е. при  =0 и  =1 получаются концы отрезка.

где все и называется выпуклой комбинацией точек .

Пусть есть некоторая область в пространстве (другими словами,

Определение. Множество (область) называется выпуклым , если из того, что и следует, что для   . Другими словами, G  выпуклое множество, если оно, вместе с любыми двумя своими точками, содержит в себе отрезок, соединяющий эти точки.

На этих рисунках "а" и "б" - выпуклые множества, а "в" не является выпуклым множеством, так как в нём есть такая пара точек, что соединяющий их отрезок не весь принадлежит этому множеству.

Теорема 1. Пусть G  выпуклое множество. Тогда любая выпуклая комбинация точек, принадлежащих этому множеству, также принадлежит этому множеству.

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

Докажем теорему методом математической индукции. При k =2 теорема верна, так как она просто переходит в определение выпуклого множества.

Пусть теорема верна для некоторого k . Возьмём точку и рассмотрим выпуклую комбинацию

Теорема доказана.

Теорема 2. Допустимая область задачи линейного программирования является выпуклым множеством.

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

1. В стандартной форме в матричных обозначениях допустимая область G определяется условием

Т.е. x принадлежит G и, следовательно, выпукло.

2. В канонической форме область G определена условиями

Пусть и принадлежат G, т.е.

.

т.е. и, следовательно, G выпукло. Теорема доказана.

Таким образом, допустимая область в задаче линейного программирования является выпуклым множеством. По аналогии с двумерным или трехмерным случаями, при любом n эту область называют выпуклым

Теорема 3. Множество оптимальных планов задачи линейного программирования выпукло (если оно не пусто).

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

Если решение задачи линейного программирования единственно, то оно выпукло по определению  точка считается выпуклым множеством Пусть теперь и два оптимальных плана задачи линейного программирования.

т.е. есть также оптимальный план и, в силу этого, множество оптимальный планов выпукло. Теорема доказана.

Теорема 4. Для того, чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы целевая функция на допустимом множестве была ограничена сверху (при решении задачи на максимум) или снизу (при решении задачи на минимум).

Эту теорему мы даем без доказательства.

Свойства выпуклого множества

Классификация и специфика задач математического программирования.

Введение в математическое программирование.

Математическое программирование является одним из способов исследования операций в экономике. Содержание математического программирования составляют теория и методы решения задач о нахождении экстремума функции на некотором множестве. Множества могут определяться как линœейными так и не линœейными ограничениями. Главная цель задач математического программирования – выбор программ действий, приводящих к наилучшему результату, с точки зрения лица, принимающего решения (ЛПР). Проблема принятия решения в последовательности операции неразрывно связано с проблемами моделирования.

Определœение модели.

Модель - ϶ᴛᴏ образ изучаемого явления или объекта.

Этапы моделирования.

1. Построение качественной модели, ᴛ.ᴇ. выделœение факторов, которые представляются наиболее важными в установлении закономерности, которым они подчиняются.

2. Построение математической модели. Запись качественной модели в математических терминах.

Математическая модель принято называть точной если всœе исходные величины числовых параметров модели являются точными (к примеру, результаты наблюдений). В этом смысле точную модель называют идеальной. Далее будем полагать, что у точной задачи всœегда существует точное решение(результаты наблюдений). В реальной ситуации сведения о входных параметрах носят, как правило, приблизительный характер (результаты измерений). В этом случае полученные задачи называются реальными, а их решения – реальными решениями.

Реальное решение может и не существовать .

2 этап. Включает также построение целœевой функции, ᴛ.ᴇ. такой числовой характеристики, большему или меньшему значению которой соответствует лучшая ситуация с точки зрения лица, принимающего решения.

3 этап. Исследование влияния переменных на значения целœевой функции, нахождение решения, поставленной задачей.

4 этап. Сопоставление результатов вычисления, полученных на 3 этапе с моделированным объектом, ᴛ.ᴇ. критерий практики.

Здесь устанавливается степень адекватности модели и моделируемого объекта.

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

· Собственно математическое программирование – детерминированные задачи, когда вся исходная информация полностью определœена;

· Стохастическое программирование. К нему относятся задачи, в которых исходная информация содержит неопределённость, либо когда некоторые параметры носят случайный характер с известными вероятностными характеристиками.

В математическом программировании выделяют следующие разделы:

1) Линœейное программирование. В этих задачах целœевая функция линœейна, а множества, на котором исследуется его экстремальное значение задается системой линœейных равенств или неравенств. В свою очередь, в линœейном программировании существуют классы задач, структура которых позволяет создавать свои специальные методы решения, выгодно отличающиеся от методов общего характера. К примеру, транспортная задача.

2) Нелинœейное программирование. Данная задача и целœевая функция и ограничения носят нелинœейный характер.
Размещено на реф.рф
Задачи нелинœейного программирования обычно классифицируют на:

a) Выпуклое программирование, когда целœевая функция выпукла и выпукло множество, на котором решается задача.

b) Квадратичное программирование, когда целœевая функция квадратична, а ограничения линœейное равенство или неравенство.

c) Многоэкстремальные задачи. Обычно выделяются специальные классы задач, часто встречающиеся в примечаниях. К примеру, задача минимизации на выпуклом множестве вогнутых функций.

3) Целочисленное программирование, когда на значения переменных или на значения целœевой функции накладывается условие целочисленности.

Специфика задач математического программирования состоит в том, что, во-первых, методы классического анализа для отыскания условных экстремумов неприменимы, т.к. даже в простых задачах экстремумы достигаются в углах многогранника решения, а, следовательно, нарушается дифференцируемость функции.

Во-вторых, в практических задачах число переменных и ограничений столь велико, что если перебирать всœе точки в экстремальности, то может не хватить ресурсов ЭВМ, в связи с этим цель математического программирования создание, где возможно, аналитических методов решения, а при отсутствии таких методов – создание эффективных вычислительных способов нахождения принудительного решения.

Элементы выпускного анализа.

Множество Х принято называть замкнутым если оно содержит всœе свои предельные точки

Множество Х принято называть ограниченным если существует шар конечного радиуса с центром в любой точке этого множества целиком включающее в себя это множество.

Множество Х принято называть выпуклым множеством если на ряду с каждыми точками Х1, Х2 є этому множеству всœе точки Х равны (1-α)· , где 0≤α≤1 так же принадлежат этому множеству Х. Т.е. если множеству Х, то и отрезок, соединяющий эти точки, тоже множеству Х.

Пример:

Дано множество Ө ={х, у такие, что х+у≤1. Доказать, что данное множество является выпуклым.

Пусть взяли две точки () и () Ө (ᴛ.ᴇ. + ≤1 и + ≤1).

Доказать, что точка

1. Теорема 1

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

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

Пусть Х пересечение множеств и, где и выпуклые множества.

Докажем, что Х выпуклое множество.

Пусть точки и Х. Докажем, что отрезок, соединяющий эти точки, тоже принадлежит множеству Х.

т.к. и Х => и Х1

Х1 выпуклое множество => отрезок [ , ] Х1

т.к. , Х => они Х2

Х2 выпуклое множество.

Отсюда следует, что отрезок [ , ] Х1∩Х2=Х

Теорема доказана.

2. Теорема 2.

Объединœение выпуклых множеств не всœегда является выпуклым.

3. Свойство определённости.

Рассмотрим двухмерное пространство, в котором имеется неĸᴏᴛᴏᴩᴏᴇ замкнутое и выпуклое множество Х и некая точка d (,), где d Х, тогда найдётся прямая

С такая, что будут выполняться неравенства

Гиперплоскостью в пространстве R принято называть множество точек x (которая удовлетворяет равенству

Свойства выпуклого множества - понятие и виды. Классификация и особенности категории "Свойства выпуклого множества" 2017, 2018.