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