«Программный модуль для предоптимизационного анализа информации в задаче двумерного размещения» - Дипломная работа

Содержание

Введение 4

Глава 1. Обзор и анализ задач геометрического размещения и методов их решения 6

1.1 Многообразие задач геометрического размещения 6

1.2 Содержательная постановка задачи двумерного размещения 7

1.3 Методы решения задач геометрического размещения 8

1.4 Оптимизационный процесс раскроя-упаковки 10

Выводы по 1 главе 13

Глава 2. Проектирование программного модуля для предоптимизационного анализа информации в задаче двумерного размещения 14

2.1 Процесс предоптимизационного анализа 14

2.2 Разработка программного модуля 18

2.3 Тестирование и анализ результатов генетических алгоритмов 24

2.3.2 Поиск лучших решений для разных классов задач 28

2.3.3 Поиск лучших решений для классов задач с большим количеством заготовок 32

Выводы по 2 главе 33

Глава 3. Разработка и тестирование программного модуля для предоптимизационного анализа информации в задаче двумерного размещения 34

3.1 Выбор языка программирования 34

3.2 Техническое задание 36

3.3 Тестирование программного модуля 38

3.4 Эффективность внедрения программного модуля предоптимизационного анализа информации в задаче двумерного размещения 40

3.4.1 Экономический эффект от внедрения программного модуля 40

3.4.2 Время разработки программы 42

Выводы по 3 главе 44

Заключение 45

Список литературы 46

Приложение 48

Введение

В различных сферах производства в настоящее время остается актуальным проблемы энергосбережения и ресурсосбережения, связанные с задачами раскроя упаковки. К данному типу задач можно отнести: задачи оптимального раскроя материала на заготовки геометрической формы. Эти задачи используются на предприятиях, где необходимо делить материалы на заготовки определенной формы, например, машиностроительной, авиастроительной, судостроительной, текстильной, кожевенной,

деревообрабатывающей, мебельной и многих других отраслях промышленности. Задачи компоновки грузов в различные виды контейнеров, компоновки схем генеральных планов промышленных предприятий, двигателей, радиоэлементов на платах и так далее. Все рассмотренные примеры по своей сути раскрывают проблему оптимизационного геометрического моделирования, которая заключается в оптимизации размещения данного вида объектов в заданных областях.

Актуальность работы

В рамках данной выпускной квалификационной работы рассмотрены задачи компоновки: грузов с разнообразными видами контейнеров, а так же раскрой материалов на заготовки геометрических форм. Создание программного модуля, который позволяет ускорить процесс поиска эффективных настроек для решения поставленной задачи необходимо потому, что данные задачи геометрического размещения широко применяются практически во всех отраслях производства. Данные задачи относятся к NP-трудным задачам, к таким задачам относятся те, у которых методов и алгоритмов, которые могут найти точное решение за, t определенный промежуток времени не существует. В связи с этим можно говорить об актуальности данной темы.

Тема выпускной квалификационной работы: программный модуль для предоптимизационного анализа информации в задаче двумерного размещения

Цель выпускной квалификационной работы

Целью выпускной квалификационной работы является: Разработка предоптимизационного модуля для повышения эффективности поиска решений в задаче геометрического размещения

Задачи выпускной квалификационной работы

Для достижения цели были поставлены следующие задачи:

1. Провести анализ моделей и методов решения задачи двумерного размещения объектов, различных геометрических форм;

2. Провести вычислительный эксперимент для анализа эффективности известных алгоритмов решения задачи двумерного размещения;

3. Разработать программный модуль для предоптимизационного анализа информации и выбора эффективного алгоритма решения;

4. Протестировать и произвести отладку программного модуля.

Выдержка из текста работы

ГЛАВА 1. ОБЗОР И АНАЛИЗ ЗАДАЧ ГЕОМЕТРИЧЕСКОГО РАЗМЕЩЕНИЯ И МЕТОДОВ ИХ РЕШЕНИЯ

1.1 Многообразие задач геометрического размещения

Задачи раскроя и упаковки включают в себя большой спектр задач, которые объединены по своей однотипной логистической структуре, но при этом растолкованы, могут быть по-разному. В различных источниках можно найти совершенно разные названия задаче раскроя и упаковки. Например, задача раскроя запаса материала, задача плотного размещения геометрических объектов в заданной области, задача загрузки рюкзака, задача упаковки ящиков (контейнеров), задача загрузки транспорта, задача выбора ассортимента, задача планировки помещений, задача обеспечения ритмичности производственного процесса, задача распределения памяти вычислительной машины, задача составления расписания

многопроцессорных систем. При этом любая из задач может быть конкретизирована по-своему. Например, если рассматривать только задачи раскроя запаса можно встретить несколько постановок. Они могут различаться по различным признакам: размеры и ассортимент материала и заготовок, геометрией материала и полученных из них заготовок, условиями реализации раскроя и другими дополнительными признаками [1].

В задачах двумерного раскроя по своей сложности лидирующими по отношению к другим задачам раскроя находятся задачи нерегулярного размещения геометрических объектов сложных форм. Это связано с тем, что достаточно сложно учитывать все условия взаимного не пересечения объектов и условий их размещения в заданных областях раскрой упаковки.

Впервые данные задачи раскроя геометрических объектов были рассмотрены великим русским математиком П.Л.Чебышевым в докладе «О кройке одежды» 1878 года [2]. В нем были рассмотрены вопросы о лучшем покрытии кривых поверхностей плоскими выкройками из ткани. В дальнейшем развитие интереса к данной задаче все больше развивалось, так 80-х годы для решения проблемы раскроя-упаковки была использована 6

теория искусственного интеллекта. В эти же годы было признано, что применение различных эвристик, возможно, лучший способ для нахождения хороших решений за приемлемое время [5].

1.2 Содержательная постановка задачи двумерного размещения

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

Рассматривается задача двумерной прямоугольной упаковки (1,5 Dimensional Bin Packing Problem, 1,5DBPP) об упаковке прямоугольников в полубесконечную по длине полосу. Она состоит в следующем [4].

Рассмотрим пример, при котором в грузовиках контейнеры, возможно, размещать, не ставя друг на друга и не превышая допустимых параметров.

Данная задача имеет следующий вид. Имеется прямоугольная полоса заданной ширины W, а также набор прямоугольных предметов T заданных размеров wi; li, i = 1, m . Найти упаковку предметов в полосу при следующих условиях:

1) ребра упакованных предметов параллельны ребрам полосы;

2) упакованные предметы не пересекаются друг с другом;

3) упакованные предметы не пересекаются со сторонами полосы.

Прямоугольная упаковка (Rectangular Packing, RP), удовлетворяющая условиям 1 - 3, называется допустимой.

Если длина L(RP) занятой части полосы достигает минимума, то RP называется оптимальной упаковкой и является решением задачи 2DBPP.

Заключение

В рамках данной выпускной квалификационной работы были рассмотрены задачи компоновки: грузов с разнообразными видами контейнеров, а так же раскрой упаковки различных материалов на заготовки геометрических форм. Была поставлена и достигнута следующая цель:

Разработан предоптимизационный модуль для повышения эффективности поиска решений в задаче геометрического размещения;

А так же реализованы следующие задачи:

• Проведен анализ моделей и методов решения задачи двумерного размещения объектов, различных геометрических форм;

• Проведен вычислительный эксперимент и оценена эффективность известных алгоритмов решения задачи двумерного размещения;

• Разработан программный модуль для предоптимизационного анализа информации, который позволяет подбирать эффективные алгоритмы и настройки;

• Протестирована и произведена отладка программного модуля.

Поставленная цель достигнута. Задачи решены в полном объеме.

Список литературы

1. Белякова, Л.Б. Об оптимальном раскрое листового материала. Автоматизация технологического проектирования при помощи ЭЦВМ [Текст] / Л.Б. Белякова М.: Машиностроение, 1968.-С.21-32.

2. Белякова Л.Б. Вопросы оптимального расположения конгруэнтных фигур на плоскости [Текст] / Л.Б. Белякова М. Автореф. дис.канд.физ.- мат.наук.-Горький:ГГУ,1970.-13с.

3. Валеева А.Ф., Тоцков И.Е. Решение задачи трехмерной упаковки. Труды международной конференции “Комплексный анализ, дифференциальные уравнения, численные методы и приложения”. Применение численных методов. Геометрические задачи [Текст]/ Валеева А.Ф., Тоцков И.Е. Уфа: ИМВЦ УНЦ РАН, 1996.-С. 30-36.

4. Гаврилова Т.С., Галина Р.Р., Михайлова А.Н. Эволюционный алгоритм для маршрутизации транспорта с учетом грузоподъемности [Текст]/ Динамика сложных сетей и их применение в интеллектуальной робототехнике. Сборник материалов Международной школы-конференции молодых ученых - Саратов: ООО «Издательство «Научная книга»», -2017, с. 31-32.

5. Филиппова А.С., Михайлова А.Н., Гаврилова Т.С., Галина Р.Р. Использование эволюционного алгоритма для изучения студентами дисциплины «Прикладные методы оптимизации» [Текст]/ Гуманистическое наследие просветителей в культуре и образовании: материалы XII Международной научно-практической конференции 14 декабря 2017 г. - Уфа: Издательство БГПУ, 2018. С. 108 -109.

6. Лаптенок Е.Д., Гаврилова Т.С., Галина Р.Р., Михайлова А.Н. Разработка эволюционного алгоритма для транспортно-логистических информационных систем [Текст]/ Актуальные проблемы науки и техники. Информационные и инфокоммуникационные технологии. УГАТУ. с. 43- 45 7. Филиппова А.С., Михайлова А.Н., Галина Р.Р., Гаврилова Т.С.

Алгоритмическое обеспечение транспортно-логистических

информационных систем [Текст]/ Материалы Всероссийской (с международным участием) студенческая научно-практической

конференции «Наука 2020» (20 апреля 2018 г.) / сост. Л.Р. Саитова, Р.Н. Измайлов. - Уфа: Изд-во БГПУ, 2018. С. 215-220.

8. Филиппова А.С., Андреева Е.В., Дяминова Э.И., Лаптенок Е.Д. Матричный алгоритм роя частиц для поддержки принятия решений при составлении расписания обслуживающих бригад // Материалы VI Всероссийской конференции «Информационные технологии

интеллектуальной поддержки принятия решений» (ITIDS’2018). - Уфа, УГАТУ, 2018. Т. 2. С. 125-128.

9. Смагин М.А., Хасанова Э.И., Басимов Э.Р. Проектирование сквозного размещения прямоугольных предметов в многосвязный ортогональный полигон. Программа для ЭВМ Смагина М.А. Уфа 2005 год

Диссертация Смагин М.А. Автоматизация проектирования рационального размещения прямоугольных деталей с использованием генетического метода на множестве эвристик автореф. на соискание степени кандидата технических наук Уфа-2005.

Примечания

Оригинал в pdf