Оптимизация размещения двумерных геометрических объектов на анизотропном материале с использованием методов математического программирования тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Петренко, Семен Васильевич

• Петренко, Семен Васильевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Петренко, Семен Васильевич

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

Введение.

Глава 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. Выводы по четвертой главе.

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

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

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

- задачи компоновки: грузов в разнообразного вида контейнеры, схем генеральных планов промышленных предприятий, двигателей, радиоэлементов на платах и т.д.;

- задачи распределения - от памяти вычислительных машин до участков леса, предназначенных для вырубки или посадки.

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

Сложность решения этих задач заключается в том, что они относятся по своей сложности к классу ЫР-трудных проблем оптимизации, т.е. для которых пока не существует методов и алгоритмов, находящих точное решение за полиномиальное время [63].

Анализ отечественной и зарубежной литературы, информационных интернет-источников позволяет сделать вывод, что исследованием и разработкой методов решения данного класса задач занимаются: Харьковская школа Р-У академика Ю.Г. Стояна; Институт алгоритмов и научных вычислений Германии (Т. Ленгауэр); В. Миленковик, К. Даниэльс (США); К. Доусланд, В. Доусланд (Великобритания); ряд российских ученых, среди которых Э.А. Мухачева, М.А. Верхотуров, В.В. Мартынов, A.A. Петунии, В.Д. Фроловский [7].

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

Разработанные на сегодняшний момент методы точного решения таких задач не находят своего применения на практике, так как оказываются эффективными только при сравнительно небольшом числе объектов. При увеличении числа объектов значительно усложняется поиск не только глобального, но и локальных экстремумов, точные методы перестают отвечать требованиям надежности, и скорости работы. Дискретность работы средств цифровой вычислительной техники, трудоемкость базирующихся на них аналитических алгоритмов в большинстве случаев обуславливает сложность математических моделей и, как следствие, неустойчивость работы создаваемого математического обеспечения. В связи с этим наибольшее применение получили приближенные методы решения, основанные на эвристических и метаэвристических подходах, дискретных способах представления геометрической информации. Основной недостаток этих методов - отсутствие математически обоснованного доказательства не только глобальной, но даже локальной оптимальности полученного решения. Применение точных алгоритмов поиска локального экстремума к результатам работы приближенных методов позволит получить математически обоснованный локальный оптимум задачи двумерного размещения объектов различного вида при раскрое и упаковке промышленных материалов, что приведет к большей экономии материальных ресурсов. Все выше сказанное определяет актуальность разработки эффективных и надежных методов поиска локального экстремума задачи двумерного размещения ГО различного вида при решении задач Р-У промышленных материалов.

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

Целью работы является разработка методов и алгоритмов поиска локального экстремума задачи двумерного нерегулярного размещения ГО на анизотропном материале (поворот ГО запрещен) на основе заданного начального приближения, а также подходов к использованию разработанных методов в комбинации с приближенными методами.

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

1) Разработать математическую модель представления задачи двумерного размещения ГО с ограничениями в виде линейных неравенств.

2) Разра ботать методы и алгоритмы нахождения локального экстремума на основе построенной модели и подходов математического программирования при заданном начальном приближении.

3) Разработать программное обеспечение для решения задачи поиска локального экстремума с учетом технологических ограничений.

4) Провеет и вычислительный эксперимент для разработанных методов и алгоритмов,

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

Результаты, выносимые на защиту:

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

2. Метод нахождения локального экстремума для задачи размещения плоских многоугольников на анизотропном материале на основе идеологии активного набора с использованием построенной модели задачи.

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

4. Схема комбинации разработанного метода поиска локального экстремума с приближенными методами последовательного одиночного размещения. Результаты вычислительных экспериментов для созданного метода поиска локального экстремума.

Научная новизна работы заключается в следующем:

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

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

3. Создана схема комбинации точного метода поиска локального экстремума с приближенными методами последовательного одиночного размещений. Такой подход позволяет не только улучшать результат, полученный приближенными методами, но и получать математически обоснованное решение практических задач Р-У.

Практическая ценность работы состоит в создании математического и программного обеспечения для решения задач построения двумерных планов раскроя-упаковки, с учетом технологических ограничений, возникающих при решении прикладных задач. Результаты вычислительного эксперимента показывают, что применение разработанного программного обеспечения позволяет улучшить решение, полученное приближенным методом на основе классического «жадного» алгоритма, на 0,5 - 8 %. Основание для выполнения исследований

Работы в данном направлении проводились автором в Уфимском государственном авиационном техническом университете в 2002-2005 гг. в рамках проектов РФФИ 01-99-00937 и 01-01-00510. Внедрение результатов:

- в учебном процессе Уфимского государственного авиационного технического университета;

- в Рекламном агентстве RMC (г. Уфа).

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях:

- Международная конференция «Информационные системы и технологии» (Новосибирск, 2003);

- Российская конференция «Дискретный анализ и исследование операций» DAOR/04 (Новосибирск, 2004);

- XIII Байкальская международная школа семинар Иркутск-Северобайкальск «Методы оптимизации и их приложение» (Северобайкальск, 2005);

- Научно-технические семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета (2002-2005гг.).

Публикации. По теме диссертации опубликованы 7 работ, в том числе 5 статей и 2 материалов конференций.

Структура работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем основной части диссертации составляет 115 е., в том числе 48 рисунков, список литературы из 80 наименований на 9 с.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Петренко, Семен Васильевич

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

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

2. Разработан итерационный метод нахождения локального экстремума задачи размещения невыпуклых ориентированных многоугольников в невыпуклой области на основе созданной математической модели и идеологии активного набора. Особенностью данного подхода является простота и надежность реализации. Кроме этого, по сравнению с подходом, разработанным в Харьковской школе Р-У академика Ю.Г. Стояна и также основанным на идеологии активного набора, представленный метод имеет более широкие возможности получения следующего приближения за счет рассмотрения всей ОДР при определении длины шага.

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

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

Проведен вычислительный эксперимент, показавший, что применение разработанного метода нахождения локального экстремума к размещениям, полученным классическим «жадным» алгоритмом, использующим упорядоченный по возрастанию площадей выпуклых оболочек список многоугольников, позволяет добиться улучшения от 0,5 до 8,0 %.

Заключение

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

Список литературы диссертационного исследования кандидат технических наук Петренко, Семен Васильевич, 2005 год

1. Бабаев Ф. В. Оптимизация раскроя материалов: Обзор. М.: НИИМАШ, 1978.-72

2. Бабаев Ф. В. Оптимальный раскрой материалов с помощью ЭВМ. М.: Машиностроение, 1982. - 168 с

3. Белякова Л.Б. Вопросы оптимального расположения конгруэнтных фигурна плоскости: Автореф.дис.канд.физ.-мат.наук.-Горький:ГГУ,1970.-1 Зс.

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

5. Верхотуров М.А. Математическое моделирование нерегулярной упаковки двух и трёхмерных геометрических объектов// Комплексный анализ, дифференциальные уравнения и смежные вопросы: Сб. трудов международной конференции. Уфа: 1996.-С.37-44

6. Верхотуров М.А. Математическое обеспечение автоматизированных систем нерегулярного размещения двух- и трехмерных геометрических объектов на базе дискретных моделей //Диссертация на соискание ученой степени доктора технических наук. Уфа 2000

7. Верхотуров М.А. Об устойчивых алгоритмах построения годографа// Принятие решений в условиях неопределенности: Межвузовский сборник. Уфа: УГАТУ, 1998.- С.270-284

8. Верхотуров М.А., Верхотурова Г.Н., Брусиловский Д.П. Методы и алгоритмы нерегулярной двумерной упаковки объектов сложных геометрических форм. Рукопись деп. в ВИНИТИ, №682-В97 от 05.03.97

9. Верхотуров М.А., Верхотурова Г.Н., Мухачёва Э.А. Об использовании оценок в задачах трёхмерной упаковки// Прикладная и индустриальная математика: Тезисы второго сибирского конгресса. Новосибирск: 1996. .1. С.139

10. Верхотуров М.А., Логинов Е.В., Лохматов О.В., Петренко C.B. Об одной реализации автоматизированной системы нерегулярного раскроя деталей сложных форм // Информационные системы и технологии // Тр. Международной конференции, Новосибирск, 2003, С. 79-83

11. Верхотуров М.А., Мартынов В.В., Мухачева Э.А. Модели и методы расчета раскроя-упаковки ГО. Уфа: УГАТУ, 1998. -217 с.

12. Верхотуров М.А., Мухачёва Э.А. Метод оценок для решения задач раскроя упаковки// Исследование операций: Тезисы 14 международной конференции. - Ванкувер: 1996.-С.24

13. Верхотуров М.А., Мухачёва Э.А. Метод оценок для решения задач раскроя упаковки// Принятие решений в условиях неопределенности:

14. Межвузовский сборник научных трудов. Уфа: 1996.-С.22-24

15. Верхотуров М.А., Мухачева Э.А., Шабрина Л.И. Многообразие задач раскроя и упаковки. Деп.в ВИНИТИ, №3023-В94.-М:1994.-8с.

16. Верхотуров М.А., Петренко C.B. Нерегулярное размещение невыпуклых ориентированных многоугольников в односвязной невыпуклой области//г

17. Тр. XIII Байкальской международной школы семинара Иркутск

18. Северобайкальск / Методы оптимизации и их приложение: В 2 т. Иркутск, 2005, т.1. Математической программирование, С. 435-443

19. Верхотуров М.А., Петренко C.B. Об одном подходе к нахождению локального экстремума задачи размещения невыпуклых ориентированных многоугольников в полубесконечной полосе// Межвузовский сборник научных трудов, Уфа: УГАТУ, 2005, С. 7-18

20. Верхотуров М.А., Сергеева О.Ю. Некоторые особенности реализации упаковки геометрических объектов на базе цепного кодирования// Принятие решений в условиях неопределенности: Межвузовский сборник научных трудов. -Уфа: 1996. -С. 12-17.

21. Верхотурова Т.Н., Верхотурова О.М., Павлов И.А., Петренко C.B. Анализ эффективности эвристических методов на примере решения задачи коммивояжера. //Принятие решений в условиях неопределенности.f.

22. Межвузовский научный сборник. Выпуск 1. -Уфа: УГАТУ, 2004. С. 199201

23. Гардан И., Люка М. Машинная графика и автоматизация конструирования.-М. :Мир, 1987.-272с.

24. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.:Мир,1985. - 509с.

25. Гиль Н.И. Математическое моделирование нерегулярного размещения плоских геометрических объектов в системах автоматизации проектирования (теоретические основы, методы, приложения): Автореф.дис.докт.техн.наук.-Минск, 1990.-32с.

26. Гиль Н.И., Комяк В.М. Об одном подходе к построению годографа вектор функции плотного размещения плоских геометрических объектов, устойчивого к вычислительной погрешности.-Харьков, 1991.-23с.-(Препринт/АН УССР, Ин-т пробл. машиностроения:350)

27. Данциг Д.Б. Линейное программирование, его применение и обобщение. -М.: Прогресс, 1966.-600с.

28. Канторович Л.В. Методы рационального раскроя металла// Производственно техн. бюллетень. - М.-1942.-35с.

29. Канторович Л.В., Горстко А.Б. Математическое оптимальное программирование М:Экономика, 1968.-96с.

30. Канторович Л.В.,Залгаллер В. А. Расчет рационального раскроя промышленных материалов.- Л.:Лениздат,1951.-199с.

31. Компьютер и задачи выбора/Автор предисл.Ю.И.Журавлев.-М:Наука,1989.-208с.(Серия "Кибернетика неограниченные возможности и возможные ограничения")

32. Логинов Е.В. Проектирование нерегулярного раскроя листовых материалов на заготовки сложных форм с использованием дискретно-логического представления информации //Диссертация на соискание ученой степени кандидата технических наук. Уфа 2002

33. Магас С. Л. Заполнение вырубок ориентированными многоугольниками // Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тез. докл. Всесоюзной конференции.-Уфа, 1987. С. 111-112

34. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. М.: Машиностроение, 1984.-176с.

35. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя упаковки геометрических объектов. - УГАТУ, Уфа: 1998.-217с.

36. Новожилова М.В. Решение задачи поиска глобального экстремума линейной функции цели на структуре линейных неравенств. Харьков, 1988.- 48с. - (Препринт /АН УССР. Ин-т пробл. Машиностроения: №292)

37. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение / Пер. с англ. М.: Мир, 1989. 478 с.

38. Рвачев В.Л. Теория R-функций и некоторые ее приложения. Киев: ^ Наук.думка, 1982.-550с.

39. Рейнгольд Э., Нивергольд Ю., Део Н. Комбинаторные алгоритмы: Теория и практика. М.: Мир, 1980.-213с.

40. Роджерс Дэвид Алгоритмические основы машинной графики, М.:«Мир», 1989. 504 с.

41. Савлов С.Ф. Построение нерегулярных укладок неориентированных многоугольников//Матем.обесп-е рацион-ого раскроя в системах автоматизированного проектирования:Материалы Всесоюзной конференции.- Уфа, 1988. С.118-120

42. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. Киев: Наук, думка, 1976. -247с.

43. Стоян Ю.Г., Новожилова М.В., Карташов А.В. Математическая модель и оптимизация линейных Ek(R ) задач размещения. - Харьков, 1991.-44с.-(Препринт /АН УССР. Ин-т пробл. Машиностроения: №353)

44. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев. : Наук, думка, 1986. -286с.

45. Федоров Е.С. Симметрия и структура кристаллов. М.:Изд-во АН СССР, 1949.-411с.

46. Чебышев П.Л. О кройке одежды. Журн. Успехи матем. наук, 1946, 1.2.С.27

47. Art RC., An approach to the two dimensional irregular cutting stock problem, IBM Cambridge Scintific Centre, Report 36-Y08, 1966

48. Aarts E., Lenstra J.K. (eds.) Local search in combinatorial optimization, John Wiley & Sons Ltd, 1997.-315p.

49. Aarts L., Van Laarhoven P. Statistical cooling: a general approach to combinatorial optimization problems, Philips J.Res 40, 1985 pp. 193-226

50. Benell Julia A., Dowsland Kathryn A., Dowsland William В., The irregular cutting-stock problem a new procedure for deriving the no-fit polygon, Computers &Operations Research 28 (2001). -pp. 271-287

51. Blazewicz J., Hawryluk P., Walkowiak R. Using a tabu search approach for solving the two-dimensional irregular cutting problem. Annals of OR, 41(1-4) , 1993. pp.313-325

52. Bounsaythip C., Maouche S., Roussel G., Algorithms for a marker making system: e-admissible resolution, 12th International Conference on Systems Science, Wroclaw, Poland, 1995

53. Christofides, N. and Whitlock, C. An algorithm for the two dimensional cutting problems. Oper. Res., 25: pp.30 - 44

54. Coffman E., Shor P. Packing in two dimensions: asymptotic average-case analysis of algorithms, Algorithmica, 9, 1993, pp.253-277

55. Dagli C.H., Taloglu M., An approach to two-dimensional cutting stock problems, International Journal of Production Research 25 (2) (1987) -pp. 175190

56. Daniels K., Li Z., Milenkovic V.J. Automatic marker making, in: Proc. 3rd Canadian conf. On Computational geometry, ed. T.Shermer, August, 1991.pp. 11-24

57. Daniels M. and Milenkovic V. J. Multiple Translational Containment. Part I: An Approximation Algorithm. Submitted to the Algorithmica special issue on Computational Geometry in Manufacturing, June 1994. In press

58. Dycknoff H. A typology of cutting and packing problems. F.R.Germany., 1991,-41p.

59. Freeman, H. and Shapira, R. Determining the minimum area encasing rectangle for an arbitrary closed curve, Comm.ACM.18(7), pp.409 - 413 (1975)

60. Fortune S., Milencovic V. Numerical stability of algorithms for line arrangements, 7-th annual ACM SCG, 1991, pp.334-341

61. Gilmore P. C., Gomory R. E. The theory and computation of knapsack functions. Oper. Res, 1966,14, pp.145-175

62. Heckmann R., Lengauer T. Computing closely matching upper and lower bounds on textile nesting problems. European Journal of Operational Research, 108, 1998, pp.473-489

63. Maouche S., Roussel G., Intelligent lay-planning system for irregular shapes and sheet with patterns and flaws: resolution by s-admissible tree search, 24th International Symposium on Industrial Robots (ISIR), Tokyo, 1993

64. Milenkovic V.J. Multiple translational containment, part II: exact algorithms.-Algorithmica special issue on Computational geometry in manufacturing, 1994,40p.

65. Milenkovic V.J., Daniels K. Translational polygon containment and minimal enclosure using mathematical programming.-ITOR special issue with papers from IFORS'96, 1996, 30p.

66. Milenkovic V, Daniels K, Li Z, Placement and compaction of non convex polygons for clothing manufacture. Fourth Canadian Conference on Computational Geometry, St John's, Newfoundland, 1992

67. O'Rourke J., Chien C.B., Olson T., Naddor D. A new linear algorithm for intersecting convex polygons // Computer Graphics and Image Processing. 1982. V.19. P. 384-391

68. Pfefferkorn C.E. A heuristic problem solving design system for equipment or furniture layouts, Communications of the ACM 18 (5), 1975, P. 286-297

69. Stoyan Yu.G., Novozhilova M.V., Kartashov A.V., Mathematical model and method of searching for a local extremum for non-convex oriented polygonsallocation problem, European Journal of Operation Research 92 (1996), -pp. 193-210

70. Stoyan YG, Ponomarenko LD, Minkowski sum and hodograph of the dense placement vector function. Report of the SSR Academy of Science, SER.A 10, 1977 *

71. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische. Losung.- Leiprig, 1987, -pp.207-217