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

На правах рукописи

Лисафина Мария Сергеевна

УПАКОВКА КРУГОВ И ЭЛЛИПСОВ В ОГРАНИЧЕННУЮ ОБЛАСТЬ

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

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

005557563

1 5 ;,г,!3 2015

Казань 2014

005557563

Работа выполнена в ФГБОУ ВПО «Казанский национальный исследовательский технический университет им. А.Н. Туполева-КАИ».

Научный руководитель:

Официальные оппоненты:

Галиев Шамиль Ибрагимович

доктор технических наук, профессор кафедры прикладной математики и информатики Казанского национального исследовательского технического университета им. А.Н. Туполева-КАИ

Заботин Игорь Ярославич

доктор физико-математических наук, доцент кафедры анализа данных и исследования операций Казанского (Приволжского) федерального университета

Ведущая организация:

Кирпичников Александр Петрович доктор физико-математических наук, профессор, заведующий кафедры Интеллектуальных систем и управления информационными ресурсами Казанского национального исследовательского технологического университета

Марийский государственный университет, г. Йошкар-Ола

Защита состоится 29 января 2015 г. в 14 часов 30 минут на заседании диссертационного совета Д 212.081.21 при Казанском (Приволжском) федеральном университете в 218 аудитории 2 корпуса по адресу: 420008, г. Казань, ул. Кремлевская, 35.

С диссертацией можно ознакомиться в научной библиотеке им. Н.И. Лобачевского при ФГАОУ ВПО «Казанский (Приволжский) федеральный университет» по адресу: 420008, г. Казань, ул. Кремлевская, 35.

Электронная версия автореферата размещена на официальном сайте Казанского (Приволжского) федерального университета http://www.kpfu.ru

Автореферат разослан 26 декабря 2014 г.

Ученый секретарь диссертационного р

совета д. ф.-м. н., профессор <3tLCfJ&r^~ O.A. Задворнов

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

Актуальность темы. Интерес к задаче упаковок связан, в первую очередь, с их приложениями к различным практическим задачам. Проблема упаковки в двух и многомерных пространствах Е", п > 2, а также на сфере в Е", п£3, находит приложения при кодировании и передачи информации.

Задача упаковки кругов одинакового или разного радиусов в заданную ограниченную область имеет приложения в логистике, при раскрое деталей из дерева, тканей и металлических листов. Также такие проблемы возникают при оптимизации расположений станций различного назначения. Упаковки эллипсов используются при анализе структур из эллиптических молекул в кристалле, упаковки эллипсоидов используются для анализа структур цементных растворов и в ряде других практических задачах. Фундаментальные результаты по упаковкам в пространстве и на сфере «-мерного евклидова пространства Е", , были получены в работах Л. Фейеша Тота, Г. Фейеша Тота, К. Роджерса, Дж. Конвея, Н. Слоэна и многих других ученых.

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

Различные подходы к задачам упаковок равных кругов содержатся в работах Биргана Е.Г. и Гентила Дж. М., Биргана Е.Г., Мартинеса Дж.М. и Ронкони Д.П., Кастилло И., Кампаса Ф.Дж. и Пшггера Дж.Д., Лоди А., Мартело С. и Монаки М., Сзабо П.Г., Хифи М. и М'Халлаха Р., Хуанга В. и многих других авторов.

Для исследования упаковок кругов разных радиусов тоже имеется много публикаций, в которых предлагаются различные эвристические процедуры, например, работы Хуанга В., Ли С., Ли У., Акеба X. и Ху Р. В некоторых работах эвристические процедуры используют локальный поиск экстремума целевой функции, например, в работах Пономаренко Л.Д. и Макмака П.М., Стояна У.Г. и Яшкова Г.Н. В работе Жоржа Дж.А., Жоржа Дж.М. и Ламара Б.В. предложены эвристики, использующие кодирование решений с помощью перестановок возможных положений кругов относительно друг друга.

Задачи упаковок эллипсов или эллипсоидов рассмотрены в работах Делане Г., Вайера Д., Хитзлера С. и Мурфи С., Зоу З.У. и Пинсона Р.П., Хираги У., Ху В.Х. и Чень Х.С., Ху В.Х., Чень Х.С. и Ли 3. и некоторых других авторов.

По задачам упаковок и родственной ей задаче покрытия много важных результатов получены российскими исследователями, среди них работы следующих авторов: Андрианова A.A., Астарков С.Н., Еремеев A.B., Ерзин

A.И., Залгаллер В.А., Залюбовский В.В., Заозерская Л.А., Кабатянский Г.А., Канторович Л.В., Козюрин И.В., Колоколов A.A., Корбут М.Ф., Левенштейн

B.И., Мухачева Э.А., Мухтарова Т.М., Фазылов В.Р., Галиев Ш.И. и др.

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

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

Задачи исследования:

1. Построить и исследовать математическую модель задачи упаковки равных кругов и кругов двух заданных радиусов в произвольную ограниченную область.

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

3. Разработать алгоритмы для решения построенных моделей.

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

5. Провести численные эксперименты, которые характеризуют результативность построенных моделей, алгоритмов и программ.

Методы исследования. В работе использованы методы исследования операций, построения математических моделей, теория оптимизации, численные методы решения оптимизационных задач, в том числе методы решения задач дискретной оптимизации и математического анализа. Для разработки комплекса программ применялись современные методы программирования и библиотека ILOG CPLEX.

Научная новизна:

- предложен подход к построению математических моделей, на основе которого

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

- получены условия непересечения горизонтальных (вертикальных) эллипсов и эллипсов с взаимно ортогональными ориентациями; введена метрика для данной задачи и подобраны ее параметры;

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

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

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

Теоретическая и практическая значимость. Теоретическая значимость

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

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

Апробация работы. Основные материалы и результаты исследований докладывались, обсуждались и получили одобрение на конференциях: III и IV International conference «Optimization and Applications» в 2012 г. в Португалии и в 2013 г. в Черногории, на Международной конференции «Дискретная оптимизация и исследование операций» (Д00р-2013) в Новосибирске в 2013

году, на XVII, XVIII и XX Международной молодежной научной конференции «Туполевские чтения» в 2009,2010 и 2012 гг.

Публикации. По теме диссертации опубликовано 12 печатных работ, в том числе 4 статьи, 3 из них - в журналах, рекомендованных ВАК РФ для публикаций основных результатов диссертации.

Личный вклад соискателя. При выполнении работ [5, б, 8-12], выполненных совместно с научным руководителем, соискатель результативно участвовал в разработке математических моделей, введении уровней положений центров упаковываемых фигур и весов этих уровней. Сравнительный анализ прямоугольного и косоугольного способа построения сеток на упаковываемом множестве, разработка условий непересечения эллипсов, подбор метрики для выяснения непересечения эллипсов, разработка алгоритмов, программного обеспечения и проведение расчетов выполнено лично соискателем.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, списка цитированной литературы, включающего 106 наименований. Общий объем диссертации насчитывает 125 страниц машинописного текста, включая 45 рисунков и 12 таблиц.

СОДЕРЖАНИЕ РАБОга

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

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

Совокупность п равных открытых кругов Кь 1 <]<п, образует упаковку в в, если каждый круг содержится в (7, 1 <у<л, и каждая точка л из в принадлежит не более чем одному из этих кругов.

Задача С1: Требуется определить максимально возможное число равных открытых кругов известного радиуса г упаковываемых в область в и определить положения их центров.

Считаем, что на Р введена декартова система координат хОу и пусть с1(я,1) - евклидово расстояние между точками 1И/. Пусть в* (<Э*с: (7) множество всех точек 5 из О таких, что расстояние от 5 до ближайшей к ней точки границы области О (/гС) не менее чем г.

Пусть () - наименьший прямоугольник, содержащий множество в* и его стороны параллельны осям координат. На множестве Q построим прямоугольную сетку с шагом А по осям х и у. Узлы сетки лежащие в б* порождают дискретное множество 1\А). Далее множество 71{А) уточняется с помощью специальной процедуры.

Аналогично прямоугольной в работе строится косоугольная сетка, одна образующая линия которой параллельна оси х, а другая параллельна вектору (1, Л). Узлы этой сетки тоже порождают конечное множество в некоторых из которых могут располагаться центры упаковываемых фигур.

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

Пусть для заданного множества б, выбрана величина шага сетки А и построено множество Т\А) = /2,

Задача С2: Требуется определить максимально возможное число непересекающихся в (7 равных открытых кругов заданного радиуса г, центры которых лежат в некоторых точках множества Т{А), и найти положения их центров.

В дальнейшем вместо задачи С1 мы решаем задачу С2. Ясно, что полученная упаковка даст приближенное решение задачи С1, но во многих инженерных расчетах такое решение может быть приемлемо.

Введем переменные:

Пусть центр упаковываемого круга К совпал с точкой то есть г, = 1, 1< / < п. Для того чтобы К не пересекался с остальными упаковываемыми кругами нужно, чтобы величины равнялись нулю для всех точек Ц, I Ф находящихся на расстоянии меньшем, чем 2г от Пусть для точки /,■ имеется /и,-точек /у, / \<.] < п, для которых < 2г. Запишем условие непересечения кругов в следующем виде.

О,

1, если в точке расположен центр круга, О, иначе

Если 2, = 1, то для всех} таких, что </(/„!/) < 2г имеем

= 0,1*у, 1 5 / < п.

В работе доказана следующая теорема. Теорема 1. Условие (2) эквивалентно условию:

+ X г]<, от,

(3)

Введем коэффициенты:

/ 1 < у <, п; ан = от,-, \<1<, п.

Условие (3) можно записать теперь в виде:

апг\ + ап*г + - + аыгп < от,, 1 < I < п. Пусть А является пхп матрицей с элементами ая, 1 2 и М

векторы: 2 = (гь2г,...,гп)Т, М = (тит2.....т„)Т, 1 </'<«, определены по (1).

Рассмотрим задачу:

Задача (4) является задачей упаковки в б наибольшего числа кругов радиуса г с центрами в некоторых из точек множества Т. Решая ее, находим N -число упаковываемых кругов радиуса г, а найденные значения г, определяют положения центров кругов.

Полагаем, что точки /, и из множества Т находятся на одном уровне, если их координаты у одинаковы. Для множества Т получим конечное число уровней, на которых расположены точки из Т. Припишем этим уровням их номера, полагая, что счет идет снизу вверх. Каждому 1-му уровню припишем вес этого уровня - положительное число с,-. Введем веса уровней так, что с/+1 < с1- Переменные г, (соответствующие течкам /,) будем умножать на веса с„ которые будут равными для всех точек одного уровня и уменьшаться с увеличением номера уровня. Рассмотрим задачу:

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

Множество в, в которое мы упаковываем фигуры, разобьем на выбранное число (от) частей:

п

N = £г( -> тах: Аг<М, zi б/"0,1}, 1<,\<>п.

(4)

П

N = -> тах: А2 <, М, г, е {0,1}, 1<Ип.

(5)

Dal={seG:( min d(s,t)>r)& ( min d(s,q ¡)^2r)}, l<.i<.m,

te fr Dai К j ePafí^ )

здесь q¡ — центр круга K¡, принадлежащего упаковке Рацл), построенной для Da(¡_{). Далее на множестве Da¡ строится сетка, узлы которой порождают

множество Тси(Л). Используя Та,(Л), строится вспомогательная задача с учетом весов уровней, решая которую, получаем упаковку Р^ для подмножества £)ш-.

Будем считать, что если число переменных (размерность) задачи (5) равна и*, то мы можем решить эту задачу за приемлемое время. Построим следующий алгоритм, в котором эвристикой является выбор числа разбиений исходного множества на части и выбор весов уровней.

Алгоритм Ä1.

1.Для множества G находим G*. Выбираем величину шага А сетки и строим множество Т(А) ={<i, h,..., t„}.

2. Если число элементов (и) множества 1\А) приемлемо (и < и*), то строим и решаем задачу (4). Процедура завершается, иначе переходим к шагу 3.

3. Если п > и*, то на области G строим m подмножеств £>ш, 1 <i<m, так, чтобы вспомогательные задачи, построенные для них, имели приемлемую размерность. Последовательно решая вспомогательные задачи для каждого подмножества, начиная с Д,ь получаем упаковки в этих подмножествах. Объединение полученных упаковок для подмножеств £>ш, 1 <i<m, считаем решением задачи упаковки для множества G. Завершаем процедуру.

Подбирая параметры алгоритма Al, можно добиться приемлемых результатов.

В работе были рассмотрены упаковки кругов в три фигуры:

- невыпуклая фигура В, см. рис. le) и 1г), ее размеры легко определить исходя из условия, что в нее упаковываются ровно 3 круга радиуса 1.

- прямоугольник шириной 3 и высотой 6, обозначим его через R;

- прямоугольник R, из которого вырезаны два круга радиусов 0.625 и 0.5, обозначим эту фигуру через Rj. Вырезанные части Rj на рис. 1а) и 16) выделены серым цветом.

Наши исследования мотивированы необходимостью вырезать как можно больше кругов (дисков) заданного радиуса из стального листа, который может оказаться частично использованным. Поэтому были выбраны прямоугольник R и фигура Rj. Размеры R выбраны так, чтобы R был подобен фигуре некоторого реального стального листа. Фигура В (сапожок) выбрана, чтобы показать возможности метода для упаковки кругов в невыпуклую область.

На рис. I представлены некоторые полученные результаты упаковок. На рис. 1 а) и 16) представлены результаты упаковки кругов в область Я* а на рис. \в) и \г) представлены результаты упаковки кругов в фигуру В.

а) б) в)

Рис. I. Упаковка кругов в произвольную область

Во всех случаях, когда задача (4) решалась без привлечения эвристики и с привлечением эвристики числа упаковываемых кругов оказывались одинаковыми. При этом время счета с использованием эвристики оказывается много (иногда в сотии раз) меньше, чем без использования эвристики. Для случаев, когда задача решалась только эвристическим алгоритмом, качество решения характеризует плотность упаковки. Для упаковок в прямоугольник Я плотность упаковки сравнивалась с плотностью наилучших известных упаковок. Сравнение показало, что плотности полученных упаковок, как правило, совпадает с плотностями наилучших известных упаковок, например, представленных в монографии Хифи и др.

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

Пусть Е является эллипсом, центр которого расположен в точке с{х,у), а длины его большой и малой полуосей равны о и Л соответственно. Величины а и Ь считаем параметрами эллипса. Пусть большая ось эллипса параллельна оси х, тогда такой эллипс с указанным центром фс,у) и параметрами а и Ь обозначаем как ЦХ,х,у,а,Ь) и считаем его горизонтальным эллипсом. Если

большая ось эллипса параллельна оси у, а его центр и параметры прежние, то такой эллипс обозначаем через Е{У\х,у,а,Ь) и считаем его вертикальным эллипсом. Считаем, что по тексту ясно, где используется кривая эллипс, а где фигура, ограниченная кривой эллипс.

Задача Е1: Требуется определить максимально возможное число равных открытых эллипсов известных параметров, упаковываемых в Я, и определить положения их осей и центров.

Пусть Л* (Д*с К) множество всех точек из Я таких, что .фу)

является центром некоторого эллипса Е, содержащегося в Я: Е с Я. Тогда открытый эллипс Е состоит только из внутренних точек множества Я: Ш(Е) с: Я, здесь и в дальнейшем т/(2) обозначает внутренность множества 2.

На множестве Я* построим прямоугольную сетку. Узлы построенной сети, обозначим через Гь г2,-"Л, п> положим, что т= {<ь <2,•■■Л), при этом каждая точка /,, 1< / < п, принадлежит множеству Я*.

Задача Е2: Требуется определить максимально возможное число упакованных в Я равных открытых эллипсов заданных параметров а и Ъ, центры которых лежат в некоторых точках множества Т и определить положения их осей и центров.

Тео,, ла 2. Пусть Е\(Х;0,0,а,Ь) и Е*(Х;0,0,2а,2Ь) эллипсы с центрами в начале координат и указанными значениями параметров. Тогда любой эллипс Е2(Х;х2хуьа,Ь), центр С2(хг,у2) которого лежит на кривой, ограничивающей фигуру Е*{Х;0,0,2а,2Ь), имеет единственную точку пересечения с эллипсом Ех{Х;0,0,а,Ь).

Следствие 2. Теорема 2 остается в силе, если в нем всюду в записях эллипсов символ ^заменить на К.

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

Введем переменные:

Пусть центр упаковываемого эллипса Е,{Х;хьуьа,Ь) совпал с точкой 1х,{х!,у,), то есть согласно (6) г,- = 1, 1< /' < п. Для того, чтобы не пересекался с остальными упаковываемыми эллипсами, нужно, чтобы для всех точек (центров эллипсов) ¡ф I Ф }, находящихся внутри эллипса Е*(Х;хьуь2а,2Ъ), величины X] равнялись нулю. Пусть имеется г,- точек / ф], 1<у <. п, которые

если в точке 1Х1 расположен центр эллипса, иначе

1 < I < и.

(6)

находятся внутри эллипса E*(X;x¡,y¡,2a,2b). Запишем указанное условие в следующем виде.

Если z¡ = 1, то для всехj таких, что txj е int(E*(X;x¡,y¿ 2а,2b)) (7)

имеем Zj = 0, i * j, 1 <i<n.

Теорема 3. Условие (7) эквивалентно условию:

riz¡+ Yjzj (8)

Введем коэффициенты:

_ 1, если txj е int(E*(X;x„yl,2a,2b)) , . } . < ^ в» = {о. eaiutx¡<£ int(E*(X;Xi,y¡,2a,2b)), ,l*h a¡¡ =r¡, 1 Si<n.

Используя теорему 3, получим, что для выбранного i условие (7), : следовательно, и условие (8) можно записать теперь в виде: anzx+ai2z2 + ... + a¡r,zn<r¡, \<i<n.

Пусть А является пхп матрицей с элементами a¡j, t<i,j <.п, Z и Мх

векторы: Z = (zbz2.....z„f, Мх =(r,,r2,...,r„)T. Рассмотрим задачу:

Nx = Y.z¡ -> /пах (9)

при ограничениях: /(Z < г,- £ fO,l j, 1 < г < л. (10)

Решая задачу (9)-(10) находим Nx - число упаковываемых эллипсов, а найденные значения z¡ определяют положения центров эллипсов.

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

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

Если эксцентриситеты эллипсов E¡ и Ег с центрами С\ и Сг соответственно равны нулю е, = е2 = 0 (а = Ь), т.е. E¡ и Е2 круги, то очевидно, что центр С2 лежит на окружности радиуса г = 2а (г = а+b), а центр этой окружности находится в точке С\. Обозначим введенную окружность через W. Когда эксцентриситеты стремятся к единице, то точка Сг стремится к точке на границе квадрата Q, стороны которого параллельны осям координат, а длина стороны квадрата равна 2а.

Точка касания двух равных эллипсов с взаимно перпендикулярными большими осями то приближается к окружности W и сторонам квадрата Q, то

отдаляется от них. Аналогичным образом ведут себя точки «окружностей», порожденные 1Р метрикой. Для р = 2 расстояние, введенное по 1р метрике, является обычным евклидовым расстоянием и <1Р = г является уравнением окружности радиуса г, например, с центром в точке ^(дг^), при этом точка Г(х„у,) лежит на окружности IV радиуса г. При р = оо уравнение с1р (л,г) = г определяет стороны квадрата 2 с центром в точке х(хяу5).

Подбор значения р осуществляем так, что точка пересечения (точка Сз) луча Ь исходящего из точки С\ с кривой ¿'р отстоит от точки С\ дальше, чем С2 (по евклидовому расстоянию), следовательно, если центр эллипса Ег лежит в точке пересечения Ь с то эллипсы Е\ и £2 не пересекаются.

Положим, что центр эллипса совпал с точкой 1х1. Теперь нужно записать условия непересечения Е, с эллипсами большие оси которых перпендикулярны большой оси эллипса £,. Пусть для имеется <?, точек для которых(1р /л) <а + Ь, 1 <г<п. Введем коэффициенты:

{1, если с]пЦ-,,1„:)<а + Ь,

рК" ,1 = 1.....= 1, ..., т,

О, иначе

С/./+я = Яв 1-' - п> са ~ 0,1<»< п, т + 1 </ < т + и,у * ¡+т.

Из коэффициентов с,у, 1<< п, т + 1 <_/ < т + п, можно построить пх(т + л) матриц) Введем векторы У2 = (V/, у„, г/, ....г^7 и А/„ = /, .... д„)т. В диссертации построены ограничения непересечения каждого возможного горизонтального эллипса с возможными вертикальными эллипсами в виде С(У2) < М„. Далее задача упаковки эллипсов, часть из которых может иметь большие оси параллельные оси д:, а часть — оси у, записана в виде:

г,+... +2„ + VI+...+vm—^ тзх (11)

при ограничениях:

лг<мх, ву<му, с(уг)<м„г,ъ{ол}.\$>$п,

уу е {0,1}, 1 <] <т. (12)

Для решения задачи предложен следующий алгоритм.

Алгоритм А2.

1.Для множества Я находим Я*. Выбираем величины шагов сетки и строим множество /2,..., /„}.

2. Если число элементов (и) множества Г приемлемо (и < п*), то строим и решаем задачу (11)-(12). Процедура завершается, иначе идем к шагу 3.

3. Если п > п*, то на области Я строим т, т>2, подмножеств \<1<т, так, чтобы вспомогательные задачи, построенные для них, имели приемлемую размерность. Последовательно решая вспомогательные задачи для каждого

подмножества, начиная с £>„i. получаем упаковки в этих подмножествах. Объединение полученных упаковок для подмножеств I iiim, считаем решением задачи упаковки для множества Л. Завершаем процедуру.

fia рис. 2 представлены некоторые результаты решения задач упаковки эллипсов в прямоугольную область.

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

Задача CNI: Требуется определ1тть упаковку в G некоторого числа кругов Kf, заданных радиусов Г\ или (и) г2, так, чтобы суммарная площадь упакованных кругов оказалась наибольшей нз возможных, и указать расположения центров этих кругов.

в) б) в) г)

Рис. 2. Упакозкн в Я: а) 45 кругов, б) 45 горизонтальных эллипсов, в) 45 вертикальны* эллипсов, г) 24 горизонтальных и 21 вертикальных

эллипсов

Для упаковки кругов радиусов г, и г2 строятся две сетки, которые порождают два конечных множества Г» (/|, и 5 = л,} узлов

этих сеток.

Задача С^: Требуется определить упаковку в О некоторого числа кругов Кзаданных радиусов г, или (и) г2, так, чтобы суммарная площадь упакованных кругов оказалась наибольшей из возможных, центры кругов радиуса г, лежали в не<оторых из точек множества Г, а центры кругов радиуса г2 лежали в некоторых из точек множества 5. При этом требуется указать расположения центров упакованных кругов.

Задача CN3 является задачей CN2 с дополнительным ограничением на число кругов радиуса г\ либо число кругов радиуса гг. .

Введем переменные 2Д1 < i < п), используя точки из Г для задачи упаковки кругов радиуса г, и vj (/ < j < т) для задачи упаковки кругов радиуса гг. Тогда можно построить задачи вида (4), ограничения которых имеют вид AZ<,M\,zt е{0\}, l<i<n и BV <M2,Vj g{ ОДЛ /< j<m соответственно. В этих ограничениях матрицы А, В и векторы Z и V получаются аналогично как для задачи (4) для радиусов г\ и гг соответственно.

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

я п т

соответствует максимизации функции (г//г2) + 2 v -. Задача CN2 упаковки

.=! j=l

кругов радиусов г, и г2 будет иметь вид:

п п т

(r,/r2)2 Zz, + I v, — шах (13)

i=i ;=i

пр. -»граничениях: AZ <M1,BV<, М2, C(VZ) < М„

z, е {0,1}, 1 </<п, Vje {0,l}, IZjim. ^^

Здесь C(VZ) < М„ условия непересечения кругов радиусов и гг. Алгоритм решения предлагается следующим.

Алгоритм A3.

1. Для множества G находим Gi и G2- Выбираем величины шага А и А* сетки и строим множества T={ti, t2,..., t„) HS={s1,s2,...,sm}.

2. Если число элементов (n+т) множества W=T U S приемлемо (п+т < п*), то строим и решаем задачу (13)-(14). Процедура завершается, иначе переходим к шагу 3.

3. Если п+т > п*, то выбираем g, g> 1, ш", l</<g-l и на области G строим g подмножеств D^, 1 </<g, так, чтобы вспомогательные задачи, построенные для них, имели приемлемую размерность. Последовательно решая вспомогательные задачи для каждого подмножества, начиная с Daь получаем упаковки в этих подмножествах. Объединение полученных упаковок считаем решением задачи упаковки для множества G. Завершаем процедуру.

Отметим, что на шаге 3 для каждого из множеств Dai, l</<g-l, мы решаем задачу упаковки дважды. Сначала решаем ее без введения весов уровней, затем

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

Задачу CN3 решаем аналогично задаче CN2, учитывая ограничения на числа кругов заданного радиуса.

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

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

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

В диссертационной работе:

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

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

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

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

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

6. Проведены многочисленные расчеты, демонстрирующие результативность моделей и алгоритмов.

Разработанный метод имеет следующие важные особенности:

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ1 Публикации в журналах из перечня ВАК и Web of Science:

1.Галиев Ш.И., Лисафина М.С. Оптимизация покрытия при наличии ограничений // Вестник КГТУ им. А.Н. Туполева. - 2012. - № 2. - С. 144 - 147.

2. Галиев Ш.И., Лисафина М.С. Численные методы оптимизации упаковок равных ортогонально-ориентированных эллипсов в прямоугольную область // Журнал вычислительной математики и математической физики. — 2013.-Т. 53,№ п.-с. 1923-1938.

3. Galiev Sh.I., Lisafina M.S. Linear models for the approximate solution of the problem of packing equal circles into a given domain // European Journal of Operation. 4esearch. - 2013. - V.230. - P. 505-514.

4. Лисафина M.C., Галиев Ш.И. Упаковки кругов разных радиусов в ограниченную область // Вестник КГТУ им. А.Н. Туполева. - 2014. - № 2, -С.168-174.

Публикации в других изданиях:

5. Куншина М.С. Ненросетевой метод решения задач покрытия и упаковок // Междунар. молодежи, научн. конф. «XVII Туполевские чтения». — Казань: Изд-во Казан, гос. техн. ун-та, 2009. - Т. IV. - С . 27-29.

6. Kunshina M.S. Multi-layered perceptron applied for covering and packing problems // Междунар. молодежи, научн. конф. «XVII Туполевские чтения». — Казань: Изд-во Казан, гос. техн. ун-та, 2009. — Т. VI. - С. 96-97.

7. Куншина М.С. Применение радиальных нейронных сетей для решения задач покрытия // Междунар. молодежи, научн. конф. «XVIII Туполевские чтения». — Казань: Изд-во Казан, гос. техн. ун-та, 2010. — Т. IV — С. 148-150.

8. Лисафина М.С. Программный комплекс для решения задачи покрытия кругами разного радиуса // Междунар. молодежи, научн. конф. «XX

1 01.11.2011 г. фамилия Куншина изменена на фамилию Лисафина.

Туполевские чтения». - Казань: Изд-во Казан, гос. техн. ун-та, 2012. — Т. III, Ч. 1. — С.446-448.

9. Galiev Sh., Lisafina М., Judin V. Optimization of a multiple covering of a surface taking into account its relief // Abstracts of III International conference «Optimization and Applications». Costa da Caparica, Portugal. September 23-30, 2012. - Moscow, 2012. - P.86-90.

10. Лисафина M.C. Алгоритмы и программный комплекс оптимизации упаковок кругов и эллипсов Н Сборник статей международной научно-практической конференции «Закономерности и тенденции развития науки в современном обществе». — Уфа, 2013. — Ч. 1. - С. 3-5.

11. Лисафина М.С., Галиев Ш.И. Приближенное решение задачи упаковки кругов разных радиусов с помощью линейного программирования II Материалы международной конференции «Дискретная оптимизация и исследование операций». — Новосибирск, 2013. - С. 140.

12. Galiev Sh.I., Lisafina M.S. Optimization of packing equal ellipses into a rectangular // Abstracts of IV International Conference on Optimization Methods and Applications (OPTIMA-2013). Petrovac, Montenegro. September 22-28, 2013. -Moscow, 2013.-P. 62-63.

Усл. печ. л. 0,93. Тираж 100. Заказ Г100 Копи-центр КНИТУ-КАИ. 420111, Казань, К.Маркса, 10