Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем

• Автор: Мухачева, Анна Сергеевна
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Уфа
• Количество страниц: 117 с. : ил.

Глава 1. Задачи одно и двухмерного раскрояупаковки и методы их решения. Эвристические методы расчета одномерного раскрояупаковки. Точные методы расчета одномерного раскрояупаковки. Задача прямоугольной упаковки. Эвристические методы решения задачи прямоугольной негильотинной упаковки. Точные методы решения задачи негильотинного прямоугольного раскроя. Основные результаты главы 1. Глава 2. Краткая характеристика исследуемых методов решения одномерного раскрояупаковки. Метод последовательного уточнения оценок V. Модифицированный метод ветвей и границ МКК. Эксперименты для одномерного раскрояупаковки с методами V и V
2. Тестовые задачи. Результаты эксперимента с методами V и V. Тестовые задачи. Результаты эксперимента с методом МКК. Глава 3. Линейная структура прямоугольной упаковки. Топологические свойства прямоугольных упаковок. Основные результаты и выводы главы 3. Глава 4. Вычислительный эксперимент. Вычислительный эксперимент 1. Утверждение 2. Элементы iv любого кортежа v различные.


Если i е Iv и i у, то е 7v. Процесс построения , отвечающего прямоугольной упаковки является элементарным. Однако процесс поиска оптимального по исходным данным задачи является трудной задачей. Это обстоятельство побеждает к разработке эвристических алгоритмов полиномиальной сложности. Линейный раскрой, отвечающий исходным данным в задаче и удовлетворяющий условиям 1 и 2 назовем ослабленным прямоугольно ориентированным линейным раскроем i ,
Относительно . Утверждение 7. Для того, чтобы . Далее рассматриваются топологические свойства прямоугольных упаковок, на изучении которых базируется детерминированный алгоритм поиска эквивалентного Сформулированы и доказаны условия существования эквивалентного Алгоритм проверки указанных условий и построения искомого основан на структурных преобразованиях внутри кортежей, названных процедурой перестройка , . Таким образом, детерминированный алгоритм сводится к выполнению следующих этапов. Этап 1. Решение задачи линейного раскроя с дополнительными ограничениями 1 и 2 методом V блочное представление . Этап 2. Построение прямоугольной упаковки с помощью метода ,последовательно одиночного размещения с процедурой перестройка. Если все необходимые процедуры перестройки оказались выполненными, то полученный является эквивалентным . В противном случае получаем с длиной Д, эта упаковка используется в качестве верхней границы длины занятой части полосы. Далее, в главе 3 приведен генетический алгоритм, который основан также на . Исходная информация , и i,.