Содержание к диссертации
ВВЕДЕНИЕ 5
1. ПОСТАНОВКА ЗАДАЧИ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ ТРЕХМЕРНЫХ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ И НЕКОТОРЫЕ ЕЕ ОСОБЕННОСТИ 12
1.1. Постановка общей задачи размещения геометрических объектов 12
1.2. Формализация описания объектов в задаче размещения 16
1.3. Математическая постановка задачи размещения трехмерных объектов с использованием теории Ф-фуикций 23
Выводы по главе 27
2. ФОРМАЛЬНОЕ ОПИСАНИЕ ГЕОМЕТРИЧЕСКИХ ОГРАНИЧЕНИЙ В ЗАДАЧЕ РАЗМЕЩЕНИЯ ТРЕХМЕРНЫХ МНОГОГРАННЫХ ОБЪЕКТОВ 28
2.1. Описание поверхности и О-уровня Ф-функции с помощью набора "псевдограней" 28
2.1.1. Принцип построения поверхности о) 28
2.1.2. Основные правила построения "псевдограней" 31
2.2. Правила определения избыточных "псевдограней" 36
2.3. Исследование "псевдограней" на принадлежность поверхности ы 50
2.3.1. Построение сечения объекта, ограниченного поверхностью и 50
2.3.2. Алгоритмы нахождения внутренних контуров границы отдельной грани поверхности и 56
2.4. Особенности построения поверхности О-уровня Ф-функции многогранников с произвольными гранями 61
Выводы по главе 69
3. МЕТОДУ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ МНОГОГРАННИКОВ В R3 1 70і
3.1. Двухэтапное решение задачи оптимального размещения многогранников в пространстве R3 70
3.2. Математическая модель задачи размещения * -"' прямоугольных гиперпараллелепипедов пространства Rp ; 72
3.3. Метод поиска глобального оптимума в задаче размещения прямоугольных гиперпараллелепипедов , 82
3.4. Правила отсечения вершин дерева решений задачи \ оптимального размещения гиперпараллелепипедов 1 84
. 3.4.1, Определение одинаковых вариантов , размещения гиперпараллелепипедов .1 85
3.4.2. Определение симметрии на множестве ! размещений 94
3.4.3. Вероятностное правило отсечения І00
3.5. Схема метода решения задачи размещения ' произвольных многогранников пространства R3 102
Выводы по главе . І05
4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ ИССЛЕДОВАНИИ 106
4.1. Комплекс программ "Поверхность" построения г поверхности 0-уровня Ф-функции произвольных ! многогранных оСъектов '106
4.2. Комплекс программ "Оптимум" поиска глобального оптимума в задаче размещения прямоугольных гиперпараллелепипедов 109
4.3. Результаты решения тестовых примеров Ill
4.3.1. Примеры построения поверхности Ф-функции 111
4.3.2. Примеры размещения параллелепипедов . 114
Выводы по главе 120
ЗАКЛЮЧЕНИЕ ' . 121
ЛИТЕРАТУРА 123
Введение к работе
Актуальность проблемы. Успехи в развитии современного ігрограммного и аппаратного обеспечения средств вычислительной техники позволяют в короткие сроки эффективно решать многие проблемы, возникающие при автоматизации проектно-конструкторских работ. При решении многих задач проектирования необходимо учитывать их особенности, связанные с целенаправленным преобразованием геометрической информации в соответствии с некоторым критерием оптимальности, что позволяет выделить эти задачи в класс задач геометрического проектирования [1]. К числу задач геометрического проектирования относятся задачи оптимального размещения геометрических объектов, возникающие при компоновке радиоэлектронных плат [2-4], эскизном проектировании технических систем [5], разработке генеральных планов промышленных предприятий [6,7], оптимальном раскрое материалов Е8-10], размещении грузов на судах и самолетах [11-13] и т.д.
Сложность задач оптимального размещения геометрических объектов потребовали для своего решения разработки специальных математических методов и алгоритмов [14-16].
Большое исследование в области геометрии было проведено Е.С.Федоровым при изучении кристаллов как природных многогранников [17,18]. В работе [16] П.Л.Чебшев рассмотрел вопросы конструирования выкроек и разверток при производстве одежды.
Начало теоретическим исследованиям в области размещения геометрических тел было положено при решении наиболее простых задач, в которых отсутствует собственно система геометрических ограничений. Для области размещения, заданной в виде набора фиксированных позиций, рассматривалась дискретно-оптимизационная задача типа квадратичной задачи о назначениях, математические методы решения которой исследованы достаточно широко [191.
Одной из первых фундаментальных работ, посвященных изучению методов размещения геометрических тел с учетом их формы и размеров, является монография Л.В.Канторовича и В.А.Залгал-лера [201. Изложенные в ней методы и алгоритмы построения оптимальных планов раскроя линейных материалов и прямоугольных листов на прямоугольные заготовки основаны на теории разрешающих множителей (индексов), предложенной Л.В.Канторовичем в работах [21-22]. Результаты этих и других работ [23-27] предвосхитили развитие теории линейного и динамического программирования [14,28,29].
Вопросы, связанные с определением плотнейших укладок и редчайших покрытий области (обычно всего пространства) трансляциями одной фигуры, были выделены в виде теории дискретной и комбинаторной геометрии [30-32]. Многие задачи комбинаторной геометрии не решены до настоящего времени, хотя их постановки известны давно (например задача плотнейшей упаковки равных шаров в Rn при п 3). Постановки и решения некоторых основных задач комбинаторной геометрии приведены в [33-35], полученные для них схемы размещения являются регулярными.
Интенсивное развитие математических методов решения экстремальных задач [36-39] (методов линейного и динамического программирования, выпуклого анализа [40], дискретной оптимизации [31,41], а также численных методов синтеза оптимальных систем [19,42]) обусловили успехи в выборе оптимальных решений задач геометрического проектирования [43]. Разработка проблемы оптимального размещения геометрических объектов осуществляется по различным направлениям.
Алгоритмы регулярного размещения объектов сложной формы в прямоугольной области, в неограниченной полосе и в ограниченных областях пространства R2, а также алгоритмы фигурного раскроя описаны в работах [44-47].
Публикации [48-501 посвящены созданию методов прямоугольного раскроя, ориентированных на гильотинную технологию резки материала.
Важным направлением развития исследуемой проблемы явг ляется разработка методов решения задачи нерегулярного размещения, в которых производится поиск оптимального расположения объектов произвольной формы в некоторой области пространства при соблюдении ограничений на положение объектов. Данные ограничения задаются обычно в виде условий взаимного попарного непересечения, могут быть также заданы ограничения в виде минимальных или максимальных допустимых расстояний, областей запрета и т.д.
Фундаментальные исследования в этом направлении выполнены В.Л.Рвачевым [51-54]. Разработанная им теория R-функций позволила автоматически описывать геометрические тела сложной формы. В работах [55-58] приведены основанные на данной теории методы формализации и решения некоторых задач размещения. Затем появляются работы Ю.Г.Стояла и его школы [15,59-65], в которых исследуются вопросы формализации и решения задач размещения на основе понятий векторной функции плотного размещения и ее годографа [15,64]. В работах [66-683 приведены результаты, устанавливающие связь между суммой Минковского двух тел [69] и годографом их векторной функции плотного размеще ния. Дальнейшие исследования привели к разработке теории Ф-функций и ее поверхностей г-уровня [70,71]- Данные работы явились теоретической основой описанных в [72-74] алгоритмов и программ размещения на плоскости геометрических объектов сложной формы.
Особое место среди задач размещения занимают задачи оптимального размещения прямоугольных объектов в прямоугольной области со сторонами» параллельными сторонам размещаемых объектов- Это объясняется простотой задания условий взаимного нелересечения и условий размещения в области. Для случая пространства R2 для решения данной задачи разработаны точные методы решения [75,76], основанные на использовании схемы метода ветвей и границ [77].
Работ, посвященных вопросам размещения трехмерных объектов, опубликовано значительно меньше» чем для решения задачи размещения плоских объектов. Особое место-среди них занимают работы Ю.Г.Стояна и его учеников 167,78-831. В данных работах рассмотрены проблемы размещения в основном простейших тел -параллелепипедов, цилиндров, шаров, а также составных тел, являющихся объединением перечисленных выше простейших тел. В то же время представляет интерес разработка эффективных мето дов размещения трехмерных тел произвольной формы.
Диссертационная работа продолжает исследования, проводимые в Институте проблем машиностроения АН Украины (ИПМаш АН Украины) под руководством члена-корреспондента АН Украины Ю.Г.Стояна.
Работа выполнялась в период с 1988 г. по 1992 г. в отделе математического моделирования и оптимального проектирования ИПМаш АН Украины в соответствии с планом научно-технических работ по:
- госбюджетной теме "Разработка математических методов геометрического проектирования (Jfi ГР 01860049704);
- госбюджетной теме Математическое моделирование сложных технических систем модульного типа" ( ГР 01900009448);
- хоздоговорной теме "Развитие методов автоматического эскизного компоновочного проектирования автономной электрофизической установки" с Научно-исследовательским институтом элехтро-физической аппаратуры им. Д.В. Ефремова (Российская Федерация, № ГР 0191Q0178G9); : и планом обучения в аспирантуре ИПМаш АН Украины,
Целью работы является разработка математической модели и метода решения задачи оптимального размещения трехмерных многогранных геометрических объектов в заданных многогранных областях пространства к3•
Научная новизна результатов диссертационной работы состоит в следующем:
- разработана и исследована математическая модель рассматриваемой задачи оптимального нерегулярного размещения многогранных объектов, основанная на использовании аппарата Ф-функций. На основании проведенного анализа особенностей ! математической модели предложен метод решения данной задачи;
- предложен алгоритм реализации условий взаимного непе-ресечения произвольных, невыпуклых многогранников простран1-ства R3 на основе поверхностей 0-уровня Ф-функций; разработан алгоритм построения многосвязных граней по-верхности 0-уровня Ф-функции;
- разработан алгоритм точного решения задачи размещения прямоугольных гиперпараллелепипедов в прямоугольном гиперла пространства Rp, р 3. Сформулированы логические правила отсечения вариантов размещения, заведомо не определяющих экстремальные решения задачи.
Степень достоверности результатов проведенных исследовании. Теоретические исследования, выполненные в диссертационной раооте, основаны на фундаментальных положениях теории Ф-функций и теории оптимизации. Математическая модель и метод решения поставленной задачи обоснованы исходя из известных, апробированных теоретических и экспериментальных результатов» полученных ранее при разработке методов оптимальных размещений плоских и объемных объектов- Достоверность выводов и ре-зультатов диссертационных исследований основана на доказательствах приведенных в работе теорем, а также подтверждается их удовлетворительным сравнением с результатами экспериментов, выполненных на предприятии п/я А-7682, и сопоставлением с известными решениями ряда задач.
Практическая значимость работы состоит в том, что разработанные метод, алгоритмы» а также комплексы программ; ; Поверхность" - для построения поверхности 0-уровня Ф-функции произвольных многогранных объектов и "Оптимум" - для поиска глобального оптимума в задаче размещения прямоугольных гиперпараллелепипедов в дальнейшем можно использовать для решения различных задач оптимального размещения, возникающих в про г цессе автоматизации проектирования в машиностроении, строительстве, радиоэлектронной промышленности и на транспорте, а также для решения задач оптимального распределения ресурсов, которые могут быть сведены к задачам размещения геометрических объектов. Эти программные комплексы могут быть применены, например, при компоновочном проектировании и построении схем загрузки транспортных средств (морских и воздушных судов, железнодорожных вагонов, контейнеров и т.п.), что позволит сократить время решения указанных выше зэдач, а также повысить эффективность использования соответствующих натериалоз и помещении.
Результаты, полученные в диссертации (алгоритм построения условий взаимного непересечения трехмерных объектов, логические правила отсечения вариантов размещения, не определяющих экстремальные решения задачи), были использованы при разработке комплекса программ трехмерных упаковок и внедрены в 1S88, 1989 гг. на предприятии п/я А-7682 с общим экономическим эффектом 37,8 тыс. руб. Апробация работы. Основные положения работы докладывались и обсуждались на
- Всесоюзной конференции "Интегрированные системы авто- : матизированного проектирования" Сг. Вологда, 198Э г.); :
- IV областной межотраслевой научно-технической конференции "Роботизация технологических процессов в машинострое- ; нии и приборостроении" (г. Житомир, 1991 г.);
- IV Всесоюзной конференции "Методы и средства обработки сложной графической информации" (г. Нижний Новгород, 1991г.)J - XV конференции молодых ученых и специалистов ИПМаш АН і Украины (г. Харьков, 1987 г.).
Публикации. Основные результаты диссертационной работы опубликованы в 8 работах [98,102,103,104,113,116,117,1181.; .
Структура и объем диссертации. Работа содержит введение, четыре главы, заключение, список литературы из 118 наиненова- ний, 26 рисунков и 3 таблицы; всего - 135 страниц. ;