Точка у является либо внутренней в множестве у, либо принадлежит границе у и тогда содержится в пересечении у с некоторой опорной к у гиперплоскостью. В случае, когда имеется несколько таких пересечении, будет выбирать то из них, которое имеет наименьшую размерность. Ясно, что если эта размерность равна нулю, то у9 будет крайней точкой у, а если она положительна, то у будет внутренней точкой соответствующего пересечения. Обозначим это пересечение через у, допуская при этом и крайние случаи у -у и у = у. Для наглядности заметим, что если у есть выпуклый многогранник, то у есть наименьшая по размерности (или, что то же самое, по включению) грань у, содержащая . [c.137]
Казалось бы, из геометрической интерпретации сразу виден способ решения задач линейного программирования. Достаточно построить многоугольник осуществимых планов и найти крайнюю точку пересечения луча, изображающего множество ассортиментных планов, с этим многоугольником. Однако если число выкраиваемых заготовок равно п, каждому раскрою соответствует точка -мерного пространства, а многоугольник осуществимых планов превращается в многогранник в этом и-мерном пространстве. Условия ассортиментное определяют луч в том же пространстве и, стало быть, геометрически задача сводится к очень сложному процессу поиска крайней точки пересечения многогранника с лучом. Таким образом, еще раз подтверждается, что кажущаяся при геометрической интерпретации простота решения задач линейного программирования является обманчивой. [c.18]
Точка v выпуклого множества V называется его угловой (крайней) точкой, если она не является внутренней точкой ни для какого отрезка, концы которого принадлежат множеству V. Угловые точки выпуклого многогранника являются его верши-нами, а сам он — выпуклой оболочкой своих вершин. [c.23]
Если допустимая область ограничена и непуста, то она является выпуклым многогранником, и задача ЗЛП в этом случае всегда разрешима, а оптимальное значение целевой функции достигается, по крайней мере, в одной из вершин многогранника. [c.199]
Приведенные крайне упрощенные примеры демонстрируют основные особенности задачи Л. п. Реальные задачи, насчитывающие много переменных, нельзя изобразить на плоскости — для их геометрической интерпретации используются абстрактные многомерные пространства. При этом допустимое решение задачи — точка в n-мерном пространстве, множество всех допустимых решений — выпуклое множество в этом пространстве выпуклый многогранник). [c.172]
ВЕРШИНА ДОПУСТИМОГО МНОГОГРАННИКА [ orner point] (области допустимых решений в задачах линейного программирования) — точка пересечения линейных ограничений (напр., на рис. Л. 1 к ст. "Линейное программирование"). Поскольку множество допустимых решений в задаче линейного программирования всегда выпукло, вершинная точка является крайней точкой множества, и она может быть принята за допустимое базисное решение задачи. [c.47]
Доказательство. Множество С является ограниченным замкнутым выпуклым многогранником в Rn. Известно, (см., например, Рокафеллар (1973)), что крайние точки можно получить как единственные решения системы п уравнений, получаемых из неравенств, задающих многогранник. При этом необходимо еще проверить, принадлежат ли найденные таким образом точки многограннику. [c.232]