Математическая модель и метод решения задачи размещения трехмерных многогранных объектов

• Автор: Черноморец, Андрей Алексеевич
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1993
• Место защиты: Харьков
• Количество страниц: 135 с.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ .
1. ПОСТАНОВКА ЗАДАЧИ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ ТРЕХМЕРНЫХ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ И НЕКОТОРЫЕ

ЕЕ ОСОБЕННОСТИ.

1.1. Постановка общей задачи размещения геометрических объектов .

1.2. Формализация описания объектов в задаче размещения

1.3. Математическая постановка задачи размещения трехмерных объектов с использованием теории Ффункций

Выводы по главе .

2. ФОРМАЛЬНОЕ ОПИСАНИЕ ГЕОМЕТРИЧЕСКИХ ОГРАНИЧЕНИИ В ЗАДАЧЕ РАЗМЕЩЕНИЯ ТРЕХМЕРНЫХ МНОГОГРАННЫХ
ОБЪЕКТОВ.

2.1. Описание поверхности о 0уровня Ффункции

с помощью набора псевдограней .
2.1.1. Принцип построения поверхности о
2.1.2. Основные правила построения псевдограней .
2.2. Правила определения избыточных псевдограней . .
2.3. Исследование псевдограней на принадлежность , поверхности о
2.3.1. Построение сечения объекта, ограниченного поверхностью и .
2.3.2. Алгоритмы нахождения внутренних контуров границы отдельной грани поверхности с.
2.4. Особенности построения поверхности 0уровня
Ффункции многогранников с произвольными
гранями.
Выводы по главе.
МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ МНОГОГРАННИКОВ В .1
3.1. Двухэтапное решение задачи оптимального размещения многогранников в
пространстве Р3.
3.2. Математическая модель задачи размещения прямоугольных гиперпараллелепипедов
пространства Рр.
3.3. Метод поиска глобального оптимума в задаче размещения прямоугольных гиперпараллелепипедов . .
3.4. Правила отсечения вершин дерева решений задачи оптимального размещения гиперпараллелепипедов . .
. 3.4.1. Определение одинаковых вариантов
размещения гиперпараллелепипедов
3.4.2. Определение симметрий на множестве размещений
3.4.3. Вероятностное правило отсечения.
3.5. Схема метода решения задачи размещения
произвольных многогранников пространства 13 . . .
Выводы по главе .
ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ ИССЛЕДОВАНИИ .
4.1. Комплекс программ Поверхность построения поверхности 0уровня Ффункции произвольных
многогранных объектов .
4.2. Комплекс программ Оптимум поиска глобального
оптимума в задаче размещения прямоугольных
гиперпараллелепипедов .
4.3. Результаты решения тестовых примеров
4.3.1. Примеры построения поверхности Ффункции
4.3.2. Примеры размещения параллелепипедов . . . Выводы по главе .
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Важным направлением развития исследуемой проблемы явг ляется разработка методов решения задачи нерегулярного размещения, в которых производится поиск оптимального расположения объектов произвольной Форш в некоторой области пространства при соблюдении ограничений на положение объектов. Данные ограничения задаются обычно в виде условий взаимного попарного непересечения, могут быть также заданы ограничения в виде минимальных или максимальных допустимых расстояний, областей запрета и т. Фундаментальные исследования в этом направлении выполнены В. Л.Рвачевым Г-]. Разработанная им теория Р-функций позволила автоматически описывать геометрические тела сложной формы. В работах [-] приведены основанные на данной теории методы формализации и решения некоторых задач размещения. Затем появляются работы Ю. Г.Стояна и его школы [,-], в которых исследуются вопросы формализации и решения задач размещения на основе понятий векторной функции плотного размещения и ее годографа [,1. Дальнейшие исследования привели к разработке теории ф-функций и ее поверхностей г-уровня [,1. Данные работы явились теоретической основой описанных в 2-1 алгоритмов и программ размещения на плоскости геометрических объектов сложной формы. Особое место среди задач размещения занимают задачи оптимального размещения прямоугольных объектов в прямоугольной области со сторонами, параллельными сторонам размещаемых объектов. Это объясняется простотой задания условий взаимного нелересечения и условий размещения в области. Для случая пространства Р? Работ, посвященных вопросам размещения трехмерных объектов, опубликовано значительно меньше, чем для решения задачи размещения плоских объектов. Особое место-среди них занимают работы Ю. Г.Стояна и его учеников [,-1. В данных работах рассмотрены проблемы размещения в основном простейших тел -параллелепипедов, цилиндров, шаров, а также составных тел, являющихся объединением перечисленных выше простейших тел. В то же время представляет интерес разработка эффективных методов размещения трехмерных тел произвольной формы. Диссертационная работа продолжает исследования, проводимые в Институте проблем машиностроения АН Украины (ИПМаш АН Украины) под руководством члена-корреспондента АН Украины Ю. Г.Стояна. Работа выполнялась в период с г. Математическое моделирование сложных технических систем модульного типа" (? Развитие методов автоматического эскизного компоновочного проектирования автономной электрофизической установки" с Научно-исследовательским институтом электро-физической аппаратуры им. Д.В. Ефремовз (Российская Федерация, Л ГР 9); . ИПМаш АН Украины. Р3. Ф-функций. На основании проведенного анализа особенностей ! Кр, р > 3. Сформулированы логические правила отсечения вариантов размещения, заведомо не определящих экстремальные решения задачи. Степень достоверности результатов проведенных исследовании. Теоретические исследования, выполненные в диссертационной раооте, основаны на фундаментальных положениях теории Ф-функций и теории оптимизации. Достоверность выводов и результатов диссертационных исследований основана на доказательствах приведенных в работе теорем, а также подтверждается их удовлетворительным сравнением с результатами экспериментов, выполненных на предприятии п/я А-, и сопоставлением с известными решениями ряда задач. Результата, полученные в диссертации (алгоритм построения условий взаимного непересечения трехмерных объектов, : логические правила отсечения вариантов размещения, не определяющих экстремальные решения задачи), были использованы при разработке комплекса программ трехмерных упаковок и внедрены в 1S, гг. А- с общим экономическим эффектом ,8 тыс. Апробация работы. Всесоюзной конференции "Интегрированные системы автоматизированного проектирования" (г. Вологда, г. IV областной межотраслевой научно-технической конференции "Роботизация технологических процессов в машиностроении и приборостроении" (г. Житомир, г. IV Всесоюзной конференции "Методы и средства обработки сложной графической информации" (г. Нижний Новгород, г. Украины (г. Харьков, г. Публикации. Структура и объем диссертации. Работа содержит введение, четыре главы, заключение, список литературы из 8 наименований, рисунков и 3 таблицы; всего - 5 страниц.