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

ПЕТРЕНКО СЕМЕН ВАСИЛЬЕВИЧ

ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ ДВУМЕРНЫХ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ НА АНИЗОТРОПНОМ МАТЕРИАЛЕ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Уфа 2005

Работа выполнена на кафедре вычислительной математики и кибернетики Уфимского государственного авиационного технического университета

Научный руководитель д-р техн. наук, проф. ВЕРХОТУРОВ Михаил Александрович

Официальные оппоненты д-р техн. наук, проф. МАРТЫНОВ Виталий Владимирович канд. техн. наук ПЕТУНИИ Александр Александрович

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

Защита диссертации состоится « 22 » декабря 2005 г. в 12 часов на заседании диссертационного совета Д212.288.03 Уфимского государственного авиационного технического университета по адресу: 450000, г. Уфа, ул. Карла-Маркса, д. 12

С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан « 21 » ноября 2005 г.

Ученый секретарь диссертационного совета д-р техн. наук, проф.

В.В. Миронов

2151545

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

тельной техники, трудоемкость бази] алгорит-

БМБЛИОТБКА л I

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

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

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

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

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

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

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

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

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

низации комплексов программных средств, машинные эксперименты для оценки эффективности алгоритмов.

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

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

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

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

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

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

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

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

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

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

Основание для выполнения исследований

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

Внедрение результатов:

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе дается обзор задач Р-У, приводится их классификация. Анализ проблем Р-У позволяет сделать вывод, что задача нерегулярного двумерного размещения является наиболее сложной среди множества задач двумерной упаковки и требует дальнейшей разработки методов и алгоритмов ее решения. В главе даются основные определения и приводится постановка данной задачи в общем виде: пусть имеется набор ГО Р,,т= 1,2, ..., п, которые требуется разместить в области О пространства Л2 так, чтобы минимизировать значение заданной целевой функции. В пространстве Я1 положение ГО определяется тремя параметрами х, у, в (координаты условного центра и угол на-

клона). ГО должны располагаться в области О без пересечений друг с другом -условие взаимного непересечения (УВН), и с фаницей области О - условие размещения в области (УРО). УВН и УРО определяют С? - область допустимых решений задачи (ОДР). Если 2 = (х„у1,...в1,х2,у2,...в2,...,хп,уг,...вп) - вектор размещения ГО Р\,Рг, ...,Р„ в области О, то из всех допустимых векторов размещения требуется найти такой ¿', который минимизирует величину С* = щш с{2), где С - некоторая целевая функция от 2. 2' является глобальным экстремумом задачи. Локальным экстремумом задачи называется размещение 2\ для которого не существует такого вектора ¿2 ={&1,йул,..Ав^дх7,<1уг,..Авг,...,<Ьп,ду,,..х1в^), что V/ е [ОД] размещение

2+г-ё2вв и с(2'+а2)<сф).

В этой главе описываются различные способы решения данной задачи, которые делятся на точные и приближенные. Точные методы размещения невыпуклых ориентированных многоугольников базируются на использовании идей и методов линейного программирования. Для задачи размещения ориентированных многоугольников в полубесконечной полосе в Харьковской школе Р-У академика Ю.Г. Стояна разработана группа точных методов, использующих структуры линейных неравенств (СЛН)1. Структура линейных неравенств Щу(х),А,т) представляет собой набор линейных неравенств у(х) = (/, (х) > 0)

(хе/?',/ = 1,2, ..,т) и матрицу А = |^|| отношений между ними, где 8ц =1

соответствует операции конъюнкции между г-м и у'-м неравенствами, а = 0 -

операции дизъюнкции.

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

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

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

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

ются: большое число проверок принадлежности точки выпуклым подобластям ОДР, ограничение поиска следующего приближения теми выпуклыми подобластями, которым принадлежит начальное решение.

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

глобальной системе координат (ГСК) ХОУ, многоугольники набора 5 - в локальных системах координат (ЛСК) XV ,У, где v¡=(x,y¡) - условный центр Я,, определяющий положение многоугольника в ГСК ХОУ (г—1,2,...,п). Размещение многоугольников в области 50 определяется вектором у = (х1,у1,х2,у2,...,х1<,уп,г), где (х,,.у,) - координаты многоугольника 5, (г=1,2,...,л), прямая х=г ограничивает занятую часть области Целью задачи является минимизация г, т.е. минимизация длины занятой части области

Для случая, когда область размещения (ОР) Бо является невыпуклой или имеет внутренние области, недоступные для размещения, для 5о строится выпуклая оболочка, что позволяет представить область в виде: 50 = Т0 \(Т1117; и.-.и?;), где Т0 - выпуклая оболочка для 80; Т), Т2, ..., Тк - дополнения области 5о до выпуклой оболочки Т0; к - количество этих областей. Границы областей Тг, ..., Г, являются в общем случае невыпуклыми многоугольниками. Таким образом, задачу можно свести к задаче размещения многоугольников Т), Т2, ..., Тк, ..., внутри выпуклой области Т0, причем многоугольники Г/, Т2,..., Тк уже размещены.

Для описания ОДР задачи необходимо смоделировать УВН многоугольников, УРО и условие нахождения многоугольников внутри области размещения, ограниченной прямой х = г.

Для построения УВН двух невыпуклых многоугольников 5, и 5

(¡=1,2,.,.,п,у=1,2,...,л) они разбиваются на выпуклые многоугольники 5' и (д=\,2,...£„г=\,2,...,к]). Допустимая область размещения невыпуклого многоугольника относительно 5 может быть определена как пересечение допустимых областей размещения каждого Б] относительно каждого 5,'. Граница допустимой области размещения одного выпуклого многоугольника относительно другого является годографом функции плотного размещения (внешним годографом). Внешним годографом или просто годографом выпуклого многоугольника В относительно выпуклого многоугольника А будем называть многоугольник Н лв, заданный относительно А и удовлетворяющий условию: если условный центр многоугольника В принадлежит многоугольнику Нлв, то ВПЛ *0, иначе ¿?ГМ = 0. Каждое ребро выпуклого многоугольника НАВ определяет полуплоскость, ограничивающую размещение многоугольника В от-

носительно А. В аналитической форме эту полуплоскость можно записать в виде неравенства Ду)<0> где v - вектор размещения многоугольников. Допустимая область размещения одного многоугольника относительно другого определяется объединением этих полуплоскостей. Таким образом, УВН может быть записано в виде конъюнктивной нормальной формы (КНФ):

0«H=nü(/;(v)£O), со

/•1 y-I

где каждое f-oe объединение неравенств соответствует годографу выпуклых составляющих разных многоугольников из набора 5; h, - число ребер в /-ом годографе; К - число всех годографов для всех выпуклых составляющих разных многоугольников из набора S.

Для моделирования УРО для выпуклой области S0 нет необходимости разбивать невыпуклые многоугольники на выпуклые. УРО любого многоугольника будет представляться в виде пересечения линейных неравенств, соответствующих ребрам внутренних годографов. Внутренним годографом многоугольника В относительно многоугольника А будем называть многоугольник Н'АВ, заданный относительно А и удовлетворяющий условию: если условный центр многоугольника В принадлежит многоугольнику Н'лв, то В П А = В, иначе ВГ\А*В. Допустимое положение многоугольника В внутри многоугольника А определяется пересечением полуплоскостей, соответствующих ребрам многоугольника Н'АВ. Следовательно, УРО можно записать в виде:

я™=nfi(/;'(v)<o)=iV/(v)<o), (2)

М >! /-1

где каждая г'-ая система неравенств соответствует внутреннему годографу мно-

п

гоугольника из набора S относительно области размещения 50; h0 - .

Для задания условия размещения многоугольника S, внутри области, ограниченной x — z, рассчитывается величина z = max {х[}, где х' - абсцисса j-

ой вершины многоугольника Smi - число вершин многоугольника S, 0-1,2,. ,.,и). В этом случае данное ограничение запишется как:

Д=П(*,+г,*2). (3)

Таким образом, математическая модель задачи имеет вид: найти размещение V* = arg min 2, где

veD

Каждое из'неравенств в (4) можно записать в виде линейного неравенства т + Ь<0, определяющего гиперполуплоскость в пространстве Л2""'.

Перепишем задачу (4) в следующем виде: требуется найти минимум линейной функции цели С=(с-х) с=(с1, с2, и соответствующий ему вектор х=(х1, х2,х*)6^* на области допустимых решений:

в = г>0 п (П А). где = П(п>+Ъ] < 0), д = и(и> ь; < 0).

м >1

При этом задана точка у=(у/, ..., - начальное приближение.

Если задача состоит в минимизации занятой части области размещения, то вектор с=(0, 0, 0, ...,0, 1). Для нахождения локального экстремума поставленной задачи был разработан метод на основе идеологии активного набора.

Идея метода заключается в следующем: на каждом шаге выбирается вектор движения ge^?* и его длина а. Новое приближение берется как v'=v+■ag. Основная задача - выбрать направление движения так, чтобы оно максимально уменьшало функцию цели.

Пусть в точке V активны к неравенств (активным будем называть то неравенство хп1. +Ь'1 <0, которое в точке V превращается в равенство и точка V принадлежит границе области £>). В этом случае задачу нахождения оптимального вектора % можно записать в виде:

найти § = тш(^с) при условиях:

1. |я|~|с|. Если |с|=1, то ограничение можно записать как [§]=1 или .

2. Для любого активного неравенства хп' +Ъ'1 <0, (г=1 ,...,т ,7=1,2,...,£,„)

(V + g)n'J +Ь'1< 0'. В точке V эти неравенства активные, значит ул' + Ы = 0, следовательно, условие сведется к <0.

Если решать задачу выбора направления движения в этой формулировке, то это будет задача математического программирования с линейной функцией цели и квадратичными ограничениями. Для решения можно использовать метод множителей Лагранжа и, например, метод ветвей и границ, но применение такого подхода на практике затруднено из-за больших вычислительных затрат. Поэтому условие 1 заменено более мягкими условиями #,<1 и g¡>-1.

В этом случае, заменив вектор g на разность векторов у и Д получим задачу линейного программирования:

тт(су-с0)

*/ =.-п'г + п'Д, у = 1,2,..,«, у,=-г, +Д +1, г = 1,2,..,л, 2, ~ У, ~Р, +1-«= 1.2,-,л, у, > 0, Д > 0,« = 1,2,...,л.

Начальное базисное решение *=0, у=~-\, z= 1, у=0 и Д=0 следует из формы записи задачи. Следовательно, базисными переменными будут (х, у, z). Здесь группа ограничений xj = -n'y + n'ß, у = 1,2,...,и, где и - число активных неравенств, соответствует условию 2, а ограничения у, = + Д +1, z, = yt - Д +1, у, > О, Д > 0, i = 1,2,...,и - первому условию.

Решая данную задачу, найдем вектор направления движения g, имеющий минимальное расхождение с вектором уменьшения функции цели.

Для нахождения длины шага - а, каждая дизъюнкция или конъюнкция линейных неравенств проверяются на пересечения с лучом, имеющим направление g и начинающимся в точке v. С этой целью для каждой группы неравенств D, (/=0,1,...,т) подсчитываются значения промежуточных величин ß\ -(уп^) + b'j и r;=(g«;) С/= 1, ..., К). Для D0 определяются множества

Л*={7"1г;>0,7 = 1,2,...Л}, J'0 = {j\y° <0,7 = 1,2,...Д0} и две величины: . Д° Д°

а™ = min{—J-}, а™ = гаах{—£-} -максимальная и минимальная длина шага

)' у уи

для D0. Для D, (¿=1,2,...,/л) - множества J* ={j\y\ >0,у = 1,2.....к},

J", = О" < 0J = 1,2,...,*,} J; = {/1 у\ < 0J = 1,2,...,*,}. Если J\ = О, то

Д' д;

рассчитываются ат,1™* = тах{—-} и а," = mini—-}. Длина шага а находится

W, у' у^

как: a = min{a'| До"" <а'<а™,а'> а™,а'<а™ Vi = 1,2,...,m\J' =®,а™ <а™}.

Следовательно, получаем следующее приближение v'=v+ag. Процесс заканчивается, когда в результате определения направления движения будет получен вектор g, такой, что (gc)>0. Последнее полученное решение v является локальным экстремумом.

Доказательство: предположим, что точка v не является точкой локального экстремума. Следовательно, 3 g' такой, что Vi е [0,1] v + tg'eD, т.е. для всех неравенств, в том числе и для активных Vi €[0,1] (v + tg')ri. + h'/ <0 => igV <0, и ((v + g')c)<(vc) => (g'c)<0. Это противоречит тому, что минимальное скалярное произведение для векторов g, удовлетворяющих условию 2 больше или равно нуля.

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

Здесь V - начальное приближение, d - величина эквидистанты. Последний компонент вектора g - g2=(cg), определяет изменение длины занятой части.

Рис 1 Алгоритм нахождения локального оптимума задачи размещения

Рассмотрим более подробно этапы решения задачи.

Процедура получения отношения между многоугольниками является основной для формирования ОДР. Ее работу можно разбить на четыре этапа: построение выпуклой оболочки ОР и определение выпуклых дополнений ОР до выпуклой оболочки, разбиение невыпуклых многоугольников на выпуклые, построение для каждого многоугольника условия размещения в области, nocipoe-ние отношений между парами выпуклых многоугольников. Результирующие отношения сводятся в треугольную матрицу reis, каждый элемент матрицы relsv определяет отношение г-ого многоугольника ку'-ому (1 <j<i, i—2, 3,..., п), relsitl задает условия размещения в выпуклой оболочке ОР и отношения г'-ого многоугольника к дополнениям ОР до выпуклой оболочки. Для построения выпуклой оболочки используется алгоритм линейной сложности по своему характеру аналогичный алгоритму Ли1.

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

' Ф Препарата, М Шеймос Вычислительная геометрия- Введение / Пер с англ М Мир, 1989 С 204-209

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

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

Р~(р^,р1,...,рт) (некоторые могут не принадлежать годографу) проверяется их размещение относительно последующих и предыдущих ребер. Если точка р, является внешней для /-1 или для /+2 ребра, то она удаляется, а точка р,л или р,+ь соответственно, заменяется пересечением этих ребер (рис. 3).

Построение внешнего годографа для двух выпуклых многоугольников является простой общеизвестной процедурой1. Для снижения вычислительных затрат при определении угла наклона ребра были введены оценки, позволяющие однозначно упорядочивать по возрастанию углов наклона ребра многоугольников. Если вектор ребра многоугольника определяется как v = (x,y), то оценка имеет вид:

л

Рис. 2. Разбиение невыпуклого многоугольника на выпуклые

г1 =шах{г'}, ¿ = 1,2,...,/я. Величина г' опреде-

]ш\,к * 1

ляется как расстояние от вершины и] (У = 1,2,...,А) многоугольника В до прямой, проведенной через точку отсчета многоугольника В, с вектором нормали пг В результате

получается набор прямых (е',е'2.....е'т). Пусть

р, - точка пересечения прямых е'г, е'м для / = 1,2,...,т. Для корректировки набора точек

Рис 3 Процедура построения внутреннего годографа

1 Benell J A, Dowsland K A, Dowland W B The irregular cutting-stock problem - a new procedure for deriving the no-fit polygon// Computers & Operations Research. 2001 №28 P. 271-287

s(v) =

12

x

V* +/

2 + т=^=1>,<0 V*+У

После построения ОДР выполняется обработка списка годографов relsv (1<7</, z=2, 3,..., я), соответствующего отношению невыпуклых многоугольников. Ее цель - ликвидация взаимных пересечений выпуклых годографов. Существует три причины выполнения данной процедры: во-первых, при решении задачи методом активного набора, активными не должны быть внутренние для совокупности годографов reis у ребра годографов (такие ребра и неравенства, соответствующие им будем называть «специальными»); во-вторых, если при решении задачи, очередное приближение попадает на некоторую вершину совокупности годографов г els,j, то возникает необходимость определения всех ребер всех годографов, активных в данной точки; в-третьих, суммарное число ребер без ликвидации взаимного пересечения в несколько раз больше, чем после ликвидации.

Алгоритм ликвидации пересечений рассматривает годографы попарно, заменяя пару годографов Н, и HJ на непересекающийся набор выпуклых многоугольников, объединение которых эквивалентно HI\JH). Ключевым моментом здесь будет нахождение этого набора многоугольников. Для этого сначала находится объединение двух выпуклых многоугольников и HJ, а затем оно

разбивается на ряд выпуклых.

Вышеописанные процедуры позволяют построить модель ОДР задачи.

Процедуры шагов 5-11 обеспечивают получение очередного приближения. Поиск активных неравенств ведется с учетом того, что активными не могут бьггь специальные неравенства relsy. Когда точка очередного приближения попадает на вершину границы набора relsy, то, если эта вершина выпуклая, в качестве активного произвольно выбирается одно из двух неспециальных неравенств, инцидентных данной вершине, если невыпуклая, то активными будут оба неспециальные неравенства. Кроме того, необходимо контролировать точку приближения на ее принадлежность именно границе допустимой области, а не ее внутренней части.

Процедуры подготовки данных для задачи ЛП и преобразования полученного решения задачи ЛП в вектор движения g предназначены для установления соответствия между переменными ЛП и элементами вектора g. Если при нахождении активных неравенств для некоторого многоугольника S, (/е[1,л]) не найдено ни одного отношения, rels4 (у'е[0,/-1]), содержащего активные не-

равенства, то компоненты вектора g, соответствующие изменению положения этого многоугольника не участвуют в качестве переменных в задаче ЛП.

После нахождения вектора % необходимо определить длину шага а (10 шаг алгоритма). Для этого создается список Я допустимых диапазонов значения а. Список инициализируется {я0™п,аот"}. При рассмотрении очередного диапазона {-со,а™ }и {а,™",+со} (г'=1, 2, ..., т) выполняется его пересечение с теми, которые уже есть в списке. Важным моментом является учет границ диапазонов. Если, например, значение а™ соответствует специальному неравенству, то выполняется пересечение всех диапазонов с интервалом (-оо.а,™1), если неспециальному, то с полуинтервалом (-оо, а,""" ].

После получения вектора g и длины шага а, суммируя вектор V с вектором ag, получаем следующее приближение.

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

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

метод поиска локального экстремума независимо от вида используемого приближенного метода ПОР.

На рисунках 5-8 приведен пример работы схемы. В качестве приближенного метода использовался классический «жадный» алгоритм.

Рис. 5. Начальное приближение

Рис. 6. Локальная оптимизация начального приближения

Рис 7 Занесение еще одного ГО и локальная Рис. 8. Занесение еще одного ГО и оптимизация окончательная оптимизация

Разработанная схема и алгоритм нахождения локального экстремума были встроены в систему «ЫейСАО/САМ», в которой для получения карт раскроя использовался метод ПОР, годографы для которого строятся на базе дискретно-логического представления информации (ДЛПИ) и цепном кодировании (ЦК). Пример работы «КевЮАО/САМ» при использовании разработанной схемы приведен на рисунке 9.

а) б)

Рис. 9. Карта раскроя, полученная с помощью «КейСАО/САМ». а) - метод ПОР с годографами на основе ДЛПИ и ЦК (длина - 4986), 6) - комбинации метода ПОР с годографами на основе ДЛПИ и ЦК и метода поиска локального экстремума (длина 4862) Исследование разработанного метода поиска локального экстремума проводилось с использованием начального приближения, полученного классическим «жадным» алгоритмом. Выборочные результаты эксперимента приведены в таблице.

№ К-во ГО Допуски Нач. длина Кон. Длина Величина улучшение (%)

1 37 0.15/0.15 401,935 383,195 4,6

2 16 0.15/0.15 188,224 184,579 1,9

3 47 1/1 405,086 390,805 3,5

4 56 1/1 472,386 450,689 4,5

5 44 1/1 447,154 433,949 2,9

6 33 1/1 289,392 281,556 2,7

7 40 1/1 377,867 369,241 2,2

8 43 1/1 377,718 365,340 3,2

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ

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

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

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

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

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

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

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

2. Петренко C.B., Верхотуров М.А. Плотная упаковка ориентированных невыпуклых многоугольников: двухэтапный способ решения //Математическое программирование и приложения: Матер, конф. Инфор-мац. бюлл. Ассоциации математического программирования. Екатеринбург: УрО РАН, 2003. №10. С. 69-70.

3. Петренко C.B., Верхотуров М.А., Верхотурова Г.Н., Логинов Е.В. Задача нерегулярного раскроя фигурных заготовок: построение пути режущего инструмента //Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2003. С.158-163.

4. Петренко C.B., Верхотурова Г.Н., Верхотурова О.М., Павлов Й.А. Анализ эффектавности эвристических методов на примере решения задачи коммивояжера //Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2004. Выпуск 1. С. 199-201.

5. Петренко C.B., Верхотуров М.А. Об одном способе решения задачи размещения невыпуклых ориентированных многоугольников в полубесконечной полосе //Дискретный анализ и исследование операций: Матер. Рос. конф. Новосибирск: Ин-т математики, 2004. С. 182.

6. Петренко C.B., Верхотуров М.А. Нерегулярное размещение невыпуклых ориентированных многоугольников в односвязной невыпуклой области //Методы оптимизации и их приложение: Тр. XIII Байкальской междунар. шк. сем. Иркутск-Северобайкальск. Математической программирование. Иркутск: ИСЭМ СО РАН, 2005. Т.1. С. 435-443.

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

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ

Диссертант

Петренко C.B.

ПЕТРЕНКО Семен Васильевич

ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ ДВУМЕРНЫХ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ НА АНИЗОТРОПНОМ МАТЕРИАЛЕ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Специальность 05 13.18 - Математическое моделирование, численные методы

и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано к печати 16 11 2005 Формат 60x84 1/16 Бумага офсетная. Печать плоская Гарнитура Times New Roman Cyr Усл. печ. л 1,0. Уел кр. отг 1,0. Уч.-изд л 0,9 Тираж 100 экз. Заказ № 513.

Уфимский государственный авиационный технический университет Центр оперативной полиграфии УГАТУ 450000, Уфа-центр ул К. Маркса, 12

» 2 3 4 1 2

РНБ Русский фонд

2006-4 27695

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

Введение.

Глава 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 %.

Заключение

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

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