Метод гиперплоскостей для построения выпуклой области

ПроведениЕ ВЕРОЯТНОСТНЫХ расчетов на основе теоретико-множественного подхода.

Тема №2.

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

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

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

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

Рис. 2.1. Построение гиперплоскостей для точек

2. Определяется для следующей, выбранной произвольно, граничной точки (точка 4) соответствующая ей генеральная прямая гиперплоскость (прямая 1-3).

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

Генеральных гиперплоскостей для данной граничной точки может быть несколько (для точки 5 прямые 1-4, 3-4), особенно при построении многомерных областей работоспособности. Поэтому поиск генеральной гиперплоскости осуществляется среди всех ранее построенных гипер­плоскостей.

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

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

Аналогичные действия выполняются для каждой генеральной гипер­плоскости, если их для данной граничной точки несколько. При этом среди вновь проведенных гиперплоскостей будут одинаковые (на рис. 2.1 через точки 4 и 5 дважды проводится прямая 4-5), информация о кото­рых должна стираться в памяти ЭВМ по тем же причинам, что и для генеральных гиперплоскостей.

4. Выбирается следующая по порядку граничная точка, и все по­вторяется с п.2.

После перебора всех граничных точек процесс построения области работоспособности заканчивается и производится определение знаков “³” “£” (для системы линейных неравенств 1).

Блок-схема алгоритма построения области работоспособности по граничным точкам приведена на рис. 2.2.

Дата добавления: 2017-01-14