РАЗДЕЛ 2
ПОСТАНОВКА ЗАДАЧ РАЗМЕЩЕНИЯ
n-МЕРНЫХ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ
В данном разделе приводятся основные понятия и определения многомерной геометрии: гиперплоскость, n-мерный параллелепипед, выпуклый n-мерный политоп и другие. Формулируются оптимизационные задачи размещения n-мерных параллелепипедов в односвязной и многосвязной областях с различными функциями цели и задача размещения выпуклых n-мерных политопов в n-мерном параллелепипеде. Рассматриваются известные методы решения оптимизационных задач геометрического проектирования применительно к поставленным задачам, анализируются достоинства и недостатки этих методов, делается вывод о необходимости решения поставленных задач комбинированными методами.
2.1. Основные понятия и определения
По аналогии с пространствами и , точки n-мерного евклидового арифметического пространства [124] определяются как упорядоченные наборы n действительных чисел.
Гиперплоскостью [125] называется множество всех точек пространства , координаты которых удовлетворяют уравнению
,(2.1)при условии, что не все числа равны нулю. Гиперплоскость можно описать с помощью скалярного произведения. Пусть точка . Рассмотрим все точки такие, что вектор, определяемый направленным отрезком , ортогонален заданному вектору . Очевидно, координаты точки P удовлетворяют условию
(2.2)или в развернутом виде
. Уравнение гиперплоскости можно записать и в другом виде. Множество векторов , удовлетворяющих уравнению (2.2), является линейным пространством - подпространством в линейном пространстве [126]. Пусть - базис этого пространства (очевидно, что размерность пространства равна (n-1)). Пусть и - векторы, определяемые соответственно направленными отрезками и , где О - начало координат в . Тогда уравнение (2.2) эквивалентно уравнению
,(2.3) где - произвольные вещественные числа.
При изменении независимо друг от друга от до точка Р опишет гиперплоскость (2.2).
Уравнение (2.1) гиперплоскости называется координатным, а уравнение (2.2) - векторным.
Построение гиперплоскости на n точках, например , осуществляется следующим образом. Известно [125], что гиперплоскость однозначно задается точкой и направлениями, задаваемыми (n-1) линейно независимыми векторами , где , k=2,...,n. Тогда уравнение гиперплоскости имеет вид (2.1), где коэффициенты и свободный член b вычисляются согласно формулам
и
где - определитель (n-1)-ого порядка, i=1,2,...,n.
Заметим [125], что определителем квадратной матрицы называется число , где - перестановка из n символов 1,2,..., n и суммирование ведется по всем перестановкам из n символов; , если - четная перестановка, и , если - нечетная перестановка.
Пусть в дана точка и вектор . Эти исходные данные определяют прямую в , т.е. множество точек таких, что направленный отрезок принадлежит а.
Пусть - текущая точка прямой. Координаты вектора имеют вид . Поскольку векторы и а коллинеарны, то числа и пропорциональны, т.е.
или
-(2.4)уравнения прямой в в параметрической форме: для любого они определяют n чисел - координат текущей точки прямой.
Пусть и - векторы, определяемые соответственно направленными отрезками и (О - начало системы координат в ). Тогда равенство (2.4) можно записать в виде (векторная форма уравнения прямой)
. (2.5) Уравнения прямой (2.5) и плоскости (2.3) можно обобщить, рассматривая в множество точек, удовлетворяющих уравнению
,где , - точки из ;
и - векторы, определяемые соответственно направленными отрезками и ;
- линейно независимые векторы;
Такое множество точек в называется k-мерным линейным многообразием в [125]. С этой точки зрения прямая является одномерным линейным многообразием, а гиперплоскость - (п-1)-мерным линейным многообразием.
Расстоянием между точками и в называется длина вектора [125]. Тогда длина вектора , т.е. расстояние между точками и , есть
. Пусть в задана точка и гиперплоскость М, определяемая уравнением .
Расстоянием d от точки до гиперплоскости М называется , где , т.е. минимальная из длин векторов, определяемых направленными отрезками , где - заданная точка, а Р - произвольная точка гиперплоскости М [125]. Формула для вычисления имеет вид
. Отклонение h точки от гиперплоскости М вычисляется по формуле [127]
. Множество точек вида , отклонения которых положительны, составляют открытое n-мерное полупространство
, расположенное по одну сторону, а множество точек вида , отклонения которых отрицательны, - открытое полупространство
, расположенное по другую сторону гиперплоскости М. Присоединяя к открытым полупространствам гиперплоскость, получим так называемые [126] замкнутые полупространства. Одно из них состоит из точек, координаты которых удовлетворяют неравенству
, другое -
. Рассмотрим понятие полиэдрального множества.
Полиэдральным множеством в (n-мерным-полиэдральным множеством) [128] называется пересечение конечного множества замкнутых полупространств.
Заметим, что полиэдральное множество является выпуклым, так как полупространство является выпуклым и пересечение выпуклых множеств также является выпуклым множеством. (В частности, выпуклые плоские многоугольники и трехмерные многогранники являются примерами (конечных) полиэдральных множеств.)
С наглядной точки зрения полиэдральное множество представляет собой "кусок" пространства, высеченный несколькими гиперплоскостями (при п=3 рис. 2.1а). Этот кусок может простираться в бесконечность (рис. 2.1б). Может случиться, что полиэдральное множество целиком содержится в некоторой k-мерной плоскости, (рис. 2.1в при п=3, k=2; - базис в ).
а)б)в) Рис. 2.1. Примеры полиэдральных множеств
Если имеется т полупространств, задаваемых неравенствами
, (2.6) то полиэдральному множеству (пересечению полупространств (2.6)) принадлежат тол
- Київ+380960830922