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

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

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

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

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

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

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

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

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

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

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

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

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

Блок 1

Производится выбор первых (N + 1) граничных точек из массива всех граничных точек

Блок 2

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

. (3)

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

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

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

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

Блоки 3, 4

Производится проверка - первые ли (N + 1) гиперплоскостей построены. Если первые, то осуществляется поиск генеральной гиперплоскости. В противном случае выполняется проверка - все ли генеральные гиперплоскости найдены и использованы при построении гиперплоскостей для данной граничной точки.

Блоки 5, 6

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

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

Блоки 7, 8

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

Блок 9

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

Блок 10

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

Блок 11

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

Блок 12

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

Диалоговое меню

Система меню ориентирована на реализацию всех этапов построения области работоспособности.

1 - вычисление величины критерия по параметрам T и x (вычисляется критерий (2) при заданных пользователем T, x).

2 – построение прямой через две заданные точки (на печать выводятся коэффициенты А, В, С прямой AT + Bx + C = 0).

3 – построение области работоспособности [но граничным точкам, заданным в строгой последовательности их расположения вдоль границы (направление обхода граничных точек не играет роли), строится система граничных прямых в координатах: T - ось координат, x - ось абсцисс].

4 - вычисление линейной формы (вычисление левой части уравнения прямой AT + Bx + C ´ S при заданных пользователем T, x).

5 - построение графика переходного процесса (строится график переходного процесса объекта контроля h(t),где вертикальными линиями отмечаются допустимые значения критерия качества - минимальное и максимальное время регулирования tp_min, tp_max).

6 - справочная информация (содержит рекомендации по выполнению лабораторной роботы).

7 - конец работы.

1.3. Пример расчета попадания точки в заданную область.

Задана таблица работоспособности объекта

Табл. 1

№ п/п	x₁	x₂	работоспособность объекта
			да
			да
			да
			да
			да
			да
			да

Вопрос: будет ли работоспособен объект с данными параметрами

Решение. Геометрическое представление исходных данных.

Проведем построение области согласно алгоритму, изложенному в разделе 1.2.

1 шаг.Берется (N + 1) точки в N – мерном пространстве в нашем случае N=2, т.е.берем точки 1, 2, 3.

Через каждые N точек проводится гиперплоскость и заполняется таблица

Табл.2

Прямая	1 – 2	2 – 3	1 – 3
Вершина
координаты вершин	2; 3	6; 10	1; 8
координаты 1-ой точки	6; 10	1; 8	6; 10
координаты 2-ой точки	1; 8	2; 3	2; 3
уравнение прямой	x₁ – 2,5x₂ + 19 = 0	x₁ + 0,2x₂ – 2,6 = 0	7x₁ - 4x₂ – 2 = 0

2 шаг. Для точки 4 ищем генеральную гиперплоскость среди всех ранее построенных плоскостей. Является ли (1 – 2) генеральной гиперплоскостью для точки 4.

S (т.4) = 7 – 2,5 × 5 + 19 > 0

S¢ (т.3) = 2 – 2,5 × 3 + 19 > 0, т.е. (1-2), не является для точки 4 генеральной гиперплоскостью.

Для т. 4 генеральная гиперплоскость (1-3);

S¢ (т.4) = 7 × 7 – 4,5 - 2 > 0

S¢ (т.2) = 7 × 1 – 4,8 - 2 < 0, т.е. (1-3), является для точки 4 генеральной гиперплоскостью.

Мы снова имеем (N + 1) точку – это {1, 3, 4}

Через каждые N точек проведем гиперплоскости (в данном случае прямые)

Для упрощения построения часть таблицы не заполняется.

Прямая 1 – 3 3 – 4 1 – 4

Вершина

После обработки каждой точки генеральная гиперплоскость и плоскости повторяющиеся (одни и те же плоскости в разных таблицах) вычеркиваются.

3 шаг.Для точки 5 генеральная гиперплоскость (1 – 4)

Прямая 1 – 4 4 – 5 1 – 5

Вершина

а также (3 – 4)

Прямая 3 – 4 3 – 5 5 – 4

Вершина

4 шаг.Для точки 6 генеральная гиперплоскость (1 – 5)

Прямая 1 – 5 5 – 6 1 – 6

Вершина

5 шаг.Для точки 7 генеральная гиперплоскость (1 – 6)

Прямая 1 – 6 6 – 7 7 – 1

Вершина

Получили границу области работоспособности:

(1 – 2) – (2 – 3) – (3 – 5) – (5 – 6) – (6 – 7) – (7 – 1).

Окончательный шаг объекта для перехода от уравнений к неравенствам необходимо в линейную форму (левая часть равенства) поставить координаты вершины.

Если величина линейной формы положительна, то знак “=” заменяется на “³”, если же отрицательна то знак “=” заменяется на “£”.

Пример: (1 – 2): x₁ – 2,5x₂ + 19 = 0.

S¢(т.3) = 2 – 2,5 × 3 + 19 > 0.

Соответствующее неравенство имеет вид: x₁ – 2,5x₂ + 19 ³ 0.

Полученная область имеет вид, представленный на рис. 1.7.

Рис. 1.7. Область решений системы неравенств.

(1 – 2) Þ x₁ – 2,5x₂ + 19 ³ 0

(2 – 3) Þ x₁ + 0,2x₂ – 2,6 ³ 0

(3 – 5) Þ x₁ + 6x₂ - 20 ³ 0

(5 – 6) Þ -x₁ + 0,75x₂ + 6,5 ³ 0

(6 – 7) Þ -x₁ – 0,5x₂ +14 ³ 0

(7 – 1) Þ -x₁ - 2x₂ + 26 ³ 0

Проверка работоспособности объекта состоит в выполнении данных неравенств. Если хотя бы одно из неравенств не удовлетворяло условию, то точка не попадает в область.

Данная методика позволяет исключить сбойные результаты в экспериментах на основе адаптивных (последовательных) процедур. Адаптивность в данном случае означает отбрасывание случайных результатов до тех пор, пока численные характеристики распределения случайной величины, например, вероятность, не будут постоянны. Построение линейной гиперплоскости для большого числа переменных не представляет сложной задачи и легко решается методами линейной алгебры [].

ЛИТЕРАТУРА

1.Компьютерные технологии адаптивной обработки данных,часть1:Лабораторный практикум / РГМУ: сост. Булаев М.П., Дорошина Н.В., Кабанов А.Н. Рязань, 2002, 27 с.

2.Элементы теории вероятностей: Практикум, Б131 /Авт.-сост. М.П.Булаев, Е.В. Прохорова; под ред. М.П. Булаева; Ряз. гос. мед. ун-т им. акад И.П.Павлова. - Рязань: РИО РГМУ, 2006. – 93 с.

ЛЕКЦИЯ 3

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒