Выпуклые множества. Крайние точки. Выпуклость множества допустимых решений. Признак крайней точки допустимого множества. Теорема о существовании оптимального решения среди крайних точек. [c.47]
Крайнее точки выпуклых множеств [c.84]
М. имеет конечное число крайних точек, называемых его вершинами, экстремальными точками (т.е. такие точки, которые не могут лежать внутри отрезка, соединяющего две точки выпуклого множества, а могут быть только одной из концевых точек этого отрезка). [c.198]
Опишем теперь алгоритм нахождения крайних точек выпуклого замкнутого многогранного множества, образованного пересечением Mm к М 1">. [c.32]
Опорные решения задачи (9.7)—(9.9) являются крайними точками допустимого множества этой задачи. (Допустимое множество всегда выпукло.) [c.193]
Как показано в [16], при ограниченных и выпуклых допустимых множествах (2.14) вектор х% 0, удовлетворяющий ограничению A xk bk, можно представить в виде выпуклой линейной комбинации конечного множества крайних точек [c.24]
Множество А, А с R", называют выпуклым, если оно вместе с каждой парой своих точек содержит и весь отрезок, соединяющий эти точки. Иными словами, подмножество А пространства Rm выпукло, если для всех пар точек у, у" е А и любого числа А е [0, 1] выполнено соотношение у + (1 - А) у" е А. Множество К, К с Rm, называется конусом, если для каждой точки у е К и любого положительного числа а выполняется включение ау е К. Конус, являющийся выпуклым, именуют выпуклым конусом. Иначе говоря, выпуклое множество является выпуклым конусом, если оно вместе с каждой своей точкой содержит и весь луч, исходящий их начала координат (в общем случае без самого начала) и проходящий через данную точку. При этом начало координат (вершина конуса) может как принадлежать, так и не принадлежать данному конусу. Можно проверить, что сумма любых двух (и более) элементов выпуклого конуса всегда принадлежит данному конусу. Конус К называют острым, если не существует такого ненулевого вектора у е К, для которого выполняется включение -у е К. Не являющийся острым конус обязательно содержит, по крайней мере, одну прямую, проходящую через начало координат (вместе с самим началом или же без него). [c.52]
Приведенные крайне упрощенные примеры демонстрируют основные особенности задачи Л. п. Реальные задачи, насчитывающие много переменных, нельзя изобразить на плоскости — для их геометрической интерпретации используются абстрактные многомерные пространства. При этом допустимое решение задачи — точка в n-мерном пространстве, множество всех допустимых решений — выпуклое множество в этом пространстве выпуклый многогранник). [c.172]
Множество допустимых решений выпукло и имеет конечное число крайних точек (вершин). [c.61]
Теорема 1 утверждает, что каждому вектору g соответствует по крайней мере одна точка g (g) границы выпуклого множества Q, в которой g определяет опорную к Q гиперплоскость G. Наоборот, [c.371]
Точка у является либо внутренней в множестве у, либо принадлежит границе у и тогда содержится в пересечении у с некоторой опорной к у гиперплоскостью. В случае, когда имеется несколько таких пересечении, будет выбирать то из них, которое имеет наименьшую размерность. Ясно, что если эта размерность равна нулю, то у9 будет крайней точкой у, а если она положительна, то у будет внутренней точкой соответствующего пересечения. Обозначим это пересечение через у, допуская при этом и крайние случаи у -у и у = у. Для наглядности заметим, что если у есть выпуклый многогранник, то у есть наименьшая по размерности (или, что то же самое, по включению) грань у, содержащая . [c.137]
Прежде всего, для того, чтобы лучше понять, в чем же выражается неприятный эффект нелинейности, проведем сравнение задач линейного и нелинейного программирования. Начнем с множества допустимых планов. В задачах линейного программирования оно выпуклое, с конечным числом крайних точек (напоминаем, что крайней точкой называется всякая точка множества, которая не является внутренней ни для какого отрезка, целиком принадлежащего этому множеству). Это сразу становится понятным, если вспомнить, что границами множества служат гиперплоскости. В задачах же нелинейного программирования (в том случае, когда нелинейны ограничения) множество допустимых планов может быть невыпуклым, может иметь бесконечное число крайних точек. Например, пусть допустимая область на плоскости ХОУ определяется такими ограничениями [c.72]
Только сначала выясним, в чем выражается неприятный эффект нелинейности. Для этого сопоставим задачи линейного и нелинейного программирования. Рассмотрим, как выглядит в них множество допустимых планов. В задачах линейного программирования оно выпуклое, с конечным числом крайних точек (напоминаем, что крайней точкой называется всякая точка множества, [c.98]
Точка v выпуклого множества V называется его угловой (крайней) точкой, если она не является внутренней точкой ни для какого отрезка, концы которого принадлежат множеству V. Угловые точки выпуклого многогранника являются его верши-нами, а сам он — выпуклой оболочкой своих вершин. [c.23]
Непустое выпуклое компактное множество a R" имеет крайние точки. [c.84]
Пусть X является линейным пространством, a Q непустое подмножество в X. Точка q е Q называется крайней точкой множества Q, если не существует открытого интервала с концами, принадлежащими множеству Q, который содержит точку q, Банахово пространства X называется строго выпуклым, если условия х, у е В, х у гарантируют неравенство 1 лг + у < 2, где В -замкнутая единичная сфера в X. [c.185]
АНТОН. Ты имеешь в виду проблему существования равновесия, которую мы разбирали еще в первой лекции ИГОРЬ. Да, но в моделях общего равновесия математикам пришлось искать в многомерном пространстве аналогии точке пересечения спроса и предложения, точке касания двух линий безразличия и тому подобным знакомым нам признакам равновесия. Поэтому математики усиленно занимались свойствами выпуклости функций и множеств. БАРБОС. Не ручаюсь за мнение других собак, но мне по душе выпуклые или в крайнем случае ровные поверхности. С ними как-то спокойнее, не ждешь подвоха в виде какой-нибудь трещины или провала. АНТОН. Хорошо. В мо- [c.215]
В приведенном рассуждении мы молча предполагали, что производственная система продуктивна, т. е. в состоянии производить валовой продукт в количестве, превосходящем его производственное потребление. Для многопродуктовой системы условия продуктивности носят более сложный характер, чем для однопродуктовой. Если, например, производство единицы 1-го продукта требует 2 ед. 2-го продукта, а производство единицы 2-го продукта в свою очередь требует 1.5 ед. 1-го продукта, то в производстве единицы любого из этих продуктов затрачивалось бы по крайней мере 2-1.5 = 3 ед. этого продукта. Такая система, очевидно, непродуктивна. МПВ непродуктивной системы пусто, а пустое множество является выпуклым, так что непродуктивность системы формально не противоречит сделанному ранее выводу. [c.678]
Очевидно, х + С является конической оболочкой для Q с вершиной в х г Q. Это означает, что произвольный луч с началом в х, лежащий в конусе х + С, обязательно содержит, по крайней мере, одну точку множества Q. Очевидно, что х + С также является выпуклым и замкнутым множеством, так как С является выпуклым и замкнутым. [c.187]
ВЕРШИНА ДОПУСТИМОГО МНОГОГРАННИКА [ orner point] (области допустимых решений в задачах линейного программирования) — точка пересечения линейных ограничений (напр., на рис. Л. 1 к ст. "Линейное программирование"). Поскольку множество допустимых решений в задаче линейного программирования всегда выпукло, вершинная точка является крайней точкой множества, и она может быть принята за допустимое базисное решение задачи. [c.47]
Пусть размерность у равна г. Тогда по теореме Каратеодори (см. п. 11.5) найдутся такие г+ 1 крайних точек j>0 у 9. .., уг множества у, чхоу является их выпуклой комбинацией [c.137]
Доказательство. Множество С является ограниченным замкнутым выпуклым многогранником в Rn. Известно, (см., например, Рокафеллар (1973)), что крайние точки можно получить как единственные решения системы п уравнений, получаемых из неравенств, задающих многогранник. При этом необходимо еще проверить, принадлежат ли найденные таким образом точки многограннику. [c.232]
Точка Р выпуклого множества V в и-мерном пространстве называется крайней, если она не может быть серединой отрезка, концы которого лежат в множестве V, т. е. если не существует точек Mit M2gK, Мг = =Мг таких, что [c.84]
Предположим, что q ne является крайней точкой множества Q. Тогда существуют две различные точки <7 >< з е > такие что открытый интервал (q, q2) содержит точку "q. Так как множество Q выпукло, ни одна из этих точек не может быть внутренной точкой в Q, ибо в противном случае один из трех интервалов [<7i > ) < (<7i 9 1 > (<7i < < ) < каждый из которых содержит точку q , целиком помещался бы в int Q, а это невозможно согласно включению q e FrQ. Таким образом ,, д2 е Н. Из последнего следует, что qt,q2effnQ. Следовательно, из (87) получается неравенство [c.186]
Теорема Хелли. Пусть А , аеа, — некоторое семейство выпуклых замкнутых множеств в Rm, среди которых по крайней мере одно ограниченное множество. Если. пересечение любых т+1 множеств Аа не пусто, то и пересечение всех множеств Аа непусто. [c.22]
АНТОН. Ты имеешь в виду проблему существования равновесия, которую мы разбирали еще в первой лекции ИГОРЬ. Да, но в моделях общего равновесия математикам пришлось искать в многомерном пространстве аналогии точке пересечения спроса и предложения, точке касания двух линий безразличия и тому подобным знакомым нам признакам равновесия. Поэтому математики усиленно занимались свойствами выпуклости функций и множеств. БАРБОС. Не ручаюсь за мнение других собак, но мне по душе выпуклые или в крайнем случае ровные поверхности. С ними как-то спокойнее, не ждешь подвоха в виде какой-нибудь трещины или провала. АНТОН. Хорошо. В модели общего равновесия доказано существование равновесия, но как все участники найдут равновесные цены ИГОРЬ. Считается, что сам рынок обладает способностью такой координации проб и ошибок. АНТОН. А ты помнишь, как в девятой лекции мы обсуждали устойчивость и рассматривали случаи, когда колебания цены по отношению к равновес- [c.58]
Смотреть страницы где упоминается термин Крайние точки выпуклых множеств
: [c.169]Смотреть главы в:
Справочник по математике для экономистов -> Крайние точки выпуклых множеств