Большая техническая энциклопедия
2 3 6
A N P Q R S U
А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я
ВА ВВ ВЕ ВЗ ВИ ВК ВЛ ВН ВО ВП ВР ВС ВТ ВУ ВХ ВЫ ВЮ ВЯ

Выпуклая оболочка - множество

 
Выпуклая оболочка множества А - это наименьшее выпуклое множество ( обозначаемое через convA), содержащее А. Аналогично определяется абсолютно выпуклая оболочка absconv А множества А. Замкнутая абсолютно выпуклая оболочка множества А - это наименьшее абсолютно выпуклое замкнутое множество, содержащее А.
Множество М и его выпуклая оболочка.| Выпуклая оболочка множества на прямой.| Выпуклая оболочка множества на плоскости. Выпуклую оболочку множества М образуют такие элементы /, которые могут быть получены из элементов М операцией усреднения. Ясно, что СоМгзМ, ибо сам элемент можно рассматривать как результат усреднения, при котором ему приписан единичный вес.
Овыкуп-ление индикатрисы при помощи смешанной стратегии. Выпуклой оболочкой множества называется пересечение всех содержащих его полупространств. Индикатриса управляемой системы может быть невыпуклой.
Выпуклой оболочкой множества называется пересечение всех содержащих его полупространств. Индикатриса управляемой системы может быть невыпук-лой.
Иллюстрация к доказатель - СТВУ те Ремы. Выпуклой оболочкой множества точек в пространстве размерности 1 является наименьший содержащий их интервал. Этот интервал может быть найден за линейное время.
Понятие выпуклой оболочки множества точек S является естественным и простым. В соответствии с определением - это наименьшее выпуклое множество, содержащее S. Чтобы наглядно представить это понятие в случае, когда S - конечное множество точек на плоскости, предположим, что это множество охвачено большой растянутой резиновой лентой. Когда лента освобождается, то она принимает форму выпуклой оболочки.
Определим выпуклую оболочку множества допустимых целочисленных точек ( решений) как минимальное выпуклое множество, содержащее все эти точки. Допустимыми решениями будет не вся область допустимых решений, находящаяся внутри и на границе выпуклой оболочки, а лишь отдельные дискретные точки этой области, имеющие все целочисленные координаты. Целевая функция достигает оптимального значения в одной из вершин этой выпуклой оболочки, которая представляет собой одно из допустимых целочисленных решений.
Определим выпуклую оболочку W множества допустимых целочисленных решений задачи как минимальное выпуклое множество, содержащее все точки, соответствующие этим решениям. Искомое решение целочисленной задачи линейного программирования соответствует некоторой крайней точке оболочки W. Понятно, что оболочка W целиком принадлежит выпуклому многограннику W0, формируемому линейными ограничениями задачи при снятом требовании на целочис-ленность. Решение задачи осуществляется поэтапно. На первом этапе решается исходная задача линейного программирования без учета требования на целочислен-ность. Если полученная точка оказывается целочисленной, то она и есть решение задачи. В противном случае к исходным добавляется новое ограничение, отсекающее: полученную экстремальную точку и уменьшающее объем выпуклого многогранника Wo. Однако получаемый при этом выпуклый многогранник W по-прежнему должен содержать в себе выпуклую оболочку W, так что ни одна из допустимых целочисленных точек не. Далее решается новая задача линейного программирования с учетом введенных ограничений, и получаемая экстремальная точка вновь анализируется на цело-численность. Описанная процедура повторяется до тех; пор, пока очередная полученная экстремальная точка не окажется целочисленной.
Теорема 3.11. Выпуклая оболочка множества из N точек на плоскости может быть найдена с помощью открытого алгоритма за время Q ( N ogN) со временем коррекции Q ( logN), т.е. может быть построена в реальном времени.
Вначале строятся выпуклые оболочки множества F при фиксированных значениях ш, а затем в соответствии с дискретной вероятностной мерой на Q определяется выпуклая комбинация множеств, построенных на первом этапе. Ясно, что полученное в результате указанных построений множество выпукло. Ограничениям (3.8) соответствуют ограничения на элементы этого множества. Задача (3.7) - (3.9) сводится в этом случае, как и задачи (3.1) - (3.3) и (3.4) - (3.6), к конечно-мерной задаче нелинейного программирования. Эти же соображения могут быть использованы для построения приближенных апостериорных решающих распределений в случаях, когда множества X и Q компактны.
Безье расположен внутри выпуклой оболочки множества точек-ориентиров.
А означает выпуклую оболочку множества А.

Определение 5.1. Выпуклую оболочку множества Mf ( A, е) называем многогранником упаковок. Аналогично, определяется многогранник разбиений и многогранник покрытий.
Показать, что выпуклая оболочка множества К не замкнута.
Точка р находится вне conv ( Si и conv ( S2, но внутри выпуклой оболочки их объединения. Находится ли р вне выпуклой оболочки множества Si.
Доказать, что выпуклую оболочку множества N можно получить, объединяя все треугольники Д с вершинами в точках этого множества.
Напомним, что выпуклой оболочкой множества ЕсХ называется наименьшее выпуклое множество в X, содержащее Е, а замкнутой выпуклой оболочкой множества Е называется замыкание его выпуклой оболочки.
Тот факт, что выпуклые оболочки множеств Л /, и Мг не содержат других точек, кроме указанных, вытекает из следующей теоремы.
Может ли быть замкнутой выпуклая оболочка незамкнутого множества.
Отметим, что замыкание выпуклой оболочки множества Та по норме пространства Ла совпадает с замыканием этой выпуклой оболочки по мере.
Доказать, что определение выпуклой оболочки множеств N эквивалентно следующему: [ N ] - наименьшее выпуклое множество, содержащее N.
А, и называется выпуклой оболочкой множества А. Оно является пересечением всех выпуклых подмножеств из X, содержащих А, и тем самым наименьшим таким подмножеством.
Можно показать, что здесь выпуклой оболочкой множества Д является ( п - 1) - мерный многогранник с 1С вершинами.
Можно считать, что вся выпуклая оболочка множества F состоит из точек - разрыва оператора А.
Привести примеры, показывающие, что выпуклая оболочка незамкнутого множества может быть не замкнута.
Из этого следует, что и выпуклая оболочка множества S / - является замкнутым ограниченным множеством.

Теорема Биркгофа [41] утверждает, что выпуклая оболочка множества бистохастических матриц в п2 - мерном пространстве имеет в качестве своих крайних точек множество матриц перестановок. Задача (2.1.5) - (2.1.7) с условиями х 0 является задачей линейного программирования; минимальное значение целевой функции достигается в крайних точках, т.е. для перестановочных матриц.
К определяется однозначно - он является выпуклой оболочкой множества всех крайних точек из X. По теореме 3.2, множество Х также имеет крайние точки.
В дальнейшем нам неоднократно придется рассматривать - выпуклые оболочки множеств в нормированных пространствах, в связи с чем целесообразно иметь удобное геометрическое описание d - отрезков. Такое описание приводится в нижеследующей теореме.
Доказать, что всякий ограниченный многогранник является выпуклой оболочкой множества своих вершин.
Доказать, что многогранник М совпадает с выпуклой оболочкой множества всех матриц ( х - - хт) / 2, где х - перестановочная ( пхя) - матрица.
Для того, чтобы множество 5 было выпуклой оболочкой множества Л, оно должно быть, во-первых, выпуклым и, во-вторых, наименьшим выпуклым множеством, содержащим множество А. Докажем, что оба эти условия выполняются.
Пусть, как обычно, соМ - - выпуклая оболочка множества М, а сбМ - ее замыкание.
Из доказанного следует, что если Н - выпуклая оболочка множества всех крайних точек / С, то для любого S.
Помимо геометрического описания, даваемого теоремой 2.1, выпуклая оболочка множества X обладает простым аналитическим представлением.
Второй из рассматриваемых алгоритмов начинает работу с построения выпуклой оболочки множества точек Р плоскости. Под выпуклой оболочкой понимается выпуклый многоугольник, каждая из вершин которого совпадает с одной из точек множества Р, а все остальные точки лежат на сторонах или внутри многоугольника. Алгоритмы построения выпуклой оболочки конечного множества точек на плоскости рассмотрены далее в этой главе. Если внутренние точки отсутствуют, то оптимальное решение задачи коммивояжера определяется через обход вершин оболочки в одном из двух направлений, начиная с любой вершины. В том случае, когда оболочка содержит s вершин ( ii 2, , s) j T J полагая Xs ( i 2, 5 s), реализуем первый алгоритм.
Это показывает, что точка т действительно принадлежит выпуклой оболочке множества / С.
Заметим, что если пользоваться этим методом для построения выпуклой оболочки множества из N точек в случае, когда допускается только добавление точек, то получим оценку для времени выполнения 0 ( N og2N), более высокую по сравнению с 0 ( N ogN) для менее мощного метода. Ясно, что это является платой за использование метода, более мощного, чем требуется в конкретной задаче.
Минимальное выпуклое множество, содержащее А, мы назовем выпуклой оболочкой множества А.
Доказать, что всякое компактное выпуклое множество совпадает с выпуклой оболочкой множества своих крайних точек.
Доказать, что всякий ограниченный выпуклый многогранник совпадает с выпуклой оболочкой множества своих вершин.

Минимальное выпуклое множество, содержащее А, мы назовем выпуклой оболочкой множества А.
Тогда X convE ( X), т.е. X совпадает с выпуклой оболочкой множества своих, крайних, точек.
По теореме Крейна - Мильмана, шар D является ш - замк-нутой выпуклой оболочкой множества своих крайних точек.
Во-вторых, некоторые аналогии между плоскостью и пространством существуют - так, выпуклые оболочки множеств из п точек [3] и максимумы в множестве из п векторов [4] могут быть найдены за время О ( п logn) как в случае двух, так и в случае трех измерений. Но несмотря на это, никакого обобщения алгоритма построения пересечения многоугольников найдено не было.
Дальнейшие свойства выпуклых многогранников, которые мы рассмотрим, связаны с понятием выпуклой оболочки множества.
Из этой теоремы и теоремы 2.13 вытекает, что выпуклый многогранник является выпуклой оболочкой множества своих крайних точек.
Следующий классический результат, принадлежащий Каратео-дори [12, 13], показывает, что при рассмотрении выпуклой оболочки множества S с: Ел нет необходимости брать комбинации, включающие более чем d - - точек.
Выпуклые оболочки функции / для различных множеств ее определения Q, и Q.. Покажем, что это определение эквивалентно данному выше определению COQ /, как выпуклой оболочки определяющего множества.
 
Loading
на заглавную 10 самыхСловариО сайтеОбратная связь к началу страницы

© 2008 - 2014
словарь online
словарь
одноклассники
XHTML | CSS
Лицензиар ngpedia.ru
1.8.11