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

Блок 11

Блок 10

Блок 9

Блоки 7, 8

Блоки 3, 4

Блок 2

Блок 1

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

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

Рис. 2.2. Алгоритм поиска генеральной гиперплоскости

Систему получают в результате составления уравнений гипер­плоскостей, записав вместо переменных координаты N точек, через которые необходимо провести гиперплоскость:

. (2.1)

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

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

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

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

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

Блоки 5, 6

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

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

Рис.2.3. Построение генеральной гиперплоскости

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

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

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

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

Блок 12

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

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

Работоспособность объекта Таблица 2.1.

№ п/п	x1	x2	работоспособность объекта
			да
			да
			да
			да
			да
			да
			да

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

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

	D

Рис. 2.4. Координаты исходных точек.

Из графического представления видно, что точка с координатами (6,6) попадает внутрь выпуклой области. Докажем этот факт аналитически, предварительно построив выпуклую область работоспособности заданного объекта.

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

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

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

Прямая	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
уравнение прямой	x1 – 2,5x2 + 19 = 0	x1 + 0,2x2 – 2,6 = 0	7x1 - 4x2 – 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.

Полученная область представлена на рис. 2.5.

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

Аналогично получаем всю совокупность неравенств, которые описывают область работоспособности объекта.

(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

Проверка работоспособности объекта состоит в выполнении данных неравенств. Если хотя бы одно из неравенств не удовлетворяло условию, то точка не попадает в область. Данная методика позволяет исключить сбойные результаты в экспериментах на основе адаптивных (последовательных) процедур. Данный метод с удалением выпуклых оболочек (выпуклых слоев) предложил Тьюки. Процедура получила название «шелушение». Она позволяет при большом количестве точек измерения эффективно удалять сбойные результаты для объектов высокой размерности и, таким образом вести адаптивную обработку данных в задаче принятия решения о работоспособности объекта. Адаптивность в данном случае означает отбрасывание случайных результатов до тех пор, пока численные характеристики распределения случайной величины, например, вероятность, не будут постоянны. В рассмотренном примере сбойным результатом являлась точка 4. Построение линейной гиперплоскости для большого числа переменных не представляет сложной задачи и легко решается методами линейной алгебры.

Рис. 2.6. Исключение сбойных результатов методом Тьюки.

Для проверки попадания точки с координатами (6; 6) в построенную область используем программу MS Excel. Все необходимые данные занести в таблицу, как показано на рис. 2.7.

В ячейках В4 и С4 записаны координаты заданной точки.

В ячейке D8 записана формула подстановки точки (6;6) в первое неравенство 6*1+6*(-2,5) = -9. В обозначениях Excel формула выглядит следующим образом: = СУММПРОИЗВ($B$4:$C$4;B8:C8).

В ячейку G8 занесена формула =D8>=F8, вычисляющая логическую функцию ИСТИНА или ЛОЖЬ. Окончательный результат записывается в ячейке G15 в виде = И(G8:G13). Это означает попадание заданной точки в построенную область.

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

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