Информационные модели и методы решения задач ортогонального раскроя-упаковки на основе конструктивных и нейросетевых подходов

• Автор: Корчевская, Оксана Валериевна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Красноярск
• Количество страниц: 147 с. : ил.

Содержание
ВВЕДЕНИЕ.
ГЛАВА 1 ПОСТАНОВКА, ПОСЛЕДОВАТЕЛЬНЫЕ И ПАРАЛЛЕЛНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДА Ч ОРТОГОНАЛЬНОЙ УПАКОВКИ И РАСКРОЯ.

1.1 Постановка и методы решения задач ортогональной упаковки и раскроя.

1.1.1 Задачи упаковки и раскроя.

1.1.2 Обзор методов решения задач линейного, прямоугольного и параллелснпсдюго раскрояупаковки.

1.1.3 Формирование приоритетного списка.

1.2 Использование искусственных нейронных сетей для решения задач комбинаторной оптимизации

1.2.1 Нейронные сети как универсальные аппроксимирующие устройства

1.2.2 Формализация нсйросстсвой технологии

1.2.3 Общие сведения о нейронных сетях Хоифилда.

1.2.4 Применение нейронной сети Хопфнлда для решения задач комбинаторной оптимизации
ГЛАВА 2 ИНФОРМАЦИОННЫЕ МОДЕЛИ ЗАДАЧ РАСКРОЯУГМКОВКИ
2.1 Обобщенная схема решения задач ортогонального раскрояупаковки
2.2 Модели задач одно, двух и трехмерного раскрояупаковки
2.3 Модель обработки данных с помощью нейронных сетей.
2.4 Формальное описание нейронной сети Хопфнлда.
ГЛАВА 3 КОНСТРУКТИВНЫЕ МЕТОДЫ РЕШЕНИЯ ТРЕХ И ДВУХМЕРНЫХ ЗАДАЧ РАСКРОЯУПАКОВКИ
3.1 Безотходные алгоритмы для задач раскрояупаковки
3.1.1 Алгоритм формирования безотходных двухмерных упаковок.
3.1.2 Алгоритм формирования безотходных трехмерных упаковок.
3.2 Метод плоскостей
3.2.1 Метод плоскостей для решения трехмерных задач раскроя упаковки .
3.2.2 Метод плоскостей для решения двухмерных задач раскроунаковки
3.3 Численный эксперимент.
3.3.1 Численный эксперимент для задач трехмерного ортогонального раскрояупаковки.
3.3.2 Численный эксперимент для задач двухмерного ортогонального раскрояупаковки.
ГЛАВА 4 ПРИМЕНЕНИЕ АППАРАТА ИСКУССТВЕННЫХ НЕЙРОННЫХ СЕТЕЙ К РЕШЕНИЮ ЗАДАЧ РАСКРОЯУПАКОВКИ.
4.1 Подход к определению совокупности прямоугольников, приводящей к минимизации занятой части полосы, для задачи двухмерного раскрояупаковки с помощью нейронных сетей Хопфнлда
4.2 Использование сигмоидных нейронных сетей для определения ШГКННХ границ решения задач раскроиупаковки.
ЗАКЛЮЧЕНИЕ
Литература


В настоящее время результаты исследования и разработок используются несколькими организациями, что подтверждается соответствующими актами о внедрении: ГОУ ВПО «Сибирский государственный технологический университет», логистической компанией «Транс-Бизнес». Апробация работы и публикации. Искусственный интеллект в XXI веке. Материалы и технологии XXI века», Пенза, . Публикации. Основные результаты работы опубликованы в печатных работах (из них 2 статьи в изданиях но списку ВАК), 1 свидетельство об официальной регистрации программы для ЭВМ. Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка использованных источников. Основное содержание работы изложено на 6 страницах текста, содержит рисунков, таблиц. Список используемых источников включает 3 наименования. Основное содержание работы. Во введении обоснована актуальность темы исследования в области задач упаковки и раскроя. Сформулированы цель работы и решаемые в ней задачи, представлена научная новизна и практическая значимость вынесенных на защиту результатов. В первой главе приведен обзор многообразия задач раскроя-упаковки и выделен класс задач, решаемых в рамках диссертационной работы. Приведены постановки наиболее известных задач «-мерного ортогонального раскроя-упаковки (п = 1, 2, 3), приведен обзор работ и методов решения задач раскроя-упаковки. Описано применение нейронных сетей для решения прикладных задач. Приведены достоинства и недостатки использования иейросстевой технологии. Определен класс нейронных сетей для решения задач комбинаторной оптимизации. Выявлен круг нерешенных задач. Во второй главе приведены информационные модели задач раскроя-упаковки. В настоящее время существуют различные представления п-мерных задач (« = 1, 2, 3) раскроя-упаковки. Их основные отличия - учет ряда ограничений, а также минимизация времени решения задачи. В работе приведена обобщенная модель обработки данных с помощью нейронных сетей в нотации ГОЕРО. Это позволяет наглядно представить и определить процессы обработки данных с помощью нейронных сетей при решении оптимизационных задач. Представлено формальное описание 0 и 1-й групп операций при нейросетевом исследовании с помощью нейронных сетей Хопфилда. Такой подход в общем случае позволяет формализовать технологию работы пользователя при нейросетевом исследовании. В третьей главе описан метод плоскостей, а также алгоритмы формирования безотходных двух и трехмерных упаковок. В работе представлен новый метод решения задач прямоугольного и параллелепипедного раскроя-упаковки - метод плоскостей. Представленные алгоритмы формирования безотходных двух и трехмерных упаковок базируются на условии получения определенного количества и размеров прямоугольников (коробок) для заданных размеров листа (параллелепипеда). Для оценки эффективности решения задач двух и трехмерного ортогонального раскроя-упаковки методом плоскостей проведена серия расчетов на основе методики Г. Ветера. За основу разбиения на различные классы предметов для задачи трехмерной упаковки взято: нижнее ограничение длины предметов - верхнее ограничение длины предметов v> (v, 'W <1, < v2 -W, і -1,. Офаничсние высоты предметов ? J2 (Пі • w