О задаче упаковки шаров в куб
Рассмотрена задача упаковки одинаковых шаров в единичный куб в n-мерном пространстве. Исследована двойственная лагранжева оценка (верхняя оценка радиуса шаров) для классической квадратичной постановки задачи и ряда постановок, полученных путем ее расширения семействами функционально избыточных огран...
Gespeichert in:
| Datum: | 2014 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/115823 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | О задаче упаковки шаров в куб / О.А. Березовский // Кибернетика и системный анализ. — 2014. — Т. 50, № 4. — С. 170-179. — Бібліогр.: 19 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-115823 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1158232017-04-14T03:02:32Z О задаче упаковки шаров в куб Березовский, А.О. Системный анализ Рассмотрена задача упаковки одинаковых шаров в единичный куб в n-мерном пространстве. Исследована двойственная лагранжева оценка (верхняя оценка радиуса шаров) для классической квадратичной постановки задачи и ряда постановок, полученных путем ее расширения семействами функционально избыточных ограничений. В базовой постановке получено аналитическое выражение для двойственной оценки. Розглянуто задачу пакування однакових куль в одиничний куб в n-вимірному просторі. Досліджено двоїсту лагранжеву оцінку (верхню оцінку радіуса куль) для класичної квадратичної постановки задачі та ряду постановок, отриманих шляхом її розширення сімействами функціонально надлишкових обмежень. У базовій постановці отримано аналітичний вираз для двоїстої оцінки. The problem of packing identical spheres in a unit cube in n-dimensional space is considered. The dual Lagrange bound (upper bound for sphere radius) for the classical quadratic formulation of the problem and some formulations obtained by expanding it by families of functionally redundant constraints is analyzed. The analytical expression for the dual bound is obtained in the basic formulation. 2014 Article О задаче упаковки шаров в куб / О.А. Березовский // Кибернетика и системный анализ. — 2014. — Т. 50, № 4. — С. 170-179. — Бібліогр.: 19 назв. — рос. http://dspace.nbuv.gov.ua/handle/123456789/115823 519.8 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Березовский, А.О. О задаче упаковки шаров в куб Кибернетика и системный анализ |
| description |
Рассмотрена задача упаковки одинаковых шаров в единичный куб в n-мерном пространстве. Исследована двойственная лагранжева оценка (верхняя оценка радиуса шаров) для классической квадратичной постановки задачи и ряда постановок, полученных путем ее расширения семействами функционально избыточных ограничений. В базовой постановке получено аналитическое выражение для двойственной оценки. |
| format |
Article |
| author |
Березовский, А.О. |
| author_facet |
Березовский, А.О. |
| author_sort |
Березовский, А.О. |
| title |
О задаче упаковки шаров в куб |
| title_short |
О задаче упаковки шаров в куб |
| title_full |
О задаче упаковки шаров в куб |
| title_fullStr |
О задаче упаковки шаров в куб |
| title_full_unstemmed |
О задаче упаковки шаров в куб |
| title_sort |
о задаче упаковки шаров в куб |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/115823 |
| citation_txt |
О задаче упаковки шаров в куб / О.А. Березовский // Кибернетика и системный анализ. — 2014. — Т. 50, № 4. — С. 170-179. — Бібліогр.: 19 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT berezovskijao ozadačeupakovkišarovvkub |
| first_indexed |
2025-07-08T09:25:40Z |
| last_indexed |
2025-07-08T09:25:40Z |
| _version_ |
1837070278488752128 |
| fulltext |
ÓÄÊ 519.8
Î.À. ÁÅÐÅÇÎÂÑÊÈÉ
Î ÇÀÄÀ×Å ÓÏÀÊÎÂÊÈ ØÀÐΠ ÊÓÁ
Àííîòàöèÿ. Ðàññìîòðåíà çàäà÷à óïàêîâêè îäèíàêîâûõ øàðîâ â åäèíè÷íûé êóá â n-ìåð-
íîì ïðîñòðàíñòâå. Èññëåäîâàíà äâîéñòâåííàÿ ëàãðàíæåâà îöåíêà (âåðõíÿÿ îöåíêà ðàäèóñà
øàðîâ) äëÿ êëàññè÷åñêîé êâàäðàòè÷íîé ïîñòàíîâêè çàäà÷è è ðÿäà ïîñòàíîâîê, ïîëó÷åí-
íûõ ïóòåì åå ðàñøèðåíèÿ ñåìåéñòâàìè ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé.  áàçî-
âîé ïîñòàíîâêå ïîëó÷åíî àíàëèòè÷åñêîå âûðàæåíèå äëÿ äâîéñòâåííîé îöåíêè.
Êëþ÷åâûå ñëîâà: ïëîòíîñòü óïàêîâêè, ýêñòðåìàëüíàÿ êâàäðàòè÷íàÿ çàäà÷à, äâîéñòâåííàÿ
ëàãðàíæåâà îöåíêà, ôóíêöèîíàëüíî èçáûòî÷íûå îãðàíè÷åíèÿ, îòðèöàòåëüíî îïðåäåëåííàÿ
ìàòðèöà.
ÂÂÅÄÅÍÈÅ
Çàäà÷à îá óïàêîâêå øàðîâ (sphere packing problem) îòíîñèòñÿ ê NP-òðóäíûì çà-
äà÷àì â òåîðèè ñëîæíîñòè âû÷èñëåíèé.  îáùåì âèäå åå ñóòü ñîñòîèò â ðàçìå-
ùåíèè íåïåðåñåêàþùèõñÿ øàðîâ â íåêîòîðîé îáëàñòè åâêëèäîâà ïðîñòðàíñòâà
ñ ìàêñèìàëüíîé ïëîòíîñòüþ, ò.å. òàêîãî ðàçìåùåíèÿ, ïðè êîòîðîì øàðàìè ïî-
êðûòà íàèáîëüøàÿ ÷àñòü ýòîé îáëàñòè (âîçìîæíî íàëè÷èå äîïîëíèòåëüíûõ
óñëîâèé, íàïðèìåð ñïåöèàëüíûå òðåáîâàíèÿ íà ðàñïîëîæåíèå öåíòðà ìàññ ïîëó-
÷åííîãî íàáîðà øàðîâ). Ñóùåñòâóåò ìíîæåñòâî ðàçíîâèäíîñòåé ýòîé çàäà÷è
[1–3], êîòîðûå ìîãóò ïðèìåíÿòüñÿ â ðàçëè÷íûõ îáëàñòÿõ, íàïðèìåð ïðè îïòè-
ìàëüíîì çàïîëíåíèè êîíòåéíåðîâ, äëÿ óïàêîâêè êàáåëåé (öèëèíäðîâ) â öèëèí-
äðè÷åñêîé òðóáå, ïðè ïðîåêòèðîâàíèè è êîìïîíîâêå ðàçíîîáðàçíûõ òåõíîëîãè-
÷åñêèõ îáúåêòîâ è ñèñòåì, ñîçäàíèè ðåçåðâíûõ êîïèé íà ñúåìíûõ íîñèòåëÿõ,
ïðè îïòèìèçàöèè õðàíåíèÿ, çàùèòû è òðàíñïîðòèðîâêè òîâàðîâ è ò.ä. Ïðèìåíå-
íèå ýòîé çàäà÷è âàæíî ïðè èññëåäîâàíèè êðèñòàëëè÷åñêèõ ñòðóêòóð, â ñëó÷àå
èñïîëüçîâàíèÿ èõ ìîäåëüíîãî îïèñàíèÿ â âèäå ñèñòåìû øàðîâ (àòîìîâ) â ïëîò-
íîé óïàêîâêå (ñîãëàñíî ïðèíöèïó ïëîòíîé óïàêîâêè ìîëåêóë, ñôîðìóëèðîâàí-
íîìó À.È. Êèòàéãîðîäñêèì, ìîëåêóëû, ìîäåëèðóåìûå âíåøíèì êîíòóðîì ïåðå-
ñåêàþùèõñÿ âàíäåðâààëüñîâûõ ñôåð àòîìîâ, â êðèñòàëëàõ «êàñàþòñÿ», ò.å. âçà-
èìíî íå ïðîíèêàþò è «íå âèñÿò» â ïóñòîòå). Ðàññìàòðèâàÿ ïðèêëàäíîå çíà÷åíèå
çàäà÷è îá óïàêîâêå øàðîâ, íåîáõîäèìî óïîìÿíóòü òàêæå î çàäà÷å ðàçðàáîòêè
íàäåæíîé ñèñòåìû ñèãíàëîâ, êîòîðàÿ ñâîäèòñÿ ê ãåîìåòðè÷åñêîé çàäà÷å ðàçìå-
ùåíèÿ òî÷åê âíóòðè íåêîòîðîé îáëàñòè ïðîñòðàíñòâà ïðè äîïîëíèòåëüíîì óñëî-
âèè, ÷òî îíè íå äîëæíû íàõîäèòüñÿ ñëèøêîì áëèçêî îäèí ê äðóãîìó (åñëè òðå-
áóåòñÿ, ÷òîáû ðàññòîÿíèå ìåæäó ýòèìè òî÷êàìè áûëî, ñêàæåì, íå ìåíüøå 2,
òî çàäà÷à ýêâèâàëåíòíà ïîñòðîåíèþ áîëåå ïëîòíîåé óïàêîâêè øàðîâ, ðàäèóñ êî-
òîðûõ ðàâåí ïîëîâèíå ýòîãî ðàññòîÿíèÿ, ò.å. 1 2/ ).
Ìíîãèå çàäà÷è óïàêîâêè, â òîì ÷èñëå è äèñêðåòíûå, ïðåäñòàâèìû â âèäå
êâàäðàòè÷íîé çàäà÷è (ýêñòðåìàëüíîé çàäà÷è, öåëåâàÿ ôóíêöèÿ è âñå ôóíêöèè îãðà-
íè÷åíèé êîòîðîé êâàäðàòè÷íûå (quadratically constrained quadratic programming)),
âñëåäñòâèå ÷åãî öåëåñîîáðàçíî èññëåäîâàòü âîçìîæíîñòü ïðèìåíåíèÿ ëàãðàíæå-
âûõ äâîéñòâåííûõ îöåíîê [4, 5] ïðè èõ ðåøåíèè. Â íàñòîÿùåé ðàáîòå ðàññìîòðåíû
íåêîòîðûå ïóòè ðåàëèçàöèè ýòîãî ïîäõîäà íà ïðèìåðå çàäà÷è óïàêîâêè îäèíàêî-
âûõ øàðîâ â åäèíè÷íûé êóá ñ ìàêñèìàëüíîé ïëîòíîñòüþ: â n-ìåðíîì åâêëèäî-
âîì ïðîñòðàíñòâå íåîáõîäèìî ìàêñèìèçèðîâàòü ðàäèóñ r îäèíàêîâûõ íåïåðåñå-
êàþùèõñÿ m øàðîâ S y r y y y ri i( , ) { : || || }� � � , i m�1, ( ( , , , )y y y yi i i in� 1 2 �
T ,
i m�1, , — íåèçâåñòíûå öåíòðû øàðîâ) ïðè óñëîâèè, ÷òî îíè ïðèíàäëåæàò åäèíè÷-
íîìó êóáó, ò.å. S y r y y yi
n n( , ) [ , ] { : , }� � � � ��01 0 1 , i m�1, .
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 4
© Î.À. Áåðåçîâñêèé, 2014
ÊÂÀÄÐÀÒÈ×ÍÀß ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ñôîðìóëèðóåì çàäà÷ó óïàêîâêè øàðîâ â êóá â âèäå çàäà÷è ìàòåìàòè÷åñêîãî
ïðîãðàììèðîâàíèÿ
max r, (1)
( )y y rik jk
k
n
� �
�
2
1
24 , 1�
�i j m , (2)
r y rik� � �1 , i m�1, , k n�1, , (3)
Çäåñü îãðàíè÷åíèå (2) ñîîòâåòñòâóåò óñëîâèþ, ñîãëàñíî êîòîðîìó âñå ïàðû øà-
ðîâ S y ri( , ) è S y rj( , ) , i j m, ,�1 , i j� , íå ïåðåñåêàþòñÿ, à îãðàíè÷åíèå (3) —
óñëîâèþ ïðèíàäëåæíîñòè øàðîâ åäèíè÷íîìó êóáó S y ri
n( , ) [ , ]� 0 1 , i m�1, .
Ðàññìàòðèâàåìàÿ ãåîìåòðè÷åñêàÿ çàäà÷à îòíîñèòñÿ ê òåì, êîòîðûå íàõîäÿòñÿ
ïîä ïîñòîÿííûì âíèìàíèåì èññëåäîâàòåëåé [3, 6–10], è îáû÷íî ñâîäèòñÿ ê ýê-
âèâàëåíòíîé çàäà÷å î ðàçìåùåíèè m òî÷åê â åäèíè÷íîì êóáå òàêèì îáðàçîì,
÷òîáû ìèíèìàëüíîå ðàññòîÿíèå ìåæäó íèìè (ðàâíîå d) áûëî ìàêñèìàëüíûì
(point packing problem):
d d* max� , (4)
( )x x dik jk
k
n
� �
�
2
1
, 1�
�i j m , (5)
0 1� �xik , i m�1, , k n�1, . (6)
Ñâÿçü ìåæäó ïåðåìåííûìè èñõîäíîé çàäà÷è (1)–(3) è çàäà÷è (4)–(6) çàäàåòñÿ
ñëåäóþùèìè ñîîòíîøåíèÿìè:
y r x rik ik� � �( )1 2 , i m�1, , k n�1, ,
r
d
d
�
�2 1( )
. (7)
Òàêèì îáðàçîì, èñõîäíàÿ ãåîìåòðè÷åñêàÿ çàäà÷à óïàêîâêè øàðîâ â êóá
ñôîðìèðîâàíà â âèäå ìíîãîýêñòðåìàëüíîé êâàäðàòè÷íîé çàäà÷è (4)–(6), íàõîæ-
äåíèå ãëîáàëüíîãî ìàêñèìóìà êîòîðîé ïðåäñòàâëÿåò îïðåäåëåííûå òðóäíîñòè,
è ñëåäîâàòåëüíî, ñòàíîâèòñÿ àêòóàëüíîé îöåíêà ãëîáàëüíîãî îïòèìóìà. Èç èç-
âåñòíûõ ïîäõîäîâ ê ïîëó÷åíèþ îöåíîê îïòèìàëüíîãî çíà÷åíèÿ öåëåâîé ôóíêöèè
â òàêèõ çàäà÷àõ ìîæíî íàçâàòü, íàïðèìåð ñâåäåíèå êâàäðàòè÷íûõ ôîðì çàäàííîé
ïîñòàíîâêè ê ëèíåéíîìó âèäó ïóòåì ââåäåíèÿ íîâûõ ïåðåìåííûõ X xx� T (çäåñü
x x x xn
n�
��( , )1 2 �
T — âåêòîð ïåðåìåííûõ èñõîäíîé êâàäðàòè÷íîé ïîñòà-
íîâêè) ñ ïîñëåäóþùåé ðåëàêñàöèåé çàäà÷è ïóòåì çàìåíû ðàâåíñòâà âçàèìîñâÿçè
ñòàðûõ è íîâûõ ïåðåìåííûõ ðàçëè÷íûìè ñåìåéñòâàìè âûïóêëûõ îãðàíè÷åíèé.
Ýòî ìîæåò áûòü êàê SDP-ðåëàêñàöèÿ (çàäà÷à ïîëóîïðåäåëåííîãî ïðîãðàììèðîâà-
íèÿ, ïîëó÷åííàÿ ñ ïîìîùüþ îãðàíè÷åíèÿ
1
0
x
x XT
�
�
��
�
�
�� � è èãíîðèðóþùàÿ òðåáî-
âàíèå, ÷òîáû ðàíã ýòîé ìàòðèöû áûë ðàâåí åäèíèöå) [11], òàê è ëèíåéíûå ðåëàê-
ñàöèè, èñïîëüçóþùèå íàëè÷èå îãðàíè÷åíèé ñïåöèàëüíîãî âèäà. Íàïðèìåð, ïðè
íàëè÷èè îãðàíè÷åíèé âèäà 0 1� �xi , i n�1, , ìîæíî èñïîëüçîâàòü RLT-ðåëàêñà-
öèè (�i j, X ij � 0 , X x xij i j� � �1 , X xij i� , X xij j� ) [12] èëè ðàçëè÷íûå îãðà-
íè÷åíèÿ äëÿ áóëåâà êâàäðàòè÷íîãî ïîëèòîïà, íàïðèìåð íåðàâåíñòâà «òðåóãîëü-
íèêîâ» (� � �i j k x x x X X Xi j k ij ik jk� � � � � �1 , X X x Xij ik i jk� � � ,
X X x Xij jk j ik� � � , X X x Xik jk k ij� � � ) [13]. (Îòìåòèì, ÷òî íàëè÷èå îãðàíè-
÷åíèé (6) èìååò äîñòàòî÷íî îáùèé õàðàêòåð, ïîñêîëüêó èõ ìîæíî ïîëó÷èòü â
ëþáîé çàäà÷å, ãäå âîçìîæíà ëîêàëèçàöèÿ ãëîáàëüíîãî ýêñòðåìóìà
x lower upper n�[ , ] , çàìåíîé ïåðåìåííûõ x upper lower x lower� � � �( ) ~ ) ,
~ [ , ]x n� 0 1 , ãäå � — çíàê îïåðàöèè ïîêîìïîíåíòíîãî ïðîèçâåäåíèÿ âåêòîðîâ.)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 4 171
Tåõíèêà ïîëóîïðåäåëåííîãî ïðîãðàììèðîâàíèÿ ïîçâîëÿåò âêëþ÷àòü â èñ-
õîäíóþ çàäà÷ó äîïîëíèòåëüíûå ëèíåéíûå îãðàíè÷åíèÿ (÷òî äåëàåò ëèíåéíûå ðå-
ëàêñàöèè åå áîëåå ñëàáûì àíàëîãîì). Ýòî ïðèâîäèò ê ðàçëè÷íûì SDP-ðåëàêñàöè-
ÿì è, ñëåäîâàåòåëüíî, ê ðàçëè÷íûì îöåíêàì îïòèìàëüíîãî çíà÷åíèÿ öåëåâîé
ôóíêöèè çàäà÷è. Áëèçêîé ê SDP-ðåëàêñàöèÿì ÿâëÿåòñÿ òåõíèêà äâîéñòâåííûõ
êâàäðàòè÷íûõ îöåíîê. Ðàçâèâàÿñü ñàìîñòîÿòåëüíî [4, 5, 14, 15], îíà ôàêòè÷åñêè
ïðèâîäèò ê ðåøåíèþ çàäà÷è, äâîéñòâåííîé ê SDP-ðåëàêñàöèè.  [16] ïîêàçàíî,
÷òî äëÿ îäíîé è òîé æå êâàäðàòè÷íîé ïîñòàíîâêè çàäà÷è äâîéñòâåííàÿ ëàãðàíæå-
âà îöåíêà íå õóæå SDP-îöåíêè, à ïðè âûïîëíåíèè óñëîâèé ðåãóëÿðíîñòè îáå
îöåíêè ñîâïàäàþò (ýòî äàåò âîçìîæíîñòü ýêñòðàïîëèðîâàòü òåîðåòè÷åñêèå ðå-
çóëüòàòû îäíîãî ñëó÷àÿ íà äðóãîé).
ÄÂÎÉÑÒÂÅÍÍÀß ËÀÃÐÀÍÆÅÂÀ ÎÖÅÍÊÀ
Äâîéñòâåííàÿ îöåíêà � * îïòèìàëüíîãî çíà÷åíèÿ öåëåâîé ôóíêöèè f * êâàäðà-
òè÷íîé çàäà÷è îáùåãî âèäà
f f x f x i I f xi
LE
j
* ( ) : ( ) , , ( ) ,� � � �sup{ 0 0 0
j I x x x xEQ
n
n� �
��; ( , ) }1 2 �
T , (8)
ãäå f x x A x b x ci i i i( ) � � �T T , i I J� � �{ }0 , îïðåäåëÿåòñÿ ñëåäóþùèì ñïîñîáîì:
� �* *( )� �
� � �
inf
u D U
u f . (9)
Çäåñü �( ) ( , )u L x u
x R n
�
�
sup , L x u x A u x b u x c u( , ) ( ) ( ) ( )� � �T T — ôóíêöèÿ Ëàãðàí-
æà äëÿ çàäà÷è (8), U u u i Ii
LE� � � �{ : , }0 , D — ìíîæåñòâî äâîéñòâåííûõ ïå-
ðåìåííûõ u m�� (m I ILE EQ� �| | | |), ïðè êîòîðûõ ìàòðèöà A u( ) îòðèöàòåëüíî
îïðåäåëåíà. Íàõîæäåíèå äâîéñòâåííîé îöåíêè � * îòíîñèòñÿ ê «õîðîøèì» çàäà-
÷àì ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ, ïîñêîëüêó âíóòðåííÿÿ çàäà÷à íàõîæäåíèÿ
ìàðãèíàëüíîé ôóíêöèè �( )u ïðè u D� ÿâëÿåòñÿ çàäà÷åé ìàêñèìèçàöèè âîãíóòîé
êâàäðàòè÷íîé ôóíêöèè, ðåøåíèå êîòîðîé îäíîçíà÷íî îïðåäåëÿåòñÿ èç ñèñòåìû óðàâíå-
íèé � � � �L u x A u x b ux ( , ) ( ) ( )2 0 ñ ïîìîùüþ âûðàæåíèÿ x u A u b u( ) ( ) ( ) /� � �1 2 ,
à âíåøíÿÿ çàäà÷à ïðåäñòàâëÿåò ñîáîé çàäà÷ó ìèíèìèçàöèè íà âûïóêëîì ìíî-
æåñòâå D U� � âûïóêëîé ôóíêöèè �( )u . Ïðèíèìàÿ âî âíèìàíèå íåîäíîçíà÷-
íîñòü ïîñòàíîâêè êâàäðàòè÷íûõ îïòèìèçàöèîííûõ çàäà÷, íàïðèìåð ïðè èõ
ðàñøèðåíèè ïóòåì ââåäåíèÿ äîïîëíèòåëüíûõ îãðàíè÷åíèé, êîòîðûå íå âëèÿþò
íà äîïóñòèìóþ îáëàñòü èñõîäíîé êâàäðàòè÷íîé çàäà÷è (èëè, êàê èõ ÷àñòî íà-
çûâàþò, ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé (superfluous èëè redundant
constraints)), ìîæíî ïîëó÷àòü ðàçëè÷íûå âåðõíèå îöåíêè ìàêñèìàëüíîãî çíà÷å-
íèÿ öåëåâîé ôóíêöèè. Îòìåòèì, ÷òî äàííàÿ ñèòóàöèÿ ïðèñóùà è SDP-ðåëàêñà-
öèÿì (â àíãëîÿçû÷íîé ëèòåðàòóðå ýòî ïðèâåëî ê ìíîæåñòâó íàçâàíèé SDP-ðåëàê-
ñàöèé, êîòîðûå îòëè÷àþòñÿ ñåìåéñòâàìè äîïîëíèòåëüíûõ îãðàíè÷åíèé â èñõîä-
íîé çàäà÷å).
Äëÿ äàëüíåéøèõ èññëåäîâàíèé ìîäèôèöèðóåì ïîñòàíîâêè çàäà÷è (4)–(6) ïó-
òåì ñëåäóþùèõ îïåðàöèé:
à) çàìåíà ïåðåìåííîé d z� 2 è ëèíåéíûõ îãðàíè÷åíèé (6) íà êâàäðàòè÷íûå
x xik ik( )� �1 0 , i m�1, , k n�1, , äëÿ òîãî, ÷òîáû îáëàñòü îòðèöàòåëüíîé îïðåäå-
ëåííîñòè ìàòðèöû ôóíêöèè Ëàãðàíæà áûëà íå ïóñòîé;
á) çàìåíà ïåðåìåííûõ x xik ik� �(~ ) /1 2 , i m�1, , k n�1, , äëÿ ïðèâåäåíèÿ çàäà-
÷è ê îäíîðîäíîìó âèäó, ò.å. ê êâàäðàòè÷íîé ïîñòàíîâêå, âî âñåõ ôóíêöèÿõ êîòîðîé
îòñóòñòâóþò ëèíåéíûå ÷ëåíû (íàïîìíèì, ÷òî çíà÷åíèå äâîéñòâåííîé îöåíêè ïðè
íåâûðîæäåííîì ëèíåéíîì ïðåîáðàçîâàíèè ïðîñòðàíñòâà íå ìåíÿåòñÿ [4]).
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 4
Òîãäà çàäà÷à (4)–(6) ïðèìåò âèä
max z 2 , (10)
4 02 2
1
z x xik jk
k
n
� � �
�
(~ ~ ) , 1�
�i j m, (11)
~x
ik
2 1 0� � , i m�1, , k n�1, . (12)
Îáîçíà÷èì u âåêòîð äâîéñòâåííûõ ïåðåìåííûõ äëÿ îãðàíè÷åíèé (11), êîì-
ïîíåíòà uij êîòîðîãî ñîîòâåòñòâóåò îãðàíè÷åíèþ âèäà (11) äëÿ i-ãî è j-ãî øàðîâ,
j i� (ðàçìåðíîñòü ýòîãî âåêòîðà m m( ) /�1 2), è � — âåêòîð äâîéñòâåííûõ ïåðå-
ìåííûõ ñîîòâåòñòâåííî äëÿ îãðàíè÷åíèé (12) (åãî ðàçìåðíîñòü mn). Ïîñêîëüêó
çàäà÷à (10)–(12) èìååò âèä îäíîðîäíîé êâàäðàòè÷íîé çàäà÷è, ðåøåíèå âíóòðåí-
íåé çàäà÷è íàõîæäåíèÿ ìàðãèíàëüíîé ôóíêöèè �( ) ( , )u L x u
x R n
�
�
sup ïðè
u D U� � � òðèâèàëüíî, à èìåííî x � 0 . Îòñþäà íàõîæäåíèå âåðõíåé äâîéñòâåí-
íîé îöåíêè � * (9) äëÿ çàäà÷è (10)–(12) ñâîäèòñÿ ê ðåøåíèþ çàäà÷è âûïóêëîãî
ïðîãðàììèðîâàíèÿ
� �* min� �
�
�
�
�
�
�
�
�� ��
u R
ik
k
n
i
m
n
11
, (13)
� �max ( ( , ))A u � 0 , (14)
u, � � 0 , (15)
ãäå ìàòðèöà A u( , )� ôóíêöèè Ëàãðàíæà — áëî÷íàÿ äèàãîíàëüíàÿ ìàòðèöà, ïåð-
âûé áëîê êîòîðîé ñîñòîèò èç îäíîãî ýëåìåíòà 1 4
1
�
�
�
uij
i j
j i
m
,
(ñîîòâåòñòâóåò ïåðå-
ìåííîé z), à îñòàëüíûå n áëîêîâ (äëÿ êàæäîé k-é êîîðäèíàòû) èìåþò îäèíà-
êîâóþ ñòðóêòóðó ~ ~ ~x x x
u u u
u u u
k k mk
j
j
m
k m
j
j
m
1 2
1
1
1 12 1
12 12 2
2
� �
� � �
�
�
�
�
�
2 2
1 2
1
1
k m
m m jm
j
m
mk
u
u u u
�
� � � �
� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
. (16)
Âñëåäñòâèå ñïåöèàëüíîãî âèäà ìàòðèöû A u( ) , îáóñëîâëåííîãî íàëè÷èåì
îãðàíè÷åíèé (12) â èñõîäíîé çàäà÷å (10)–(12), îãðàíè÷åíèå (14) ìîæíî ó÷åñòü
ñ ïîìîùüþ òî÷íîé øòðàôíîé ôóíêöèè â âèäå ôóíêöèè ìàêñèìóìà.
Ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 1. Ïðè N mn� � � * òî÷êè ìèíèìóìà çàäà÷è (13)–(15) è çàäà÷è
� � � � �
�
*
,
maxmin max ( ; ( ( , ));� � �
� ��
u
u
ik
k
n
i
m
ikN A u
0 11
0 , , , , )i m k n� �
�
�
�
�
�
�
�
�
1 1 (17)
ñîâïàäàþò.
Äîêàçàòåëüñòâî ýòîãî óòâåðæäåíèÿ àíàëîãè÷íî äîêàçàòåëüñòâó ðåçóëüòàòîâ,
ïîëó÷åííûõ â [14, 17], è îñíîâàíî íà òåîðåìå Ïøåíè÷íîãî [18, ñ. 25].
Òàêèì îáðàçîì, íàõîæäåíèå äâîéñòâåííîé ëàãðàíæåâîé îöåíêè äëÿ ìíîãî-
ýêñòðåìàëüíîé çàäà÷è (10)–(12) ñâåäåíî ê ðåøåíèþ çàäà÷è (17), êîòîðàÿ îòíîñèò-
ñÿ ê çàäà÷àì âûïóêëîé íåãëàäêîé îïòèìèçàöèè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 4 173
ÀÍÀËÈÒÈ×ÅÑÊÎÅ ÂÛÐÀÆÅÍÈÅ ÄËß ÄÂÎÉÑÒÂÅÍÍÎÉ ÎÖÅÍÊÈ ÇÀÄÀ×È (10)–(12)
Äâîéñòâåííàÿ îöåíêà � * (17), ïîëó÷åííàÿ äëÿ ïîñòàíîâêè çàäà÷è (10)–(12),
÷èñëåííî ðàâíà îöåíêå, ïîëó÷åííîé äëÿ SDP-ðåëàêñàöèè ïîñòàíîâêè çàäà÷è
(4)–(6) [10], ïîñêîëüêó, âî-ïåðâûõ, ïðåîáðàçîâàíèå ïîñëåäíåé â çàäà-
÷ó (10)–(12) (ìîäèôèêàöèè à) è á)) íå ìåíÿþò âòîðîé îöåíêè, è, âî-âòîðûõ,
äëÿ îáåèõ îöåíî÷íûõ çàäà÷ âûïîëíÿåòñÿ óñëîâèå ðåãóëÿðíîñòè Ñëåéòåðà, ÷òî
ñîãëàñíî òåîðåìå [16] ÿâëÿåòñÿ äîñòàòî÷íûì óñëîâèåì ðàâåíñòâà ýòèõ îöåíîê.
 [10] íàðÿäó ñ ðåçóëüòàòàìè ÷èñëåííûõ ýêñïåðèìåíòîâ ñôîðìóëèðîâàíî
ïðåäïîëîæåíèå, ÷òî ïðè n � 2 îöåíêà, ïîëó÷åííàÿ SDP-ðåëàêñàöèåé ïîñòàíîâêè
çàäà÷è (4)–(6), çàäàåòñÿ àíàëèòè÷åñêè
� * � �
�
1
1
1m
.
Äîêàæåì ýòî ïðåäïîëîæåíèå, äëÿ ÷åãî ðàññìîòðèì çàäà÷ó (17). Ïóñòü èìååì
òî÷êó ( , )* *u � , â êîòîðîé êîîðäèíàòû uij
* ,1�
�i j m , îòðèöàòåëüíû. Òîãäà äëÿ
äîêàçàòåëüñòâà òîãî, ÷òî ( , )* *u � ÿâëÿåòñÿ ðåøåíèåì çàäà÷è (17), äîñòàòî÷íî ïî-
êàçàòü, ÷òî ìíîæåñòâî ñóáãðàäèåíòîâ ìèíèìèçèðóåìîé ôóíêöèè (17)
�( , ) max ( ; ( ( , )); , ,maxu N A u iik
k
n
i
m
ik� � � � �� � � �
��
11
0 1 m k n, , )�1 â ýòîé òî÷êå
ñîäåðæèò íóëåâîé âåêòîð (â ñëó÷àå u*
0 îãðàíè÷åíèåì ìîæíî ïðåíåáðå÷ü è çà-
äà÷ó (17) ðàññìàòðèâàòü êàê áåçóñëîâíóþ çàäà÷ó ìèíèìèçàöèè âûïóêëîé íåäèô-
ôåðåíöèðóåìîé ôóíêöèè). Ïîêàæåì, ÷òî ýòî óñëîâèå âûïîëíÿåòñÿ äëÿ òî÷êè
( , )* *u � , îïðåäåëåííîé ñëåäóþùèì îáðàçîì:
— âñå ýëåìåíòû âåêòîðà u* îäèíàêîâû:
u
m ò m ò
ij
*
( ) ( )
� �
�
� �
�
1
4
1
1
2
1
2 1
, i j m, ,�1 , i j
(äëÿ òîãî, ÷òîáû âûïîëíÿëîñü ðàâåíñòâî 1 4 0
1
� �
�
�
uij
i j
j i
m
,
);
— âñå ýëåìåíòû âåêòîðà � * îäèíàêîâû:
� ik ji
j
j i
ij
j i
m
iju u
m ò
mu
ò
* * * *
( ) ( )
� � �
�
� � �
��
�
1
1
2 1
1
2 1
, i m�1, , k n�1, .
Íåòðóäíî âèäåòü, ÷òî ïðè ýòèõ çíà÷åíèÿõ äâîéñòâåííûõ ïåðåìåííûõ
A u( , )* *� ÿâëÿåòñÿ îòðèöàòåëüíî-ïîëóîïðåäåëåííîé ìàòðèöåé ðàíãà n , â êîòî-
ðîé íåíóëåâûå ñîáñòâåííûå ÷èñëà ðàâíû � k
m
� �
�
1
2 1( )
, k n�1, (ïî îäíîìó äëÿ
êàæäîãî áëîêà (16)), à ñîîòâåòñòâóþùèå èì ñîáñòâåííûå âåêòîðû îïðåäåëÿþòñÿ
êàê � � � �k n
nmR� � �( )01 1 2
1
�
T , ãäå âåêòîð-ñòðîêè � l m
mR� �0 äëÿ âñåõ
l k� , l n�1, , — íóëåâûå, à ïðè l k� âåêòîð-ñòðîêè � k m
m
m
e R� �
1 T (0m è
em — ñîîòâåòñòâåííî íóëåâàÿ è åäèíè÷íàÿ m-ìåðíàÿ âåêòîð-ñòðîêà). Äëÿ íàãëÿä-
íîñòè ïðèâåäåì ñîîòâåòñòâóþùèé äàííîé òî÷êå ( , )* *u � âèä ôóíêöèè Ëàãðàíæà
ïîñòàíîâêè çàäà÷è (10)–(12)
L z x u
m m
x
mn
m
ik
i
m
k
n
( , , , )
( ) (
* *� � �
�
�
�
�
�
�
�
�
�
�
��
1
2 1 21
2
1 �1)
.
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 4
Ïîêàæåì, ÷òî â âûáðàííîé òî÷êå ( , )* *u � ñóùåñòâóåò íóëåâîé ñóáãðàäèåíò
ìèíèìèçèðóåìîé ôóíêöèè (17), ò.å. 0�� � �� �( , ) { ( , )}* * * *u conv u� � . Êîîð-
äèíàòû ñóáãðàäèåíòîâ �� ( , )* *u � îïðåäåëÿþòñÿ ïî ôîðìóëàì
� � ��u uij ij
u N A u( , ) ( ( ( , )))* *
max
* *� � � � ,
� � � � ��� �� � � �
ik ik
u N A u( , ) ( ( ( , )))* *
max
* *1 ,
ãäå êîýôôèöèåíò � , 0 1� �� , ââåäåí äëÿ ó÷åòà òîãî, ÷òî
(max{ , ; ( ( , ))}) { , ( ( ( , )))max
* *
max
* *0 0� � � �A u conv A u�� �},
à ñóáãðàäèåíò ôóíêöèè ìàêñèìàëüíîãî ñîáñòâåííîãî ÷èñëà ìàòðèöû A u( , )�
â òî÷êå ( , )* *u � åñòü ( ( ( , ))) ( : ( ( , )))max
* *
max
* *� � � �A u conv p p A u�� �� ,
p R nm m m� � �( )/1 2 , ãäå êîìïîíåíòû âåêòîðà p îïðåäåëÿþòñÿ èç ðàâåíñòâ
p s s s s s
u z x x x x
k
n
ij ik ik jk jk
� � � � �
�
4 22 2 2
1
( ) , p s
ik ikx�
� 2 . (18)
Çäåñü s l n mn Rl
nm� � � � � �{ , , }� 1 1 1 — ëþáîé âåêòîð èç íàáîðà ñîáñòâåííûõ
âåêòîðîâ ìàòðèöû A u( , )* *� , ñîîòâåòñòâóþùèõ åå íóëåâûì ñîáñòâåííûì ÷èñ-
ëàì, à sxik
— åãî êîîðäèíàòà, ñîîòâåòñòâóþùàÿ ïåðåìåííîé xik . Èíûìè ñëîâà-
ìè, ñ ó÷åòîì òîãî, ÷òî ñîáñòâåííîå ÷èñëî ðàâíî íóëþ, s ïðåäñòàâëÿåò ïðîèç-
âîëüíûé íîðìèðîâàííûé âåêòîð, ïðèíàäëåæàùèé îðòîãîíàëüíîìó äîïîëíåíèþ
ê ïîäïðîñòðàíñòâó conv l nl( , , )� �1 .
Îïðåäåëèì âåêòîð s Ri j nm( , ) � �1 ñëåäóþùèì îáðàçîì: ( )nm n� �1 2 åãî êîì-
ïîíåíò ðàâíû íóëþ, è òîëüêî êîìïîíåíòû, ñîîòâåòñòâóþùèå ~xik è ~x jk , k n�1, ,
ðàâíû
1
2n
è �
1
2n
ñîîòâåòñòâåííî. Ðàññìîòðèì íàáîð âåêòîðîâ, ñîñòîÿùèé èç m
âåêòîðîâ S s i j mi j= { ( , ) , }1�
� è âåêòîðà s nm
0 10� ( , )T (íåíóëåâàÿ êîîðäèíàòà
ñîîòâåòñòâóåò ïåðåìåííîé z). Äëÿ ýòîãî íàáîðà ëåãêî ïðîâåðèòü, ÷òî:
— âñå âåêòîðû íîðìèðîâàíû (|| ||s0 1� , || ||( , )s i j �1 � �s Si j( , ) ) è ïðèíàäëå-
æàò îðòîãîíàëüíîìó äîïîëíåíèþ ê conv l nl( , , )� �1 (( , )( , )s i j
l� � 0 � �s Si j( , ) ,
( , )s l
0 0� � , l n�1, );
— âåêòîð p i j( , ) , âû÷èñëåííûé äëÿ s Si j( , ) � ïî ôîðìóëàì (18), èìååò âñå íó-
ëåâûå êîìïîíåíòû, êðîìå p
nu
i j
k
n
ij
( , ) � �
�
�
�
�
�
� � �
�
2
2
1
, p
nu
i j
k
n
li
( , ) � �
�
�
�
�
�
� � �
�
1
2
1
21
,
1�
l i , p
u
i j
il
( , ) � �
1
2
, i l m
� , l j� , p
u
i j
lj
( , ) � �
1
2
, 1�
l j , l i� , p
u
i j
jl
( , ) � �
1
2
,
j l n
� , p p
nik jk
i j i j
� �
( , ) ( , )� �
1
2
, k n�1, ;
— êîìïîíåíòû âåêòîðà p0 , âû÷èñëåííîãî äëÿ s0 ïî ôîðìóëàì (18), ðàâíû
p e
u m m
0
1 24� �( )/ , p mn�
0 0� .
Ðàññìîòðèì ëèíåéíóþ êîìáèíàöèþ p p p
i j
p S
i j
� �
�
� 0 ( , )
( , )
. Ïîñêîëüêó
pu
i j
p S
i j
( , )
( , )�
� � �
��
�
�
�
�
� �2
2
2
1 2
m
em m( )/ è p
m
n
ei j
p S
mn
i j
�
( , )
( , )�
�
�1
2
, òî ïðè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 4 175
� � �
��
�
�
�
�
�
1
4
2
2
2
m
ñïðàâåäëèâî
� � � �
�
�
�
�
�u u u u
i j
p S
ij ij ij iji j
u N p N p p( , )* * ( , )
( , )
� � � � 0
�
�
�
�
�
� 0 �� ,
� � � � ��� �
� �
ik ik
u N p( , )* * 1 0 ïðè � �
��
�
�
�
�
�
�
m
n
N
1
2
1
.
Èòàê, â òî÷êå ( , )
( )
,
( )
* *
( )/u
m ò
e
ò
em m mn� � �
�
�
�
�
�
��
�
�
���
1
2 1
1
2 1
1 2 , âíóòðåííåé
òî÷êå äîïóñòèìîãî ìíîæåñòâà çàäà÷è (17) (u*
0), ñïðàâåäëèâî âêëþ÷åíèå
0�� � �� �( , ) { ( , )}* * * *u u� �conv , ò.å. îíà ÿâëÿåòñÿ òî÷êîé ìèíèìóìà âûïóêëîé
çàäà÷è (17); çíà÷åíèå ìèíèìèçèðóåìîé ôóíêöèè �( , )u � â ýòîé òî÷êå ðàâíî
�( , )
( )
* * *u
mn
m
ik
k
n
i
m
� �� � �
���
11 2 1
.
Òàêèì îáðàçîì, ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå 2. Äâîéñòâåííàÿ îöåíêà çàäà÷è (10)–(12) ðàâíà � *
( )
�
�
mn
m2 1
.
Ñëåäñòâèå 1. Êâàäðàò ðàññòîÿíèÿ ìåæäó òî÷êàìè â çàäà÷å î ðàçìåùåíèè m
òî÷åê â åäèíè÷íîì êóáå â n-ìåðíîì ïðîñòðàíñòâå íå ïðåâûøàåò
mn
m2 1( )�
.
Îòñþäà, êàê ÷àñòíûé ñëó÷àé, ñëåäóåò ñïðàâåäëèâîñòü ïðåäïîëîæåíèÿ [10],
÷òî ïðè n � 2 èìååì � * � �
�
1
1
1m
.
Ñëåäñòâèå 2. Ðàäèóñ øàðîâ â çàäà÷å óïàêîâêè m îäèíàêîâûõ øàðîâ â n-ìåð-
íûé åäèíè÷íûé êóá íå ïðåâûøàåò
r
mn
m mn
�
� �2 2 1( ( ) )
. (19)
Ýòî ñëåäñòâèå ïîëó÷àåòñÿ ïðÿìîé ïîäñòàíîâêîé îöåíêè � * *
( )
�
�
�
mn
m
d
2 1
â ñîîòíîøåíèå (7) ñâÿçè ìåæäó ïåðåìåííûìè ðîäñòâåííûõ çàäà÷ (óïàêîâêè øà-
ðîâ â êóá è çàäà÷è î ðàçìåùåíèè òî÷åê â êóáå).
ÀÍÀËÈÇ ÏÎËÓ×ÅÍÍÎÉ ÄÂÎÉÑÒÂÅÍÍÎÉ ÎÖÅÍÊÈ
Îáîñíîâàííàÿ âûøå îöåíêà � *
( )
�
�
mn
m2 1
(óòâåðæäåíèå 2) ïðè m � �� ñòðåìèòñÿ
ê
n
2
, è ñîîòâåòñòâåííî âåðõíÿÿ îöåíêà äëÿ ðàäèóñà r
mn
m mn
�
� �2 2 1( ( ) )
ñòðå-
ìèòñÿ ê
n
n2 2( )�
(èç ñëåäñòâèÿ 2). Ýòîò ðåçóëüòàò óñòóïàåò ýëåìåíòàðíîé îöåí-
êå, êîòîðàÿ ñëåäóåò èç îãðàíè÷åííîñòè ñóììû îáúåìîâ øàðîâ îáúåìîì êîíòåéíåðà
V S y r Vi
n
i
m
( ( , )) ([ , ] )�
�
0 1
1
,
÷òî ýêâèâàëåíòíî Ñ rn
n
i
m
�
�
1
1 (Ñ
n
n
n
�
�
�
�
�
�
�
�
/2
2
1�
, �( )x — ãàììà-ôóíêöèÿ), îòêóäà
r
mÑn
n
�
�
�
��
�
�
��
1
1/
. (20)
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 4
Íàïðèìåð, äëÿ äâóõìåðíîãî ïðîñòðàíñòâà èç âûðàæåíèÿ (20) ïîëó÷àåì îöåíêó
r m� �( ) / 1 2 , êîòîðàÿ ïðè m � �� ñòðåìèòñÿ ê íóëþ, è óæå ïðè m � 5 ëó÷øå îöåí-
êè (19). Ñðàâíèòü êà÷åñòâî ýòèõ îöåíîê ìîæíî ñ ïîìîùüþ ðèñ. 1, ãäå ïîêàçàíû ãðà-
ôèêè çàâèñèìîñòè âåðõíèõ îöåíîê ðàäèóñà r øàðîâ îò èõ êîëè÷åñòâà m â çàäà÷å îá
óïàêîâêå â åäèíè÷íûé êóá â äâóõìåðíîì ïðîñòðàíñòâå. Çäåñü êðèâàÿ Opt ñîîòâåò-
ñòâóåò èçâåñòíûì îïòèìàëüíûì çíà÷åíèÿì (http://www.packomania.com/); DE —
äâîéñòâåííîé îöåíêå (19) äëÿ çàäà÷è (10)–(12); Vol — îöåíêå (20), òîæäåñòâåí-
íîé óñëîâèþ, ÷òî ñóììà îáúåìîâ øàðîâ ìåíüøå îáúåìà êîíòåéíåðà.
Èç îïèñàííîãî âûøå ñëåäóåò íåîáõîäèìîñòü óëó÷øåíèÿ îöåíêè äëÿ çàäà÷è
(4)–(6). Ýòîãî ìîæíî äîñòè÷ü, íàïðèìåð, ïóòåì ýâðèñòè÷åñêîãî «óòî÷íåíèÿ» çà-
äà÷è (ôàêòè÷åñêè, äðóãàÿ çàäà÷à). Òàê, â [10] äëÿ ñëó÷àÿ äâóõìåðíîãî ïðîñòðà-
íñòâà ïðåäëîæåíî ñóçèòü îáëàñòü îïðåäåëåíèÿ çàäà÷è, èñõîäÿ èç ñèììåòðèè, çà-
ìåíèâ îãðàíè÷åíèÿ (6) íà
0 5 11. � �xi , i m�1 1, , � m m1 2� / ; 0 5 12. � �xi , i m�1 2, , � m m2 1 2� / . (21)
Ïîäîáíûå èçìåíåíèÿ ïîñòàíîâêè çàäà÷è, õîòÿ è óòî÷íÿþò äâîéñòâåííóþ
îöåíêó (â [10] ïðåäïîëàãàåòñÿ, ÷òî äëÿ m � 5 SDP-îöåíêà çàäà÷è (4), (5), (21) ðàâ-
íà
! "
1
4
1
1
1 4
�
�
�
�
�
�
�
�
�
�( ) /m
), êà÷åñòâåííî íè÷åãî íå ìåíÿþò.
Äðóãîé ïóòü óëó÷øåíèÿ îöåíêè äëÿ èñõîäíîé çàäà÷è — ðàñøèðåíèå çàäà-
÷è (4)–(6) ðàçëè÷íûìè ñåìåéñòâàìè ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé,
÷òî ìîæåò ïðèâåñòè ê óëó÷øåíèþ äâîéñòâåííîé îöåíêè ïîëó÷åííîé êâàäðàòè÷-
íîé ïîñòàíîâêè.
Ïðè ÷èñëåííûõ ýêñïåðèìåíòàõ äëÿ äâóõ- è òðåõìåðíîãî ïðîñòðàíñòâà ïðè äîáàâ-
ëåíèè êâàäðàòè÷íûõ îãðàíè÷åíèé, ñîîòâåòñòâóþùèõ êàê RLT-íåðàâåíñòâàì, òàê è íå-
ðàâåíñòâàì «òðåóãîëüíèêîâ», ëàãðàíæåâà äâîéñòâåííàÿ îöåíêà íå ìåíÿëàñü, ÷òî ñî-
ãëàñóåòñÿ ñ âû÷èñëèòåëüíûìè ðåçóëüòàòàìè äëÿ SDP-ðåëàêñàöèè [10, 19]. Îòìåòèì,
÷òî ñ òî÷êè çðåíèÿ ðàññìîòðåííûõ Í.Ç. Øîðîì â [4, 5] ñïîñîáîâ ïîñòðîåíèÿ ôóíêöèî-
íàëüíî èçáûòî÷íûõ îãðàíè÷åíèé ïåðâûå ÿâëÿþòñÿ ðåçóëüòàòîì ïîïàðíûõ ïðîèçâåäå-
íèé ëèíåéíûõ îãðàíè÷åíèé (6) (íàïðèìåð, èç ( )( )1 0 0� � �x xi j ñëåäóåò x x xi j j� , èç
( )( )1 1 0� � �x xi j ñëåäóåò x x x xi j i j� � �1), à âòîðûå — ðåçóëüòàòîì ñóìì òðîéíûõ
ïðîèçâåäåíèé óêàçàííûõ ëèíåéíûõ îãðàíè÷åíèé (6) (íàïðèìåð, èç ñóììû
( )( )( )x x xi j k� � � �0 0 0 0 è ( )( )( )1 1 1 0� � � �x x xi j k ñëåäóåò x x x x xi j k i j� � � �
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 4 177
0,00
0,05
0,10
0,15
0,20
0,25
0,30
0,35
0,40
0,45
2 3 4 5 6 7 8 9 10 20 30 50
Opt
DE
Vol
Ðèñ. 1. Ãðàôèêè çàâèñèìîñòè âåðõíèõ îöåíîê ðàäèóñà r øàðîâ îò èõ êîëè÷åñòâà m â çàäà÷å îá
óïàêîâêå â åäèíè÷íûé êóá â äâóõìåðíîì ïðîñòðàíñòâå
r
m
� � �x x x xi k j k 1, èç ñóììû ( )( )( )1 0 0 0� � � �x x xi j k è ( )( )( )x x xi j k� � � �0 1 1 0
ñëåäóåò x x x x x x xi j i k i j k� � � ). Ïîñëåäíèé ñïîñîá ïîñòðîåíèÿ íå îãðàíè÷èâàåòñÿ
íåðàâåíñòâàìè «òðåóãîëüíèêîâ», ò.å. ïîíÿòíî, ÷òî êâàäðàòè÷íûå îãðàíè÷åíèÿ, ñîîò-
âåòñòâóþùèå RLT-íåðàâåíñòâàì, òàêæå ïîëó÷àþòñÿ èç òðîéíûõ ïðîèçâåäåíèé, òàê
êàê èç íèõ ñëåäóþò äâîéíûå ïðîèçâåäåíèÿ (íàïðèìåð, èç ñóììû
( )( )( )x x xi j k� � � �0 1 1 0 è ( )( )( )1 1 1 0� � � �x x xi j k ñëåäóåò ( )( )1 1 0� � �x xj k ,
à çíà÷èò, è x x x xj k j k� � �1).
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå äëÿ íàõîæäåíèÿ âåðõíåé îöåíêè ðàäèóñà øàðîâ â çàäà÷å óïàêîâêè
îäèíàêîâûõ øàðîâ â êóá ïðèìåíåí äâîéñòâåííûé ïîäõîä [4, 5] ê ñîîòâå-
òñòâóþùåé êâàäðàòè÷íîé ïîñòàíîâêå çàäà÷è. Ïîëó÷åíî àíàëèòè÷åñêîå âûðàæå-
íèå (â âèäå ôóíêöèè îò êîëè÷åñòâà øàðîâ m è ðàçìåðíîñòè ïðîñòðàíñòâà
n (ñì. óòâåðæäåíèå 2)) äëÿ äâîéñòâåííîé îöåíêè îïòèìàëüíîãî çíà÷åíèÿ öåëå-
âîé ôóíêöèè ìíîãîýêñòðåìàëüíîé êâàäðàòè÷íîé çàäà÷è (10)–(12), êîòîðîå ïîä-
òâåðæäàåò ñôîðìóëèðîâàííîå â [10] ïðåäïîëîæåíèå äëÿ ÷àñòíîãî ñëó÷àÿ ýòîé
îöåíêè ïðè n � 2 . Ðàñøèðåíèå çàäà÷è (10)–(12) çà ñ÷åò äîïîëíèòåëüíûõ (ôóíê-
öèîíàëüíî èçáûòî÷íûõ) êâàäðàòè÷íûõ îãðàíè÷åíèé, ñîîòâåòñòâóþùèõ êàê
RLT-íåðàâåíñòâàì, òàê è íåðàâåíñòâàì «òðåóãîëüíèêîâ», íå èçìåíèëî îöåíêè.
Îäíàêî ìíîãîâàðèàíòíîñòü âûáîðà ôóíêöèîíàëüíî èçáûòî÷íûõ îãðàíè÷åíèé
ïîçâîëÿåò îïòèìèñòè÷íî îöåíèâàòü âîçìîæíîñòü óëó÷øåíèÿ äâîéñòâåííîé îöåí-
êè (âîçìîæíî, äàæå ïîëó÷åíèÿ òî÷íîé). Íàïðèìåð, äëÿ êâàäðàòè÷íîé çàäà÷è îá-
ùåãî âèäà (8) â êà÷åñòâå äîïîëíèòåëüíûõ îãðàíè÷åíèé ìîæíî âûáðàòü îãðàíè-
÷åíèÿ âèäà f x P xi ( )* ( ) � 0 äëÿ ëþáîãî i I EQ� è ïðîèçâîëüíîãî ïîëèíîìà P x( )
èëè âèäà f x P xi ( )* ( ) � 0 äëÿ ëþáîãî i I LE� è ïðîèçâîëüíîãî ïîëèíîìà P x( ),
êîòîðûé ïðèíèìàåò íåîòðèöàòåëüíûå çíà÷åíèÿ íà äîïóñòèìîé îáëàñòè çàäà÷è (8).
Ïðè ýòîì äëÿ ïðèâåäåíèÿ ïîëèíîìèàëüíûõ îãðàíè÷åíèé ê êâàäðàòè÷íîìó âèäó ïî-
íàäîáÿòñÿ íîâûå ïåðåìåííûå R R Ri j k( ) ( ) ( )( ) ( ) ( )� � �� , � � �( ) ( ) ( )i j k� � (íåîò-
ðèöàòåëüíûé öåëî÷èñëåííûé âåêòîð � � � � �( ) ( ) ( ) ( )( , , , )r r r
n
r� �
1 2
�
T îïðåäåëÿåò
ïåðåìåííóþ R r( )( )� , êîòîðîé â èñõîäíîì ïðîñòðàíñòâå �n ñîîòâåòñòâóåò ìîíîì
R x x xr
n
r r
n
r
( )( )
( ) ( ) ( )
�
� � ��
1 2
1 2
� ) è ñâÿçûâàþùèå èõ îãðàíè÷åíèÿ R Ri j( ) ( )( ) ( )� � �
� �R Rk l( ) ( )( ) ( )� � 0 ïðè � � � �( ) ( ) ( ) ( )i j k l� � � (äëÿ ó÷åòà íåîäíîçíà÷íîñòè
ïðåäñòàâëåíèÿ ìîíîìà x x x
r r
n
r
n1 2
1 2
� � �
( ) ( ) ( )
� , � � � � �( ) ( ) ( ) ( ) ( )r i j k l� � � � â íîâîì
ïðîñòðàíñòâå ïåðåìåííûõ).  êà÷åñòâå ïðèìåðà âîçìîæíûõ äîïîëíèòåëüíûõ
îãðàíè÷åíèé ïðèâåäåì îãðàíè÷åíèÿ f x f xi j( )* ( ) � 0 (i I EQ� ), f x f xi j( )* ( ) � 0 (
i j I LE, � ), f x f xi ( )* ( )0 0� (i I EQ� ), f x f xi ( )* ( )0 0� (i I LE� è f * � 0),
f x f xi
2
0 0( )* ( ) � ( )i I EQ� , f x f xi ( )* ( )
0
2 0� (i I LE� ), f x f xi ( )* ( )� �0 0
(i I EQ� ) è ìíîãèå äðóãèå. Îòìåòèì, ÷òî ââåäåíèå íîâûõ «ìîíîìíûõ» ïåðåìåí-
íûõ è ñâÿçûâàþùèõ èõ ðàâåíñòâ ñàìî ïî ñåáå ÿâëÿåòñÿ ýôôåêòèâíûì ñðåäñòâîì
óëó÷øåíèÿ îöåíêè.
 çàêëþ÷åíèå ïîä÷åðêíåì, ÷òî èñïîëüçîâàíèå ôóíêöèîíàëüíî èçáûòî÷íûõ
îãðàíè÷åíèé äëÿ óòî÷íåíèÿ äâîéñòâåííûõ êâàäðàòè÷íûõ îöåíîê ÿâëÿåòñÿ äîñòà-
òî÷íî èíòåðåñíûì è ïåðñïåêòèâíûì (âïðî÷åì, êàê è äëÿ SDP-ðåëàêñàöèé, ÷òî
ïîäòâåðæäàåòñÿ ìíîæåñòâîì ïóáëèêàöèé). Îäíàêî ïðè ýòîì ïîâûøàåòñÿ çíà÷è-
ìîñòü ðåøåíèÿ ñëåäóþùèõ âîïðîñîâ: îïðåäåëåíèå ïðàâèëà ãåíåðàöèè ôóíêöèî-
íàëüíî èçáûòî÷íûõ îãðàíè÷åíèé (ñ òî÷êè çðåíèÿ îïòèìàëüíîñòè èõ âûáîðà),
òî÷íîñòü ïîëó÷àåìîé äâîéñòâåííîé îöåíêè è ò.ï.
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 4
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ã è ë ü á å ð ò Ä . , Ê î í - Ô î ñ ñ å í Ñ . Íàãëÿäíàÿ ãåîìåòðèÿ. — 3-å èçä. — Ì.: Íàóêà, 1981. —
302 c.
2. Ñ ë î ý í Í . Ä æ . À . Óïàêîâêà øàðîâ // Â ìèðå íàóêè. — 1984. — ¹ 3. — Ñ. 72–82.
3. C o n w a y J . H . , S l o a n e N . J . A . Sphere packings, lattices and groups (sec. ed.). — New York:
Springer-Verlag, 1993. — 679 p.
4. Ø î ð Í . Ç . , Ñ ò å ö å í ê î Ñ . È . Êâàäðàòè÷íûå ýêñòðåìàëüíûå çàäà÷è è íåäèôôåðåíöèðóåìàÿ
îïòèìèçàöèÿ. — Êèåâ: Íàóê. äóìêà, 1989. — 208 ñ.
5. S h o r N . Z . Nondifferentiable optimization and polynomial problems. — Dordrecht: Kluwer,
1998. — 394 p.
6. M a r a n a s C . D . , F l o u d a s C . A . , P a r d a l o s P . M . New results in the packing of equal circles
in a square // Discrete Math. — 1995. — 142. — P. 287–293.
7. L o c a t e l l i M . , R a b e r U . Packing equal circles in a square: a deterministic global optimization
approach // Discrete Appl. Math. — 2002. — 122. — P. 139–166.
8. S z a r o P . G . , M a r k o t M . C . , C s e n d e s T . Global optimization in geometry — circle packing
into the square // Essays and surveys in global optimization / C. Audel, P. Hancen, G. Savard
(Eds). — Dordrecht: Kluver, 2005. — P. 233–266.
9. M h a n d H i f i a n d R y m M ’ H a l l a h . A literature review on circle and sphere packing problems:
Models and methodologies // Adv. Oper. Res. — 2009. — 22 p. (doi:10.1155/2009/150624).
10. A n s t r e i c h e r K . On convex relaxations for quadratically constrained quadratic programming //
Math. Program. — 2012. — N 136. — P. 233–251.
11. V a n d e r b e r g h e L . , B o y d S . Semidefinite programming // SIAM Rev. — 1996. — N 38. —
P. 49–95.
12. S h e r a l i H . D . , A d a m s W . P . A reformulation–linearization tecchnique for solving discrete and
continuous nonconvex problems. — Dordrecht: Kluwer, 1998. — 516 p.
13. Y a j i m a Y . , F u j i e T . A polyhedral approach for nonconvex quadratic programming problems
with box constraints // J. Global Optim. — 1998. — N 13. — P. 151–170.
14. Á å ð å ç î â ñ ê è é Î . À . , Ñ ò å ö þ ê Ï . È . Îá îäíîì ñïîñîáå íàõîæäåíèÿ äâîéñòâåííûõ êâàä-
ðàòè÷íûõ îöåíîê Øîðà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2008. — ¹ 2. — Ñ. 89–99.
15. Á å ð å ç î â ñ ê è é Î . À . Î òî÷íîñòè äâîéñòâåííûõ îöåíîê äëÿ êâàäðàòè÷íûõ ýêñòðåìàëüíûõ çà-
äà÷ // Òàì æå. — 2012. — ¹ 1. — Ñ. 33–39.
16. F u j i t T . , K o j i m a M . Semidefinite programming relaxation for nonconvex quadratic problems //
J. Global Optim. — 1997. — N 10. — P. 367–380.
17. Ø î ð Í . Ç . , Á å ð å ç î â ñ ê è é Î . À . Íîâûå àëãîðèòìû ðåøåíèÿ çàäà÷è î ìàêñèìàëüíîì âçâå-
øåííîì ðàçðåçå ãðàôà // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1995. — ¹ 2. — Ñ. 100–106.
18. Ï ø å í è ÷ í û é Á . Í . Ìåòîä ëèíåàðèçàöèè. — Ì.: Íàóêà, 1983. — 136 ñ.
19. A n s t r e i c h e r K . Semidefinite programming upsilon ersus the reformulation–linearization techni-
que for nonconvex problems // J. Global Optim. — 2009. — N 43. — P. 471–484.
Ïîñòóïèëà 10.09.2013
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 4 179
|