📄Работа №30261
Тема: Решение задачи построения негильотинного размещения набора прямоугольников на листе на основе перебора перестановок
Тип работы
Магистерская диссертация
Предмет
Информатика и вычислительная техника
Объем:
42 листов
Год:
2018
Просмотров:
775
4900
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 3
ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ НЕГИЛЬОТИННОГО РАЗМЕЩЕНИЯ
НАБОРА ПРЯМОУГОЛЬНИКОВ НА ПОЛУПОЛОСЕ 7
1.1. Модель размещения набора прямоугольников на листе 7
1.2. Метод ветвей и границ 11
ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА 14
2.1. Фиксация переменных для очевидных случаев 14
2.2. Метод перебора перестановок. 16
2.3. Алгоритм решения задачи 17
ГЛАВА 3. РЕАЛИЗАЦИЯ АЛГОРИТМА 20
3.1. Программное обеспечение для реализации алгоритма 20
3.2. Вычислительные эксперименты 24
ЗАКЛЮЧЕНИЕ 34
СПИСОК ЛИТЕРАТУРЫ 35
ПРИЛОЖЕНИЕ 1
ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ НЕГИЛЬОТИННОГО РАЗМЕЩЕНИЯ
НАБОРА ПРЯМОУГОЛЬНИКОВ НА ПОЛУПОЛОСЕ 7
1.1. Модель размещения набора прямоугольников на листе 7
1.2. Метод ветвей и границ 11
ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА 14
2.1. Фиксация переменных для очевидных случаев 14
2.2. Метод перебора перестановок. 16
2.3. Алгоритм решения задачи 17
ГЛАВА 3. РЕАЛИЗАЦИЯ АЛГОРИТМА 20
3.1. Программное обеспечение для реализации алгоритма 20
3.2. Вычислительные эксперименты 24
ЗАКЛЮЧЕНИЕ 34
СПИСОК ЛИТЕРАТУРЫ 35
ПРИЛОЖЕНИЕ 1
📖 Введение
Задача размещения прямоугольников является одним из типов задачи оптимизации. Задача оптимизации - это задача получения наилучших показателей или значений параметров объектов, при заданных условиях. Попытки найти лучшие решения для существующих прикладных задач привели к формированию специализированных математических методов, в восемнадцатом столетии были приняты математические основы оптимизации (численные методы, вариационное исчисление и другие). Но до второй половины двадцатого столетия методы оптимизации в многочисленных сферах науки и техники использовались весьма нечасто, так как фактическое применение математических методов оптимизации требовало большой вычислительной деятельности, которую было трудно, а иногда и невозможно, реализовать без применения вычислительных машин, которые существуют в наши дни.
Математической постановке задачи размещения прямоугольников на листе уже почти восемьдесят лет ([1],[2]), но она не теряет своей актуальности, так как её решение представляет большой практический интерес. Задача оптимального размещения деталей, как задача экономного использования промышленных материалов, с каждым годом становится все более актуальной. Например, задача минимизации отходов материала при производстве возникает во многих областях промышленности, для оптимального размещения товаров на складах для хранения и при транспортировке, для оптимального размещения статей в газетах и журналах. А значит, возрастает необходимость поиска новых эффективных алгоритмов решения данной задачи.
Решением важнейших производственных задач размещения занимались такие ученые как Л.В. Канторович и В. А. Залгаллер. Они первыми предложили использование методов линейного программирования с неявно заданной матрицей ограничений [3].
В наши дни для решения задачи предлагаются различные оптимизационные алгоритмы. Например, Э.А. Мухачевой и В.М. Картаком предложен метод ветвей и границ для решения одномерной задачи упаковки [2]. Асимптотически точные решения описаны в работах Э.Х. Гимади, а М.И. Свириденко разработана асимптотическая полиномиальная аппроксимационная схема для решения задачи гильотинного размещения [4]. Все эти задачи относятся к классу NP-трудных проблем и не имеют алгоритмов, имеющих полиномиальную сложность и позволяющих решить задачу за приемлимое на практике время.
Задача оптимального размещения прямоугольников на листе состоит в том, чтобы определить, возможно ли размещение заданного набора прямоугольников на листе с заданной шириной и длиной и, если размещение возможно, определить оптимальный способ размещения прямоугольников на листе, то есть для каждого прямоугольника определить его положение.
В настоящее время достаточно хорошо изучены задачи нефигурного (линейного и прямоугольного гильотинного) раскроя, то есть когда возможными являются только сквозные линии от одного края листа до другого, параллельные кромкам материала. В данной работе будет рассмотрен негильотинный раскрой.
Задача прямоугольного размещения на листе также является NP- полной задачей оптимизации [5] и поиск её решения - весьма трудоёмкий процесс. Однако на практике часто возникает необходимость получении решения (например, при раскрое дорогостоящих материалов), поэтому для её решения разрабатываются эвристические алгоритмы [3-7], то есть алгоритмы, дающие приближенное решение задачи с определенной точностью, но не гарантирующие оптимальной упаковки для любого набора данных.
В [4] и [5] описаны различные постановки задачи прямоугольного размещения и подходы к её решению. В [5] предложен обзор моделей, оценкок, приближенных и точных алгоритмов, реализаций метаэвристик для ориентированного случая задачи прямоугольной упаковки в полосу и в контейнеры. В [3] описана постановка задачи упаковки прямоугольников и кругов в терминах нелинейного целочисленного программирования, а также предложены способы кодировки положения фигур на плоскости, в частности, двухконтактная кодировка, где положение фигуры зависит от положения соседних фигур.
В [7] модель задачи представлена в виде задачи нелинейного программирования, метод решения основан на применении жадных алгоритмов и многоступенчатом сведении задачи к задачам меньших порядков. В [6] для неориентированного размещения прямоугольников на полосе применяется генетический алгоритм, который также разбивает исходную задачу на подзадачи меньшей размерности.
В [1] предложены линейные частично булевы модели задачи негильотинного размещения набора прямоугольников на листе и полуполосе. Для получения точного решения был применен метод ветвей и границ Лэнд и Дойг и эвристические приемы для уменьшения трудоемкости задачи. Модель, описанная в статье [1], была выбрана в качестве основы для разработки алгоритма решения задачи методом перебора перестановок прямоугольников. Так как поиск точного решения задачи занимает достаточно большое время, предполагается, что метод перебора перестановок, то есть решение задачи с учетом расположения прямоугольников относительно друг друга, позволит улучшить эффективность поиска точного решения задачи.
Целью данной работы является решение задачи негильотинного размещения набора прямоугольников на листе методом перебора перестановок.
Для достижения этой цели были поставлены следующие задачи:
- изучить имеющиеся модели и методы решения задачи негильотинного размещения набора прямоугольников на листе;
- разработать алгоритм метода ветвей и границ для нахождения оптимального решения задачи негильотинного размещения набора прямоугольников на листе
- реализовать разработанный алгоритм;
- разработать генератор задач негильотинного размещения прямоугольников на листе с обширным набором вариантов для удобства исследования эффективности реализации алгоритма;
- провести вычислительные эксперименты и проанализировать вычислительную эффективность разработанного алгоритма на наборе задач.
Математической постановке задачи размещения прямоугольников на листе уже почти восемьдесят лет ([1],[2]), но она не теряет своей актуальности, так как её решение представляет большой практический интерес. Задача оптимального размещения деталей, как задача экономного использования промышленных материалов, с каждым годом становится все более актуальной. Например, задача минимизации отходов материала при производстве возникает во многих областях промышленности, для оптимального размещения товаров на складах для хранения и при транспортировке, для оптимального размещения статей в газетах и журналах. А значит, возрастает необходимость поиска новых эффективных алгоритмов решения данной задачи.
Решением важнейших производственных задач размещения занимались такие ученые как Л.В. Канторович и В. А. Залгаллер. Они первыми предложили использование методов линейного программирования с неявно заданной матрицей ограничений [3].
В наши дни для решения задачи предлагаются различные оптимизационные алгоритмы. Например, Э.А. Мухачевой и В.М. Картаком предложен метод ветвей и границ для решения одномерной задачи упаковки [2]. Асимптотически точные решения описаны в работах Э.Х. Гимади, а М.И. Свириденко разработана асимптотическая полиномиальная аппроксимационная схема для решения задачи гильотинного размещения [4]. Все эти задачи относятся к классу NP-трудных проблем и не имеют алгоритмов, имеющих полиномиальную сложность и позволяющих решить задачу за приемлимое на практике время.
Задача оптимального размещения прямоугольников на листе состоит в том, чтобы определить, возможно ли размещение заданного набора прямоугольников на листе с заданной шириной и длиной и, если размещение возможно, определить оптимальный способ размещения прямоугольников на листе, то есть для каждого прямоугольника определить его положение.
В настоящее время достаточно хорошо изучены задачи нефигурного (линейного и прямоугольного гильотинного) раскроя, то есть когда возможными являются только сквозные линии от одного края листа до другого, параллельные кромкам материала. В данной работе будет рассмотрен негильотинный раскрой.
Задача прямоугольного размещения на листе также является NP- полной задачей оптимизации [5] и поиск её решения - весьма трудоёмкий процесс. Однако на практике часто возникает необходимость получении решения (например, при раскрое дорогостоящих материалов), поэтому для её решения разрабатываются эвристические алгоритмы [3-7], то есть алгоритмы, дающие приближенное решение задачи с определенной точностью, но не гарантирующие оптимальной упаковки для любого набора данных.
В [4] и [5] описаны различные постановки задачи прямоугольного размещения и подходы к её решению. В [5] предложен обзор моделей, оценкок, приближенных и точных алгоритмов, реализаций метаэвристик для ориентированного случая задачи прямоугольной упаковки в полосу и в контейнеры. В [3] описана постановка задачи упаковки прямоугольников и кругов в терминах нелинейного целочисленного программирования, а также предложены способы кодировки положения фигур на плоскости, в частности, двухконтактная кодировка, где положение фигуры зависит от положения соседних фигур.
В [7] модель задачи представлена в виде задачи нелинейного программирования, метод решения основан на применении жадных алгоритмов и многоступенчатом сведении задачи к задачам меньших порядков. В [6] для неориентированного размещения прямоугольников на полосе применяется генетический алгоритм, который также разбивает исходную задачу на подзадачи меньшей размерности.
В [1] предложены линейные частично булевы модели задачи негильотинного размещения набора прямоугольников на листе и полуполосе. Для получения точного решения был применен метод ветвей и границ Лэнд и Дойг и эвристические приемы для уменьшения трудоемкости задачи. Модель, описанная в статье [1], была выбрана в качестве основы для разработки алгоритма решения задачи методом перебора перестановок прямоугольников. Так как поиск точного решения задачи занимает достаточно большое время, предполагается, что метод перебора перестановок, то есть решение задачи с учетом расположения прямоугольников относительно друг друга, позволит улучшить эффективность поиска точного решения задачи.
Целью данной работы является решение задачи негильотинного размещения набора прямоугольников на листе методом перебора перестановок.
Для достижения этой цели были поставлены следующие задачи:
- изучить имеющиеся модели и методы решения задачи негильотинного размещения набора прямоугольников на листе;
- разработать алгоритм метода ветвей и границ для нахождения оптимального решения задачи негильотинного размещения набора прямоугольников на листе
- реализовать разработанный алгоритм;
- разработать генератор задач негильотинного размещения прямоугольников на листе с обширным набором вариантов для удобства исследования эффективности реализации алгоритма;
- провести вычислительные эксперименты и проанализировать вычислительную эффективность разработанного алгоритма на наборе задач.
✅ Заключение
В данной работе были исследованы методы решения задачи размещения прямоугольников на листе и предложена реализация алгоритма решения задачи негильотинного размещения прямоугольников на листе методом перебора перестановок.
Нельзя не отметить, что использование метода ветвей и границ позволило сократить время решения тестовых задач по сравнению с решением задач полным перебором, благодаря фиксации булевых переменных перед решением задачи.
Однако использованных методов недостаточно для значительного ускорения работы программы при увеличении размерности задачи. Тем не менее, для наборов с малым количеством прямоугольников задача решается быстро.
В дальнейшем возможно применение методов распараллеливания алгоритма для ускорения решения поставленной задачи, а также изменение алгоритма ветвления таким образом, чтобы не решать затратные и бесперспективные задачи, что увеличит эффективность работы алгоритма для задач большей размерности.
Нельзя не отметить, что использование метода ветвей и границ позволило сократить время решения тестовых задач по сравнению с решением задач полным перебором, благодаря фиксации булевых переменных перед решением задачи.
Однако использованных методов недостаточно для значительного ускорения работы программы при увеличении размерности задачи. Тем не менее, для наборов с малым количеством прямоугольников задача решается быстро.
В дальнейшем возможно применение методов распараллеливания алгоритма для ускорения решения поставленной задачи, а также изменение алгоритма ветвления таким образом, чтобы не решать затратные и бесперспективные задачи, что увеличит эффективность работы алгоритма для задач большей размерности.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.