Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы
Рассмотрен класс задач евклидовой комбинаторной оптимизации как задач дискретной оптимизации на множестве комбинаторных конфигураций, отображенном в арифметическое евклидово пространство. Дан обзор современных методов евклидовой комбинаторной оптимизации. Описаны свойства соответствующих образов ком...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2020 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/190377 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы / Ю.Г. Стоян, С.В. Яковлев // Кибернетика и системный анализ. — 2020. — Т. 56, № 3. — С. 30–46. — Бібліогр.: 119 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860246218181967872 |
|---|---|
| author | Стоян, Ю.Г. Яковлев, С.В. |
| author_facet | Стоян, Ю.Г. Яковлев, С.В. |
| citation_txt | Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы / Ю.Г. Стоян, С.В. Яковлев // Кибернетика и системный анализ. — 2020. — Т. 56, № 3. — С. 30–46. — Бібліогр.: 119 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Рассмотрен класс задач евклидовой комбинаторной оптимизации как задач дискретной оптимизации на множестве комбинаторных конфигураций, отображенном в арифметическое евклидово пространство. Дан обзор современных методов евклидовой комбинаторной оптимизации. Описаны свойства соответствующих образов комбинаторных множеств. Предложена теория непрерывных функциональных представлений и выпуклых продолжений для решения указанного класса задач. Отмечены области практического приложения и перспективные направления исследований.
Розглянуто клас задач евклідової комбінаторної оптимізації як задач дискретної оптимізації на множині комбінаторних конфігурацій, відображеній в арифметичний евклідів простір. Наведено огляд сучасних методів евклідової комбінаторної оптимізації. Описано властивості відповідних образів комбінаторних множин. Запропоновано теорію неперервних функціональних представлень і опуклих продовжень для розв'язання зазначеного класу задач. Визначено сфери практичного застосування та перспективні напрямки досліджень.
Euclidean combinatorial optimization problems are considered as discrete optimization problems on a set of combinatorial configurations mapped into an arithmetic Euclidean space. Modern methods of Euclidean combinatorial optimization are overviewed. The properties of the corresponding images of combinatorial sets are described. A theory of continuous functional representations and convex extensions is proposed for solving this class of problems. Areas of practical application and promising research areas are indicated.
|
| first_indexed | 2025-12-07T18:37:00Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Þ.Ã. ÑÒÎßÍ, Ñ.Â. ßÊÎÂËÅÂ
ÒÅÎÐÈß È ÌÅÒÎÄÛ ÅÂÊËÈÄÎÂÎÉ ÊÎÌÁÈÍÀÒÎÐÍÎÉ
ÎÏÒÈÌÈÇÀÖÈÈ: ÑÎÂÐÅÌÅÍÍÎÅ ÑÎÑÒÎßÍÈÅ È ÏÅÐÑÏÅÊÒÈÂÛ
Àííîòàöèÿ. Ðàññìîòðåí êëàññ çàäà÷ åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçà-
öèè êàê çàäà÷ äèñêðåòíîé îïòèìèçàöèè íà ìíîæåñòâå êîìáèíàòîðíûõ êîí-
ôèãóðàöèé, îòîáðàæåííîì â àðèôìåòè÷åñêîå åâêëèäîâî ïðîñòðàíñòâî. Äàí
îáçîð ñîâðåìåííûõ ìåòîäîâ åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè. Îïè-
ñàíû ñâîéñòâà ñîîòâåòñòâóþùèõ îáðàçîâ êîìáèíàòîðíûõ ìíîæåñòâ. Ïðåäëî-
æåíà òåîðèÿ íåïðåðûâíûõ ôóíêöèîíàëüíûõ ïðåäñòàâëåíèé è âûïóêëûõ ïðî-
äîëæåíèé äëÿ ðåøåíèÿ óêàçàííîãî êëàññà çàäà÷. Îòìå÷åíû îáëàñòè ïðàêòè-
÷åñêîãî ïðèëîæåíèÿ è ïåðñïåêòèâíûå íàïðàâëåíèÿ èññëåäîâàíèé.
Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ êîíôèãóðàöèÿ, åâêëèäîâî êîìáèíàòîðíîå
ìíîæåñòâî, åâêëèäîâû ìîäåëè, îïòèìèçàöèÿ.
Çàäà÷è êîìáèíàòîðíîé îïòèìèçàöèè ïðåäñòàâëÿþò èíòåðåñ äëÿ èññëåäîâàòå-
ëåé, ïîñêîëüêó ÿâëÿþòñÿ ìîäåëÿìè ðàçëè÷íûõ ïðèêëàäíûõ çàäà÷ ïðîåêòèðîâà-
íèÿ, ïëàíèðîâàíèÿ, ðàçìåùåíèÿ, óïðàâëåíèÿ. Â íàñòîÿùåå âðåìÿ èìååòñÿ áîëü-
øîå ÷èñëî ïóáëèêàöèé, ïîñâÿùåííûõ ìîäåëÿì è ìåòîäàì ðåøåíèÿ òàêèõ çà-
äà÷ è èõ êëàññèôèêàöèè [1–8]. Îäíèì èç ïðàêòè÷åñêè âàæíûõ êëàññîâ çàäà÷
êîìáèíàòîðíîé îïòèìèçàöèè ÿâëÿþòñÿ çàäà÷è åâêëèäîâîé êîìáèíàòîðíîé
îïòèìèçàöèè, âîçíèêàþùèå â ðåçóëüòàòå îòîáðàæåíèÿ êîìáèíàòîðíûõ ìíî-
æåñòâ â àðèôìåòè÷åñêîå åâêëèäîâî ïðîñòðàíñòâî. Ýòè çàäà÷è îáëàäàþò ðÿäîì
èíòåðåñíûõ ñâîéñòâ, ïîçâîëÿþùèõ ïðåäëîæèòü ýôôåêòèâíûå ìåòîäû äëÿ èõ
ðåøåíèÿ. Â äàííîé ñòàòüå ïðèâåäåí îáçîð ñóùåñòâóþùèõ ïîäõîäîâ ê ìîäåëè-
ðîâàíèþ çàäà÷ åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè, ìåòîäîâ ðåøåíèÿ,
à òàêæå óêàçàíà îáëàñòü èõ ïðèëîæåíèÿ è îïèñàíû ïåðñïåêòèâû äàëüíåéøèõ èñ-
ñëåäîâàíèé â ýòîì íàïðàâëåíèè.
ÅÂÊËÈÄÎÂÛ ÊÎÌÁÈÍÀÒÎÐÍÛÅ ÌÍÎÆÅÑÒÂÀ È ÇÀÄÀ×È ÅÂÊËÈÄÎÂÎÉ
ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Èññëåäîâàíèå çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè ïðåäïîëàãàåò, ñ îäíîé ñòîðî-
íû, àíàëèç îáëàñòè äîïóñòèìûõ ðåøåíèé, à ñ äðóãîé — èçó÷åíèå ñâîéñòâ
ôóíêöèé, çàäàííûõ íà ñîîòâåòñòâóþùèõ êîìáèíàòîðíûõ ìíîæåñòâàõ. Â ðàáî-
òàõ [9–11] âûäåëåí êëàññ òàê íàçûâàåìûõ åâêëèäîâûõ êîìáèíàòîðíûõ ìíî-
æåñòâ, ýëåìåíòàìè êîòîðûõ ÿâëÿþòñÿ óïîðÿäî÷åííûå íàáîðû èç íåêîòîðîãî
ìíîæåñòâà ïðîèçâîëüíîé ïðèðîäû.
Îïðåäåëåíèå åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ òåñíî ñâÿçàíî ñ ïîíÿòè-
åì êîìáèíàòîðíîé êîíôèãóðàöèè. Ïóñòü J N N� { }1, ,� . Ðàññìîòðèì êîíå÷íîå
àáñòðàêòíîå ñòðîãî óïîðÿäî÷åííîå ìíîæåñòâî � � �� { }1, ,� m .  ñîîòâåòñòâèè
ñ [12] ïîä êîìáèíàòîðíîé êîíôèãóðàöèåé � ��, ,� � ïîíèìàåòñÿ îòîáðàæåíèå
� :J N � � , óäîâëåòâîðÿþùåå çàäàííîìó íàáîðó îãðàíè÷åíèé �. Ìíîæåñòâî J N
íàçûâàþò íóìåðóþùèì, à ìíîæåñòâî � — îáðàçóþùèì (â íåêîòîðûõ èñòî÷íè-
êàõ — ðåçóëüòèðóþùèì). Çàìåòèì, ÷òî òðåáîâàíèÿ êîíå÷íîñòè è ñòðîãîé óïîðÿ-
äî÷åííîñòè îáðàçóþùåãî ìíîæåñòâà îáóñëîâëèâàþòñÿ, ïðåæäå âñåãî, çàäà÷àìè,
âîçíèêàþùèìè ïðè ïåðå÷èñëåíèè è ïîñòðîåíèè ðàçëè÷íûõ êîìáèíàòîðíûõ êîí-
ôèãóðàöèé [13]. Ïðè ïðåäïîëîæåíèè, ÷òî ìíîæåñòâî � íå áîëåå ÷åì ñ÷åòíî, â ðà-
áîòå [7] áûëî ââåäåíî ïîíÿòèå êîìáèíàòîðíîãî îáúåêòà, ÷òî ïîçâîëèëî çíà÷è-
30 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
� Þ.Ã. Ñòîÿí, Ñ.Â. ßêîâëåâ, 2020
òåëüíî ðàñøèðèòü êëàññ ðåøàåìûõ çàäà÷, è ïðåäëîæåíà ñõåìà ïîñòðîåíèÿ êîì-
áèíàòîðíûõ îáúåêòîâ áîëåå âûñîêîãî ïîðÿäêà èòåðàöèîííûì âêëþ÷åíèåì âî
ìíîæåñòâî � íîâûõ ôîðìèðóåìûõ îáúåêòîâ.
Òàêèì îáðàçîì, åâêëèäîâî êîìáèíàòîðíîå ìíîæåñòâî P ìîæíî ðàññìàòðè-
âàòü êàê ñîâîêóïíîñòü êîìáèíàòîðíûõ êîíôèãóðàöèé (îáúåêòîâ), ïðåäñòàâëÿþ-
ùèõ ñîáîé óïîðÿäî÷åííûå íàáîðû ýëåìåíòîâ îáðàçóþùåãî ìíîæåñòâà � , ò.å.
� � �� � �1, ,� N , ãäå � i � , i N J . Ó÷åò îñíîâíûõ ñâîéñòâ îòîáðàæåíèÿ
� :J N � � (áèåêòèâíîñòü, èíúåêòèâíîñòü, ñþðúåêòèâíîñòü), à òàêæå äîïîëíè-
òåëüíûõ òðåáîâàíèé, ôîðìèðóþùèõ ñèñòåìó îãðàíè÷åíèé �, ïîçâîëÿåò ôîðìè-
ðîâàòü ðàçëè÷íûå êëàññû åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ: ïåðåñòàíîâîê
(áåç ïîâòîðåíèé è ñ ïîâòîðåíèÿìè), öèêëè÷åñêèõ ïåðåñòàíîâîê, ÷åòíûõ ïåðåñòà-
íîâîê, ïåðåñòàíîâîê ñî çíàêîì, ðàçìåùåíèé (áåç ïîâòîðåíèé, ñ ïîâòîðåíèÿìè è
ñ áåñêîíå÷íûìè ïîâòîðåíèÿìè), ïåðåñòàíîâî÷íûõ ìàòðèö, áóëåâûõ ìíîæåñòâ, èõ
ñïåöèàëüíûõ ïîäìíîæåñòâ è ò.ä.
Âûäåëåíèå åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ â ñïåöèàëüíûé êëàññ îáîñíî-
âûâàåòñÿ ñïåöèôè÷åñêèìè ñâîéñòâàìè, ñâÿçàííûìè ñ âîçìîæíîñòüþ èõ áèåêòèâ-
íîãî îòîáðàæåíèÿ � íà íåêîòîðîå òî÷å÷íîå ïîäìíîæåñòâî E àðèôìåòè÷åñêîãî
åâêëèäîâà ïðîñòðàíñòâà îïðåäåëåííîé ðàçìåðíîñòè, ò.å.
� : P �
E R n . (1)
Ïðè ýòîì ëþáîé êîìáèíàòîðíîé êîíôèãóðàöèè � P áóäåò ñîîòâåòñòâîâàòü
òî÷êà x E òàêàÿ, ÷òî x � � �( ), � �� �1 ( )x .
Äëÿ òîãî ÷òîáû ïîä÷åðêíóòü, ÷òî òî÷êè ìíîæåñòâà E � �( )P ÿâëÿþòñÿ îáðà-
çàìè êîìáèíàòîðíûõ êîíôèãóðàöèé � P ïðè îòîáðàæåíèè (1), â [14] ââåäåíî
ïîíÿòèå åâêëèäîâîé êîìáèíàòîðíîé êîíôèãóðàöèè, êîòîðàÿ ïðåäñòàâëÿåòñÿ êîð-
òåæåì � �� �, , ,� � è çàäàåò îáðàç êîìáèíàòîðíîé êîíôèãóðàöèè � ��, ,� � â R n .
Íàçîâåì E � �( )P ìíîæåñòâîì åâêëèäîâûõ êîìáèíàòîðíûõ êîíôèãóðàöèé. Ïðè-
âåäåííûå ðàññóæäåíèÿ îáîáùàþòñÿ íà êîìáèíàòîðíûå îáúåêòû, ÷òî ïîçâîëÿåò
àíàëîãè÷íî îïðåäåëèòü ïîíÿòèå åâêëèäîâà êîìáèíàòîðíîãî îáúåêòà è ìíîæåñòâà
åâêëèäîâûõ êîìáèíàòîðíûõ îáúåêòîâ.
Âîïðîñ çàäàíèÿ îòîáðàæåíèÿ �:P � E âàæåí êàê ñ òåîðåòè÷åñêîé, òàê è
ñ ïðàêòè÷åñêîé òî÷åê çðåíèÿ, ïîñêîëüêó íåïîñðåäñòâåííî ñâÿçàí ñ àäåêâàòíîñ-
òüþ ìîäåëåé çàäà÷ íà ìíîæåñòâàõ P è Å. Òàê êàê ìíîæåñòâî P â îáùåì ñëó÷àå íå
áîëåå ÷åì ñ÷åòíî, îòîáðàæåíèå (1) ñóùåñòâóåò äëÿ ëþáîãî n � 1. Îñîáîå çíà÷åíèå
èìååò çàäàíèå îòîáðàæåíèÿ �, ïðè êîòîðîì ìíîæåñòâî E � �( )P èìååò ñïåöèàëü-
íóþ ñòðóêòóðó. Äëÿ êîíå÷íûõ òî÷å÷íûõ ìíîæåñòâ E R n
, ýòî, ïðåæäå âñåãî,
ñâÿçàíî ñî ñâîéñòâàìè âûïóêëûõ îáîëî÷åê (ìíîãîãðàííèêîâ)
� conv E. Â òî æå
âðåìÿ âñÿêîìó ýëåìåíòó � �j êîíå÷íîãî îáðàçóþùåãî ìíîæåñòâà � ìîæíî
ïîñòàâèòü â ñîîòâåòñòâèå óïîðÿäî÷åííûé íàáîð äåéñòâèòåëüíûõ ÷èñåë
a
j j
k
j k
a a R
j
j� ( , , )
1
� , ïîëîæèâ a
j
j j� � ( )� , j m J .
Çàäàäèì áèåêòèâíîå îòîáðàæåíèå �:P � E, ïîñòàâèâ êàæäîìó ýëåìåíòó
� P âèäà � � �� �1 1
, , , ,� �N j jN
� � , ji m J , i N J , â ñîîòâåòñòâèå òî÷êó
x x x x Rn
n� ( , , , )1 2 � ïî ñëåäóþùåìó ïðàâèëó. Ïóñòü K k
j
j
m
�
max
J
. Ïîëîæèì
x x x xn
i iN� �( , , , ) ( , , )1 2
1� �g g ,
ãäå g a
j j j
k
j Ka a R
j
� � ( , ) ( , , , , , )0
1
0 0� � , j m J , n NK� . Åñëè k Kj � äëÿ
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 31
íåêîòîðûõ j m J , òî g a
j j� . Çàìåòèì, ÷òî äîáàâëåíèå íóëåâûõ êîîðäèíàò
äëÿ âåêòîðîâ a
j , j m J , îáåñïå÷èâàåò áèåêòèâíîñòü ïðåäëîæåííîãî îòîáðàæå-
íèÿ â ñëó÷àå èõ ðàçëè÷íûõ ðàçìåðíîñòåé.
Ïðè K �1 èìååì n N� , x x x a an i in
� �( , , ) ( , , )1 1
� � , ãäå a j j j� � ( )� ,
j m J , — äåéñòâèòåëüíûå ÷èñëà. Åñëè ïðè ýòîì ýëåìåíòàìè îáðàçóþùåãî ìíî-
æåñòâà � òàêæå ÿâëÿþòñÿ äåéñòâèòåëüíûå ÷èñëà, òî ïîëàãàåì � j j j( )� �� , ò.å.
a j j� � , j m J . Îïèñàííûé ïîäõîä ê ôîðìàëèçàöèè îòîáðàæåíèÿ (1) íàçîâåì
ïîãðóæåíèåì åâêëèäîâà êîìáèíàòîðíîãî ìíîæåñòâà P â R n .
Êîìïëåêñíîìó èññëåäîâàíèþ ìíîæåñòâ åâêëèäîâûõ êîìáèíàòîðíûõ êîíôè-
ãóðàöèé ïîñâÿùåíà ìîíîãðàôèÿ [14]. Ïîëó÷åííûå â íåé ðåçóëüòàòû áàçèðóþòñÿ
íà ðàáîòàõ [9–11, 15–19], â êîòîðûõ îïèñàíû ñâîéñòâà ðàçëè÷íûõ êëàññîâ êîìáè-
íàòîðíûõ ìíîæåñòâ ïðè èõ ïîãðóæåíèè â R n . Ïðè ýòîì â êà÷åñòâå îáðàçóþùåãî,
êàê ïðàâèëî, ðàññìàòðèâàëîñü êîíå÷íîå ìíîæåñòâî äåéñòâèòåëüíûõ ÷èñåë.
Áîëåå ñëîæíûå åâêëèäîâû êîìáèíàòîðíûå êîíôèãóðàöèè, ïðåäñòàâëÿþùèå
êîìïîçèöèîííûå îáðàçû èñõîäíûõ ìíîæåñòâ, îïèñàíû â [20–22].
 äàëüíåéøåì, ÷òîáû ïîä÷åðêíóòü, ÷òî ðàññìàòðèâàåòñÿ îáðàç ñîîòâåòñòâó-
þùåãî êîìáèíàòîðíîãî ìíîæåñòâà, áóäåì äîáàâëÿòü îïðåäåëåíèå «åâêëèäîâî».
Îñîáîå çíà÷åíèå ïðè èññëåäîâàíèè ðàçëè÷íûõ êëàññîâ ìíîæåñòâ åâêëèäî-
âûõ êîìáèíàòîðíûõ êîíôèãóðàöèé èìååò èçó÷åíèå ñâîéñòâ êîìáèíàòîðíûõ ìíî-
ãîãðàííèêîâ êàê âûïóêëûõ îáîëî÷åê òî÷å÷íûõ ìíîæåñòâ E R n�
�( )P .
Àíàëèòè÷åñêèì ñïîñîáàì îïèñàíèÿ ìíîãîãðàííèêîâ äëÿ åâêëèäîâûõ ìíîæåñòâ
ïåðåñòàíîâîê è ðàçìåùåíèé, îïðåäåëåíèþ èõ ðàçìåðíîñòè, óñòàíîâëåíèþ êðèòå-
ðèåâ âåðøèí, ãðàíåé, ñìåæíîñòè âåðøèí è ãðàíåé, ìèíèìàëüíûì íåñâîäèìûì
ïðåäñòàâëåíèÿì ïîñâÿùåíû ðàáîòû [11, 14–19, 23, 24]. Îòìåòèì òàêæå ñòàòüè
[25, 26], â êîòîðûõ ðàññìàòðèâàþòñÿ îáùèå ïðèíöèïû èñïîëüçîâàíèÿ
ïîëèýäðàëüíîãî ïîäõîäà â çàäà÷àõ êîìáèíàòîðíîé îïòèìèçàöèè.
Ñôîðìóëèðóåì çàäà÷ó îïòèìèçàöèè íà åâêëèäîâîì êîìáèíàòîðíîì ìíî-
æåñòâå P â ñëåäóþùåé ïîñòàíîâêå. Ïóñòü çàäàí ôóíêöèîíàë F R: P � 1. Òðåáóåò-
ñÿ íàéòè
� �
�
* min ( )�
�
arg
P
F , (2)
ãäå � �P P — ìíîæåñòâî äîïóñòèìûõ ðåøåíèé.
Ïðåäïîëîæèì, ÷òî �: P � E — áèåêòèâíîå îòîáðàæåíèå òàêîå, ÷òî äëÿ íå-
êîòîðîé ôóíêöèè f E R: � 1 äëÿ âñåõ x E âûïîëíÿåòñÿ óñëîâèå
f x F x( ) ( ( ))� �� 1 . (3)
Òîãäà çàäà÷ó (2) ìîæíî ñôîðìóëèðîâàòü â ñëåäóþùåì âèäå: íàéòè
x f x
x E E
* min ( )�
�
arg
'
, (4)
ãäå E' '� �( )P — îáðàç ìíîæåñòâà P' â R n .
Çàäà÷ó (4) íàçîâåì çàäà÷åé åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè, à ìî-
äåëü, ïîñòðîåííóþ â ðåçóëüòàòå çàäàíèÿ áèåêòèâíîãî îòîáðàæåíèÿ �: P � E è
ôîðìèðîâàíèÿ ôóíêöèè f E R: � 1, óäîâëåòâîðÿþùåé óñëîâèþ (3), íàçîâåì
åâêëèäîâîé êîìáèíàòîðíîé ìîäåëüþ.
Ïîñòðîåíèå åâêëèäîâûõ êîìáèíàòîðíûõ ìîäåëåé èìååò òâîð÷åñêèé õàðàê-
òåð è çàâèñèò îò ðàññìàòðèâàåìîãî êëàññà çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè.
Íà÷àëî êîìïëåêñíûì èññëåäîâàíèÿì çàäà÷ åâêëèäîâîé êîìáèíàòîðíîé îïòèìè-
çàöèè ïîëîæåíî â ìîíîãðàôèè [11], ãäå âïåðâûå ðàññìàòðèâàëèñü ìîäåëè êîìáè-
32 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
íàòîðíûõ çàäà÷ â àðèôìåòè÷åñêîì åâêëèäîâîì ïðîñòðàíñòâå, à òàêæå áûëè ïðåä-
ëîæåíû ïîäõîäû ê ïîñòðîåíèþ áèåêòèâíîãî îòîáðàæåíèÿ �:P � E è ôîðìàëèçà-
öèè öåëåâûõ ôóíêöèé äëÿ íåêîòîðûõ îïòèìèçàöèîííûõ çàäà÷ ãåîìåòðè÷åñêîãî
ïðîåêòèðîâàíèÿ.
Çàäà÷è åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè â ñîîòâåòñòâèè ñ êëàññèôè-
êàöèåé, ïðèâåäåííîé â [6], ìîæíî ðàññìàòðèâàòü êàê ñïåöèàëüíûé êëàññ çàäà÷
äèñêðåòíîé îïòèìèçàöèè. Äëÿ ôîðìàëèçàöèè ýòîãî êëàññà íåîáõîäèìî ðåøèòü
äâå âçàèìîñâÿçàííûå çàäà÷è: çàäàòü áèåêòèâíîå îòîáðàæåíèå �:P �
E R n è
íàéòè ñîãëàñîâàííîå ñ íèì àíàëèòè÷åñêîå âûðàæåíèå äëÿ ôóíêöèè f E R: � 1,
óäîâëåòâîðÿþùåå óñëîâèþ (3).
Ñôîðìóëèðóåì çàäà÷ó (4) â ñëåäóþùåé ïîñòàíîâêå:
f x( ) min� , x X , (5)
ãäå ìíîæåñòâî X çàäàåòñÿ ñèñòåìîé îãðàíè÷åíèé
x E , (6)
g xi ( ) � 0, i k J , (7)
g xi ( ) � 0, i m k J J\ , (8)
à ôóíêöèè f x( ), g xi ( ), i m J , îïðåäåëåíû íà ìíîæåñòâå E ëèáî íà åãî
íåêîòîðîì íàäìíîæåñòâå
~
E E� .
Îãðàíè÷åíèÿ (6) íàçîâåì ïðÿìûìè, à (7), (8) — ôóíêöèîíàëüíûìè. Âûáîð
ôóíêöèîíàëüíûõ îãðàíè÷åíèé çàâèñèò îò ñâîéñòâ ìíîæåñòâà E. Ñâîéñòâà çàäà÷è
(5)–(8) îïðåäåëÿþòñÿ ñïîñîáîì îïèñàíèÿ ìíîæåñòâà X , à òàêæå ñâîéñòâàìè
ôóíêöèé f x g xi( ), ( ), i m J , íà E.  ÷àñòíîì ñëó÷àå ìîæíî ïîëîæèòü, ÷òî ïðÿ-
ìûå îãðàíè÷åíèÿ (6) îòñóòñòâóþò. Ïðè ýòîì âîçíèêàåò çàäà÷à ôóíêöèîíàëü-
íî-àíàëèòè÷åñêîãî ïðåäñòàâëåíèÿ êîíå÷íîãî ìíîæåñòâà E R n
, ò.å. åãî îïèñà-
íèÿ â âèäå ñèñòåìû óðàâíåíèé è íåðàâåíñòâ ñ ïîìîùüþ íåïðåðûâíûõ ôóíêöèé,
àíàëèòè÷åñêèé âèä êîòîðûõ èçâåñòåí. Ïîëó÷åííûå â ýòîì íàïðàâëåíèè ðåçóëüòà-
òû ïîñëóæèëè îñíîâîé òåîðèè íåïðåðûâíûõ ôóíêöèîíàëüíûõ ïðåäñòàâëåíèé
äëÿ îáðàçîâ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ, ïîëîæåíèÿ êîòîðîé íàøëè
îòðàæåíèå â ðàáîòàõ [27–34]. Îñîáîå âíèìàíèå â íèõ óäåëåíî êëàññèôèêàöèè
ôóíêöèîíàëüíûõ ïðåäñòàâëåíèé, à òàêæå ôóíêöèîíàëüíî-àíàëèòè÷åñêîìó ïðåä-
ñòàâëåíèþ òàê íàçûâàåìûõ âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâ [35, 36].
Êîíå÷íîå ìíîæåñòâî E R n
íàçîâåì âåðøèííî-ðàñïîëîæåííûì, åñëè îíî
ñîâïàäàåò ñ ìíîæåñòâîì âåðøèí ñâîåé âûïóêëîé îáîëî÷êè, ò.å. E E� vert conv .
Òàêèì îáðàçîì, âåðøèííî-ðàñïîëîæåííîå ìíîæåñòâî ìîæíî çàäàòü êàê ìíî-
æåñòâî âåðøèí âûïóêëîãî ìíîãîãðàííèêà
� convE. Èìåííî â òàêîì ïðåäñòàâ-
ëåíèè îíî âïåðâûå ââåäåíî â ðàáîòå [35].
Çàìåòèì, ÷òî òî÷êè âåðøèííî-ðàñïîëîæåííîãî ìíîæåñòâà E R n
, è òîëüêî
îíè, óäîâëåòâîðÿþò óñëîâèþ E �
�� , ãäå
� conv E, à � — îãðàíè÷åííàÿ
ñòðîãî âûïóêëàÿ ïîâåðõíîñòü ïðîñòðàíñòâà R n . Ýòî ñâîéñòâî íåïîñðåäñòâåííî
ñëåäóåò èç ñóùåñòâîâàíèÿ äëÿ ëþáîãî âûïóêëîãî ìíîãîãðàííèêà îãðàíè÷åííîé
ñòðîãî âûïóêëîé ïîâåðõíîñòè, ñîäåðæàùåé åãî âåðøèíû [37]. Òàêèì îáðàçîì,
ëþáîå âåðøèííî-ðàñïîëîæåííîå ìíîæåñòâî E R n
ïðåäñòàâèìî â âèäå ïåðåñå-
÷åíèÿ ìíîãîãðàííèêà è ñòðîãî âûïóêëîé ïîâåðõíîñòè. ×òîáû ïîä÷åðêíóòü ýòîò
ôàêò, â íåêîòîðûõ ðàáîòàõ, íàïðèìåð [29–31], èñïîëüçóåòñÿ ýêâèâàëåíòíîå
ïîíÿòèå ïîëèýäðàëüíî-ïîâåðõíîñòíîãî ìíîæåñòâà.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 33
Øèðîêèì êëàññîì âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâ ÿâëÿþòñÿ ïîëèýä-
ðàëüíî-ñôåðè÷åñêèå ìíîæåñòâà E R n
, äîïóñêàþùèå ïðåäñòàâëåíèå â âèäå ïåðå-
ñå÷åíèÿ ìíîãîãðàííèêà
� convE è îïèñàííîé ãèïåðñôåðû S S r� ( , ):�
| | | |x r� �� , ïàðàìåòðàìè êîòîðîé ÿâëÿåòñÿ ðàäèóñ r � 0 è êîîðäèíàòû öåíòðà
� � �� ( , , )1 � n . Íà÷àëî ñèñòåìàòè÷åñêèì èññëåäîâàíèÿì ïîëèýäðàëüíî-ñôåðè-
÷åñêèõ ìíîæåñòâ áûëî ïîëîæåíî â ñòàòüÿõ [38, 39] è íàøëî ïðîäîëæåíèå â ðàáî-
òàõ [40–45].
Íàèáîëåå èññëåäîâàííûé êëàññ ïîëèýäðàëüíî-ñôåðè÷åñêèõ ìíîæåñòâ —
åâêëèäîâû ìíîæåñòâà ïåðåñòàíîâîê [11, 14–18]. Äðóãèìè ïðèìåðàìè ïîëèýä-
ðàëüíî-ñôåðè÷åñêèõ ìíîæåñòâ ÿâëÿþòñÿ åâêëèäîâû ìíîæåñòâà öèêëè÷åñêèõ ïå-
ðåñòàíîâîê, ÷åòíûõ ïåðåñòàíîâîê, ïåðåñòàíîâîê ñî çíàêîì, à òàêæå ìíîæåñòâà
áîëåå ñëîæíîé ñòðóêòóðû [14, 21, 46–49].
Êëàññ âåðøèííî-ðàñïîëîæåííûõ è ïîëèýäðàëüíî-ñôåðè÷åñêèõ ìíîæåñòâ îá-
ëàäàåò òåì ñâîéñòâîì, ÷òî îïåðàöèè ïðÿìîãî ïðîèçâåäåíèÿ íå âûâîäÿò èõ èç
íåãî. Â ñâÿçè ñ ýòèì ïåðñïåêòèâíûì ïðåäñòàâëÿåòñÿ íàïðàâëåíèå, ñâÿçàííîå ñ ãå-
íåðàöèåé êîìáèíàòîðíûõ ìíîæåñòâ, ñîõðàíÿþùèõ ñâîè ñâîéñòâà [50].
ÒÅÎÐÈß ÂÛÏÓÊËÛÕ ÏÐÎÄÎËÆÅÍÈÉ
ÍÀ ÂÅÐØÈÍÍÎ-ÐÀÑÏÎËÎÆÅÍÍÛÕ ÌÍÎÆÅÑÒÂÀÕ
Âåðøèííàÿ ðàñïîëîæåííîñòü áîëüøèíñòâà åâêëèäîâûõ êîìáèíàòîðíûõ ìíî-
æåñòâ ïîçâîëÿåò ïðèìåíèòü ê ðåøåíèþ çàäà÷ åâêëèäîâîé êîìáèíàòîðíîé îïòè-
ìèçàöèè òåîðèþ âûïóêëûõ ïðîäîëæåíèé, îñíîâû êîòîðîé çàëîæåíû â ðàáîòàõ
[35, 36, 51–53]. Îñíîâíûå ïîëîæåíèÿ äàííîé òåîðèè áàçèðóþòñÿ íà ñëåäóþùèõ
ñâîéñòâàõ ôóíêöèé, çàäàííûõ íà âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâàõ.
Ïóñòü ìíîæåñòâî E R n
êîíå÷íî è E E� vert conv . Òîãäà äëÿ ëþáîé ôóíê-
öèè f E R: � 1 ñóùåñòâóåò òàêàÿ âûïóêëàÿ ôóíêöèÿ
~
:f E Rconv � 1, ÷òî
~
( ) ( )f x f x� äëÿ ëþáûõ x E . Äëÿ ôóíêöèé
~
( )f x , óäîâëåòâîðÿþùèõ òàêîìó óñëî-
âèþ íà ìíîæåñòâå E, áóäåì èñïîëüçîâàòü îáîçíà÷åíèå
~
( ) ( )f x f x
E
� . Íàçîâåì
~
( )f x
ïðîäîëæåíèåì ôóíêöèè f x( ) íà X . Åñëè ôóíêöèÿ
~
( )f x âûïóêëàÿ íà âûïóêëîì
ìíîæåñòâå X E� conv , òî íàçîâåì åå âûïóêëûì ïðîäîëæåíèåì f x( ) íà X . Åñëè
âûïóêëàÿ ôóíêöèÿ
~
( )f x äèôôåðåíöèðóåìà íà X , òî áóäåì ãîâîðèòü î äèôôåðåí-
öèðóåìîì âûïóêëîì (ñòðîãî, ñèëüíî âûïóêëîì) ïðîäîëæåíèè f x( ) íà X .
Äëÿ êëàññà ïîëèýäðàëüíî-ñôåðè÷åñêèõ ìíîæåñòâ ìîæíî ïðèìåíèòü ñëåäóþ-
ùèé ïîäõîä ê ïîñòðîåíèþ ñèëüíî âûïóêëîãî ïðîäîëæåíèÿ. Ïóñòü
~
( )f x — âû-
ïóêëîå ïðîäîëæåíèå íà âûïóêëîå ìíîæåñòâî X E� conv ôóíêöèè f x( ), çàäàí-
íîé íà ïîëèýäðàëüíî-ñôåðè÷åñêîì ìíîæåñòâå E. Òîãäà ñèëüíî âûïóêëîå ñ ïàðà-
ìåòðîì � � 0 ïðîäîëæåíèå ôóíêöèè f x( ) íà X ïðåäñòàâèìî â âèäå
� � �( )
~
( ) (| | | | )x f x x r� � � �2 2 ,
ãäå ( , )� r — ïàðàìåòðû ïîëèýäðàëüíî-ñôåðè÷åñêîãî ïðåäñòàâëåíèÿ ìíîæåñòâà E.
Óñèëåíèåì ïðèâåäåííûõ âûøå ðåçóëüòàòîâ ÿâëÿåòñÿ äîêàçàííàÿ â [35] òåî-
ðåìà î ñóùåñòâîâàíèè äèôôåðåíöèðóåìîãî ñèëüíî âûïóêëîãî ïðîäîëæåíèÿ
~
:f E Rconv � 1 äëÿ ëþáîé ôóíêöèè f E R: � 1.
Îñîáî îòìåòèì ïîñòðîåíèå âûïóêëûõ ïðîäîëæåíèé äëÿ êëàññà êâàäðàòè÷-
íûõ ôóíêöèé. Ïóñòü E R n
— ïîëèýäðàëüíî-ñôåðè÷åñêîå ìíîæåñòâî ñ ïàðà-
ìåòðàìè ( , )� r . Òîãäà âûïóêëûì ïðîäîëæåíèåì êâàäðàòè÷íîé ôóíêöèè f x( ) �
� �( , ) ( , )Cx x b x íà ïðîñòðàíñòâî R n áóäåò ôóíêöèÿ
~
( ) (
~
, ) (
~
, )
~
f x Cx x b x d� � � ,
34 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
ãäå C cij n n� �[ ] — ïðîèçâîëüíàÿ ñèììåòðè÷íàÿ n n� -ìàòðèöà, b — n-ìåðíûé
âåêòîð,
~
C Ñ I� � � , � � �
� �
� �| | | |
:
c cii
i c
ij
i jii 0
,
~
b b� �2��,
~
( )d r� �� �2 2 , I — åäè-
íè÷íàÿ ìàòðèöà.
Ïðèâåäåííûå ðåçóëüòàòû ïîñòóëèðóþò ñóùåñòâîâàíèå âûïóêëûõ, ñèëüíî
âûïóêëûõ è äèôôåðåíöèðóåìûõ ïðîäîëæåíèé äëÿ ïðîèçâîëüíûõ ôóíêöèé, çà-
äàííûõ íà âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâàõ. Ïðè ýòîì îñíîâíîé èíòåðåñ
ïðåäñòàâëÿþò ñïîñîáû ïîñòðîåíèÿ òàêèõ ïðîäîëæåíèé. Ðàññìîòðåíèå òîãî èëè
èíîãî êëàññà âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâ ïîçâîëÿåò êîíêðåòèçèðîâàòü,
à â íåêîòîðûõ ñëó÷àÿõ è îáîáùèòü ïðèâåäåííûå ðåçóëüòàòû.
Êîíñòðóêòèâíûé ïîäõîä ê ïîñòðîåíèþ âûïóêëîãî ïðîäîëæåíèÿ äëÿ ïîëèíî-
ìèàëüíûõ ôóíêöèé, çàäàííûõ íà åâêëèäîâîì ìíîæåñòâå ïåðåñòàíîâîê, âïåðâûå
îïèñàí â [35]. Â ðàáîòàõ [54, 55] ïðåäëîæåíû ìîäèôèêàöèè òàêîãî ïîäõîäà, ïî-
çâîëÿþùèå â íåêîòîðûõ ñëó÷àÿõ óïðîñòèòü âû÷èñëèòåëüíûå ïðîöåäóðû è óìåíü-
øèòü êîëè÷åñòâî íåîáõîäèìûõ îïåðàöèé ïðè åãî ðåàëèçàöèè.  ñòàòüå [40]
ïðèâåäåí àíàëèòè÷åñêèé âèä ãëàäêîãî âûïóêëîãî ïðîäîëæåíèÿ äëÿ ìîíîìîâ, çà-
äàííûõ íà ìíîæåñòâå ïåðåñòàíîâîê. Ýòîò ðåçóëüòàò ïîçâîëèë óòâåðæäàòü î ñó-
ùåñòâîâàíèè ãëàäêèõ âûïóêëûõ ïðîäîëæåíèé äëÿ ëþáûõ ôóíêöèé, çàäàííûõ íà
âåðøèíàõ ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà. Áîëåå òîãî, â áîëüøèíñòâå ñëó÷àåâ
ïîëó÷åííûå âûïóêëûå ïðîäîëæåíèÿ ñ ñîõðàíåíèåì âûðàæåíèÿ ìîæíî ðàñøè-
ðèòü íà âûïóêëûå íàäìíîæåñòâà X E� âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâ,
â ÷àñòíîñòè íà X R n� � . Îòìåòèì òàêæå ðàáîòû [44, 45], â êîòîðûõ ïðåäëàãàåòñÿ
ïîäõîä ê ïîñòðîåíèþ âûïóêëîãî äâàæäû äèôôåðåíöèðóåìîãî ïðîäîëæåíèÿ
~
( )f x
íà âûïóêëîå íàäìíîæåñòâî X S� conv äëÿ ôóíêöèè f x C R n( ) ( ) 2 , çàäàííîé íà
ãèïåðñôåðå S S r x r� � �( , ) : | | | |� � . Îäíàêî èñïîëüçîâàíèå òàêîãî ïîäõîäà îãðàíè÷è-
âàåòñÿ ñëîæíîñòüþ îïðåäåëåíèÿ ïàðàìåòðà M â ïðåäñòàâëåíèè
~
( ) ( )f x f x� �
� � �M x r(| | | | )� 2 2 .
Ñðåäè ïðèìåíåíèé òåîðèè âûïóêëîãî ïðîäîëæåíèÿ äëÿ äðóãèõ êëàññîâ
åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ îòìåòèì ðàáîòû [16, 31, 56–58].
ÌÅÒÎÄÛ ÅÂÊËÈÄÎÂÎÉ ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Îäíèì èç îñíîâíûõ ðåçóëüòàòîâ òåîðèè âûïóêëûõ ïðîäîëæåíèé ÿâëÿåòñÿ ïîä-
õîä ê ýêâèâàëåíòíîé ïîñòàíîâêå çàäà÷è îïòèìèçàöèè íà âåðøèííî-ðàñïîëî-
æåííûõ ìíîæåñòâàõ, ïðåäëîæåííûé â [35] è ôîðìàëèçîâàííûé â äàëüíåéøåì
â [36, 40]. Ðàññìîòðèì çàäà÷ó îïòèìèçàöèè (5)–(8) â ïðåäïîëîæåíèè, ÷òî E —
âåðøèííî-ðàñïîëîæåííîå ìíîæåñòâî. Ïðåäñòàâèì ðàâåíñòâà (8) â âèäå íåðà-
âåíñòâ è ïîñòðîèì âûïóêëûå ïðîäîëæåíèÿ èñõîäíûõ ôóíêöèé íà âûïóêëîå
ìíîæåñòâî X E� conv :
~
( ) ( )f x f x
E
� , (9)
~ ( ) ( ),g x g x ii
E
i m� J , (10)
~ ( ) ( ), \g x g x ii
E
i l r m� � � J J , (11)
ãäå r m k� �2 .
Ñ ó÷åòîì (9)–(11) ôîðìèðóåì îïòèìèçàöèîííóþ çàäà÷ó
~
( ) minf x � , x X
~
, (12)
ãäå ìíîæåñòâî
~
X çàäàåòñÿ ñèñòåìîé îãðàíè÷åíèé
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 35
x E E � vert conv , (13)
~ ( )g xi � 0, i r J , (14)
à ôóíêöèè
~
( ), ~ ( )f x g xi , i r J , âûïóêëû íà X .
Ýêâèâàëåíòíîñòü íà âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâàõ E èñõîäíûõ
ôóíêöèé è èõ âûïóêëûõ ïðîäîëæåíèé ïîçâîëÿåò ñôîðìóëèðîâàòü ñëåäóþùóþ
çàäà÷ó îïòèìèçàöèè íà âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâàõ, ýêâèâàëåíòíóþ
çàäà÷å (5)–(8).
Ïóñòü ìíîæåñòâî E R n
êîíå÷íî è E E� vert conv . Ñôîðìèðóåì ìíîæåñòâà
G x E g xi� �{ : ( ) 0, i k J , g xi ( ) � 0, i m k J J\ },
~
: ~ ( )G x E g xi� �{ 0, i r J }.
Òîãäà
arg argmin ( ) min
~
( )
~x G x G
f x f x
� . (15)
 ðàâåíñòâå (15) ìîæíî èñïîëüçîâàòü äèôôåðåíöèðóåìûå è ñèëüíî âûïóê-
ëûå ïðîäîëæåíèÿ ôóíêöèé
~
( ), ~ ( ),f x g x ii r J , íà ìíîæåñòâî
� convE, à òàêæå
íà åãî âûïóêëûå íàäìíîæåñòâà. ×àñòî ïîñòðîåííîå âûïóêëîå ïðîäîëæåíèå íà
ñ ñîõðàíåíèåì àíàëèòè÷åñêîãî âèäà ôóíêöèè ìîæåò áûòü ðàñøèðåíî íà íåêîòî-
ðîå âûïóêëîå ìíîæåñòâî X �
è äàæå íà âñå ïðîñòðàíñòâî R n .
Øèðîêèé êëàññ ìåòîäîâ ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòèìèçàöèè áàçèðóåòñÿ
íà ðàçëè÷íûõ ïîäõîäàõ ê äåêîìïîçèöèè èñõîäíîé çàäà÷è ñ ïðèìåíåíèåì òåîðèè
âûïóêëîãî ïðîãðàììèðîâàíèÿ ïðè ðåøåíèè âñïîìîãàòåëüíûõ çàäà÷ â ðàçëè÷íûõ
ñõåìàõ ãëîáàëüíîé îïòèìèçàöèè íà âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâàõ.
Ïóñòü E R n
— âåðøèííî-ðàñïîëîæåííîå ìíîæåñòâî. Î÷åâèäíî, ÷òî ëþ-
áîå ïîäìíîæåñòâî E E'
òàêæå ÿâëÿåòñÿ âåðøèííî-ðàñïîëîæåííûì. Ðàññìîò-
ðèì ñåìåéñòâî { }L ii k, J ìíîãîîáðàçèé ïðîñòðàíñòâà R n òàêèõ, ÷òî
E Ei
i k
�
J
� , E E Li i� � �� , E Ei j� � � � �i j i jm, ,J . (16)
Òàêèì îáðàçîì, ïðåäñòàâëåíèå (16) çàäàåò äåêîìïîçèöèþ âåðøèííî-ðàñïîëîæåííîãî
ìíîæåñòâà íà âåðøèííî-ðàñïîëîæåííûå ìíîæåñòâà { }E ii k, J ìåíüøåé ìîù-
íîñòè. Î÷åâèäíî, ÷òî ïðè ýòîì âîçíèêàåò âîïðîñ âûáîðà êàê ñàìèõ ìíîãîîá-
ðàçèé { }L ii k, J , òàê è èõ êîëè÷åñòâà. Íàèáîëåå ðàñïðîñòðàíåííûì ÿâëÿåòñÿ
ðàçëîæåíèå E R n
ïî ìíîæåñòâàì, ïðèíàäëåæàùèì ëèíåéíûì ìíîãîîáðàçè-
ÿì. Ïðåæäå âñåãî, ýòî îáóñëîâëåíî äîñòàòî÷íî ïðîñòûì ñïîñîáîì îïðåäåëåíèÿ
ñòðóêòóðû âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâ { }E ii k, J . Ðàçëè÷íûå ñïîñî-
áû ðàçëîæåíèÿ îáðàçîâ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ ïî ãèïåðïëîñ-
êîñòÿì îïèñàíû â [11, 14–17]. Îáùàÿ ñõåìà ðàçëîæåíèÿ ïîëèýäðàëüíî-ñôåðè-
÷åñêèõ ìíîæåñòâ ïî ñåìåéñòâó ãèïåðñôåð ïðåäëîæåíà â [38, 39, 59]. Çàìåòèì,
÷òî âñÿêîå òî÷å÷íîå ìíîæåñòâî E R n
ïðåäñòàâèìî êàê îáúåäèíåíèå âåðøèí-
íî-ðàñïîëîæåííûõ ìíîæåñòâ. Âîçìîæíîñòè ïðèëîæåíèÿ òàêèõ ðàçëîæåíèé ïðè
ëîêàëèçàöèè ðåøåíèé â çàäà÷àõ öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ îïèñàíû â [59].
Äåêîìïîçèöèîííûå ìåòîäû îïòèìèçàöèè òåñíî ñâÿçàíû ñ ðåøåíèåì ðåëàê-
ñàöèîííûõ çàäà÷ äëÿ îöåíêè ìèíèìóìîâ ôóíêöèè f x( ) íà ôîðìèðóåìûõ ïîä-
ìíîæåñòâàõ è èñïîëüçîâàíèåì ðàçëè÷íûõ ñõåì âåòâëåíèÿ òèïà ìåòîäîâ âåòâåé è
ãðàíèö [60] è ïîñëåäîâàòåëüíîãî àíàëèçà âàðèàíòîâ [61]. Ïðèìåíåíèå ìåòîäà
âåòâåé è ãðàíèö ïðè ðåøåíèè íåêîòîðûõ çàäà÷ åâêëèäîâîé êîìáèíàòîðíîé
îïòèìèçàöèè îïèñàíî â ðàáîòàõ [62–64].
36 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
Îñóùåñòâèì ðåëàêñàöèþ çàäà÷è (12)–(14). Äëÿ êëàññà âåðøèííî-ðàñïîëî-
æåííûõ ìíîæåñòâ ïðèìåíèì òðè ïîäõîäà ê ðåëàêñàöèè, îñëàáèâ óñëîâèå (13):
ïîëàãàÿ x E conv (ïîëèýäðàëüíàÿ ðåëàêñàöèÿ), x � (ïîâåðõíîñòíàÿ ðåëàêñàöèÿ)
ëèáî x conv� (âûïóêëàÿ ïîâåðõíîñòíàÿ ðåëàêñàöèÿ). Âî âñåõ ñëó÷àÿõ äëÿ ïðîèç-
âîëüíîé ôóíêöèè f x( ) è ïðîèçâîëüíûõ ôóíêöèîíàëüíûõ îãðàíè÷åíèé ðåøåíèå
íåïðåðûâíûõ ðåëàêñàöèîííûõ çàäà÷ ñóùåñòâåííî íå óïðîùàåòñÿ.
Ïðè ïîëèýäðàëüíîé è âûïóêëîé ïîâåðõíîñòíîé ðåëàêñàöèè âîñïîëüçóåìñÿ
îïèñàííûì âûøå ïîäõîäîì ê ïîñòðîåíèþ ýêâèâàëåíòíîé çàäà÷è îïòèìèçàöèè íà
âåðøèííî-ðàñïîëîæåííûõ ìíîæåñòâàõ.
Ñôîðìèðóåì îïòèìèçàöèîííóþ çàäà÷ó
~
( ) minf x � , x G
~
, (17)
ãäå
~
: ~ ( ) ,G x X g x ii r� � { }0 J , à ôóíêöèè
~
( ), ~ ( ),f x g x ii r J , âûïóêëû íà âû-
ïóêëîì ìíîæåñòâå X E� .
Çàäà÷à (17) âûïóêëàÿ, è åå ðåøåíèå ÿâëÿåòñÿ íèæíåé îöåíêîé ìèíèìóìà
ôóíêöèè f x( ) íà E.
 ñëó÷àå ïîëèýäðàëüíîé ðåëàêñàöèè ïîëîæèì X E� conv . Ïðè ýòîì ýôôåê-
òèâíîñòü ìåòîäîâ ðåøåíèÿ çàäà÷è (17) ñóùåñòâåííî çàâèñèò îò ñòðóêòóðû êîìáè-
íàòîðíîãî ìíîãîãðàííèêà. Äëÿ íåêîòîðûõ åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ
ìíîãîãðàííèê çàäàåòñÿ ïîëèíîìèàëüíûì îò ðàçìåðíîñòè çàäà÷è ÷èñëîì îãðàíè-
÷åíèé.  òî æå âðåìÿ ïåðåñòàíîâî÷íûé ìíîãîãðàííèê îïèñûâàåòñÿ êîëè÷åñòâîì
îãðàíè÷åíèé ïîðÿäêà 2n [17]. Îáîéòè ñâÿçàííûå ñ ýòèì çàòðóäíåíèÿ ïîçâîëÿåò
ïîäõîä, îñíîâíàÿ èäåÿ êîòîðîãî îïèñàíà â ðàáîòàõ [56, 65]. Â îñíîâó ïîëîæåíû
ñâîéñòâà çàäà÷è îïòèìèçàöèè ëèíåéíîé ôóíêöèè íà ïåðåñòàíîâî÷íîì ìíîãî-
ãðàííèêå Ï, ðåøåíèå êîòîðîé ñâîäèòñÿ ê óïîðÿäî÷åíèþ êîýôôèöèåíòîâ öåëåâîé
ôóíêöèè. Êðîìå òîãî, â [39, 51, 52] ðàññìîòðåíû ñïåöèàëüíûå êëàññû çàäà÷ êâàä-
ðàòè÷íîé îïòèìèçàöèè íà
, ñâîäèìûå ê ëèíåéíûì çàäà÷àì. Ýòî äàëî âîçìîæ-
íîñòü ýôôåêòèâíî èñïîëüçîâàòü ìåòîä óñëîâíîãî ãðàäèåíòà Ôðàíêà–Âóëôà è ìå-
òîä ïðîåêöèè ãðàäèåíòà äëÿ îïòèìèçàöèè íà
äèôôåðåíöèðóåìûõ âûïóêëûõ
ôóíêöèé.  îáùåì ñëó÷àå äëÿ ðåøåíèÿ çàäà÷è (17) â ðàáîòàõ [66, 67] ïðåäëàãàåò-
ñÿ ïðèìåíèòü ìåòîä óñëîâíîãî ãðàäèåíòà ñîâìåñòíî ñ ìåòîäîì øòðàôíûõ ôóíê-
öèé. Îäíàêî ïðè ýòîì çàìåäëÿåòñÿ ñêîðîñòü ñõîäèìîñòè òàêîãî ïîäõîäà.
Âîçìîæíîñòü îïèñàòü âåðøèííî-ðàñïîëîæåííîå ìíîæåñòâî E (à çíà÷èò,
è ñîîòâåòñòâóþùèé êîìáèíàòîðíûé ìíîãîãðàííèê
� convE) îãðàíè÷åííîé
ñòðîãî âûïóêëîé ïîâåðõíîñòüþ � ïîçâîëÿåò èñïîëüçîâàòü äëÿ íèæíåé îöåíêè
ìèíèìóìà f x( ) íà E ðåøåíèå çàäà÷è îïòèìèçàöèè (17) ïðè X � conv� . Î÷åâèä-
íî, ÷òî òàêàÿ îöåíêà áóäåò ñëàáåå, ÷åì ïðè X E� conv , îäíàêî ñòðóêòóðà îãðàíè-
÷åíèé çàäà÷è (17) íàìíîãî ïðîùå, ÷òî ïîçâîëÿåò ïðèìåíÿòü áîëåå ýôôåêòèâíûå
ìåòîäû âûïóêëîé îïòèìèçàöèè.
Ïðè ïîâåðõíîñòíîé ðåëàêñàöèè âîçíèêàåò çàäà÷à îïòèìèçàöèè âûïóêëîé
ôóíêöèè íà îãðàíè÷åííîé ñòðîãî âûïóêëîé ïîâåðõíîñòè.  îáùåì ñëó÷àå ýòà çà-
äà÷à ÿâëÿåòñÿ ìíîãîýêñòðåìàëüíîé. Íà ñåãîäíÿøíèé äåíü ýôôåêòèâíûå ìåòîäû
åå ðåøåíèÿ îòñóòñòâóþò.  òî æå âðåìÿ äëÿ êëàññà êâàäðàòè÷íûõ ôóíêöèé íà ïî-
ëèýäðàëüíî-ñôåðè÷åñêèõ ìíîæåñòâàõ â ðàáîòàõ [38, 39] ïðåäëîæåí ïîäõîä, îñíî-
âàííûé íà âîçìîæíîñòè òî÷íîãî ðåøåíèÿ çàäà÷è îïòèìèçàöèè êâàäðàòè÷íîé
ôóíêöèè íà ãèïåðñôåðå. Èçâåñòíî, ÷òî òàêàÿ çàäà÷à ñâîäèòñÿ ê íàõîæäåíèþ ñîá-
ñòâåííîãî âåêòîðà, ñîîòâåòñòâóþùåãî íàèìåíüøåìó ñîáñòâåííîìó çíà÷åíèþ
ìàòðèöû êâàäðàòè÷íîé ôîðìû. Óêàçàííûé ïîäõîä ðåàëèçîâàí äëÿ êâàäðàòè÷íîé
îïòèìèçàöèè íà ïîëèýäðàëüíî-ñôåðè÷åñêîì ìíîæåñòâå ïåðåñòàíîâîê áåç äîïîë-
íèòåëüíûõ îãðàíè÷åíèé. Äëÿ äåêîìïîçèöèè çàäà÷è èñïîëüçîâàëîñü ðàçëîæåíèå
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 37
âåðøèííî-ðàñïîëîæåííîãî ìíîæåñòâà êàê ïî ãèïåðïëîñêîñòÿì, òàê è ïî ãðàíÿì
è ðåáðàì ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà.
Çàìåòèì, ÷òî â çàäà÷àõ êâàäðàòè÷íîé îïòèìèçàöèè íà ñôåðè÷åñêèõ ìíî-
æåñòâàõ ïðè íàëè÷èè äîïîëíèòåëüíûõ ëèíåéíûõ ëèáî êâàäðàòè÷íûõ îãðàíè÷å-
íèé ìîæíî âîñïîëüçîâàòüñÿ îöåíêàìè èç ðàáîò [68, 69].
Ïðåäëîæåííûå âûøå ïîäõîäû ê ïîëó÷åíèþ íèæíåé îöåíêè ìèíèìóìà ïðî-
èçâîëüíîé ôóíêöèè, çàäàííîé íà âåðøèííî-ðàñïîëîæåííîì ìíîæåñòâå, ïîçâîëÿ-
þò, êàê ïðàâèëî, íàéòè è çíà÷åíèå àðãóìåíòà, ñîîòâåòñòâóþùåãî ýòîé îöåíêå.
 òàêîì ñëó÷àå ðàññìîòðåííóþ òåîðèþ âûïóêëûõ ïðîäîëæåíèé ìîæíî èñïîëü-
çîâàòü äëÿ óñèëåíèÿ óêàçàííûõ îöåíîê. Ýòîìó âîïðîñó ïîñâÿùåíû ðàáîòû
[35, 36, 51–53], îñíîâíûå ðåçóëüòàòû êîòîðûõ áàçèðóþòñÿ íà ýêñòðåìàëüíûõ
ñâîéñòâàõ âûïóêëûõ ôóíêöèé.
Ïðèâåäåì ñëåäóþùèå ðåçóëüòàòû, ïîëó÷åííûå ïðèìåíèòåëüíî ê âåðøèííî-ðàñ-
ïîëîæåííûì ìíîæåñòâàì ñ ó÷åòîì ñâîéñòâ âûïóêëûõ ïðîäîëæåíèé ôóíêöèé.
Ïóñòü E � vert
, ãäå
� convE, à ôóíêöèÿ
~
:f X R� 1 — âûïóêëîå ïðîäîë-
æåíèå ôóíêöèè f E R: � 1 íà âûïóêëîå ìíîæåñòâî X �
. Òîãäà äëÿ ëþáîãî
~x X èìååì
min ( ) (~ ) (
~
(~), ~ ) min (
~
(~), )
x E x
f x f x f x x f x x
� � �' '
. (18)
Äëÿ òîãî ÷òîáû x E* áûëà òî÷êîé ìèíèìóìà ôóíêöèè f x( ) íà ìíîæåñòâå E,
äîñòàòî÷íî, ÷òîáû äëÿ íåêîòîðîãî åå âûïóêëîãî ïðîäîëæåíèÿ
~
( )f x íà
èìåëî
ìåñòî ðàâåíñòâî
min (
~
( ), )* *
x
f x x x
� �
' 0.
Òî÷êó ~x ìîæíî âûáðàòü êàê ðåøåíèå çàäà÷è âûïóêëîãî ïðîãðàììèðîâàíèÿ
~ min
~
( )x f x
x
�
arg
. (19)
Äëÿ êëàññà êâàäðàòè÷íûõ ôóíêöèé f x( ), åñëè ðåøåíèå çàäà÷è (19) ÿâëÿåòñÿ
âíóòðåííåé òî÷êîé ìíîãîãðàííèêà
, ïîëîæèì
~ min
~
( )x f x
x S E
�
�
arg .
Ïóñòü ôóíêöèÿ
~
( )f x — ñèëüíî âûïóêëîå ñ ïàðàìåòðîì � � 0 ïðîäîëæåíèå
ôóíêöèè f x( ) íà
. Òîãäà
min ( )
~
( ) min | | | |* *
x E x E
f x f x x x
� � �� 2 , (20)
ãäå x * — ðåøåíèå çàäà÷è (19).
Êðîìå òîãî, äëÿ ëþáîãî ~x
èìååì
min ( )
~
(~) | |
~
(~ )| | min ~ ~
x E x E
f x f x f x x x
� � � � �
1
4
1
2
2
�
�
�
' f x' (~ )
2
. (21)
Êîíêðåòèçàöèÿ ïðèâåäåííûõ ðåçóëüòàòîâ äëÿ ïîëó÷åíèÿ íèæíåé îöåíêè ìè-
íèìóìà ôóíêöèè f x( ) íà E çàâèñèò îò êëàññà ðàññìàòðèâàåìûõ âåðøèííî-ðàñïî-
ëîæåííûõ ìíîæåñòâ. Ïðåæäå âñåãî, ýòî îáóñëîâëåíî âîçìîæíîñòüþ ðåøåíèÿ çà-
äà÷ ìèíèìèçàöèè â ïðàâûõ ÷àñòÿõ íåðàâåíñòâ (18), (20), (21). Òàê, äëÿ çàäà÷
îïòèìèçàöèè íà åâêëèäîâîì ìíîæåñòâå ïåðåñòàíîâîê óêàçàííûå çàäà÷è ïîëèíî-
ìèàëüíî ðàçðåøèìû, ÷òî ïîçâîëèëî ïîëó÷èòü íèæíèå îöåíêè, íåïîñðåäñòâåííî
èñïîëüçóÿ ÿâíûé âèä ýòèõ ðåøåíèé [35, 36, 52, 70]. Ïðè äîïîëíèòåëüíûõ
ëèíåéíûõ îãðàíè÷åíèÿõ ìîæíî ïðèìåíèòü ìåòîä, ïðåäëîæåííûé â [71].
38 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
 ïîñëåäíåå âðåìÿ èíòåíñèâíî ðàçâèâàåòñÿ íàïðàâëåíèå, ñâÿçàííîå
ñ èñïîëüçîâàíèåì ãåíåòè÷åñêèõ àëãîðèòìîâ ïðè ðåøåíèè çàäà÷ êîìáèíàòîðíîé
îïòèìèçàöèè [72, 73]. Â ðàáîòàõ [74, 75] ïðåäëîæåí îäèí èç ïîäõîäîâ ê ðåàëè-
çàöèè ãåíåòè÷åñêèõ àëãîðèòìîâ ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ íà åâêëèäîâîì
ìíîæåñòâå ïåðåñòàíîâîê, îïèñàíû ñïîñîáû ïîñòðîåíèÿ ñîîòâåòñòâóþùèõ îïåðà-
òîðîâ êðîññîâåðà è ìóòàöèè. Òåñòèðîâàíèå íà ðàçëè÷íûõ èçâåñòíûõ çàäà÷àõ,
à òàêæå îïûò ïðèìåíåíèÿ ïðè ðåøåíèè ðåàëüíûõ çàäà÷ ïîäòâåðäèëè ýôôåêòèâ-
íîñòü ðàçðàáîòàííûõ ãåíåòè÷åñêèõ àëãîðèòìîâ [76].
Äðóãèì àêòóàëüíûì íàïðàâëåíèåì èññëåäîâàíèé â òåîðèè åâêëèäîâîé êîì-
áèíàòîðíîé îïòèìèçàöèè ÿâëÿþòñÿ ìåòîäû îòñå÷åíèé äëÿ ëèíåéíûõ (ëèáî ñâî-
äÿùèõñÿ ê ëèíåéíûì) çàäà÷. Îáùàÿ ìåòîäîëîãèÿ ìåòîäîâ îïèñàíà â ðàáîòàõ
[77–80] è çàêëþ÷àåòñÿ â ðåëàêñàöèè èñõîäíîé çàäà÷è ñ ïîñëåäóþùèì èñïîëüçî-
âàíèåì ñèìïëåêñ-ìåòîäà äëÿ ðåøåíèÿ çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ íà
êîìáèíàòîðíîì ìíîãîãðàííèêå, ò.å. âûïóêëîé îáîëî÷êå ñîîòâåòñòâóþùåãî êîì-
áèíàòîðíîãî ìíîæåñòâà. Åñëè íàéäåííîå ðåøåíèå áóäåò íåäîïóñòèìûì, òî ôîð-
ìèðóåòñÿ äîïîëíèòåëüíîå ëèíåéíîå îãðàíè÷åíèå, îòñåêàþùåå ïîëó÷åííóþ òî÷-
êó. Ïîñòðîåíèå îãðàíè÷åíèé äëÿ îòñå÷åíèÿ áàçèðóþòñÿ íà ñâîéñòâàõ
êîìáèíàòîðíûõ ìíîãîãðàííèêîâ, â ÷àñòíîñòè êðèòåðèÿõ âåðøèí, ðåáåð è ò.ä.
Ïðåäñòàâëÿåò èíòåðåñ ãðàôî-àíàëèòè÷åñêèé ïîäõîä ê ðåøåíèþ çàäà÷ åâêëè-
äîâîé êîìáèíàòîðíîé îïòèìèçàöèè. Çàìåòèì, ÷òî ìîæíî óñòàíîâèòü âçàèìîñâÿçü
ìåæäó çàäà÷àìè íà åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâàõ è ãðàôàìè ñîîòâåòñòâó-
þùèõ êîìáèíàòîðíûõ ìíîãîãðàííèêîâ [17–19]. Èñïîëüçîâàíèå ñòðóêòóðíûõ
ñâîéñòâ äîïóñòèìîé îáëàñòè ïîçâîëÿåò ïðåäëîæèòü îðèãèíàëüíûå ìåòîäû ðåøå-
íèÿ êîìáèíàòîðíûõ çàäà÷ ñ ïðèìåíåíèåì ñâîéñòâ ãðàôîâ êîìáèíàòîðíûõ ìíî-
ãîãðàííèêîâ è ñàìèõ êîìáèíàòîðíûõ ìíîæåñòâ. Â ðàáîòàõ [18, 81, 82] íà îñíîâå
ãðàôîâûõ ìîäåëåé îïèñàí ïîäõîä ê ðåøåíèþ ýêñòðåìàëüíûõ çàäà÷ êîìáèíàòîð-
íîé îïòèìèçàöèè, îñíîâàííûé íà èõ íàïðàâëåííîì ñòðóêòóðèðîâàíèè â ñî÷åòà-
íèè ñ ìåòîäîì ïîñëåäîâàòåëüíîãî àíàëèçà âàðèàíòîâ [61]. Ïðåäëîæåíû ìåòîäû
ãåíåðèðîâàíèÿ ïîñëåäîâàòåëüíîñòè ýëåìåíòîâ êîìáèíàòîðíûõ êîíôèãóðàöèé
òðàíñïîçèöèåé åãî ýëåìåíòîâ. Îñóùåñòâëÿåòñÿ ïåðåìåùåíèå ìàêñèìàëüíîãî ýëå-
ìåíòà ìíîæåñòâà, ôîðìèðóþùåãî ñîîòâåòñòâóþùóþ êîíôèãóðàöèþ. Èññëåäîâà-
íû çàäà÷è åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè ñ ëèíåéíîé è äðîáíî-ëèíåé-
íîé öåëåâûìè ôóíêöèÿìè è äîïîëíèòåëüíûìè ëèíåéíûìè îãðàíè÷åíèÿìè.
ÏÐÀÊÒÈ×ÅÑÊÈÅ ÏÐÈËÎÆÅÍÈß È ÏÅÐÑÏÅÊÒÈÂÛ ÄÀËÜÍÅÉØÈÕ ÈÑÑËÅÄÎÂÀÍÈÉ
Ìåòîäû åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè ïðåäïîëàãàþò àíàëèòè÷åñêîå
çàäàíèå öåëåâîé ôóíêöèè, äîïóñêàþùåå íåïðåðûâíîå åå ïðîäîëæåíèå íà
êîìáèíàòîðíûé ìíîãîãðàííèê ñ ñîõðàíåíèåì èñõîäíîãî âûðàæåíèÿ. Ïåðñïåê-
òèâíûìè ïðåäñòàâëÿþòñÿ èññëåäîâàíèÿ, ñâÿçàííûå ñ îïèñàíèåì êîìáèíàòîðíûõ
ìíîãîãðàííèêîâ äëÿ íîâûõ åâêëèäîâûõ êîìáèíàòîðíûõ êîíôèãóðàöèé
� �� �, , ,� � , îñîáåííî äëÿ ìíîãîìåðíûõ îáðàçóþùèõ ìíîæåñòâ. Ïðè ýòîì
âîçíèêàåò íåîáõîäèìîñòü ïîñòðîåíèÿ òàêèõ îòîáðàæåíèé �:P � E, êîòîðûå ïîçâî-
ëÿþò ôîðìèðîâàòü ñîîòâåòñòâóþùèå âåðøèííî-ðàñïîëîæåííûå ìíîæåñòâà E. Åñòåñò-
âåííûì ðàçâèòèåì ýòîãî íàïðàâëåíèÿ ÿâëÿåòñÿ ïîñòðîåíèå âûïóêëûõ ïðîäîëæåíèé
äëÿ ðàçëè÷íûõ êëàññîâ ôóíêöèé, çàäàííûõ íà ñôîðìèðîâàííûõ ìíîæåñòâàõ.
Ïðèíöèïèàëüíûì äëÿ âîçìîæíîñòè ïðèëîæåíèÿ òåîðèè âûïóêëûõ ïðîäîë-
æåíèé ÿâëÿåòñÿ âîïðîñ î ïîñòðîåíèè ýêâèâàëåíòíîé åâêëèäîâîé ìîäåëè äëÿ çà-
äà÷è êîìáèíàòîðíîé îïòèìèçàöèè. Ýòî òðåáóåò íå òîëüêî çàäàíèÿ îòîáðàæåíèÿ
�:P � E åâêëèäîâà êîìáèíàòîðíîãî ìíîæåñòâà P íà êîíå÷íîå òî÷å÷íîå ìíîæåñ-
òâî E R n
çàäàííîé ñòðóêòóðû (íàïðèìåð, âåðøèííî-ðàñïîëîæåííîå ëèáî ïî-
ëèýäðàëüíî-ñôåðè÷åñêîå), à è âûáîðà ñîãëàñîâàííîãî ñ èñõîäíîé çàäà÷åé
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 39
àíàëèòè÷åñêîãî âèäà ôóíêöèè f x( ). Ïîýòîìó ïåðñïåêòèâíûì ïðåäñòàâëÿåòñÿ ïî-
ñòðîåíèå íîâûõ åâêëèäîâûõ ìîäåëåé äëÿ ðàçëè÷íûõ êëàññîâ çàäà÷ êîìáèíàòîð-
íîé îïòèìèçàöèè. Ýòî, â ñâîþ î÷åðåäü, ïðåäïîëàãàåò èññëåäîâàíèå ïðèêëàäíûõ
çàäà÷ â öåëÿõ ôîðìèðîâàíèÿ îáðàçóþùåãî ìíîæåñòâà � åâêëèäîâûõ êîìáèíàòîð-
íûõ êîíôèãóðàöèé � �� �, , ,� � , ôîðìàëèçàöèè íàáîðà îãðàíè÷åíèé � è îïðåäå-
ëåíèÿ àíàëèòè÷åñêîãî âèäà öåëåâîé ôóíêöèè.
Èìïóëüñîì ê èçó÷åíèþ çàäà÷ åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè ïî-
ñëóæèëî èññëåäîâàíèå ìîäåëåé è ìåòîäîâ ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ [11],
ñâÿçàííûõ ñ ïðåîáðàçîâàíèåì ãåîìåòðè÷åñêîé èíôîðìàöèè î ìàòåðèàëüíûõ
îáúåêòàõ. Ãåîìåòðè÷åñêàÿ èíôîðìàöèÿ î ñîâîêóïíîñòè îáúåêòîâ S S S m� { }1, ,�
âêëþ÷àåò îïèñàíèå èõ ôîðìû, ìåòðè÷åñêèõ ïàðàìåòðîâ, çàäàþùèõ ðàçìåðû
îáúåêòîâ, à òàêæå ïàðàìåòðû ðàçìåùåíèÿ, îïðåäåëÿþùèå ïîëîæåíèå îáúåêòîâ
â ïðîñòðàíñòâå. Â ðàáîòàõ [83, 84] ñôîðìèðîâàíî êîíôèãóðàöèîííîå ïðî-
ñòðàíñòâî �( )S , îáîáùåííûìè ïåðåìåííûìè êîòîðîãî ÿâëÿþòñÿ ìåòðè÷åñêèå
ïàðàìåòðû è ïàðàìåòðû ðàçìåùåíèÿ ãåîìåòðè÷åñêèõ îáúåêòîâ. Îòîáðàæåíèå
: ( )S S� � , óäîâëåòâîðÿþùåå çàäàííîé ñèñòåìå îãðàíè÷åíèé �, çàäàåò ðàçëè÷-
íûå ïðîñòðàíñòâåííûå êîíôèãóðàöèè ãåîìåòðè÷åñêèõ îáúåêòîâ — ðàçìåùåíèÿ,
êîìïîíîâêè, ïîêðûòèÿ, ðàçáèåíèÿ, ñîâðåìåííîìó èññëåäîâàíèþ êîòîðûõ ïîñâÿ-
ùåíû ðàáîòû [85–91].
Ìîæíî âûäåëèòü êîìáèíàòîðíóþ ñòðóêòóðó òàêèõ çàäà÷, ñâÿçàííóþ ñ âûáî-
ðîì ïîñëåäîâàòåëüíîñòè ðàçìåùåíèÿ îáúåêòîâ. Îäíàêî ïðîñòðàíñòâåííûå êîí-
ôèãóðàöèè ãåîìåòðè÷åñêèõ îáúåêòîâ íåðàçðûâíî ñâÿçàíû ñ êîìáèíàòîðíûìè
êîíôèãóðàöèÿìè, à ÷èñëîâûå çíà÷åíèÿ îáîáùåííûõ ïåðåìåííûõ îáóñëîâëèâàþò
âîçìîæíîñòü ïîñòðîåíèÿ ìàòåìàòè÷åñêèõ ìîäåëåé çàäà÷ ãåîìåòðè÷åñêîãî ïðîåê-
òèðîâàíèÿ êàê çàäà÷ îïòèìèçàöèè íà åâêëèäîâûõ êîìáèíàòîðíûõ êîíôèãóðàöè-
ÿõ. Ïðè ýòîì ïîðîæäàþòñÿ ðàçëè÷íûå êëàññû ïðîñòðàíñòâåííûõ êîíôèãóðàöèé,
â êîòîðûõ îáîáùåííûå ïåðåìåííûå (èëè íåêîòîðûå èç íèõ) ìîãóò ïðèíèìàòü
äèñêðåòíûå çíà÷åíèÿ.  ðåçóëüòàòå èìååì îïòèìèçàöèîííûå çàäà÷è íàçíà÷åíèÿ
ñ ðàçëè÷íûìè öåëåâûìè ôóíêöèÿìè.  êà÷åñòâå ïðàêòè÷åñêîãî ïðèëîæåíèÿ ðå-
çóëüòàòîâ îòìåòèì çàäà÷è êîìïîíîâî÷íîãî ñèíòåçà ñëîæíûõ ñèñòåì, â êîòîðûõ
òðåáóåòñÿ ìèíèìèçèðîâàòü îáúåì êîíòåéíåðà, ñóììàðíóþ äëèíó ñîåäèíåíèé,
îáåñïå÷èâàòü ìèíèìàëüíûé íåáàëàíñ [92–96].
Îòìåòèì òàêæå ïîäõîä [97, 98], ñâÿçàííûé ñ èñêóññòâåííûì ðàñøèðåíèåì ðàç-
ìåðíîñòè ïðîñòðàíñòâà îáîáùåííûõ ïåðåìåííûõ ñ îäíîâðåìåííûì ôîðìèðîâàíèåì
æåñòêîé ñèñòåìû îãðàíè÷åíèé íà íèõ. Ïðè ýòîì âûäåëÿåòñÿ êîìáèíàòîðíàÿ ñòðóê-
òóðà çàäà÷ ðàçìåùåíèÿ ãåîìåòðè÷åñêèõ îáúåêòîâ, â ðåçóëüòàòå ÷åãî çàäàåòñÿ ïîëèýä-
ðàëüíî-ñôåðè÷åñêîå ïðåäñòàâëåíèå ìíîæåñòâà èõ ìåòðè÷åñêèõ ïàðàìåòðîâ.
Âàæíûì íàïðàâëåíèåì â åâêëèäîâîé êîìáèíàòîðíîé îïòèìèçàöèè ÿâëÿþòñÿ
èññëåäîâàíèÿ, ñâÿçàííûå ñ ðàçëè÷íûìè âèäàìè íåîïðåäåëåííîñòåé. Ê èõ ÷èñëó
îòíîñÿòñÿ, ïðåæäå âñåãî, èíòåðâàëüíûå çàäàíèÿ ïàðàìåòðîâ çàäà÷è, à òàêæå ìíî-
ãèå êðèòåðèè îöåíêè êà÷åñòâà ðåøåíèé. Ðàçðàáîòêå èíòåðâàëüíûõ ìîäåëåé êîì-
áèíàòîðíîé îïòèìèçàöèè ïîñâÿùåíû, â ÷àñòíîñòè, ðàáîòû [99–104]. Íå÷åòêèå çà-
äà÷è ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ è ñâîéñòâà îòíîøåíèé òîëåðàíòíîñòè ïðè
îáðàáîòêå äàííûõ ðàññìîòðåíû â [96, 105–111].
Äëÿ ðåøåíèÿ ìíîãîêðèòåðèàëüíûõ çàäà÷ åâêëèäîâîé êîìáèíàòîðíîé îïòè-
ìèçàöèè ïðèìåíèìû îáùèå òåîðåòè÷åñêèå ïîäõîäû.  ñâÿçè ñ ýòèì îòìåòèì ðà-
áîòû [112–115], â êîòîðûõ ñ èñïîëüçîâàíèåì ñòðóêòóðíûõ ñâîéñòâ ìíîæåñòâ ðå-
øåíèé óêàçàííûõ çàäà÷ ïîëó÷åíû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ èõ ñó-
ùåñòâîâàíèÿ, îïòèìàëüíîñòè è óñòîé÷èâîñòè. Ýòî äàëî îñíîâó äëÿ ðàçðàáîòêè
ýôôåêòèâíûõ ìåòîäîâ íàõîæäåíèÿ ðàçíûõ âèäîâ îïòèìàëüíûõ ðåøåíèé ìíî-
ãîêðèòåðèàëüíûõ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè.  ÷àñòíîñòè, ìîíîãðà-
40 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
ôèÿ [112] ïîñâÿùåíà ðàçðàáîòêå è îáîñíîâàíèþ ìàòåìàòè÷åñêèõ ìîäåëåé è âû-
÷èñëèòåëüíûõ ìåòîäîâ ðåøåíèÿ âåêòîðíûõ çàäà÷ äèñêðåòíîé îïòèìèçàöèè íà
ðàçëè÷íûõ êîìáèíàòîðíûõ ìíîæåñòâàõ. Îñîáîå âíèìàíèå óäåëåíî èññëåäîâà-
íèþ ñòðóêòóðíûõ ñâîéñòâ äîïóñòèìîé îáëàñòè, êðèòåðèàëüíîãî êîíóñà, ìíî-
æåñòâ äîìèíèðîâàíèÿ ðåøåíèé çàäà÷. Ñ ó÷åòîì óñòàíîâëåííîé âçàèìîñâÿçè ìåæäó
âåêòîðíûìè çàäà÷àìè íà êîìáèíàòîðíûõ ìíîæåñòâàõ è îïòèìèçàöèîííûìè çàäà÷à-
ìè ïîëó÷åíû óñëîâèÿ îïòèìàëüíîñòè ðàçëè÷íûõ âèäîâ ýôôåêòèâíûõ ðåøåíèé.
 ðàáîòàõ [116, 117] íà îñíîâå ðàçâèòèÿ èäåé åâêëèäîâîé êîìáèíàòîðíîé
îïòèìèçàöèè è ìåòîäà ãëàâíîãî êðèòåðèÿ ðàçðàáîòàíû è îáîñíîâàíû âîçìîæíûå
ïîäõîäû äëÿ ðåøåíèÿ òàêèõ çàäà÷ ñ ëèíåéíûìè è äðîáíî-ëèíåéíûìè öåëåâûìè
ôóíêöèÿìè. Ïåðñïåêòèâíûì ïðåäñòàâëÿåòñÿ ðàñøèðåíèå ïîëó÷åííûõ ðåçóëüòà-
òîâ íà äðóãèå êëàññû åâêëèäîâûõ êîìáèíàòîðíûõ ìíîæåñòâ, à òàêæå ðàññìîòðå-
íèå êâàäðàòè÷íûõ è âûïóêëûõ öåëåâûõ ôóíêöèé. Åñëè â èñõîäíîé ïîñòàíîâêå
ôóíêöèè íå âûïóêëû, ìîæíî ñòðîèòü ýêâèâàëåíòíûå ìîäåëè ñ èñïîëüçîâàíèåì
òåîðèè âûïóêëûõ ïðîäîëæåíèé. Îòìåòèì òàêæå ñòàòüþ [118], â êîòîðîé ðàññìîò-
ðåíû äâóõóðîâíåâûå çàäà÷è, ñîäåðæàùèå íà íèæíåì óðîâíå ëèíåéíûå çàäà÷è
äèñêðåòíîé îïòèìèçàöèè, îïòèìàëüíûå ðåøåíèÿ êîòîðûõ èñïîëüçóþòñÿ ïðè çà-
äàíèè äîïóñòèìîé îáëàñòè çàäà÷è âåðõíåãî óðîâíÿ. Îïèñàííûé ïîäõîä ìîæíî
ðàñïðîñòðàíèòü íà ðÿä çàäà÷ ãåîìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ, â êîòîðûõ îáëàñòü
äîïóñòèìûõ ðåøåíèé ôîðìèðóåòñÿ êàê çàäà÷à ìèíèìèçàöèè ñïåöèàëüíîãî êëàññà
ôóíêöèè â êîíôèãóðàöèîííîì ïðîñòðàíñòâå ãåîìåòðè÷åñêèõ îáúåêòîâ [119].
 çàêëþ÷åíèå îòìåòèì, ÷òî òåîðèþ, ìîäåëè è ìåòîäû åâêëèäîâîé êîìáèíà-
òîðíîé îïòèìèçàöèè ìîæíî ïðèìåíÿòü êàê ýôôåêòèâíûé èíñòðóìåíòàðèé äëÿ
ðàçðàáîòêè íîâûõ ïîäõîäîâ ê ðåøåíèþ òðóäíîðåøàåìûõ çàäà÷ äèñêðåòíî-íå-
ïðåðûâíîé ñòðóêòóðû, à òàêæå èñïîëüçîâàòü èõ ïðèëîæåíèÿ â ðàçëè÷íûõ èíòåë-
ëåêòóàëüíûõ èíôîðìàöèîííî-àíàëèòè÷åñêèõ ñèñòåìàõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñåðãèåíêî È.Â., Øèëî Â.Ï. Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: ïðîáëåìû, ìåòîäû ðåøåíèÿ,
èññëåäîâàíèÿ. Êèåâ: Íàóê. äóìêà, 2003. 261 ñ.
2. Sergienko I.V., Shylo V.P. Modern approaches to solving complex discrete optimization problems.
Journal of Automation and Information Sciences. 2016. Vol. 48, N 1. P. 15–24.
3. Pardalos P.M., Du D-Z., Graham R.L. (Eds.) Handbook of combinatorial optimization. New York:
Springer, 2013. 3399 p.
4. Korte B., Vygen J. Combinatorial optimization: Theory and algorithms. Berlin; Heidelberg; New York:
Springer, 2012. 660 p.
5. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: Algorithms and complexity. Mineola (NY):
Dover Publications, 2013. 528 p.
6. Sergienko I.V., Hulianytskyi L.F., Sirenko S.I. Classification of applied methods of combinatorial optimi-
zation. Cybernetics and Systems Analysis. 2009. Vol. 45, N 5. P. 732–741.
7. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization problems.
Springer Optimization and Its Applications. 2017. Vol. 130. P. 239–250.
8. Çãóðîâñêèé Ì.Ç., Ïàâëîâ À.À. Òðóäíîðåøàåìûå çàäà÷è êîìáèíàòîðíîé îïòèìèçàöèè â ïëàíèðîâàíèè
è ïðèíÿòèè ðåøåíèé. Êèåâ: Íàóê. äóìêà, 2016. 716 ñ.
9. Ñòîÿí Þ.Ã. Íåêîòîðûå ñâîéñòâà ñïåöèàëüíûõ êîìáèíàòîðíûõ ìíîæåñòâ. Õàðüêîâ: Èí-ò ïðîáë.
ìàøèíîñòðîåíèÿ ÀÍ ÓÑÑÐ, 1980. 22 ñ. (Ïðåïðèíò. ÀÍ ÓÑÑÐ, Èí-ò ïðîáë. ìàøèíîñòðîåíèÿ; ¹ 85).
10. Ñòîÿí Þ.Ã. Îá îäíîì îòîáðàæåíèè êîìáèíàòîðíûõ ìíîæåñòâ â åâêëèäîâî ïðîñòðàíñòâî. Õàðüêîâ:
Èí-ò ïðîáë. ìàøèíîñòðîåíèÿ ÀÍ ÓÑÑÐ, 1982. 33 ñ. (Ïðåïðèíò. ÀÍ ÓÑÑÐ, Èí-ò ïðîáë.
ìàøèíîñòðîåíèÿ; ¹ 173).
11. Ñòîÿí Þ.Ã., ßêîâëåâ Ñ.Â. Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû ãåîìåòðè÷åñêîãî
ïðîåêòèðîâàíèÿ. Êèåâ: Íàóê. äóìêà, 1986. 268 ñ.
12. Berge C. Principes de combinatoire. Paris: Dunod, 1968. 146 p.
13. Ñà÷êîâ Â.Í. Êîìáèíàòîðíûå ìåòîäû äèñêðåòíîé ìàòåìàòèêè. Ìîñêâà: Íàóêà, 1975. 319 ñ.
14. Ñòîÿí Þ.Ã., ßêîâëåâ Ñ.Â., Ïè÷óãèíà Î.Ñ. Åâêëèäîâû êîìáèíàòîðíûå êîíôèãóðàöèè. Õàðüêîâ:
Êîíñòàíòà, 2017. 404 ñ.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 41
15. Ñòîÿí Þ.Ã., ªìåöü Î.Î. Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. Êè¿â: ²í-ò ñèñòåìí.
äîñë³äæ. îñâ³òè, 1993. 188 ñ.
16. Åìåö Î.À., Áàðáîëèíà Ò.Í. Êîìáèíàòîðíàÿ îïòèìèçàöèÿ íà ðàçìåùåíèÿõ. Êèåâ: Íàóê. äóìêà, 2008.
159 ñ.
17. Åìåëè÷åâ Â.À., Êîâàëåâ Ì.Ì., Êðàâöîâ Ì.Ê. Ìíîãîãðàííèêè, ãðàôû, îïòèìèçàöèÿ (êîìáèíàòîðíàÿ
òåîðèÿ ìíîãîãðàííèêîâ). Ìîñêâà: Íàóêà, 1981. 344 ñ.
18. Äîíåöü Ã.Ï., Êîëº÷ê³íà Ë.Ì. Åêñòðåìàëüí³ çàäà÷³ íà êîìá³íàòîðíèõ êîíô³ãóðàö³ÿõ. Ïîëòàâà:
ÏÓÅÒ, 2011. 328 ñ.
19. Ïè÷óãèíà Î., Áðóñ À. Êîìïüþòåðíîå èññëåäîâàíèå êîìáèíàòîðíûõ ìíîæåñòâ è ìíîãîãðàííèêîâ:
Êëàññèôèêàöèÿ. Ïðèìåíåíèå â îïòèìèçàöèè è òåîðèè ãåîìåòðè÷åñêèõ ãðàôîâ. Saarbriicken: LAP
LAMBERT Acad. Publ., 2014. 144 c.
20. Ñòîÿí Þ.Ã., Ãðåáåííèê È.Â. Êîìïîçèöèîííûå îáðàçû êîìáèíàòîðíûõ ìíîæåñòâ è íåêîòîðûå èõ
ñâîéñòâà. Ïðîáë. ìàøèíîñòðîåíèÿ. 2005. Ò. 8, ¹ 3. Ñ. 56–62.
21. Ãðåáåííèê È.Â. Êîìáèíàòîðíîå ìíîæåñòâî ïåðåñòàíîâîê êîðòåæåé è åãî ñâîéñòâà. Ðàäèîýëåêòðîíèêà.
Èíôîðìàòèêà. Óïðàâëåíèå. 2005. ¹ 1. Ñ. 92–98.
22. Ñòîÿí Þ.Ã., Ãðåáåííèê È.Â. Îïèñàíèå êëàññîâ êîìáèíàòîðíûõ êîíôèãóðàöèé íà îñíîâå
îòîáðàæåíèé. Äîêë. ÍÀÍ Óêðàèíû. 2008. ¹ 10. Ñ. 28–31.
23. Yemets O.A., Yemets A.O., Polyakov I.M. Criterion of an edge of a general polyhedron of arrangements.
Cybernetics and Systems Analysis. 2018. Vol. 54, N 5. P. 796–805.
24. Yemets O.A., Yemets A.O., Polyakov I.M. Optimization on arrangements: The simplex form of polyhe-
dron of arrangements. Journal of Automation and Information Sciences. 2017. Vol. 49, N 12. P. 14–28.
25. Aardal K., Hoesel S. Polyhedral techniques in combinatorial optimization. I: Computations. Statistica
Neerlandica. 1996. N 15. P. 3–26.
26. Aardal K., Hoesel S. Polyhedral techniques in combinatorial optimization. II: Theory. Statistica
Neerlandica. 1999. N 2. P. 131–177.
27. Ïè÷óãèíà Î.Ñ., ßêîâëåâ Ñ.Â. Íåïðåðûâíûå ôóíêöèîíàëüíûå ïðåäñòàâëåíèÿ â çàäà÷àõ äèñêðåòíîé
îïòèìèçàöèè. Õàðüêîâ: Çîëîòàÿ ìèëÿ, 2018. 312 ñ.
28. Pichugina O.S., Yakovlev S.V. Continuous representations and functional extensions in combinatorial op-
timization. Cybernetics and Systems Analysis. 2016. Vol. 52, N 6. P. 921–930.
29. Pichuginà O., Yakovlev S. Convex extensions and continuous functional representations in optimization,
with their applications. J. Coupled Syst. Multiscale Dyn. 2016. Vol. 4, N 2. P. 129–152.
30. Pichugina O.S., Yakovlev S.V. Functional and analytic representations of the general permutations.
Eastern-European Journal of Enterprise Technologies. 2016. Vol. 1, N 4. P. 27–38.
31. Pichuginà O., Yakovlev S. Continuous approaches to the unconstrained binary quadratic problems.
Mathematical and Computational Approaches in Advancing Modern Science and Engineering. Edited
B�lair J., Frigaard I., Kunze H. Cham: Springer, Switzerland, 2016. P. 689–700.
32. Pichugina O.S., Yakovlev S.V. Continuous representation techniques in combinatorial optimization. IOSR
Journal of Mathematics. 2017. Vol. 13, N 2, Ver. V. P. 12–25.
33. Pichugina O.S., Yakovlev S.V. Euclidean combinatorial configurations: continuous representations and
convex extensions. Advances in Intelligent Systems and Computing. 2019. Vol. 1020. P. 65–80.
34. Pichugina O., Yakovlev S. Euclidean combinatorial configurations: Typology and applications.
2019 IEEE First Ukraine Conference on Electrical and Computer Engineering (July 2–6, 2019, Lviv).
Lviv, 2019. P. 1065–1070.
35. Yakovlev S.V. The theory of convex continuations of functions on vertices of convex polyhedral. Comp.
Math. and Math. Phys. 1994. Vol. 34. P. 1112–1119.
36. Yakovlev S. Convex extensions in combinatorial optimization and their applications. Springer Opti-
mization and Its Applications. 2017. Vol. 130. P. 567–584.
37. Ïîãîðåëîâ À.Â. Âíåøíÿÿ ãåîìåòðèÿ âûïóêëûõ ïîâåðõíîñòåé. Ìîñêâà: Íàóêà, 1969. 760 c.
38. Ñòîÿí Þ.Ã., ßêîâëåâ Ñ.Â., Ïàðøèí Î.Â. Îïòèìèçàöèÿ êâàäðàòè÷íûõ ôóíêöèé íà ìíîæåñòâå
ïåðåñòàíîâîê, îòîáðàæåííîì â R n. Äîêë. ÀÍ ÓÑÑÐ. Ñåð. À. 1989. ¹ 5. Ñ. 73–78.
39. Stoyan Y.G., Yakovlev S.V., Parshin O.V. Quadratic optimization on combinatorial sets in R n. Cybernetics
and Systems Analysis. 1991. Vol. 27, N 4. P. 562–567.
40. Yakovlev S.V., Pichugina O.S. Properties of combinatorial optimization problems over polyhedral-spheri-
cal sets. Cybernetics and Systems Analysis. 2018. Vol. 54, N 1. P. 99–109.
41. Pichugina O., Yakovlev S. Optimization on polyhedral-spherical sets: Theory and applications.
2017 IEEE First Ukraine Conference on Electrical and Computer Engeneering (May 29–June 2, Kyiv).
Kyiv, 2017. P. 1167–1175.
42. Yakovlev S., Pichugina O., Yarovaya O. On optimization problems on the polyhedral-spherical configura-
tions with their properties. 2018 IEEE First International Conference on System Analysis and Intelligent
Computing (October 8–12, 2018, Kyiv). Kyiv, 2018. P. 94–100.
42 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
43. Yakovlev S., Pichugina O., Yarovaya O. Polyhedral-spherical configurations in discrete optimization
problems. Journal of Automation and Information Sciences. 2019. Vol. 51, N 1. P. 26–40.
44. Ñòîÿí Þ.Ã., ßêîâëåâ Ñ.Â., Åìåö Î.À., Âàëóéñêàÿ Î.À. Î ñóùåñòâîâàíèè âûïóêëîãî ïðîäîëæåíèÿ
ôóíêöèé, çàäàííûõ íà ãèïåðñôåðå. Äîêë. ÍÀÍ Óêðàèíû. 1998. ¹ 2. Ñ. 128–133.
45. Stoyan Yu.G., Yakovlev S.V., Yemets O.A., Valuyskaya O.A. Construction of convex continuations for
functions defined on hypersphere. Cybernetics and System Analysis. 1998. Vol. 34, N 2. P. 27–36.
46. Stoyan Yu., Grebennik I., Kalashnikov V., Lytvynenko O. Enumeration and generation of permutations
with a partially fixed order of elements. International Journal of Combinatorial Optimization Problems
and Informatics. 2017. Vol. 8, N 1. P. 19–30.
47. Pichugina O., Kartashov O. Signed permutation polytope packing in VLSI design. 15th International
Conference on the Experience of Designing and Application of CAD Systems (February 26–March 2, 2019,
Polyana, Ukraine). Polyana, 2019. P. 50–55.
48. Ïè÷óãèíà Î.Ñ., ßêîâëåâ Ñ.Â. Âûïóêëûå ïðîäîëæåíèÿ äëÿ êëàññà êâàäðàòè÷íûõ çàäà÷ íà
ïåðåñòàíîâî÷íûõ ìàòðèöàõ. Êîìïüþòåðíàÿ ìàòåìàòèêà. 2016. Âûï. 1. Ñ. 143–154.
49. Grebennik I.V. Description and generation of permutations containing cycles. Cybernetics and Systems
Analysis. 2010. Vol. 46, N 6. P. 945–952.
50. Grebennik I.V., Lytvynenko O.S. Generation of combinatorial sets possessing special characteris-
tics. Cybernetics and Systems Analysis. 2012. Vol. 48, N 6. P. 890–898.
51. Ñòîÿí Þ.Ã, ßêîâëåâ Ñ.Â. Ïîñòðîåíèå âûïóêëûõ è âîãíóòûõ ôóíêöèé íà ïåðåñòàíîâî÷íîì
ìíîãîãðàííèêå. Äîêë. ÀÍ ÓÑÑÐ. 1988. ¹ 5. Ñ. 68–70.
52. Yakovlev S.V. Bounds on the minimum of convex functions on Euclidean combinatorial sets. Cybernetics
and Systems Analysis. 1989. Vol. 25, N 3. P. 385–391.
53. ßêîâëåâ Ñ.Â. Òåîðèÿ âûïóêëûõ ïðîäîëæåíèé â çàäà÷àõ êîìáèíàòîðíîé îïòèìèçàöèè. Äîêë. ÍÀÍ
Óêðàèíû. 2017. ¹ 8. Ñ. 20–26.
54. Valuiskaya O.A., Yemets O.À., Romanova N.G. Stoyan–Yakovlev’s modified method applied to convex
continuation of polynomials defined on polypermutations. Computational Mathematics and Mathematical
Physics. 2002. Vol. 42, N 4. P. 591–596.
55. Yakovlev S., Pichugina O. On constrained optimization of polynomials on permutation set. Proceedings of
the Second International Workshop on Computer Modeling and Intelligent Systems (April 15–19,
2019, Zaporizhzhia). Zaporizhzhia, 2019. P. 570–580.
56. ßêîâëåâ Ñ.Â., Ãðåáåííèê È.Â. Î íåêîòîðûõ êëàññàõ çàäà÷ îïòèìèçàöèè íà êîìáèíàòîðíûõ
ìíîæåñòâàõ ðàçìåùåíèé. Èçâ. âóçîâ. Ñåð. Ìàò. 1991. ¹ 11. Ñ. 74–86.
57. Ïè÷óãèíà Î.Î. Àëãîðèòì ïîñòðîåíèÿ âûïóêëîãî ïðîäîëæåíèÿ íà ïîëèïåðåñòàíîâêàõ è ñôåðà åãî
ïðèìåíåíèÿ. Problems of Computer Intellectualization. Kyiv (Ukraine)–Sofia (Bulgaria), 2012. P. 125–132.
58. Pichugina O., Yakovlev S. Quadratic optimization models and convex extensions on permutation matrix
set. In: Shakhovska N. and Medykovskyy M.O. (Eds.) Advances in Intelligent Systems and Computing IV.
Cham: Springer Nature, Switzerland, 2019. P. 231–246.
59. Yakovlev S.V., Grebennik I.V. Localization of solutions of some problems of nonlinear integer optimiza-
tion. Cybernetics and Systems Analysis. 1993. Vol. 29, N 5. P. 419–426.
60. Land A.H., Doig A.G. An automatic method of solving discrete programming problems. Econometrica.
1960. Vol. 28, N 3. P. 497–520.
61. Ìèõàëåâè÷ Â.Ñ. Ïîñëåäîâàòåëüíûå àëãîðèòìû îïòèìèçàöèè è èõ ïðèìåíåíèå. Êèáåðíåòèêà. 1965.
¹ 1. Ñ. 45–56; ¹ 2. Ñ. 85–88.
62. Sergienko I.V., Iemets O.A., Chernenko O.A. Solving the conditional optimization problem for a frac-
tional linear objective function on a set of arrangements by the branch and bound method. Cybernetics
and Systems Analysis. 2012. Vol. 48, N 6. P. 832–836.
63. Iemets O.A., Yemets A.O. The solution of a minimization problem of the weighted length of a connecting
grid by branch and bound method. Journal of Automation and Information Sciences. 2012. Vol. 44, N 7.
P. 22–33.
64. Iemets O.A., Parfionova T.A. Transportation problems on permutations: properties of estimates in the
branch and bound method. Cybernetics and Systems Analysis. 2014. Vol. 46, N 6. P. 953–959.
65. ßêîâëåâ Ñ.Â., Ïàðøèí Î.Â. Ïðèáëèæåííûå ìåòîäû îïòèìèçàöèè íà âåðøèíàõ ïåðåñòàíîâî÷íîãî
ìíîãîãðàííèêà. Âåñòí. Õàðüê. óí-òà. Äèíàìè÷åñêèå ñèñòåìû. 1989. Bûï. 334. Ñ. 198–206.
66. Ïè÷óãèíà Î.Ñ., ßêîâëåâ Ñ.Â. Ìåòîäû ãëîáàëüíîé îïòèìèçàöèè íà ïåðåñòàíîâî÷íîì ìíîãîãðàííèêå
â êîìáèíàòîðíûõ çàäà÷àõ íà âåðøèííî ðàñïîëîæåííûõ ìíîæåñòâàõ. Ìàòåìàòè÷åñêîå è êîìïüþòåðíîå
ìîäåëèðîâàíèå. Ñåð. Ôèç.-ìàò. íàóêè. 2017. ¹ 15. Ñ. 258–264.
67. Ïè÷óãèíà Î.Ñ., ßêîâëåâ Ñ.Â. Ìåòîäû øòðàôíûõ ôóíêöèé äëÿ ðåøåíèÿ çàäà÷ îïòèìèçàöèè íà
ïîëèýäðàëüíî-ñôåðè÷åñêèõ ìíîæåñòâàõ. Ðàäèîýëåêòðîíèêà è èíôîðìàòèêà. 2016. ¹ 1. Ñ. 18–26.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 43
68. Stetsyuk P.I. Shor’s r-algorithms: Theory and practice. Springer Optimization and Its Applications. 2017.
Vol. 130. P. 239–250.
69. Stetsyuk P.I. Theory and software implementations of Shor’s r-algorithms. Cybernetics and Systems
Analysis. 2017. Vol. 53, N 5. P. 692–703.
70. Ñòîÿí Þ.Ã., ßêîâëåâ Ñ.Â. Ñâîéñòâà âûïóêëûõ ôóíêöèé íà ïåðåñòàíîâî÷íîì ìíîãîãðàííèêå. Äîêë.
ÀÍ ÓÑÑÐ. Ñåð. À. 1988. ¹ 3. Ñ. 238–240.
71. Yakovlev S.V., Valuiskaya O.A. Optimization of linear functions at the vertices of a permutation polyhe-
dron with additional linear constraints. Ukrainian Mathematical Journal. 2001. Vol. 53, N 9.
P. 1535–1545.
72. Ãóëÿíèöüêèé Ë.Ô., Ìóëåñà Î.Þ. Ïðèêëàäí³ ìåòîäè êîìá³íàòîðíî¿ îïòèì³çàö³¿. Êè¿â: ÂÏÖ
«Êè¿âñüêèé óí³âåðñèòåò», 2016. 142 ñ.
73. Êîçèí È.Â. Ýâîëþöèîííûå ìîäåëè â çàäà÷àõ äèñêðåòíîé îïòèìèçàöèè. Çàïîðîæüå: Çàïîðîæ. íàö.
óí-ò, 2019. 204 ñ.
74. Yakovlev S., Kartashov O., Yarovaya O. On class of genetic algorithms in optimization problems on com-
binatorial configuration. 2018 IEEE XI²I International Scientific and Technical Conference on Computer
Sciences and Information Technologies (September 11–14, 2018, Lviv). Lviv, 2018. P. 374–377.
75. Yakovlev S., Kartashov O., Pichugina O. Optimization on combinatorial configurations using genetic al-
gorithms. In: CEUR Workshop Proceedings. 2019. Vol. 2353. P. 28–40.
76. Yakovlev S., Kartashov O., Pichugina O., Korobchynskyi K. Genetic algorithms for solving combinatorial
mass balancing problem. 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering.
(July 2–6, 2019, Lviv). Lviv, 2019. P. 1061–1064.
77. ªìåö Î.O., ªìåö ª.Ì. ³äñ³êàííÿ â ë³í³éíèõ ÷àñòêîâî êîìá³íàòîðíèõ çàäà÷àõ åâêë³äîâî¿
êîìá³íàòîðíî¿ îïòèì³çàö³¿. Äîï. ÍÀÍ Óêðà¿íè. 2000. ¹ 9. Ñ. 105–109.
78. Yemets O.A., Yemets Y.M. A modification of the method of combinatorial truncation in optimization
problems over vertex-located sets. Cybernetics and Systems Analysis. 2009. Vol. 45, N 5. P. 785–791.
79. Yemets O.A., Yemets Y.M., Chilikina T.V. Combinatorial cutting while solving optimization nonlinear
conditional problems of the vertex located sets. Journal of Automation and Information Sciences. 2010.
Vol. 42, N 5. P. 21–29.
80. Iemets O.O., Yemets E.M., Olhovskiy D.M. The method of cutting the vertices of permutation polyhedron
graph to solve linear conditional optimization problems on permutations. Cybernetics and Systems Analysis.
2014. Vol. 50, N 4. P. 613–619.
81. Äîíåö Ã.À., Êîëå÷êèíà Ë.Í. Îá îäíîì ïîäõîäå ê ðåøåíèþ êîìáèíàòîðíîé çàäà÷è îïòèìèçàöèè íà
ãðàôàõ. Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. 2009. ¹ 4. Ñ. 36–42.
82. Donec G.A., Kolechkina L.M. Construction of hamiltonian paths in graphs of permutation polyhedra.
Cybernetics and Systems Analysis. 2016. Vol. 46, N 1. P. 7–13.
83. Stoyan Y.G., Yakovlev S.V. Configuration space of geometric objects. Cybernetics and Systems Analysis.
2018. Vol. 54, N 5. P. 716–726.
84. Yakovlev S.V. On some classes of spatial configurations of geometric objects and their formalization.
Journal of Automation and Information Sciences. 2018. Vol. 50, N 9. P. 38–50.
85. Stoyan Yu., Romanova T. Mathematical models of placement optimisation: two- and three-dimensional
problems and applications. Modeling and Optimization in Space Engineering. New York: Springer, 2013.
Vol. 73. P. 363–388.
86. Grebennik I.V., Kovalenko A.A., Romanova T.E., Urniaieva I.A., Shekhovtsov S.B. Combinatorial con-
figurations in balance layout optimization problems. Cybernetics and Systems Analysis. 2018. Vol. 54,
N 2. P. 221–231.
87. Stoyan Y., Pankratov A., Romanova T., Fasano G., Pint�r J.D. Optimized packings in space engineering
applications: Part I. Modeling and Optimization in Space Engineering. Springer Optimization and Its Ap-
plications. 2019. Vol 144. P. 395–437.
88. Stoyan Y., Grebennik I., Romanova T., Kovalenko A. Optimized packings in space engineering applica-
tions: Part II. Modeling and Optimization in Space Engineering. Springer Optimization and Its Applica-
tions. 2019. Vol 144. P. 439–457.
89. Yakovlev S.V. Configuration spaces of geometric objects with their applications in packing, layout and
covering problems. Advances in Intelligent Systems and Computing. 2019. Vol. 1020. P. 122–132.
90. Kiseleva E.M., Prytomanova O.M., Zhuravel S.V. Algorithm for solving a continuous problem of optimal
partitioning with neurolinguistic identification of functions in target functional. Journal of Automation
and Information Science. 2018. Vol. 50, N 3. P. 1–20.
91. Kiseleva Å.Ì., Kadochnikova Y.E. Solving a continuous single-product problem of optimal partitioning
with additional conditions. Journal of Automation and Information Science. 2009. Vol. 41, N 7. P. 48–63.
92. Stoyan Yu.G., Semkin V.V., Chugay A.M. Optimization of 3D objects layout into a multiply connected
44 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
domain with account for shortest distances. Cybernetics and Systems Analysis. 2014. Vol. 50, N 3.
P. 374–385.
93. Stoyan Y., Romanova T., Pankratov A., Kovalenko A., Stetsyuk P. Balance layout problems: Mathemati-
cal modeling and nonlinear optimization. Springer Optimization and Its Applications. 2016. Vol. 114.
P. 369–400.
94. Stoyan Yu.G., Sokolovskii V.Z., Yakovlev S.V. Method of balancing rotating discretely distributed
masses. Energomashinostroenie. 1982. N 2. P. 4, 5.
95. Pichugina O. Placement problems in chip design: Modeling and optimization. 4th International Scien-
tific-Practical Conference Problems of Infocommunications. Science and Technology (October 10–13,
2017, Kharkiv). Kharkiv, 2017. P. 465–473.
96. Ãðèöèê Â.Â., Øåâ÷åíêî À.²., Êèñåëüîâà Î.Ì., ßêîâëåâ Ñ.Â., Á³äþê Ï.²., óëü Ì.²., Êðàê Þ.Â.,
Êóëÿñ À.²., Ðîìàíîâà Ò.ª., Ñòåöþê Ï.². Ìàòåìàòè÷í³ ìåòîäè îïòèì³çàö³¿ òà ³íòåëåêòóàëüí³
êîìï’þòåðí³ òåõíîëî㳿 ìîäåëþâàííÿ ñêëàäíèõ ïðîöåñ³â ³ ñèñòåì ç óðàõóâàííÿì ïðîñòîðîâèõ ôîðì
îá’ºêò³â. Äîíåöüê: Íàóêà ³ îñâ³òà, 2011. 480 ñ.
97. ßêîâëåâ Ñ.Â. Î êîìáèíàòîðíîé ñòðóêòóðå çàäà÷ îïòèìàëüíîãî ðàçìåùåíèÿ ãåîìåòðè÷åñêèõ
îáúåêòîâ. Äîêë. ÍÀÍ Óêðàèíû. 2017. ¹ 9. Ñ. 63–68.
98. Yakovlev S.V. The method of artificial dilation in problems of optimal packing of geometric objects.
Cybernetics and Systems Analysis. 2017. Vol. 53, N 5. P. 725–731.
99. Hulianytskyi L.F., Riasna I.I. Automatic classification method based on a fuzzy similarity relation. Cyber-
netics and Systems Analysis. 2016. Vol. 52, N 1. P. 30–37.
100. Ãóëÿíèöüêèé Ë.Ô., Ðÿñíà ².². Äî ôîðìàë³çàö³¿ çàäà÷ êîìá³íàòîðíî¿ îïòèì³çàö³¿ íà íå÷³òêèõ
ìíîæèíàõ. Òåîð³ÿ îïòèìàëüíèõ ð³øåíü. 2016. ¹ 1. Ñ. 17–25.
101. Ãðåáåííèê È.Â. Èíòåðâàëüíûå ìîäåëè êîìáèíàòîðíîé îïòèìèçàöèè êâàçèëèíåéíûõ ôóíêöèé
â ïðîñòðàíñòâå. Äîêë. ÍÀÍ Óêðàèíû. 2004. ¹ 9. C. 60–64.
102. Ãðåáåííèê È.Â., Ðîìàíîâà Ò.Å. Îòîáðàæåíèå èíòåðâàëüíûõ êîìáèíàòîðíûõ ìíîæåñòâ â åâêëèäîâî
ïðîñòðàíñòâî. Ïðîáë. ìàøèíîñòðîåíèÿ. 2002. Ò. 5, ¹ 2. Ñ. 87–91.
103. ªìåöü Î.Î., ªìåöü Î.Î. Ðîçâ’ÿçóâàííÿ çàäà÷ êîìá³íàòîðíî¿ îïòèì³çàö³¿ íà íå÷³òêèõ ìíîæèíàõ.
Ïîëòàâà: ÏÓÅÒ, 2011. 239 ñ.
104. Yemets O.A., Roskladka A.A. Combinatorial optimization under uncertainty. Cybernetics and Systems
Analysis. 2008. Vol. 44, N 5. P. 655–663.
105. Ðîìàíîâà Ò.Å., Åâñååâà Ë.Ã., Ñòîÿí Þ.Ã. Êîìáèíàòîðíàÿ îïòèìèçàöèîííàÿ çàäà÷à ðàçìåùåíèÿ
ïðÿìîóãîëüíèêîâ ñ ó÷åòîì ïîãðåøíîñòåé èñõîäíûõ äàííûõ. Äîêë. ÍÀÍ Óêðàèíû. 1997. ¹ 7.
Ñ. 56–60.
106. Ñòîÿí Þ.Ã., Ðîìàíîâà Ò.Å. Account of errors in optimization placement problem. Ïðîáë.
ìàøèíîñòðîåíèÿ. 1998. Ò. 1, ¹ 2. Ñ. 31–41.
107. Ãðåáåííèê È.Â., Ðîìàíîâà Ò.Å. Ó÷åò ïîãðåøíîñòåé ïðè ïîñòðîåíèè ìàòåìàòè÷åñêèõ ìîäåëåé
îïòèìèçàöèîííûõ êîìáèíàòîðíûõ çàäà÷. Àâòîìàòèçèðîâàííûå ñèñòåìû óïðàâëåíèÿ è ïðèáîðû
àâòîìàòèêè. 2002. Âûï. 119. Ñ. 64–69.
108. Kiseleva E., Hart L., Prytomanova O., Kuzenkov A. An algorithm to construct generalized Voronoi
diagrams with fuzzy parameters based on the theory of optimal partitioning and neuro-fuzzy technologies.
8th International Conference on Mathematics, Information Technologies, Education (March 23–25, 2019,
Xi’an, China). Xi’an, 2019. Ð. 148–162.
109. Mashtalir V.P., Yakovlev S.V. Point-set methods of clusterization of standard information. Cybernetics
and Systems Analysis. 2001. Vol. 37, N 3. Ð. 295–307.
110. Gerasin S.N., Shlyakhov V.V., Yakovlev S.V. Set coverings and tolerance relations. Cybernetics and Sys-
tems Analysis. 2008. Vol. 43, N 3. P. 333–340.
111. Mashtalir V.P., Shlyakhov V.V., Yakovlev S.V. Group structures on quotient sets in classification prob-
lems. Cybernetics and Systems Analysis. 2014. Vol. 50, N 4. P. 507–518.
112. Ñåìåíîâà Í.Â., Êîëº÷ê³íà Ë.Ì. Âåêòîðí³ çàäà÷³ äèñêðåòíî¿ îïòèì³çàö³¿ íà êîìá³íàòîðíèõ
ìíîæèíàõ: ìåòîäè äîñë³äæåííÿ òà ðîçâ’ÿçàííÿ. Êè¿â: Íàóê. äóìêà, 2009. 266 ñ.
113. Emelichev V.A., Kotov V.M., Kuzmin K.G., Semenova N.V., Lebedeva T.T., Sergienko T.I. Stability and
effective algorithms for solving multiobjective discrete optimization problems with incomplete informa-
tion. Journal of Automation and Information Sciences. 2014. Vol. 46, N 2. P. 27–41.
114. Lebedeva T.T., Semenova N.V., Sergienko T.I Qualitative characteristics of the stability vector discrete
optimization problems with different optimality principles. Cybernetics and Systems Analysis. 2014.
Vol. 50, N 2. P. 228–233.
115. Sergienko I.V., Lebedeva T.T., Semenova N.V. Existence of solutions in vector optimization problems.
Cybernetics and Systems Analysis. 2000. Vol. 36, N 6. P. 823–828.
116. Semenova N.V., Kolechkina L.N., Nagirna A.N. An approach to solving discrete vector optimization
problems over a combinatorial set of permutations. Cybernetics and Systems Analysis. 2008. Vol. 44, N 3.
P. 441–451.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 45
117. Semenova N.V., Kolechkina L.N., Nagornaya A.N. On approach to solving vector problems with fractionally
linear functions of the criteria on the combinatorial set of arrangements. Journal of Automation and Infor-
mation Sciences. 2010. Vol. 42, N 2. P. 67–80.
118. Sergienko I.V., Semenova N.V., Semenov V.V. Bilevel optimization problems of distribution of
interbudget transfers within given limitations. Cybernetics and Systems Analysis. 2019. Vol. 55, N 6.
P. 730–740.
119. Yakovlev S.V. Formalizing spatial configuration optimization problems with the use of a special function
class. Cybernetics and Systems Analysis. 2019. Vol. 55, N 4. P. 581–589.
Íàä³éøëà äî ðåäàêö³¿ 21.11.2019
Þ.Ã. Ñòîÿí, Ñ.Â. ßêîâëåâ
ÒÅÎÐ²ß ² ÌÅÒÎÄÈ ÅÂÊ˲ÄÎÂί ÊÎÌÁ²ÍÀÒÎÐÍί ÎÏÒÈ̲ÇÀÖ²¯:
ÑÓ×ÀÑÍÈÉ ÑÒÀÍ ² ÏÅÐÑÏÅÊÒÈÂÈ
Àíîòàö³ÿ. Ðîçãëÿíóòî êëàñ çàäà÷ åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿ ÿê
çàäà÷ äèñêðåòíî¿ îïòèì³çàö³¿ íà ìíîæèí³ êîìá³íàòîðíèõ êîíô³ãóðàö³é,
â³äîáðàæåí³é â àðèôìåòè÷íèé åâêë³ä³â ïðîñò³ð. Íàâåäåíî îãëÿä ñó÷àñíèõ
ìåòîä³â åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. Îïèñàíî âëàñòèâîñò³ â³äïîâ³äíèõ
îáðàç³â êîìá³íàòîðíèõ ìíîæèí. Çàïðîïîíîâàíî òåîð³þ íåïåðåðâíèõ
ôóíêö³îíàëüíèõ ïðåäñòàâëåíü ³ îïóêëèõ ïðîäîâæåíü äëÿ ðîçâ'ÿçàííÿ çàçíà-
÷åíîãî êëàñó çàäà÷. Âèçíà÷åíî ñôåðè ïðàêòè÷íîãî çàñòîñóâàííÿ òà ïåðñïåê-
òèâí³ íàïðÿìêè äîñë³äæåíü.
Êëþ÷îâ³ ñëîâà: êîìá³íàòîðíà êîíô³ãóðàö³ÿ, åâêë³äîâà êîìá³íàòîðíà ìíîæè-
íà, åâêë³äîâ³ ìîäåë³, îïòèì³çàö³ÿ.
Yu.G. Stoyan, S.V. Yakovlev
THEORY AND METHODS OF EUCLIDIAN COMBINATORIAL OPTIMIZATION:
CURRENT STATE AND PROSPECTS
Abstract. Euclidean combinatorial optimization problems are considered as
discrete optimization problems on a set of combinatorial configurations mapped
into an arithmetic Euclidean space. Modern methods of Euclidean combinatorial
optimization are overviewed. The properties of the corresponding images of
combinatorial sets are described. A theory of continuous functional
representations and convex extensions is proposed for solving this class of
problems. Areas of practical application and promising research areas are
indicated.
Keywords: combinatorial configuration, Euclidean combinatorial set, Euclidean
models, optimization.
Còîÿí Þðèé Ãðèãîðüåâè÷,
÷ë.-êîð. ÍÀÍ Óêðàèíû, äîêòîð òåõí. íàóê, çàâåäóþùèé îòäåëîì Èíñòèòóòà ïðîáëåì ìàøèíîñòðîåíèÿ
èì. À.Í. Ïîäãîðíîãî ÍÀÍ Óêðàèíû, Õàðüêîâ.
ßêîâëåâ Ñåðãåé Âñåâîëîäîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð êàôåäðû Íàöèîíàëüíîãî àýðîêîñìè÷åñêîãî óíèâåðñèòåòà
èì. Í.Å. Æóêîâñêîãî «Õàðüêîâñêèé àâèàöèîííûé èíñòèòóò», e-mail: svsyak7@gmail.com.
46 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
|
| id | nasplib_isofts_kiev_ua-123456789-190377 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T18:37:00Z |
| publishDate | 2020 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стоян, Ю.Г. Яковлев, С.В. 2023-06-04T16:56:12Z 2023-06-04T16:56:12Z 2020 Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы / Ю.Г. Стоян, С.В. Яковлев // Кибернетика и системный анализ. — 2020. — Т. 56, № 3. — С. 30–46. — Бібліогр.: 119 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190377 519.85 Рассмотрен класс задач евклидовой комбинаторной оптимизации как задач дискретной оптимизации на множестве комбинаторных конфигураций, отображенном в арифметическое евклидово пространство. Дан обзор современных методов евклидовой комбинаторной оптимизации. Описаны свойства соответствующих образов комбинаторных множеств. Предложена теория непрерывных функциональных представлений и выпуклых продолжений для решения указанного класса задач. Отмечены области практического приложения и перспективные направления исследований. Розглянуто клас задач евклідової комбінаторної оптимізації як задач дискретної оптимізації на множині комбінаторних конфігурацій, відображеній в арифметичний евклідів простір. Наведено огляд сучасних методів евклідової комбінаторної оптимізації. Описано властивості відповідних образів комбінаторних множин. Запропоновано теорію неперервних функціональних представлень і опуклих продовжень для розв'язання зазначеного класу задач. Визначено сфери практичного застосування та перспективні напрямки досліджень. Euclidean combinatorial optimization problems are considered as discrete optimization problems on a set of combinatorial configurations mapped into an arithmetic Euclidean space. Modern methods of Euclidean combinatorial optimization are overviewed. The properties of the corresponding images of combinatorial sets are described. A theory of continuous functional representations and convex extensions is proposed for solving this class of problems. Areas of practical application and promising research areas are indicated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы Теорія і методи евклідової комбінаторної оптимізації: сучасний стан і перспективи Theory and methods of Euclidian combinatorial optimization: current state and prospects Article published earlier |
| spellingShingle | Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы Стоян, Ю.Г. Яковлев, С.В. Системний аналіз |
| title | Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы |
| title_alt | Теорія і методи евклідової комбінаторної оптимізації: сучасний стан і перспективи Theory and methods of Euclidian combinatorial optimization: current state and prospects |
| title_full | Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы |
| title_fullStr | Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы |
| title_full_unstemmed | Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы |
| title_short | Теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы |
| title_sort | теория и методы евклидовой комбинаторной оптимизации: современное состояние и перспективы |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/190377 |
| work_keys_str_mv | AT stoânûg teoriâimetodyevklidovoikombinatornoioptimizaciisovremennoesostoânieiperspektivy AT âkovlevsv teoriâimetodyevklidovoikombinatornoioptimizaciisovremennoesostoânieiperspektivy AT stoânûg teoríâímetodievklídovoíkombínatornoíoptimízacíísučasniistaníperspektivi AT âkovlevsv teoríâímetodievklídovoíkombínatornoíoptimízacíísučasniistaníperspektivi AT stoânûg theoryandmethodsofeuclidiancombinatorialoptimizationcurrentstateandprospects AT âkovlevsv theoryandmethodsofeuclidiancombinatorialoptimizationcurrentstateandprospects |