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

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

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

1. Выбираются произвольным образом первые (N+I) граничные точки и строятся по ним (N + 1) гиперплоскости. Для каждой построенной гиперплоскости запоминаются координаты граничных точек, по которым она построена, и координаты ее вершины.

Вершиной данной гиперплоскости условимся называть ту точку из выбранных (N+1) точек, через которую не проводится гиперплоскость.

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

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

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

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

4. Выбирается следующая по порядку граничная точка и все повторяется с п.2. (После перебора всех граничных точек процесс построения области работоспособности заканчивается (рис.1.) и произво-дится определение знаков ³ и £ для системы линейных неравенств.)

Знаки неравенств ³ и £ определяются в результате подстановки координат вершин гиперплоскости в уравнение гиперплоскости. При этом используется свойство вершин принадлежать области работоспособности. Символ £ соответствует отрицательному знаку результата подстановки, символ ³ – положительному. Для удобства использования результатов построения области работоспособности все неравенства приводятся к виду ³ 0.

1.3.1. Построение гиперплоскости через заданные N граничных точек

Эта процедура занимает центральное место в данном алгоритме. Коэффициенты гиперплоскости (неравенства) определяются в результате решения системы линейных алгебраических уравнений (N + 1)-го порядка. Систему получают в результате составления уравнений гиперплоскостей, записав вместо переменных координаты N точек, через которые необходимо провести гиперплоскость:

--------------------------------

. (1)

Так как количество неизвестных коэффициентов (N+I), то необходимо одному из них задать произвольное значение, например a = 1. Однако в этом случае невозможно построить гиперплоскость параллельную оси координат X.

Аналогично, если присвоить значение другому коэффициенту b = 1 уравнений (1), то предлагаемый подход будет неприменим для построения гиперплоскостей, параллельных соответствующим осям координат, а при задании k ¹ 0 – для построения гиперплоскостей, проходящих через начало координат.

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

В результате решения системы (N+1)-го порядка (1) определяются значения коэффициентов (N+1)-й гиперплоскости. Исключение из уравнений гиперплоскостей дополнительной переменной позволяет получить уравнение плоскости в N -мерном пространстве.

Поиск по сайту: