РАЗДЕЛ 2
ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ
В данном разделе дается определение класса задач оптимизационного геометрического проектирования, задается представление геометрической информации о двумерных геометрических объектах, осуществляется постановка основной задачи исследования. Рассматривается понятие Ф-функции. Приводятся основные ее свойства. Рассматриваются Ф-функции для базовых и составных ориентированных объектов. Приводится постановка и математическая модель основной оптимизационной задачи.
2.1. Класс задач оптимизационного геометрического проектирования
Задачи упаковки и раскроя возникают в различных отраслях науки и техники. Они связаны с обработкой геометрической информации и заключаются в поиске оптимального размещения геометрических объектов в заданных областях размещения. Данные задачи связаны с обработкой больших объемов геометрической информации, учетом большого количества различных требований и ограничений и выходят за рамки классической теории исследования операций.
Необходимость выделения таких задач в отдельный класс, так называемых задач геометрического проектирования, вызвано нестандартностью методов их моделирования и решения. Наиболее сложными среди данного множества задач являются задачи, которые состоят в поиске оптимального размещения (упаковки) конечного множества геометрических объектов произвольной пространственной формы в заданных областях при условии, что объекты могут вращаться.
Для аналитического описания реальных объектов вводится понятие геометрической информации. Геометрическая информация g о произвольном точечном множестве (геометрическом объекте) T [70] состоит из трех компонент: совокупности пространственных форм c, набора метрических характеристик m, которые определяют размеры пространственных форм c, параметров размещения v, которые задают месторасположение точечного множества S.
Геометрическая информация g может быть определена как однозначно, так и с точностью до заданных множеств "значений" некоторых параметров компонент c, m, v. Такие параметры называются независимыми переменными информации g и обозначаются как .
Определение 2.1. Отображение вида
называется задачей геометрического проектирования [70].
Определение 2.2. Оптимизационной задачей геометрического проектирования называется задача, в которой независимые переменные u определяются как решение определенной задачи оптимизации [70].
В оптимизационных задачах геометрического проектирования, необходимо найти экстремальное значение заданного функционала .
Как следует из определения 2.2, в общем случае задачи геометрического проектирования отличаются по следующим признакам:
- вид (особенности) геометрической информации g
- вид (особенности) отображения P
- вид функционала .
2.2. Представление геометрической информации об объектах в пространстве R2
В классе оптимизационных задач геометрического проектирования в качестве математических моделей материальных объектов выбираются непустые точечные множества T ? R2, которые удовлетворяют следующим требованиям:
1) - канонически замкнутое множество [106]
2) внутренность (int) и замыкание (cl) множества имеют один и тот же гомотопический тип [106]
Точечные множества, удовлетворяющие требованиям 1)-2), называются -объектами [70].
Как известно, пространственная форма линейно связного точечного множества в топологическом пространстве определяется его гомотопическим типом. Однако в евклидовом пространстве R2, топологическое определение пространственной формы является слишком грубым, поскольку при таком подходе не учитывается все разнообразие пространственных форм точечных множеств, порождаемых линейностью и метрикой евклидового пространства (например, не учитываются такие понятия как выпуклость, вогнутость, порядок гладкости, дифференцируемость и т.д.). Поэтому в евклидовом пространстве R2 пространственная форма линейно связного точечного множества задается не только гомотопическим типом, но и пространственной формой его границы.
Пусть
, (2.1)
где ; - -объект, компоненты линейной связности, границы которого имеют гомотопический тип топологической окружности в пространстве R2.
Геометрическую информацию о описывает кортеж , где - пространственная форма в пространстве R2, - пространственная форма компоненты линейной связности границы объекта , . Здесь , если гомотопический тип объекта - точка, и , если гомотопический тип объекта - топологическая окружность; - метрические характеристики , которые определяют размеры , причем количество элементов и их качество непосредственно зависят от ; - параметры размещения , ui ? R2 - вектор трансляции полюса объекта относительно собственной системы координат объекта , - угол поворота. Заметим, что полюс объекта совпадает с началом его собственной системы координат.
Для представления геометрической информации о произвольном -объекте базисной является геометрическая информация о компонентах линейной связности его границы.
Полагаем, что пространственная форма базового объекта (компоненты линейной связности) в пространстве R2 может принимать следующие значения: круг - ; прямоугольник - ; правильный многоугольник - ; выпуклый многоугольник - .
Таким образом, в общем случае, пространственная форма компоненты линейной связности принимает значения .
Полагаем, что метрические характеристики для соответствующих пространственных форм задаются следующим образом: , где - радиус ; , где a - полудлина, b - полуширина прямоугольника, , где - количество вершин многоугольника, - радиус описанной окружности, - угол поворота, , где - количество вершин многоугольника, ,..., - последовательность координат вершин многоугольника.
Таким образом, в общем случае метрические характеристики компоненты линейной связности задаются в виде . Обозначим через число элементов метрических характерис