Оптимизация размещения двумерных геометрических объектов на анизотропном материале с использованием методов математического программирования

• Автор: Петренко, Семен Васильевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Уфа
• Количество страниц: 115 с. : ил.

Содержание

Используемые в работе сокращения

Введение
Глава 1. Обзор существующих моделей и методов решения задачи нерегулярного размещения деталей сложных форм

1.1. Многообразие задач раскрояупаковки.

1.2. Классификация моделей раскрояупаковки

1.3. Основные определения и постановка задачи размещения плоских геометрических объектов

1.3.1 Основные понятия и определения

1.3.2 Общая постановка задачи размещения плоских ГО.

1.4. Методы решения задач упаковки ГО

1.4.1 Классификация методов решения задач нерегулярного размещения ГО .

1.4.2 Точные методы решения задач нерегулярного размещения ГО
1.4.3 Методы комбинаторной оптимизации и способ выборочного размещения и удаления.
1.4.4 Метод последовательного уточнения оценок
1.4.5 Решение задачи размещения плоских ГО на основе дискретнологического представления информации
1.5. Выводы по первой главе
Глава 2. Математическая модель задачи нерегулярного размещения плоских многоугольников в произвольной односвязной области и итерационный метод нахождения ее локального экстремума
2.1. Описание математической модели задачи.
2.2. Решение задачи поиска локального оптимума.
2.3. Иллюстрация работы метода.
2.4. Выводы по второй главе
Глава 3. Алгоритмы реализации разработанного метода нахождения локального экстремума задачи размещения невыпуклых ориентированных многоугольников в невыпуклой многоугольной области размещения
3.1. Алгоритм реализации итерационного метода нахождения локального экстремума.
3.2. Построение выпуклой оболочки для многоугольника.
3.3. Алгоритм разбиения невыпуклых многоугольников на выпуклые
3.4. Построение годографов для моделирования УВН и УРО.
3.5. Ликвидация взаимного пересечения годографов.
3.6. Выводы по третьей главе.
Глава 4. Комбинация алгоритма нахождения локального экстремума с приближенными методами последовательного одиночного размещения и его исследование.
4.1. Общая схема комбинации точного метода поиска локального экстремума и приближенных методов ПОР
4.2. Модификация предложенной схемы для классического жадного алгоритма
4.3. Модификация предложенной схемы для метода ПОР по принципу первый подходящий с упорядочиванием ППУ на основе ДЛПИ и ЦК.
4.4. Вычислительные эксперименты
4.5. Выводы по четвертой главе
Заключение
Список литературы


Применение точных алгоритмов поиска локального экстремума к результатам работы приближенных методов позволит получить математически обоснованный локальный оптимум задачи двумерного размещения объектов различного вида при раскрое и упаковке промышленных материалов, что приведет к большей экономии материальных ресурсов. Все выше сказанное определяет актуальность разработки эффективных и надежных методов поиска локального экстремума задачи двумерного размещения ГО различного вида при решении задач РУ промышленных материалов. Эта задача может быть решена посредством разработки эффективных математических моделей и их решения с помощью методов математического программирования. Целью работы является разработка методов и алгоритмов поиска локального экстремума задачи двумерного нерегулярного размещения ГО на анизотропном материале поворот ГО запрещен на основе заданного начального приближения, а также подходов к использованию разработанных методов в комбинации с приближенными методами. Разра ботать математическую модель представления задачи двумерного размещения ГО с ограничениями в виде линейных неравенств. Разра ботать методы и алгоритмы нахождения локального экстремума на основе построенной модели и подходов математического программирования при заданном начальном приближении. Разработать программное обеспечение для решения задачи поиска локального экстремума с учетом технологических ограничений. Провести вычислительный эксперимент для разработанных методов и алгоритмов. Методы исследования. Результаты исследований, выполненных в работе, базируются на основных положениях системного анализа, исследования операций, аналитической и вычислительной геометрии, машинной графики, а также структурного, модульного и объектноориентированного программирования. В процессе исследований использовались методы и инструменты организации комплексов программных средств, машинные эксперименты для оценки эффективности алгоритмов. Математическая модель задачи размещения плоских ориентированных многоугольников в невыпуклой области с ограничениями в виде специальной структуры на основе пересечений и объединений линейных неравенств. Метод нахождения локального экстремума для задачи размещения плоских многоугольников на анизотропном материале на основе идеологии активного набора с использованием построенной модели задачи. Алгоритмическое и программное обеспечение для реализации разработанного метода поиска локального экстремума задачи размещения деталей в заданной области с учетом технологических ограничений. Схема комбинации разработанного метода поиска локального экстремума с приближенными методами последовательного одиночного размещения. Результаты вычислительных экспериментов для созданного метода поиска локального экстремума. Область допустимых решений математической модели задачи размещения плоских ориентированных многоугольников в многоугольной области задается в аналитическом виде как специальная структура неравенств, имеющая вид пересечения систем и объединений линейных неравенств. Разработанный итерационный метод поиска локального экстремума на основе идеологии активного набора применим не только к системам, но и к специальным структурам линейных неравенств, включающих как пересечение, так и объединение линейных неравенств. Создана схема комбинации точного метода поиска локального экстремума с приближенными методами последовательного одиночного размещения. Такой подход позволяет не только улучшать результат, полученный приближенными методами, но и получать математически обоснованное решение практических задач РУ. Практическая ценность работы состоит в создании математического и программного обеспечения для решения задач построения двумерных планов раскрояупаковки, с учетом технологических ограничений, возникающих при решении прикладных задач. Работы в данном направлении проводились автором в Уфимском государственном авиационном техническом университете в гг. РФФИ 7 и 0. Рекламном агентстве г. Уфа. Апробация работы. Публикации. По теме диссертации опубликованы 7 работ, в том числе 5 статей и 2 материалов конференций. Структура работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем основной части диссертации составляет 5 с.