Равновесная упаковка кругов в круг минимального радиуса

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

Full description

Saved in:

Bibliographic Details
Date:	2013
Main Authors:	Ненахов, Э.И., Романова, Т.Е., Стецюк, П.И.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Series:	Теорія оптимальних рішень
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/85057
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Равновесная упаковка кругов в круг минимального радиуса / Э.И. Ненахов, Т.Е. Романова, П.И. Стецюк // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 143-153. — Бібліогр.: 10 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-85057
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-850572025-02-23T19:51:42Z Равновесная упаковка кругов в круг минимального радиуса Рівноважна упаковка кіл у коло мінімального радіуса Balanced packing problem of circles in a circle of minimum radius Ненахов, Э.И. Романова, Т.Е. Стецюк, П.И. Рассматривается проблема упаковки системы неравных кругов в круг минимального радиуса, так чтобы центр тяжести системы размещаемых кругов находился в центре внешнего круга. Даны две ее формулировки: в виде квадратичной экстремальной задачи и задачи обратно-выпуклого программирования. Для поиска локальных экстремумов предлагается метод, основанный на модификации r -алгоритма. Приводятся результаты вычислительных экспериментов. Розглядається проблема упаковки системи нерівних кіл у коло мінімального радіуса, так щоб центр ваги системи кіл збігався із центром зовнішнього кола. Дано два її формулювання – у вигляді квадратичної екстремальної задачі й у вигляді задачі обернено-опуклого програмування. Для пошуку локальних екстремумів запропоновано метод на основі модифікації r -алгоритма та наведено результати обчислювальних експериментів. The paper considers a packing problem of a set of unequal circles into a containing circle of the minimum radius subject to the center of gravity of the set of circles is located at the center of the containing circle. We introduce two formulations of the packing problem: in the form of a quadratic extremal problem and, as well as, in the form of inverse-convex programming. We employ a method based on the modification of the r -algorithm for local optimization. The results of computational experiments are given. 2013 Article Равновесная упаковка кругов в круг минимального радиуса / Э.И. Ненахов, Т.Е. Романова, П.И. Стецюк // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 143-153. — Бібліогр.: 10 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/85057 519.8 ru Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматривается проблема упаковки системы неравных кругов в круг минимального радиуса, так чтобы центр тяжести системы размещаемых кругов находился в центре внешнего круга. Даны две ее формулировки: в виде квадратичной экстремальной задачи и задачи обратно-выпуклого программирования. Для поиска локальных экстремумов предлагается метод, основанный на модификации r -алгоритма. Приводятся результаты вычислительных экспериментов.
format	Article
author	Ненахов, Э.И. Романова, Т.Е. Стецюк, П.И.
spellingShingle	Ненахов, Э.И. Романова, Т.Е. Стецюк, П.И. Равновесная упаковка кругов в круг минимального радиуса Теорія оптимальних рішень
author_facet	Ненахов, Э.И. Романова, Т.Е. Стецюк, П.И.
author_sort	Ненахов, Э.И.
title	Равновесная упаковка кругов в круг минимального радиуса
title_short	Равновесная упаковка кругов в круг минимального радиуса
title_full	Равновесная упаковка кругов в круг минимального радиуса
title_fullStr	Равновесная упаковка кругов в круг минимального радиуса
title_full_unstemmed	Равновесная упаковка кругов в круг минимального радиуса
title_sort	равновесная упаковка кругов в круг минимального радиуса
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2013
url	https://nasplib.isofts.kiev.ua/handle/123456789/85057
citation_txt	Равновесная упаковка кругов в круг минимального радиуса / Э.И. Ненахов, Т.Е. Романова, П.И. Стецюк // Теорія оптимальних рішень: Зб. наук. пр. — 2013. — № 12. — С. 143-153. — Бібліогр.: 10 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT nenahovéi ravnovesnaâupakovkakrugovvkrugminimalʹnogoradiusa AT romanovate ravnovesnaâupakovkakrugovvkrugminimalʹnogoradiusa AT stecûkpi ravnovesnaâupakovkakrugovvkrugminimalʹnogoradiusa AT nenahovéi rívnovažnaupakovkakílukolomínímalʹnogoradíusa AT romanovate rívnovažnaupakovkakílukolomínímalʹnogoradíusa AT stecûkpi rívnovažnaupakovkakílukolomínímalʹnogoradíusa AT nenahovéi balancedpackingproblemofcirclesinacircleofminimumradius AT romanovate balancedpackingproblemofcirclesinacircleofminimumradius AT stecûkpi balancedpackingproblemofcirclesinacircleofminimumradius
first_indexed	2025-11-24T20:00:29Z
last_indexed	2025-11-24T20:00:29Z
_version_	1849703194647592960
fulltext	Теорія оптимальних рішень. 2013 143 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается проблема упа- ковки системы неравных кругов в круг минимального радиуса, так чтобы центр тяжести системы размещаемых кругов находился в центре внешнего круга. Даны две ее формулировки: в виде квадра- тичной экстремальной задачи и – задачи обратно-выпуклого про- граммирования. Для поиска ло- кальных экстремумов предлага- ется метод, основанный на мо- дификации r -алгоритма. Приво- дятся результаты вычислитель- ных экспериментов.  Э.И. Ненахов, Т.Е. Романова, П.И. Стецюк, 2013 ÓÄÊ 519.8 Ý.È. ÍÅÍÀÕÎÂ, Ò.Å. ÐÎÌÀÍÎÂÀ, Ï.È. ÑÒÅÖÞÊ ÐÀÂÍÎÂÅÑÍÀß ÓÏÀÊÎÂÊÀ ÊÐÓÃÎÂ Â ÊÐÓÃ ÌÈÍÈÌÀËÜÍÎÃÎ ÐÀÄÈÓÑÀ∗∗∗∗ Введение. Наиболее эффективный способ упаковки кругов не так уж очевиден. Одна из известных постановок звучит так: найти та- кой способ расположения непересекающихся равных кругов на плоскости, при котором будет покрыта наибольшая часть этой плос- кости. Возникающие при этом упаковки кру- гов обладают многими интересными свойст- вами. Так, например, доказано, что наилуч- шему заполнению плоскости (плотность рав- на 3 / 6 0.9069π ≈ ) соответствует размеще- ние центров кругов в вершинах правильных шестиугольников [1]. Более сложной является задача плотной упаковки кругов (многомерных шаров) в компактных областях [2]. Например, задача поиска минимального радиуса круга, в кото- ром нужно разместить непересекающиеся круги заданных радиусов. Задача усложняет- ся, если ввести дополнительные ограничения на механические свойства системы разме- щаемых объектов (динамическое равновесие, моменты инерции, устойчивость), возни- кающих в space engineering [3]. Одна из таких задач является предметом исследования в данной работе. Подход к ее решению связан с формулировкой проблемы в виде многоэкстремальных задач математи- ческого программирования, и поиска их ло- кальных экстремумов с помощью методов негладкой оптимизации. ∗ Работа частично поддержана совместным гран- том НТЦУ и НАН Украины (проект № 5710). Э.И. НЕНАХОВ, Т.Е. РОМАНОВА, П.И. СТЕЦЮК 144 Теорія оптимальних рішень. 2013 Математическая модель задачи. Пусть в двухмерном евклидовом про- странстве имеется семейство кругов i S с заданными радиусами i r и весами i w , = 1, ,i mK . Полагаем, что центр тяжести круга i S находится в его центре. Равновесной упаковкой кругов i S , = 1, ,i mK , назовем такую их упаковку в круг S , чтобы радиус круга S был минимальным и центр тяжести семейства кругов i S , = 1, ,i mK , совпадал с центром круга S . Не ограничивая общности, будем считать, что центр круга S находится в начале координат. Пусть ( , ) i i x y – неизвестный центр круга i S , r – неизвестный радиус круга S . Обозначим известные величины =1 = / m i i ii w wλ ∑ , = 1, ,i mK , и очевидную нижнюю границу на искомый радиус =1, , = max low i i m r r K . Тогда равновесной упаковке двухмерных кругов i S , = 1, ,i mK , соответствует многоэкстремальная задача нелинейного программирования в 2 1mE + : * , , = min r r x y low r r ≥ (1) при ограничениях 2 2 2( ) , = 1, , , i i i x y r r i m+ ≤ − K (2) 2 2 2( ) ( ) ( ) , 1 < ,i j i j i jx x y y r r i j m− + − ≥ + ≤ ≤ (3) =1 =1 = 0, = 0. m m i i i i i i x yλ λ∑ ∑ (4) Ограничения (2) гарантируют, что каждый круг i S содержится внутри круга S , а ограничения (3) – что никакие два круга из i S , = 1, ,i mK , не пересе- каются (не имеют общих внутренних точек). Ограничения (4) означают, что центр тяжести семейства кругов i S , = 1, ,i mK , находится в начале координат (в центре круга S ). Задача (1)–(4) возникает в проблеме упаковки одинаковых по высоте m прямых круговых цилиндров в цилиндрический контейнер минимального радиуса с учетом ограничений, связанных c механическими характеристиками поведения системы (динамическое равновесие, моменты инерции, устойчивость) [3, 4]. Последняя относится к 3D-задачам размещения и форму- лируется в виде задачи нелинейного программирования c линейной целевой функцией, линейными и нелинейными ограничениями в форме неравенств [5]. Количество переменных в задаче равно 3 1m + , из них по 3 переменных отвечают параметрам размещения каждого объекта и переменная r отвечает радиусу основания контейнера. Ограничения в задаче включают: a) m квадра- тичных невыпуклых ограничений принадлежности объектов цилиндрическому РАВНОВЕСНАЯ УПАКОВКА КРУГОВ В КРУГ МИНИМАЛЬНОГО РАДИУСА Теорія оптимальних рішень. 2013 145 контейнеру; b) ( 1)/2m m − невыпуклых квадратичных ограничений непересече- ния размещаемых объектов; c) шесть линейных неравенств на допустимые отклонения от центра масс системы (ограничения равновесия); d) шесть квадра- тичных неравенств на допустимые отклонения от моментов инерции системы (ограничения моментов инерции); e) шесть дробно-квадратичных неравенств на допустимые погрешности угла наклона главной оси системы от осей координат (ограничения устойчивости). Отдельным случаем вышеописанной 3D-задачи упаковки является 2D-задача (1)–(4), где учтены только ограничения равновесия (см. рис. 1, [4]). Для 2D-задачи ограничения равновесия, т. е. линейные неравенства на допу- стимые отклонения от центра масс системы одинаковых по высоте цилиндров, сформулированы с помощью ограничений в форме равенств (4). Это оказыва- ется удобным при разработке методов оптимизации, так как учет ограничений- равенств можно обеспечить либо проектированием на гиперлоскость, либо удалением одной из переменных в каждом из двух равенств, перейти к задаче нелинейного программирования, в которой будет на две переменные меньше. РИС. 1. Пример оптимального размещения 49-ти круговых цилиндров в круговом контейнере Квадратичная экстремальная задача. Задача (1) – (4) является квадра- тичной экстремальной задачей, где целевая функция и часть ограничений – линейные. Ее можно сформулировать в виде * * 2 2 , , = ( ) = min r r x y low f r r ≥ (5) при ограничениях 2 2 2( ) , = 1, , , i i i x y r r i m+ ≤ − K (6) 2 2 2( ) ( ) ( ) , 1 < ,i j i j i jx x y y r r i j m− + − ≥ + ≤ ≤ (7) Э.И. НЕНАХОВ, Т.Е. РОМАНОВА, П.И. СТЕЦЮК 146 Теорія оптимальних рішень. 2013 2 2 =1 =1 = 0, = 0, m m i i i i i i x y     λ λ        ∑ ∑ (8) где целевая функция f и все ограничения заданы квадратичными функциями. Задача (5) –( 8) является более удобной для исследования нижней границы оптимального значения f с помощью предложенной Н.З. Шором техники лагранжевых двойственных оценок в квадратичных многоэкстремальных задачах [6]. Эта техника включает в себя алгоритмы поиска двойственных оценок на основе методов недифференцируемой оптимизации и использование функционально избыточных ограничений для улучшения точности двойствен- ных оценок. Чтобы обеспечить нетривиальную, т. е. не равную − ∞ нижнюю оценку для f достаточно к задаче (5) – (8) добавить квадратичное неравенство 2 ( ) 0,low up low upr r r r r r− + + ≤ (9) где up r – верхняя граница на неизвестный радиуc r . Вначале ее можно устано- вить равной low mr , т. е. очевидной границе сверху на r , а затем последователь- но уточнять по мере нахождения локальных минимумов в задаче (1) – (4), либо (5) – (8). Квадратичное неравенство (9) является следствием умножения двух линейных неравенств: неравенства 0 low r r− ≥ и неравенства 0 up r r− ≤ . Заме- тим, что подобные квадратичные неравенства можно строить и для некоторых из компонент переменных , , = 1, , i i x y i mK . Пусть q – двойственная оценка снизу для f в задаче (5) – (9) и пусть * <q f . Тогда ее можно последовательно улучшать не только за счет добавле- ния функционально избыточных квадратичных ограничений, которые являются нетривиальными следствиями условий задачи, а также за счет замены некото- рых из неравенств в (7) равенствами, что означает, что соответствующие этим неравенствам круги должны соприкасаться друг с другом. Задача обратно-выпуклого программирования. Задачу равновесной упаковки кругов в круг минимального радиуса можно записать как задачу обратно-выпуклого программирования [7], которая дополнена линейными и выпуклыми ограничениями. Эта задача имеет следующий вид: , , = min r x y r r (10) при ограничениях 2 2 2( ) ( ) ( ) , 1 < ,i j i j i jx x y y r r i j m− + − ≥ + ≤ ≤ (11) =1 =1 = 0, = 0, m m i i i i i i x yλ λ∑ ∑ (12) РАВНОВЕСНАЯ УПАКОВКА КРУГОВ В КРУГ МИНИМАЛЬНОГО РАДИУСА Теорія оптимальних рішень. 2013 147 2 2 , = 1, , ,i i ix y r r i m+ ≤ − K (13) и может быть решена с помощью метода линеаризации [7, 8]. Из задачи (10) – (13) следует еще одна формулировка задачи равновесной упаковки кругов. Она является условной задачей минимизации негладкой выпуклой функции и имеет следующий вид: ( )* 2 2 , =1, , = min max i i i x y i m r x y r+ + K (14) при ограничениях 2 2 2( ) ( ) ( ) , 1 < ,i j i j i jx x y y r r i j m− + − ≥ + ≤ ≤ (15) =1 =1 = 0, = 0. m m i i i i i i x yλ λ∑ ∑ (16) Для нахождения локальных минимумов всех указанных выше задач можно использовать методы негладкой оптимизации. Опишем метод, который мы будем использовать. ( )r α -алгоритм и программа ralgb5. ( )r α -алгоритм относится к семей- ству субградиентных методов минимизации негладких выпуклых функций, которые известны как r -алгоритмы Н.З. Шора. r -алгоритмы базируются на процедуре наискорейшего спуска в преобразованном пространстве переменных и обеспечивают монотонность (или почти монотонность) по значениям минимизируемой функции. r -алгоритмы используют операцию растяжения пространства в направлении разности двух последовательных субградиентов, которая улучшает свойства овражной функции в преобразованном пространстве переменных. Пусть ( )f x – выпуклая функция от n переменных, > 1α . ( )r α – алгорит- мом минимизации ( )f x называется итеративная процедура построения после- довательностей векторов { } =0k k x ∞ и матриц { } =0k k B ∞ по следующему правилу: 1 1= , = ( ), = 0,1,2, , k k k k k k k k x x h B B B R k+ + β− ξ η K (17) где 0 ( ) = , = arg min ( ), ( ) T k f k k k k k kT h k f k B g x h f x hB B g x ≥ ξ − ξ P P (18) 1 1 = , = ( ) ( ), = < 1. T k k k k f k f kT k k B r r g x g x B r +η − β αP P (19) Здесь 0x – начальное приближение, 0 = n B I – единичная n n× -матрица (в каче- стве матрицы 0B часто выбирают диагональную матрицу n D с положитель- ными элементами на диагонали, с помощью которой осуществляется Э.И. НЕНАХОВ, Т.Е. РОМАНОВА, П.И. СТЕЦЮК 148 Теорія оптимальних рішень. 2013 масштабирование переменных), k h – шаговый множитель (определяется из условия минимума функции в направлении нормированного антисубградиента в преобразованном пространстве переменных), α – коэффициент растяжения пространства, ( ) = ( 1) T nR Iβ η + β − ηη – оператор «сжатия» пространства субградиентов в нормированном направлении η с коэффициентом 1 = < 1β α , ( ) f k g x и 1( ) f k g x + – произвольные субградиенты функции ( )f x в точках k x и 1k x + . Если ( ) = 0 f k g x , то k x является точкой минимума функции ( )f x и про- цесс (17) – (19) останавливается. ( )r α -алгоритм с адаптивной регулировкой шага в направлении нормиро- ванного антисубградиента в преобразованном пространстве переменных реализован в виде octave-программы ralgb5. Программа находит приближение * r x к точке минимума функции ( )f x . Ее название связано с тем, что пересчет матрицы B в алгоритме (17) – (19) требует 25n арифметических операций. Программа ralgb5 позволяет находить более точные приближения * r x , чем изве- стная программа ralgb4, которая экономит 2 n арифметических операций на каждой итерации [9]. Управляющие параметры в обеих программах одинаковы. Адаптивная регулировка шага связана с приближенным поиском минимума функции по направлению и реализуется с помощью параметров 0h , 1q , h n , 2q . Здесь 0h – величина начального шага (используется на 1-й итерации, на каждой последующей итерации эта величина уточняется); 1q – коэффициент умень- шения шага ( 1 1q ≤ ), если условие завершения спуска по направлению выполня- ется за один шаг; 2q – коэффициент увеличения шага ( 2 1q ≥ ); натуральное число h n задает число шагов одномерного спуска ( > 1 h n ), через каждые из которых шаг будет увеличиваться в 2q раз. Выбор как коэффициента растяже- ния пространства так и параметров адаптивной регулировки шага ориентирован на то, чтобы увеличивалась точность поиска минимума функции по направле- нию в процессе счета и при этом число шагов по направлению не должно быть большим. Условия завершения работы ( )r α -алгоритма определяются параметрами x ε и g ε : он останавливается в точке 1k x + , если выполнено условие 1k k x x x+ − ≤ εP P (останов по аргументу); или условие 1( ) f k g g x + ≤ εP P (останов по норме гради- ента, используется для гладких функций). Аварийное завершение программы связано либо с тем, что функция ( )f x неограничена снизу, либо начальный шаг 0h слишком мал и его требуется увеличить. РАВНОВЕСНАЯ УПАКОВКА КРУГОВ В КРУГ МИНИМАЛЬНОГО РАДИУСА Теорія оптимальних рішень. 2013 149 При минимизации негладких функций рекомендуется следующий выбор параметров: = 2 3α ÷ , 0 = 1.0h , 1 = 1.0q , 2 = 1.1 1.2q ÷ , = 2 3 h n ÷ . Если известна априорная оценка расстояния от начальной точки 0x до точки минимума ,x то начальный шаг 0h целесообразно выбирать порядка 0x x−P P. При минимизации гладких функций рекомендуемые параметры такие же, за исключением 1q , их следует выбирать 1 = 0.8 0.95.q ÷ Это обу- словлено тем, что дополнительное измельчение шага способствует увеличению точности поиска минимума функции по направлению, что при минимизации гладких функций обеспечивает более быструю скорость сходимости. При таком выборе параметров, как правило, число спусков по направлению редко превосходит два, а за n шагов точность по функции улучшается в три-пять раз. Параметры останова 6 5, 10 10x g − −ε ε ÷: при минимизации выпуклой функции (даже существенно овражной структуры) обеспечивают нахождение * r x со значением функции, достаточно близким к оптимальному. При этом обычно для негладких функций выполняется условие * * 6 5 * ( ) ( ) 10 10 \| ( ) \| 1 r f x f x f x − −− ÷ + : ( 12 1010 10− −÷: – для гладких функций), что подтверждается результатами многочисленных тестовых и реальных расчетов. Метод решения и тестовый эксперимент. С помощью негладких штрафов задача (1) – (4) сводится к задаче минимизации негладкой функции 1 1 2 2 3( , , ) ( , , ) ( , ) max{0, }lowf r x y r P F r x y P F x y P r r= + + + − + , (20) где kP – положительные штрафные коэффициенты, 1, 2, 3k = . Здесь функция 1( , , )F r x y имеет такой вид: 1 1 1 1 ( , , ) max{0, } max{0, }, m m m i ij i i j i F r x y = = = + = ϕ + ψ∑ ∑∑ где 2 2 2( ) , i i i i x y r rϕ = + − − 2 2 2( ) ( ) ( ) ,ij i j i j i jx x y y r rψ = − + − − + а функция 2 ( , )F x y имеет следующий вид: 2 =1 =1 =1 =1 ( , ) max{0, , } max{0, , }, m m m m i i x i i x i i y i i y i i i i F x y x x y y= λ − δ − λ − δ + λ − δ − λ − δ∑ ∑ ∑ ∑ где x δ и y δ – заданные допуски на отклонения координат центра тяжести семейства кругов от начала координат. Э.И. НЕНАХОВ, Т.Е. РОМАНОВА, П.И. СТЕЦЮК 150 Теорія оптимальних рішень. 2013 Алгоритм решения задачи (1) – (4) состоит в следующем. Для заданного на- бора стартовых точек осуществляется поиск локальных минимумов функции ( , , )f r x y с помощью программы ralgb5, в которой величина шага адаптивно настраивается с помощью указанных выше параметров. Наилучший из локаль- ных минимумов функции (20), для которого штрафная часть в функции ( , , )f r x y равна нулю, принимается за решение задачи (1) – (4). Стартовые точ- ки генерируются случайным образом. Рассматривался тестовый пример: 5m = , 1 0.1r = , 2 0.2r = , 3 0.3r = , 4 0.5r = , 5 0.8r = , 1 0.0785m = , 2 0.314m = , 3 0.7065m = , 4 1.9625m = , 5 5.024m = , 0.0001. x y δ = δ = На рис. 2, а приведено размещение кругов, соответствующее одному из оптимальных решений задачи (1) – (3), для него * 1.300f = и достигается оно в точке * * ( , , )r x y = (1.300,1.034,0.431,0.075,0.833,0.601,0.784,– 0.592,0.538,0.370,– 0.336), которая является точкой глобального минимума функции (20). На рис. 2, б при- дено размещение кругов, соответствующее одному из найденных локальных минимумов задачи (1) –( 4). Ему соответствует 1.316f = и точка локального минимума * * *( , , )r x y = (1.316,– 1.113,0.491,– 0.03,1.116,– 1.016,– 0.01,– 0.527,0.623,0.368,– 0.319). а б РИС. 2. Размещение объектов: а – без учета ограничений на центр тяжести, б – с учетом ограничений на центр тяжести При расчетах использовались 20 стартовых точек, которые генерировались датчиком случайных чисел с равномерным распределением на единичном квадрате. При этом глобальный минимум задачи (1) – (3) был найден из 19 стар- товых точек из 20, а наилучшее решение задачи (1)–(4) – из 3 стартовых точек. РАВНОВЕСНАЯ УПАКОВКА КРУГОВ В КРУГ МИНИМАЛЬНОГО РАДИУСА Теорія оптимальних рішень. 2013 151 О числах Шеннона и Ловаса. Задачи об оптимальной упаковке шаров тесно связаны с помехоустойчивыми кодами, или, другими словами, кодами, корректирующими ошибки при передаче информации. Это связано с двумя важными условиями, которым должна удовлетворять система кодовых слов, чтобы эти слова были надежно различимы. Первое условие означает, что соответствующие кодовым словам точки должны быть разделены некоторым минимальным «расстоянием». Евклидово расстояние служит достаточно хорошей мерой различимости соответствующих кодовых слов и описывается с помощью ограничений по подобию ограничений (3) только для n -мерного евклидового пространства. Второе условие связано с тем, что энергия, затра- чиваемая на передачу отдельного кодового слова, хорошо описывается квадра- тичными функциями, которые означают расстояние от кодового слова до начала координат. Таким образом, задача разработки надежной системы сигналов, обеспечивающей эффективное использование энергии, сводится к геометриче- ской задаче размещения точек внутри некоторой области пространства при дополнительном условии, означающем что точки не должны находиться слиш- ком близко друг к другу. Общая суть задач о помехоустойчивых кодах на языке теории графов такова. Пусть G – граф, вершинами которого являются буквы алфавита, а две вершины соединены ребром, если соответствующие этим вершинам буквы алфавита могут быть перепутаны. Тогда число устойчивости (независимости) графа G (его принято обозначать ( )Gα ) определяет наибольшее количество однобуквенных сообщений, которые можно послать, не боясь их перепутать. Устойчивые (независимые) множества вершин в графе G , на которых достига- ется ( ),Gα дают такие наборы букв алфавита, каждый из которых можно пере- слать, не боясь перепутать входящие в этот набор буквы. Задачи о помехо- устойчивых кодах определяются конкретным алфавитом и определенным способом (правилом) перепутывания букв алфавита, а число ( )Gα дает макси- мальный объем помехоустойчивого кода, который для них можно получить. Эти задачи дали теории оптимизации такие понятия, как шенноновская емкость графа ( )Gθ и число Ловаса ( )Gϑ [10]. Для измерения максимальной частоты передачи информации с нулевой ве- роятностью ошибки К. Шеннон ввел величину ( ) 1/ ( ) = ( ) ,lim k k k G G →+∞ θ α которая получила название шенноновской емкости графа G . Здесь k G – граф, верши- нами которого служат все возможные k -буквенные слова. Две вершины в графе k G соединены ребром, если соответствующие им слова могут быть перепутаны, причем два k -буквенных слова перепутываемы, если для всех i , 1 i k≤ ≤ их i -ые буквы перепутываемы или равны. Максимальное число неперепутываемых k -буквенных сообщений равно ( )kGα . Э.И. НЕНАХОВ, Т.Е. РОМАНОВА, П.И. СТЕЦЮК 152 Теорія оптимальних рішень. 2013 Задача определения емкости графа ( )Gθ оказалась очень сложной даже для небольших графов. Так, долгое время для графа в форме пятиугольника 5C (нечетный цикл, состоящий из пяти вершин) был известен только результат: 55 ( ) 5 / 2,C≤ θ ≤ полученный К. Шенноном в 1956 году. И только 21 год спустя [10], Л. Ловас нашел емкость пятиугольника 5C , доказав, что полученная Шенноном нижняя оценка точная. Сделал он это с помощью числа ( ),Gϑ которое впоследствии получило название числа Ловаса ∗ . Для пятиугольника 5C число Ловаса 5( )Cθ равно 5 . Для произвольного графа G число Ловаса ( )Gϑ может быть вычислено за полиномиальное время и служит верхней оцен- кой для числа устойчивости ( )Gα . Когда граф G является совершенным, то ( ) = ( ),G Gϑ α и, следовательно, число Ловаса есть точной оценкой для числа устойчивости совершенного графа. Заключение. Решение многоэкстремальных квадратичных задач для про- блем оптимальной упаковки неравных кругов с учетом ограничений поведения с помощью методов негладкой оптимизации представляется перспективным для параллельных вычислительных комплексов. Во-первых, субградиентные мето- ды с преобразованием пространства легко распараллеливаются, благодаря ис- пользованию простых матрично-векторных операций. Во-вторых, существуют параллельные реализации процедуры мультистарта, когда за отдельным процес- сором закреплен алгоритм поиска локального экстремума из соответствующей начальной точки. Эти особенности делают предлагаемый метод перспективным для реализации в системах параллельных или распределенных вычислений раз- личных проблем упаковки большого количества кругов или многомерных шаров. Е.І. Ненахов, Т.Є. Романова, П.І. Стецюк РІВНОВАЖНА УПАКОВКА КІЛ У КОЛО МІНІМАЛЬНОГО РАДІУСА Розглядається проблема упаковки системи нерівних кіл у коло мінімального радіуса, так щоб центр ваги системи кіл збігався із центром зовнішнього кола. Дано два її формулювання – у вигляді квадратичної екстремальної задачі й у вигляді задачі обернено-опуклого програму- вання. Для пошуку локальних екстремумів запропоновано метод на основі модифікації r -алгоритма та наведено результати обчислювальних експериментів. ∗ Число Ловаса совпадает с оценкой Шора для числа устойчивости графа, т. е лагран- жевой двойственной оценкой в квадратичной булевой задаче, с помощью которой формулируется задача нахождения независимого множества вершин в графе [6]. РАВНОВЕСНАЯ УПАКОВКА КРУГОВ В КРУГ МИНИМАЛЬНОГО РАДИУСА Теорія оптимальних рішень. 2013 153 Е.І. Nenakhov, Т.Е. Romanova, P.І. Stetsyuk BALANCED PACKING PROBLEM OF CIRCLES IN A CIRCLE OF MINIMUM RADIUS The paper considers a packing problem of a set of unequal circles into a containing circle of the minimum radius subject to the center of gravity of the set of circles is located at the center of the containing circle. We introduce two formulations of the packing problem: in the form of a quadratic extremal problem and, as well as, in the form of inverse-convex programming. We employ a me- thod based on the modification of the r -algorithm for local optimization. The results of computa- tional experiments are given. 1. Слоэн Н. Дж. А. Упаковка шаров // В мире науки. – 1984. – № 3. – С. 72–82. 2. Stoyan Y., Yaskov G. Packing congruent hyperspheres into a hypersphere // Journal of Global Optimization. – 2012. – Vol. 52, Issue 4. – P. 855–868. 3. Fasano G., Pintеr J.D., eds. Modeling and Optimization in Space Engineering. Springer Opti- mization and Its Applications. – Springer. – New York. – 2012. – 404 p. 4. Chao Che, Yi-shou Wang, Hong-fei Teng. Test problems for quasi-satellite packing: Cylinders packing with behavior constraints and all the optimal solutions known. – Ортіmization Online. – 2008. – 11 p. http://www.optimization-online.org/DB_HTML/2008/09/2093.html. 5. Коваленко А.А., Панкратов А.В., Романова Т.Е., Стецюк П.И. Упаковка круговых цилин- дров в цилиндрический контейнер с учетом специальных ограничений поведения систе- мы // Журнал обчислювальної та прикладної математики. – 2013. – № 1(111). – С. 106–115. 6. Shor N.Z. Nondifferentiable optimization and polynomial problems. – Kluwer Academic Pub- lishers. – 1998. – 394 p. 7. Пшеничный Б.Н., Соболенко Л.А. Метод линеаризации для обратно-выпуклого програм- мирования // Кибернетика и системный анализ. – 1995. – № 6. – С. 86–97. 8. Ненахов Э.И., Соболенко Л.А. Метод линеаризации и негладкая оптимизация // Системні дослідження та інформаційні технології. – 2009. – № 3. – С. 90 –104. 9. Шор Н.З., Стецюк П.И. Использование модификации r -алгоритма для нахождения гло- бального минимума полиномиальных функций // Кибернетика и системный анализ. – 1997. – № 4. – C. 28–49. 10. Lovasz L. On the Shannon capacity of a graph // IEEE Trans. Inform. Theory. – 1979. – 25, N 1. – P. 1–7. Получено 05.04.2013

Равновесная упаковка кругов в круг минимального радиуса

Institution

Similar Items