Упаковка кругов и эллипсов в ограниченную область тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Лисафина, Мария Сергеевна

• Лисафина, Мария Сергеевна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Лисафина, Мария Сергеевна

Оглавление

Введение

Глава 1. Упаковка равных кругов

1.1. Постановка задачи

1.2. Математическая модель задачи

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

1.4. Подбор параметров алгоритма

1.5. Численные результаты

1.6. Выводы

Глава 2. Упаковка равных эллипсов

в прямоугольную область

2.1. Постановка задачи

2.2. Случай эллипсов с большими осями параллельными друг другу

2.2.1. Условие касания эллипсов

2.2.2. Способы построения сетки

2.2.3. Упаковка горизонтальных эллипсов

2.2.4. Упаковка вертикальных эллипсов

2.3. Случай эллипсов с взаимно перпендикулярными большими осями

2.3.1. Условия касания эллипсов

2.3.2. Упаковка эллипсов

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

2.5. Подбор параметров алгоритма

2.6. Численные результаты

2.7. Выводы

Глава 3. Упаковка кругов разных радиусов

3.1. Постановка задачи

3.2. Упаковка кругов радиусов г\ и г г

3.3. Алгоритм решения задач упаковок кругов радиусов г\ и гг

3.4. Численные результаты

3.5. Выводы

Глава 4. Программное обеспечение

4.1. Описание комплекса программ

4.2. Структура комплекса программ

4.3. Руководство пользователя

4.4. Выводы

Заключение

Список использованной литературы

Введение диссертации (часть автореферата) на тему «Упаковка кругов и эллипсов в ограниченную область»

Введение

Проблема упаковок тел и фигур возникает в различных практических задачах. Первая математическая постановка задачи упаковок, видимо, принадлежит И. Кеплеру. Если частицы имеют форму шаров, то ясно, что как бы они ни располагались в пространстве, между ними неизбежно останутся зазоры, и вопрос состоит в том, чтобы объем зазоров свести к минимуму. Кеплер рассмотрел несколько различных вариантов расположения шаров и для каждого варианта вычислил коэффициент заполнения пространства. Один из первых вариантов расположения шаров, рассмотренных Кеплером, сейчас принято называть гранецентрированной кубической решеткой. Гипотеза Кеплера (1611г.) гласит:

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

Математически доказать гипотезу не удавалось на протяжении 400 лет. Сообщение о компьютерном доказательстве гипотезы Кеплера появилось в 1998 году в работе математика Томаса Хейлса. В 1998 году Хейлс объявил о найденном им строгом математическом решении задачи Кеплера, основанном на сочетании аналитической геометрии и сложных компьютерных вычислений. Журнал «Анналы математики» принял статью на экспертизу и создал комиссию из двадцати ведущих специалистов в этой области для составления отзыва о статье. Экспертная комиссия начала свою работу на конференции в Принстонском университете по выработке общей стратегии. Шли годы, референты постепенно выходили из состава комиссии, и наконец, в начале 2004 года было окончательно решено отказаться от усилий рецензировать статью. Редколлегия журнала решила опубликовать «теоретическую часть» работы, а «компьютерную часть» переадресовать в какой-нибудь другой журнал.

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

помех. Для максимального увеличения объема передаваемой информации эти сферы должны быть упакованы так плотно, как возможно. В 1970-е годы Лэнг изобрел модем, используя упаковку сфер Е8 в 8 мерном пространстве. Также были задействованы и другие результаты по упаковкам сфер. Это помогло развитию Интернета, так как появилась возможность передавать данные по телефону вместо использования специально разработанных кабелей. О связи проблемы упаковки шаров с кодированием информации см. работы [55, 62, 91].

Аналогичная проблема упаковки кругов на плоскости была решена только в 1940 году L. Fejes Toth, см., например, [42].

Проблема упаковки фигур в заданном ограниченном множестве важна для различных приложений. Задача упаковки кругов одинакового или разного радиусов в заданную ограниченную область является известной задачей, которая имеет важные приложения в технике и экономике. Эти задачи широко применяются в промышленности и логистики. К таким задачам относятся прокладка кабелей/проводов, погрузка платформ, раскрой тканей/стекла/дерева/бумаги, заполнение контейнеров [84] или раскрой дисков из металлического листа.

Упаковки эллипсов используются при анализе структур из эллиптических молекул в кристалле [70], в работе [101] упаковки эллипсоидов используются для анализа структур цементных растворов, см. также работы [99, 102, 106, 56], касающиеся задач упаковки эллипсов.

Интерес к задаче упаковок и идейно схожей к ней задаче покрытия связан, как уже указано, в первую очередь, с важными их приложениями к различным практическим задачам. Многочисленные различные приложения указанных задач можно найти в работах Love, Morris и Wesolowsky [82], ReVelle и Eiselt [91], Hamacher и Drezner [64].

Проблема упаковки кругов, эллипсов, квадратов, прямоугольников или иных фигур на плоскости или внутри заданных областей, например, квадрата, треугольника, круга или полосы исследуется многими авторами и разработаны различные подходы к их решению, см., например, Birgin and Gentil [49], Castillo, Kampas and Pinter [53], Cui and Xu [55], Grosso [63], Hifi and M'Hallah [65], Lubachevsky and Graham [83], Lodi, Martello, Monaci [80], Locatelli and Räber [79], Specht [92, 93], Szabó [98]. Среди множества таких работ необходимо отметить обзоры, выполненные в работах Castillo, Kampas and Pinter [53], Lodi, Martello, Monaci [80] и Hifi and M'Hallah [65].

В настоящее время разработаны различные модели задач упаковок, которые во многих случаях сводят задачу упаковок к задачам нелинейного программирования, см., например, Birgin, Martinez and Ronconi [50], а в случае упаковок прямоугольников к задаче линейного

программирования, использование линейного программирования см. например, в работе Lodi, Martello and Monaci [80].

Имеется серия работ, в которых рассматриваются задачи упаковок кругов в прямоугольник, в частности, в единичный квадрат, см. работы: De Groot [52], Wengerodt [100], Peikert [69], Nurmela and Ostegard [63], Friedman [55], Szabo, Markot, Csendes and all [98].

Так, в работе Marañas и др. [86], решается задача упаковки п равных кругов в единичный квадрат с целью максимизации минимального расстояния между центрами кругов; то есть

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

Максимизировать d при ограничениях

0 < х, < 1, / 6 / 0 < у, < 1, /е/

d<T¡(x,-Xjf +(у,-у^, 1 <i<j<n

где х, ,уь i е I, обозначают координаты точки /.

Одной из задач, часто решаемых на производстве, является укладка цилиндров. Она заключается в определении максимального числа равных кругов известного радиуса г, которые могут быть упакованы в прямоугольник фиксированной известной высоты L и ширины W, при этом круги должны полностью помещаться в заданный прямоугольник и не могут пересекаться. Birgin, Marti 'nez and Ronconi [50] решают эту задачу упаковки, рассматривая серию задач. В каждой задаче исследуется возможность упаковки к равных кругов известного радиуса г в прямоугольник L, W. Если такая упаковка осуществима, то к увеличивается на 1 и задача решается снова. Алгоритм останавливается, когда задача не может дать требуемую упаковку. Решаемая задача формулируется следующим образом:

Минимизировать max(o, 4г2 - (х, - Xj f - (у, -^j2)" при ограничениях

r<x,<L-r, /е/' = {1,...Д} r<y,<IV-r, i е V

где х, ,у, обозначают координаты /-ой точки, i G /.

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

Интерес представляет задача определения размеров прямоугольника минимальной площади, в который упаковываются п непересекающихся равных кругов (известного фиксированного радиуса), где соотношения высоты и ширины прямоугольника варьируются. Для задачи упаковки неравных кругов в прямоугольник фиксированной высоты L и минимальной ширины W Stoyan и Yaskov [95] предложили следующую математическую модель

Минимизировать W

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

г, <х, £L-rt, iel

г, <у, <W-r„ iel

(x.-xjf+iy.-yj)2 <(Г,+ГУ> 1 </'<;'<«,

W > 0, x, > 0, у, > 0, ie/

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

Также существует большой цикл публикаций по упаковкам в треугольную область, в круговую область, в полосу и т.д. Укажем некоторые работы, в которых можно имеются обзоры по таким упаковкам: Hifi and M'Hallah [65], Lodi, Martello and Monaci [80] и монография Szabo et al. [98], см. также библиографию в этих работах.

Исследование упаковок кругов разных радиусов проводится во многих работах. George, George and Lamar [62] предлагают смешанную целочисленную задачу для упаковки неравных кругов заданного радиуса в прямоугольник L,W с заданными размерами. Модель рассматривает х„ у„ i £ I, как непрерывные переменные и использует бинарные переменные ö„ i G I, для определения включения/исключения кругов из набора. Модель формулируется следующим образом:

п

Минимизировать

/=i

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

Sf^x^öXb-r), iel

S.r^y^S.iW-r,), iel

x,>0, yt >0, <5,e{0,l}, iel где c„ i E I, - стоимость включения круга i радиуса г, в прямоугольник L, W. Эта модель использует п целочисленных искомых переменных, 2п непрерывных искомых переменных и 2и + и(я-1)/2 функциональных ограничений. Эту модель очень сложно решить, используя любой стандартный решатель задач смешанного целочисленного математического

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

Имеется много публикаций, в которых для решения задачи упаковки неравных кругов предлагаются различные эвристические процедуры, использующие жадные алгоритмы, см. Huang, Y Li, Akeb and С. Li [72], Huang, Y Li, С. Li and Xu [73], Kubach, Bortfeldt and Gehring [77]. В некоторых работах эвристические процедуры используют локальный поиск экстремума целевой функции, см. Ponomarenko and Makmak [90], Stoyan and Yaskov [94]. В последней указанной работе предложена математическая модель и метод решения, основанный на комбинации алгоритма ветвей и границ и некоторого варианта градиентного метода, для упаковки кругов разного радиуса в полосу.

Для оптимизации упаковок кругов разного радиуса кроме указанных выше методов также используется:

диаграммы Вороного, см. Lu, Choi, Sun and Wang [84],

- метод имитации отжига Hifi, Pasches and Zissimopoulos[69] генетические алгоритмы Hifi and M'Hallah [65],

- метод наибольшего свободного места Huang, Li Y, Akeb and Li CM [72], Huang, Li Y, Li С. and Xu [73],

- алгоритм динамического адаптивного локального поиска Hifi and M'Hallah [66],

- некоторая модификация эвристического подхода Huang and Zhan [76], Huang and Kang [71],

- гибридный алгоритм, комбинирующий метод имитации отжига со стратегией запрета Zhang and Deng [104], Huang, Jurkowiak, Y. Li, С. Li and Xu [74],

- модель нелинейного программирования Yu and Zhang [103],

- методы глобальной оптимизации Castillo, Kampas and Pinter [53], Locatelli and Raber [79],

- использование различных решателей: MINOS - Birgin and Sobral [51], SNOPT -Addisa, Locatelli and Schoena [44], MathOpimizer - Pinter and Kampas [89] и многие другие методы.

Предлагаемые методы могут успешно работать для одних областей и могут быть неэффективными для других областей. Так, например, в работе Mladenovich, Plastria and Urosevic [87] для решения задачи упаковки кругов в круге вводится полярная система координат, которая оказывается более приемлемой, чем прямоугольная система координат, но эта система координат вряд ли будет удобной, например, для случая упаковки в полосу.

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

Проблема упаковки различных фигур и родственная ей задача покрытия давно и достаточно успешно исследуется в России учеными из Москвы, Уфы, Омска, Новосибирска, Казани и других регионов России, см. работы [1-30]. Важное значение для развития методов решения задач упаковок имеют исследования по общим методам оптимизации и, особенно, по дискретной оптимизации, см. работы [8, 13, 16, 17, 21, 25, 30]. Также представляют интерес работы по оптимизации специальных классов задач, см. [14, 15, 18, 20] и исследования по разработке математических моделей различных проблем, см., например, работы [4, 9-11, 24].

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

неизвестного) диаметра. В практических задачах, как правило, размеры упаковываемых фигур

\ 1

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

Результаты, полученные автором по теме диссертации, опубликованы в работах [5, 6, 22, 23, 26-29, 58-60]. При выполнении работ [5, 6, 28, 29, 58-60], выполненных совместно с научным руководителем, автор принимал участие в разработке математических моделей, введении уровней положений центров упаковываемых фигур и весов этих уровней. Сравнительный анализ прямоугольного и косоугольного способа построения сеток на упаковываемом множестве, разработка условий непересечения эллипсов, подбор метрики для выяснения непересечения эллипсов, разработка алгоритмов, программного обеспечения и проведение расчетов выполнено лично соискателем.

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

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

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

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

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

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

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

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

В первой главе работы предлагаются модели целочисленного линейного программирования для определения наибольшего возможного числа равных кругов фиксированного радиуса, упаковываемых в заданную связную замкнутую ограниченную область С. Задача упаковки равных кругов в связную область О заменена на задачу упаковки, когда центры кругов могут располагаться только в некоторых точках дискретного множества Т, построенного на С. Для решения задач целочисленного линейного программирования больших размерностей исходная задачи упаковки на всем заданном множестве разбивается на задачи упаковки на частях исходного множества. При этом вводятся уровни точек множества Т и веса уровней. Введение уровней точек дискретного множества и весов уровней позволяют разбивать задачи больших размерностей на подзадачи приемлемых размерностей, таким образом, что их решения будут согласованными. Кроме того, введение уровней и весов уровней позволяет решать задачи упаковки кругов с прижиманием их к заданной одной или нескольким сторонам области О, например, прижимая их вниз, либо вверх, либо вниз и к правой или (и) левой сторонам области О и т.п. В этой главе предложены численные алгоритмы для приближенного решения задач упаковок равных кругов заданных радиусов в произвольную ограниченную область. Разработанный алгоритм использует построенные в работе модели, уровни расположения решений и веса этих уровней. Проведенные численные расчеты показывают результативность подхода. Численные результаты сравнивались с известными из литературы результатами. Выявлено, что полученные в работе упаковки для прямоугольной области совпадают с лучшими известными результатами. В общем случае упаковка оценивается по плотности полученной упаковки.

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

R. Рассматриваются два варианта упаковки, когда большие оси упаковываемых эллипсов взаимно параллельны и случай, когда большие оси упаковываемых эллипсов взаимно перпендикулярны. Установлены условия непересечения эллипсов с заданными их параметрами. Показана приемлемость использования 1р метрики для выяснения условий непересечения эллипсов с взаимно перпендикулярными большими осями. Задача упаковки равных эллипсов с заданными параметрами с центрами в точках построенного множества Т, в данной главе, как и для упаковки кругов, сведена к решению задачи целочисленного линейного программирования. На основе введенных разбиения множества R, уровней и весов уровней предложен численный алгоритм приближенного решения задачи упаковки эллипсов, когда построенная задача целочисленного линейного программирования имеет большую размерность. Рассмотрены также случаи, когда необходимо ввести ограничения на число эллипсов, большие оси которых параллельны оси Ох либо оси Оу. Предложена методология решения таких задач и численными экспериментами выявлена результативность предложенной методики.

В третьей главе работы строятся целочисленные линейные модели для численного решения упаковок кругов двух заданных радиусов в произвольную замкнутую ограниченную область G, при которой общая площадь упаковываемых кругов принимает наибольшее возможное значение. Для задачи упаковки строится задача целочисленного (булевого) линейного программирования, содержащая условия непересечения кругов радиуса /*i, условия непересечешш кругов радиуса /*2 и условия непересечении кругов радиусов /•] и гг. При рассмотрении упаковки кругов радиусов г\ и )~2 строятся две сетки, которые порождают два конечных множества Т и S узлов этих сеток. Для решения задач целочисленного линейного программирования больших размерностей исходная задачи упаковки на всем заданном множестве разбита на задачи упаковки на частях исходного множества. При этом вводятся уровни точек множеств Т и S и веса уровней. На основе введенных разбиения множества G, уровней и весов уровней предложен численный алгоритм приближенного решения задачи, когда построенная задача имеет большую размерность. Рассмотрены также случаи, когда необходимо ввести ограничения на число кругов радиуса п или на число кругов радиуса /-2,

Разработанный комплекс программ представлен в четвертой главе диссертации. Он реализовывает алгоритмы, описанные в первых трех главах настоящей работы, в том числе алгоритмы построения сетки на упаковываемой области, подбор параметров метрики для случая упаковки эллипсов, расчета матриц коэффициентов модели, разделения области на подобласти и прижимания упаковываемых фигур. Кроме того, разработан алгоритм определения упаковываемой области при помощи задания ограничивающих ее кривых. Для решения построенных линейных моделей подключена библиотека ILOG CPLEX Optimizer 11.2, которая позволяет использовать в программе ILOG CPLEX оптимизаторы, предназначенные

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

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

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

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

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

Глава 1. Упаковка равных кругов

1.1. Постановка задачи

Пусть G — связная ограниченная замкнутая область с непустой внутренностью на плоскости Р. Совокупность п равных открытых кругов Kj, 1 <j<n, образует упаковку в G, если каждый круг Kj содержится в G, 1 <j<n, и каждая точка s m G принадлежит не более чем одному из этих кругов.

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

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

кругов известного радиуса г упаковываемых в область G и определить положения их центров.

Мы считаем, что на Р введена декартова система координат хОу и пусть d(s, t) -

евклидово расстояние между точками sut. Пусть G* (G*cz G) множество всех точек s из G

таких, что расстояние от s до ближайшей к ней точки границы области G (frG) не менее чем г:

G* = {se G : win d(s,t)>r}. Считаем, что множество G* не пусто. Очевидно, что множество tefrG

G* - замкнутое множество, которое может оказаться и несвязным, и содержащим изолированные точки. Легко убедиться, что каждый открытый круг К радиуса г с центром в G* состоит только из внутренних точек множества G, следовательно, находится внутри G: KczG. Очевидно, верно и обратное: каждый открытый круг радиуса г, содержащийся в G имеет центр в G*

Пусть Q - наименьший прямоугольник, содержащий множество G* и его стороны параллельны осям координат. На множестве Q построим прямоугольную сетку с шагом А по осям х и у. Мы полагаем, что А делитель г, т.е. г = кА, здесь к - целое число, к > 1. Диагональ маленьких квадратиков, порожденных сеткой, равна л/2 А Узлы построенной сети обозначим

через Ji, S2,...,SN, N> 1. Если построить круги V, радиуса л/2 АН с центрами в точках s„ 1< i <N, то они образуют покрытие множества Q, следовательно, и множества G*. Построим множество Т(А) с помощью следующей процедуры.

Процедура 1:

1. T(A) - пустое множество

2. Для каждого /, 1 < i < N, если Vj n G* - 0, то переходим к следующему значению /,

иначе:

a) если St е G*, то добавляем s,- к множеству Т(А);

b) если Si <£ G*, то выбираем ближайшую к Sj точку s из G* и добавляем выбранную точку s к множеству Т(А), если ее там нет.

В результате применения процедуры 1 получим некоторое множество из п точек Т(А) = {/i, t2,...,t„}. Координаты х, и yt точек 1< / < п, находятся известным образом. Каждая точка /„ 1 <i<n, принадлежит множеству G*.

Если последовательно строятся сначала сетка для А, а затем для А/1, то полагаем, что строятся множества Т(А) и Т(А/2) по процедуре 1, затем полагаем, что Т(А/2) - Т(А) и Т(А/2). Аналогичным образом строим Т(А/2к) по процедуре 1 и затем объединяем его с предыдущим множеством Т(А/2к~'), полученное множество считаем за Т(А/2к).

Сетка на G может строиться достаточно произвольно или могут быть заданы (выбраны) точки множества Т(А) = {t\, (2,---,t„} без использования сетки или с частичным использованием узлов сетки. . . .. ..

Пусть множество Т(А) построено.

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

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

Замечание 1. Для выбранного радиуса г при оптимальной упаковке в G (при решении задачи С1), центры кругов не обязательно находятся в точках из Т(А), для выбранного значения А. Следовательно, числа упаковываемых кругов, найденные при решении задач С1 и С2, могут не совпадать.

Продемонстрируем это на простом примере. Рассмотрим упаковку трех кругов наибольшего возможного радиуса гз в единичный квадрат V. Известная оптимальная упаковка (см., например, [98]) изображена на Рисунке 1.1. Множество V* возможных положений центров кругов является квадратом abed, сторона которого равна 1 - 2гз. Этот квадрат изображен на Рисунке 1.1 штриховыми линиями.

Пусть точки а, Е и F - центры кругов при оптимальной упаковке. Для получения оптимальной упаковки нужно, чтобы некоторые узлы сетки совпали с точками а, Е и F. При построении прямоугольной сетки на квадрате abed с помощью деления его сторон на равные части не удается (за конечное число шагов) получить совпадение точек £hFc узлами сетки,

так как ¿F=(l-2/*3)tg(7t/12), гъ = 1/(2+1/л/2+л/б/2) = 0.25433309503, см., например, [98]. В результате, при построении прямоугольной равномерной сетки получим, что число упаковываемых кругов равно двум, а не трём. Построим сетку, одна из линий которой образует с осью х угол л/12, а другая - с осью у угол я/12. Тогда точки Е и F совпадут с некоторыми узлами сетки и при этом будет упаковано три круга. Таким образом, результат зависит от способа построения сетки.

Рисунок 1.1. Оптимальная упаковка трех кругов наибольшего возможного радиуса /*з в

Список литературы диссертационного исследования кандидат наук Лисафина, Мария Сергеевна, 2014 год

Список использованной литературы

1. Алдын-оол, Т. А. Покрытие плоской области случайно распределенными сенсорами / Т. А. Алдын-оол, А. И. Ерзин, В.В. Залюбовский / Вестн. НГУ. Сер. матем., мех., информ. -2010. -№ 10, Часть 4. - С. 7-25.

2. Андрианова, A.A. Модели задачи негильотинного размещения набора прямоугольников на листе и полуполосе / A.A. Андрианова, Т.М. Мухтарова, В.Р. Фазылов / Ученые записки Казанского университета. Физико-математические науки. - 2013. - Т.155, №2. - С. 5-18.

3. Астраков, С. Н. Сенсорные сети и покрытие плоскости кругами / С. Н. Астраков, А. И. Ерзин, В. В. Залюбовский / Дискрета, анализ и исслед. опер. - 2009. - № 16, Часть 3. -С. 3-19.

4. Галиев, Ш.И. Вычислительные алгоритмы оптимизации покрытий плоских областей заданным числом эллипсов / Ш.И. Галиев / Ж. вычисл. матем. и матам, физ. - 1995. - Т.35, №5.-С. 772-783.

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

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

7. Гаранжа, В. А. Параллельная реализация метода Ньютона для решения больших задач линейного программирования. / В. А. Гаранжа, А. И. Голиков, Ю. Г. Евтушенко, M. X. Нгуен / Ж. вычисл. матем. и матем. физ. - 2009. - Т. 49, № 8. - С. 1369-1384.

8. Емеличев, В.А. Многогранники, графы, оптимизация / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов/М.: Наука. - 1981.

9. Еремеев, A.B. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования / A.B. Еремеев, Л.А. Заозерская, A.A. Колоколов / Дискретный анализ и исследование операций. - Серия 2, Т.7, № 2. - С. 22-46.

10. Заботин, И .Я. Метод отсечений с обновлением погружающих множеств и оценки точности решения / И.Я. Заботин, P.C. Яруллин / Ученые записки Казанского ун-та. Сер. физ.-мат. науки.-Т. 155, кн. 2.-2013.-С. 54-64.

11. Заботин, И.Я. Об одном подходе к построению алгоритмов отсечений с отбрасыванием отсекающих плоскостей / И.Я. Заботин, P.C. Яруллин / Изв. вузов. Математика. - 2013. -№ 3. - С. 74-79.

12. Заозерская, J1. А. Оценки среднего числа итераций для некоторых алгоритмов решения задачи об упаковке множества / Л. А. Заозерская, А. А. Колоколов / Журнал вычислительной математики и математической физики. - 2010. - Т. 50, №2. - С. 242-248.

13. Измайлов, А.Ф. Численные методы оптимизации / А.Ф. Измайлов, М.В. Солодков / М.: Физматлит. - 2005.

14. Кабатянский, Г. А.О границах для упаковок на сфере и в пространстве / Г. А. Кабатянский, В. И. Левенштейн / Проблемы передачи информации. - 1978. - Т. 14, № 1. - С. 3-25.

15. Канторович, Л. В. Рациональный раскрой промышленных материалов / Л. В. Канторович, В. А. Залгаллер / Новосибирск: Наука СО. -1971.

16. Кирпичников, А.П. Прикладная теория массового обслуживания / А.П. Кирпичников / Казань.-2008.

17. Ковалев, М.М. Дискретная оптимизация (целочисленное программирование) / М.М. Ковалев / Изд. 2-е, стереотипное. М.: Едиториал УРСС, 2003.

18. Козюрин, H.H. О сложности построения асимптотически оптимальных покрытий и упаковок / Козюрин, H.H./ Докл. РАН. - 1998. - Т. 363, № 1.-С.11-13.

19. Колоколов, A.A. Решение задачи об упаковке множества с использованием алгоритмов перебора L-классов и последовательной оптимизации / A.A. Колоколов, М.Ф. Корбут / Международная конференция «Дискретная оптимизация и исследование операций»: Материалы конференции (Новосибирск, 24 - 28 июня 2013 г.) - Новосибирск: Издательство Института математики, 2013. - С. 149. - Режим доступа: www.math.nsc.ru/conference/door/ 2013/Book of abstracts_D О OR_2013 .pdf.

20. Конвей, Дж. Упаковки шаров, решетки и группы / Дж. Конвей, Н. Слоэн / М.: Мир. - 1990. -Т. I, II.

21. Корбут, A.A. Дискретное программирование / A.A. Корбут, Ю.Ю. Финкельштейн / М.: Наука. - 1969.

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

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

24. Левенштейн В. И. Границы для упаковок метрических пространств и некоторые их приложения / Левенштейн В. И. / Проблемы кибернетики. - 1983. -№ 40. - С. 43-110.

25. Леонтьев, В.К. Дискретная оптимизация / В.К. Леонтьев / Ж. вычисл. матем. и матем. физ. -2007. - Т. 47, № 2. - С. 338-352.

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

27. Лисафина, М.С. Программный комплекс для решения задачи покрытия кругами разного радиуса. / М.С. Лисафина / Междунар. молодежи, научн. конф. «XX Туполевские чтения». - Казань: Изд-во Казан, гос. техн. ун-та, 2012. - Т. III, Часть 1. - С.446-448.

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

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

30. Моисеев, H.H. Методы оптимизации / H.H. Моисеев, Ю.П. Иванилов, Е.М. Столярова / М.: Наука. - 1978.

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

32. Мухачева, Э. А. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя / Э. А. Мухачева, А. И. Ермаченко, Т. М. Сиразетдинов, А. Р. Усманова / Информационные технологии. - 2001. - № 6. - С. 25-31.

33. Мухачева, Э. А. Генетический алгоритм блочной структуры в задачах двумерной упаковки / Э. А. Мухачева, А. С. Мухачева, А. В. Чиглинцев / Информационные технологии. - 1999. -№ 11.-С. 13-18.

34. Мухачева, Э. А. Методы локального поиска оптимума в задачах ортогонального раскроя и упаковки: аналитический обзор и перспективы развития / Э. А. Мухачева, А. С. Мухачева, А. Ф. Валеева, В. М. Картак / приложение / Информационные технологии. - 2004. - № 5. -С. 2-17.

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

36. Роджерс, К. Укладки и покрытия / К. Роджерс / М.: Мир. - 1968.

37. Сигал, И.Х. Введение в прикладное дискретное программирование / И.Х. Сигал, А.П. Иванова / М.: Физматлит. - 2002. - 240с.

38. Сиделышков, В. М. О плотнейшей укладке шаров на поверхности n-мерной евклидовой сферы и числе векторов двоичного кода с заданным кодовым расстоянием / В. М. Сиделышков /Докл. АН СССР. - 1973.-№ 213. - С. 1029-1032.

39. Сиделышков, В. М. Об экстремальных многочленах, используемых при оценках мощности кода / В. М. Сиделышков / Проблемы передачи информации. - 1980. - Т. 16, № 3. -С. 17-30.

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

41. Сухарев, А.Г. Курс методов оптимизации. / А.Г. Сухарев / Учебное пособие. 2-е изд. - М.: Физматлит, 2005.

42. Тот, Л.Ф. Расположение на плоскости, на сфере и в пространстве / Л.Ф. Тот / М.: Физматлит, 1958.

43. Финкелыитейн, Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования / Финкельштейн Ю.Ю. / М.: Наука, 1976.

44. Addis, В. Disk packing in a square: A new global optimization approach. / B. Addis, M. Locatelli, F. Schoen / INFORMS J. on Computing. - 2008. - V. 20, No 4. - P.516- 524.

45. Addis, B. Efficiently packing unequal disks in a circle. / B. Addis, M. Locatelli, F. Schoen / Operations Research Letters. - 2008. - V. 36, No 1. - P. 37 - 42.

46. Akeb, H. Adaptive beam search lookahead algorithms for the circular packing problem / H. Akeb, M. I-Iifi, R. M'Hallah. / International Transactions in Operational Research. - 2009. - P. 1-23.

47. Akeb, II. A beam search algorithm for the circular packing problem / H. Akeb, M. Hifi, R. M'Hallah. / Comput. Oper. Res. - 2009. - V. 36, No 5. - P. 1513-1528.

48. Bennell, J.A. Tools of mathematical modelling of arbitrary object packing problems, / J.A.

Bennell, G. Scheithauer, Yu. Stoyan, T. Romanova / J. Annals of Operations Research, Publisher

i

Springer Netherlands. - 2010. - V. 179, No l.-P. 343-368

49. Birgin, E.G. New and improved results for packing identical unitary radius circles within triangles, rectangles and strips / E.G. Birgin, J.M. Gentil / Computer & Operations Research. -2010.-V. 37, No 7.-P. 1318-1327.

50. Birgin, E.G. Optimizing the packing of cylinders into a rectangular container: a nonlinear approach / E.G. Birgin, J.M. Marti'nez, D.P. Ronconi / European Journal of Operational Research. -2005.-No 160.-P. 19-33.

51. Birgin, E.G. Minimizing the object dimensions in circle and sphere packing problems / Birgin E.G., Sobral F.N.C. / Comput. Oper. Res. - 2008. - V.35, No 7. - P. 2357-2375.

52. Canbolat, M.S. Planar maximal covering with ellipses / M. S. Canbolat, M. von Massow / Computers & Industrial Engineering. - 2009. - V. 57. - P. 201-208.

53. Castillo, I. Solving circle packing problems by global optimization: Numerical results and industrial applications /1. Castillo, F.J. Kampas, J.D. Pinter / European J. of Oper. Res. - 2008. -No 191.-P. 786-802.

54. Chernov, N. Mathematical model and efficient algorithms for object packing problem. / N. Chernov, Y. Stoyan, T. Romanova / Computational Geometry: Theory and Applications - 2010 -V. 43.-No 5.-P. 535-553

55. Cui, Y. Strips minimization in two-dimensional cutting stock of circular items / Y. Cui, D. Xu / Computers and Operations Research. - 2010. - No 37. - P. 621-629.

56. Delaney, G. Random packing of elliptical disks / Delaney G., D. Weaire, S. Hutzler and S. Murphy/ Philosophical Magazine Letters. - 2005. - V. 85, No 2. - P.89-96.

57. Folkman, J.H. A packing inequality for compact subsets of the plane / J.H. Folkman, R.L. Graham / Canadian Mathematical Bulletin. - 1969. - No 12. - P.745-752.

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

59. Galiev, Sh.I. Linear models for the approximate solution of the problem of packing equal circles into a given domain / Sh.I. Galiev, M.S. Lisafina / European Journal of Operational Research. -2013.-No230.-P. 505-514.

60. Galiev, Sh. Optimization of a multiple covering of a surface taking into account its relief / Sh. Galiev, M. Lisafina, V. Judin / Proceedings of III International conference Optimization and Applications (OPTIMA-2012). Costa da Caparica, Portugal, September 2012. - Moscow, 2012 -P.86-90.

61. Gaspar, Zs. Upper bound of density for packing of equal circles in special domains in the plane / Zs. Gaspar, T. Tarnai / Periodica Polytechnica. ser. Civ. Eng. - 2000. - V. 44, No 1. - P. 13-32.

62. George, J.A. Packing different-sized circles into a rectangular container / J.A. George, J.M. George, B.W. Lamar / European Journal of Operational Research. - 1995. - No 84. - P.693-712.

63. Grosso, A.R. Solving the problem of packing equal and unequal circles in a circular container / A.R. Grosso, M.J.U. Jamali, M. Locatelli, F. Schoen / Journal of Global Optimization. - 2010. -V. 47, No l.-P. 63-81.

64. Hamacher, H.W. Facility Location: Application and Theory / H.W. Hamacher, Z. Drezner (Eds.) / 2d. ed., NewYork: Springer-Verlag. - 2004.

65. Hifi, M. Adaptive and restarting techniques-based algorithms for circular packing problems / M. Hifi, R. M'Hallah / Comput. Optim. Appl. - 2008. - V. 39, No 1. - P. 17-35.

66. Hifï, M. A dynamic adaptive local search algorithm for the circular packing problem. / M. Hifi, R. M'Hallah / European Journal of Operational Research. - 2007. - V. 127, No 3. - P.l280- 1294.

67. Hifi, M. A Literature Review on Circle and Sphere Packing Problems: Models and Methodologies / M. Hifi, R. M'Hallah / Advances in Operations Research. - 2009. - Article ID 150624, doi: 10.1155/2009/150624.-22 p.

68. Hifi, M. Approximate algorithms for constrained circular cutting problems / M. Hifi, R. M'Hallah / Comput. Oper. Res. - 2004. - V. 31. - No 5. - P.675-694.

69. Hifi, M. A simulated annealing approach for the circular cutting problem / M. Hifi, V.Th.Paschos, V. Zissimopoulos / European Journal of Operational Research. - 2004. - V. 127. - No 2. - P.430-448.

70. Hiragi, Y. Molecular Shape and Structure of Regular Molecular Assembles. II. The Geometrical Conditions for Two Dimensional Packings of the elliptic Molecule / Y. Hiragi,/ Bull. Inst. Chem. Res., Kyoto Univ.-1978.-V. 56,No. 4-P. 170-175.

71. Huang, W. A heuristic quasi-physical strategy for solving disks packing problem. / W. Huang, Y. Kang / Simulation Modelling Practice and Theory. - 2002. - No 10. - P. 195-207.

72. Huang, W. Greedy algorithms for packing unequal circles into a rectangular container. / W.Huang, Y. Li, H. Akeb, C. Li / Journal of the Operational Research Society. - 2005. - V. 56, No 5. -P.:539-548.

73. Huang, W. New heuristics for packing unequal circles into a circular container / W. Huang, Y. Li, C. Li, R. Xu / Comput. Oper. Res. - 2006. - V. 33, No 8. - P.2125-2142.

74. Iluang, W. A two-level search strategy for packing unequal circles into a circular container / W. Huang, Y. Li, В .Jurkowiak, C. Li, R. Xu / In: Proceedings of the International Conference on Principles and Practice of Constraint Programming, Springer, Berlin. - 2003. - P. 868-872.

75. Huang, W. A "Learning From Human" Heuristic for Solving Unequal Circle Packing Problem. / W. Huang, Y. Li, S. Gérard, Li C., R.C. Xu / In Hao J.K. and Liu B.D. (eds) Proceedings of the First International Workshop on Heuristics, Beijing, China. - 2002. - P. 39-45.

76. Huang, W.Q. A quasi-physical method for solving packing problems. / W.Q. Huang, S.H. Zhan / Mathematical Reviews, American Mathematical Society. - 1982. - V. 82. - No 52002.

77. Kubach, T. Parallel greedy algorithms for packing unequal circles into a strip or a rectangle. / T. Kubach, A. Bortfeldt, II. Gehring / Central European Journal of Operations Research. - 2009. -V. 17, No 4. - P.461-477.

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

79. Locatelli, M. Packing equal circles in a square. A deterministic global optimization approach / M. Locatelli, M. Raber / Discrete Applied Mathematics. - 2008. - V. 122. - P. 139-166.

80. Lodi, A. Two-dimensional packing problems: A survey. / A. Lodi, S. Martello, M. Monaci / European Journal of Operational Research. - 2002. -V. 141. - P. 241-252.

81. Love, R.F. Mathematical Models of Road Travel Distances / R.F. Love, J.G. Morris / Management Science. - 1979. - V. 25, No. 2. - P. 130-139.

82. Love, R.F. Facilities Location Models and Methods / R.F. Love, J.G. Morris, G.O. Wesolowsky / North Holland: ORSA Publications in Operational Research Series. - 1988.

83. Lubachevsky, B.D. Minimum perimeter rectangles that enclose congruent non-overlapping circles / B.D. Lubachevsky, R.L. Graham / Discrete Mathematics. - 2009. - No 309. - P. 1947-62.

84. Lu, L. Variational Circle Packing Based on Power Diagram/ L. Lu, Y.K. Choi, F. Sun, W. Wang -Режим доступа: http://vr.sdu.edu.cn/~lulin/CP_TechReport.pdf.

85. L'u, Zh. PERM for solving circle packing problem / Zhipeng L'u and Wenqi Huang. / Comput. Oper. Res. - 2008. - V. 35, No 5. - P.1742-1755.

86. Maranas, C.D. New results in the packing of equal circles in a square / C. D. Maranas, C. A. Floudas, P. M. Pardalos / Discrete Mathematics. - 1995. - V. 142, No 1-3. - P.287-293.

87. Mladenovi'c, N. Reformulation descent applied to circle packing problems / N. Mladenovi'c, F. Plastria, D. Uro^sevi'c / Comput. Oper. Res. - 2005. - V. 32, No 9. - P.2419-2434.

88. Miyazawa, F.K. Two- and three-dimensional parametric packing / F.K. Miyazawa, Y. Wakabayashi / Computers & Operations Research, - 2007. - V. 34, No 9. - P.2589-2603.

89. Pinter, J. Nonlinear optimization in mathematica using mathoptimizer professional / J. Pinter, F. Kampas / Mathematica Education Res. - 2005. - No 10. - P.l-18.

90. Ponomarenko, L.D. New approaches to minimization on permutations when packing geometric objects / L.D. Ponomarenko, P.M. Makmak. / in: Theory and Methods of Automated Design. Inst, for Technical Cybernetics, Ac. Sci. BSSR, Minsk. - 1980. - No 4. - P. 8-14 (in Russian).

91. ReVelle, C.S. Location analysis: A synthesis and survey / C.S. ReVelle, H.A. Eiselt / European Journal of Operational Research. - 2005. - No 165. - P.l-19.

92. Specht, E. High density packing of equal circles in rectangles with variable aspect ratio / Specht, E. / Computers & Operations Research. - 2013. - No 40. - P. 58-69.

93. Specht E. The best known packings of equal circles in a rectangle with variable aspect ratio (complete up to N 500) - Режим доступа: http://www.pack0mania.c0m/crc_var/S.

94. Stoyan, Y.G. A mathematical model and a solution method for the problem of placing various-sized circles into a strip / Y.G. Stoyan, G.N. Yaskov / European Journal of Operational Research. - 2004. - V. 156, No 3. - P. 590-600.

95. Stoyan, Y.G. Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints / Y.G. Stoyan, G.N. Yaskov / International Transactions in Operational Research. - 1998. - V. 5, No 1. - P. 45-58.

96. Stoyan, Y. Packing cylinders and rectangular parallelepipeds with distances between them/ Y. Stoyan, A. Chugay / European J. Oper. Res. - 2008. - No 197. - P. 446-455.

97. Stoyan, Y. Phi-functions for complex 2D objects. 40R Quarterly / Y. Stoyan, N. Gil, T. Romanova, G. Scheithauer / Journal of the Belgian, French and Italian Operations Research Societies. - 2004. -V. 2, No 1. - P. 69-84.

98. Szabo, P.G. New Approaches to Circle Packing in a Square: With Program Codes / P.G. Szabo, MCs Mark'ot, T. Csendes, E. Specht, L.G. Casado, I. Garcia / Springer. - 2007.

99. Toth, L.F. Packing of ellipses with continuously distributed area / L. F. Toth / Journal of Discrete Mathematics. - 1986. - V. 60. - P. 263-267.

100. Wang, H. An improved algorithm for the packing of unequal circles within a larger containing circle / H. Wang, W. Huang, Q. Zhang, D. Xu / European Journal of Operational Research -September 2002. - V. 127, No 2. - P.440-453.

101 .Xu, W.X. Microstructural characterization of fresh cement paste via random packing of ellipsoidal cement particles / W.X. Xu, H.S. Chen / Materials Characterization. - 2012. - No 66. - P. 16 - 23.

102.Xu, W.X. An overlapping detection algorithm for random sequential packing of elliptical particles / W.X. Xu, H.S. Chen, Z. Lv / Physica A. - 2011. - V. 390. - P. 2452-67.

103.Yu, H.X. The augmented Lagrangian method for the packing of unequal circles within a strip / H.X. Yu, L.W. Zhang / International Journal of Pure and Applied Mathematics. - 2005. - V. 1, No 18. -P.463-470.

104.Zhang, D.F. An effective hybrid algorithm for the problem of packing circles into a larger containing circle / D.F. Zhang, A.S. Deng / Computers and Operations Research. - 2005. - No 32. -P. 1941-51.

105.Zabotin, I. Ya. One Approach to Constructing Cutting Algorithms with Dropping of Cutting Planes / Ya. Zabotin, R. S. Yarullin. / Russian Mathematics (Iz. VUZ). - 2013. - No 3. - P. 60 -64.

106.Zhou, Z.Y. Discrete particle simulation of gas fluidization of ellipsoidal particles. / Z.Y. Zhou, D. Pinson, R.P. Zou, A. B. Yu / Chem.Eng. Sci. - 2011. - V. 66. - P. 6128^5.