Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок
Рассмотрена задача на множестве перестановок с квадратичной функцией цели и дополнительными линейными ограничениями. Предложен метод решения сформулированной задачи, который включает два этапа. На первом этапе находится множество опорных решений. Составляется квадратичная функция для соответствующей...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2020 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/190366 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок / Г.А. Донец, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и системный анализ. — 2020. — Т. 56, № 2. — С. 129–140. — Бібліогр.: 27 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859655576581046272 |
|---|---|
| author | Донец, Г.А. Колечкина, Л.Н. Нагорная, А.Н. |
| author_facet | Донец, Г.А. Колечкина, Л.Н. Нагорная, А.Н. |
| citation_txt | Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок / Г.А. Донец, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и системный анализ. — 2020. — Т. 56, № 2. — С. 129–140. — Бібліогр.: 27 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Рассмотрена задача на множестве перестановок с квадратичной функцией цели и дополнительными линейными ограничениями. Предложен метод решения сформулированной задачи, который включает два этапа. На первом этапе находится множество опорных решений. Составляется квадратичная функция для соответствующей транспозиции и формируются подзадачи с дополнительными ограничениями. При их решении находится множество опорных решений, удовлетворяющих ограничениям основной задачи. Второй этап заключается в нахождении оптимального решения из подмножества оптимальных решений и множества допустимых решений.
Розглянуто задачу на множині перестановок з квадратичною функцією цілі і додатковими лінійними обмеженнями. Запропоновано метод розв'язання сформульованої задачі, який складається з двох етапів. На першому етапі здійснюється знаходження множини опорних розв’язків. Складається квадратична функція для відповідної транспозиції і формуються підзадачі з додатковими обмеженнями. Для їхнього розв’язання знаходять множину опорних розв’язків, що задовольняє обмеження основної задачі. Другий етап полягає в знаходженні оптимального розв’язку з підмножини оптимальних розв'язків і множини допустимих розв’язків.
The problem with a quadratic objective function and additional linear constraints is considered on the set of permutations. A solution method is proposed, which consists of two stages. At the first stage, the set of support solutions is found. A quadratic function is composed for the corresponding transposition and sub-problems are generated with additional constraints. A set of supporting solutions that satisfy the constraints of the main problem can be found in the course of their solution. The second stage is to find the optimal solution from the subset of optimal solutions and the set of feasible solutions.
|
| first_indexed | 2025-12-07T13:38:50Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Ã.À. ÄÎÍÅÖ, Ë.Í. ÊÎËÅ×ÊÈÍÀ, À.Í. ÍÀÃÎÐÍÀß
ÌÅÒÎÄ ÐÅØÅÍÈß ÇÀÄÀ×È ÓÑËÎÂÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Ñ ÊÂÀÄÐÀÒÈ×ÍÎÉ ÔÓÍÊÖÈÅÉ ÖÅËÈ
ÍÀ ÌÍÎÆÅÑÒÂÅ ÏÅÐÅÑÒÀÍÎÂÎÊ
Àííîòàöèÿ. Ðàññìîòðåíà çàäà÷à íà ìíîæåñòâå ïåðåñòàíîâîê ñ êâàäðàòè÷íîé
ôóíêöèåé öåëè è äîïîëíèòåëüíûìè ëèíåéíûìè îãðàíè÷åíèÿìè. Ïðåäëîæåí
ìåòîä ðåøåíèÿ ñôîðìóëèðîâàííîé çàäà÷è, êîòîðûé âêëþ÷àåò äâà ýòàïà. Íà
ïåðâîì ýòàïå íàõîäèòñÿ ìíîæåñòâî îïîðíûõ ðåøåíèé. Ñîñòàâëÿåòñÿ êâàäðà-
òè÷íàÿ ôóíêöèÿ äëÿ ñîîòâåòñòâóþùåé òðàíñïîçèöèè è ôîðìèðóþòñÿ ïîäçà-
äà÷è ñ äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè. Ïðè èõ ðåøåíèè íàõîäèòñÿ ìíî-
æåñòâî îïîðíûõ ðåøåíèé, óäîâëåòâîðÿþùèõ îãðàíè÷åíèÿì îñíîâíîé çàäà-
÷è. Âòîðîé ýòàï çàêëþ÷àåòñÿ â íàõîæäåíèè îïòèìàëüíîãî ðåøåíèÿ èç
ïîäìíîæåñòâà îïòèìàëüíûõ ðåøåíèé è ìíîæåñòâà äîïóñòèìûõ ðåøåíèé.
Êëþ÷åâûå ñëîâà: óñëîâíàÿ îïòèìèçàöèÿ, êâàäðàòè÷íàÿ ôóíêöèÿ, ìíîæå-
ñòâî ïåðåñòàíîâîê, òðàíñïîçèöèÿ ýëåìåíòîâ, ïðèðîñò ôóíêöèè, ïðèðîñò
îãðàíè÷åíèÿ, ìíîæåñòâî äîïóñòèìûõ ðåøåíèé, ìíîæåñòâî îïîðíûõ ðåøå-
íèé, îïòèìàëüíîå ðåøåíèå.
ÂÂÅÄÅÍÈÅ
Ìíîãèå ïðèêëàäíûå çàäà÷è, ìîäåëèðóåìûå ýêñòðåìàëüíûìè äèñêðåòíûìè çà-
äà÷àìè, ÷àñòî èìåþò âûñîêóþ ðàçìåðíîñòü, ïîýòîìó îíè äîâîëüíî ñëîæíû ñ
âû÷èñëèòåëüíîé òî÷êè çðåíèÿ. Îñîáîå ìåñòî â äèñêðåòíîé îïòèìèçàöèè çàíè-
ìàþ çàäà÷è íà êîìáèíàòîðíûõ ìíîæåñòâàõ.
 îáùåì ñëó÷àå çàäà÷à êîìáèíàòîðíîé îïòèìèçàöèè — ýòî çàäà÷à î ìàêñè-
ìèçàöèè èëè ìèíèìèçàöèè ôóíêöèè ïðè çàäàííûõ îãðàíè÷åíèÿõ è ïðè óñëîâèè,
÷òî íà íåêîòîðûå (èëè äàæå íà âñå) ïåðåìåííûå íàëàãàþò òðåáîâàíèå öåëî÷èñ-
ëåííîñòè. Çàäà÷à êîìáèíàòîðíîé îïòèìèçàöèè øèðîêî èñïîëüçóåòñÿ íà
ïðàêòèêå, îäíàêî ìíîãèå âàæíûå çàäà÷è ñ òåîðåòè÷åñêîé è ïðàêòè÷åñêîé òî÷åê
çðåíèÿ ÿâëÿþòñÿ NP-ïîëíûìè. Ýòî îçíà÷àåò, ÷òî äëÿ íèõ íåèçâåñòíî è, ñêîðåå
âñåãî, íå ñóùåñòâóåò ïîëèíîìèàëüíûõ àëãîðèòìîâ ðåøåíèÿ. Ââèäó óêàçàííûõ
ïðè÷èí àêòóàëüíà ïðîáëåìà óìåíüøåíèÿ âðåìåíè ðàáîòû àëãîðèòìîâ ðåøåíèÿ
òðóäíîðàçðåøèìûõ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè, â ÷àñòíîñòè ñîêðàùåíèå
ìíîæåñòâà äîïóñòèìûõ ðåøåíèé â íåêîòîðûõ ìåòîäàõ (âåòâåé è ãðàíèö, îòñå÷å-
íèé, äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ è ìíîãèõ äðóãèõ).
Ïîýòîìó âîçíèêàåò íåîáõîäèìîñòü â ðàçðàáîòêå íàèáîëåå ýôôåêòèâíûõ
àëãîðèòìîâ, îñíîâàííûõ íà ñïåöèôè÷åñêèõ ñâîéñòâàõ êîìáèíàòîðíûõ ìíîæåñòâ.
Ñëåäîâàòåëüíî, îäíîé èç âàæíûõ ïðîáëåì â îáëàñòè äèñêðåòíîé îïòèìèçàöèè
ÿâëÿåòñÿ âûÿâëåíèå ñâîéñòâ êîìáèíàòîðíûõ ìíîæåñòâ â ýêñòðåìàëüíûõ çàäà÷àõ,
èñïîëüçîâàíèå êîòîðûõ ïîçâîëèëî áû óñòàíîâèòü ðåãóëÿðíîñòü èçìåíåíèÿ çíà÷å-
íèé öåëåâûõ ôóíêöèé â çàâèñèìîñòè îò ïîðÿäêà àðãóìåíòîâ, ñïåöèôèêè è
ñòðóêòóðû êîìáèíàòîðíûõ ìíîæåñòâ.
 íàñòîÿùåå âðåìÿ ïîëó÷åíû ïîëîæèòåëüíûå ðåçóëüòàòû â îáëàñòè èññëåäî-
âàíèÿ ðàçëè÷íûõ êëàññîâ êîìáèíàòîðíûõ ìîäåëåé è ðàçðàáîòêè íîâûõ ìåòîäîâ
èõ ðåøåíèÿ [1–11]. Ôóíäàìåíòàëüíûé âêëàä â ðàçâèòèå äèñêðåòíîé, â ÷àñòíîñòè
êîìáèíàòîðíîé, îïòèìèçàöèè âíåñëè ìíîãèå çàðóáåæíûå ó÷åíûå: Ì. Ãýðè,
Ñ. Áåðãå, Ä. Äæîíñîí, Õ. Ïàïàäèìèòðèó, Ï. Ïàðäàëîñ, Ê. Ñòàéãëèõ, Ð. Ñòýíëè,
Ô. Õàðàðè, Â.À. Åìåëè÷åâ, Â.Ì. Ñà÷êîâ [12–17].  ñâîþ î÷åðåäü, ðàáîòû ìíîãèõ
óêðàèíñêèõ ó÷åíûõ (Ë.Ô. Ãóëÿíèöêèé, Ï.È. Ñòåöþê, È.Â. Ñåðãèåíêî, Í.Ñ. Øîð,
Þ.Ã. Ñòîÿí, Ñ.Â. ßêîâëåâ, Î.A. Åìåö, Â.Î. Ïåðåïåëèöà è ìíîãèå äðóãèå) ïîñâÿ-
ùåíû èçó÷åíèþ ðàçëè÷íûõ êëàññîâ ïðîáëåì êîìáèíàòîðíîé îïòèìèçàöèè.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 129
© Ã.À. Äîíåö, Ë.Í. Êîëå÷êèíà, À.Í. Íàãîðíàÿ, 2020
Òàê, â ðàáîòàõ [10, 11, 18–21] àâòîðû èçëàãàþò òåîðèþ âûïóêëûõ ïðîäîëæå-
íèé è åå ïðèëîæåíèÿ â çàäà÷àõ êîìáèíàòîðíîé îïòèìèçàöèè. Ïðèìåíåíèå êîì-
áèíàòîðíûõ ìîäåëåé â ïðàêòè÷åñêèõ çàäà÷àõ îòðàæåíî â ïóáëèêàöèÿõ Ë.Ô. Ãó-
ëÿíèöêîãî, È.Â. Ñåðãèåíêî, Þ.Ã. Ñòîÿíà, Ñ.Â. ßêîâëåâà, Í.Ñ. Øîðà. Çàäà÷è
ñ êâàäðàòè÷íîé ôóíêöèåé öåëè íà ðàçëè÷íûõ êîìáèíàòîðíûõ ìíîæåñòâàõ îïèñà-
íû â ðàáîòàõ [18, 22, 27].
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ çàäà÷à óñëîâíîé îïòèìèçàöèè ñ êâàäðà-
òè÷íîé ôóíêöèåé öåëè íà ìíîæåñòâå ïåðåñòàíîâîê, ïðåäëîæåí ìåòîä ðåøåíèÿ
äàííîé çàäà÷è, îñíîâàííûé íà ñâîéñòâàõ êîìáèíàòîðíîãî ìíîæåñòâà. Ñòàòüÿ ÿâ-
ëÿåòñÿ ïðîäîëæåíèåì ðàáîò [4, 22–25] è ñîñòîèò èç äâóõ ÷àñòåé.  ïåðâîé ÷àñòè
îïèñûâàåòñÿ ïîñòàíîâêà çàäà÷è è åå ñâîéñòâà, âòîðàÿ ÷àñòü ïîñâÿùåíà èçëîæå-
íèþ ìåòîäà ðåøåíèÿ ïîñòàâëåííîé çàäà÷è.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È ÓÑËÎÂÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Ñ ÊÂÀÄÐÀÒÈ×ÍÎÉ ÔÓÍÊÖÈÅÉ ÖÅËÈ ÍÀ ÌÍÎÆÅÑÒÂÅ ÏÅÐÅÑÒÀÍÎÂÎÊ
Ââåäåì íåîáõîäèìûå îïðåäåëåíèÿ [26]. Ïóñòü çàäàíû ìóëüòèìíîæåñòâî
A a a aq� � �{ , }1 2 � , åãî îñíîâàíèå S A e e ek( ) { , }� � �1 2 � , ò.å. íàáîð ðàçëè÷íûõ
ýëåìåíòîâ ìíîæåñòâà, ãäå e Rj � 1 � �j N k , è êðàòíîñòü ýëåìåíòîâ
k e j N qj j k k( ) , ,� � � � � �� � � �1 2 � .
Ìóëüòèìíîæåñòâî B ñ îñíîâàíèåì S B( ) íàçûâàåòñÿ ïîäìóëüòèìíîæåñòâîì
ìóëüòèìíîæåñòâà A ñ îñíîâàíèåì S A( ) , åñëè S B S A( ) ( )� è äëÿ êàæäîãî ýëå-
ìåíòà a S B� ( ) âûïîëíÿåòñÿ íåðàâåíñòâî k a k aB A( ) ( )� .
Óïîðÿäî÷åííîé n-âûáîðêîé èç ìóëüòèìíîæåñòâà A íàçûâàåòñÿ íàáîð
a a a ai i in
� � �( , )
1 2
� , (1)
ãäå a Aij
� � �i Nj n , � � j N i in s t, , åñëè s t s N t Nn n � � � �, .
Îïðåäåëåíèå 1 [26]. Ìíîæåñòâî ïåðåñòàíîâîê ñ ïîâòîðåíèÿìè èç n äåéñòâè-
òåëüíûõ ÷èñåë, ñðåäè êîòîðûõ k ðàçëè÷íûõ, íàçûâàåòñÿ îáùèì ìíîæåñòâîì ïå-
ðåñòàíîâîê è îáîçíà÷àåòñÿ P Ank ( ) . Îíî ÿâëÿåòñÿ ìíîæåñòâîì óïîðÿäî÷åííûõ
n-âûáîðîê âèäà (1) èç ìóëüòèìíîæåñòâà A ïðè óñëîâèè n q k�
.
Îïðåäåëåíèå 2 [26]. Ïðè n q k� � èìååì ìíîæåñòâî ïåðåñòàíîâîê áåç ïîâòî-
ðåíèé Pn . Î÷åâèäíî, ÷òî P A P An nk( ) ( )� .  òåõ ñëó÷àÿõ, êîãäà êîíêðåòíî íå óêà-
çàí âèä ìíîæåñòâà ïåðåñòàíîâîê, ìíîæåñòâà çàïèñûâàþòñÿ êàê Pn . Ýëåìåíòàìè
ìíîæåñòâà ïåðåñòàíîâîê Pn ÿâëÿþòñÿ óïîðÿäî÷åíûå íàáîðû a a a an� � �( , )1 2 � èç
n ñèìâîëîâ. Êàæäûé ñèìâîë âõîäèò â íàáîð òîëüêî îäèí ðàç è ÿâëÿåòñÿ ïðåäñòàâè-
òåëåì ìíîæåñòâà A i Ni n, � .
Îïðåäåëåíèå 3 [4]. Ïåðåñòàíîâêó a a an1 2, � �� íàçûâàþò ëåêñèêîãðàôè÷åñêè
ñëåäóþùåé çà � � � � �a a an1 2, � , åñëè íå ñóùåñòâóåò ïåðåñòàíîâêè �� �� � � ��a a an1 2, � òàêîé,
÷òî ( , ) ( , )� � � � � � �� �� � � ��a a a a a an n1 2 1 2� � è ( , ) ( , )�� �� � � �� � � �a a a a a an n1 2 1 2� � .
Èçâåñòíî [26], ÷òî âûïóêëàÿ îáîëî÷êà ìíîæåñòâà ïåðåñòàíîâîê ÿâëÿåòñÿ
ìíîãîãðàííèêîì ïåðåñòàíîâîê
� conv P A( ) , ìíîæåñòâî âåðøèí P A( ) êîòîðîãî
ðàâíî ìíîæåñòâó ïåðåñòàíîâîê: vert
( ) ( )A P A� . Óïîðÿäî÷èì ýëåìåíòû ìóëü-
òèìíîæåñòâà A â ïîðÿäêå âîçðàñòàíèÿ: a a aq1 2� � �� , à ýëåìåíòû åãî îñíîâà-
íèÿ – â ïîðÿäêå óáûâàíèÿ: e e ek1 2� � �� . Òîãäà âûïóêëàÿ îáîëî÷êà îáùåãî íà-
áîðà ïåðåñòàíîâîê P A( ) ïðåäñòàâëÿåò ñîáîé îáùèé ìíîãîãðàííèê
( ) ( )A P A� conv , êîòîðûé îïèñûâàåòñÿ ñèñòåìîé ëèíåéíûõ íåðàâåíñòâ
x a
x a
j
j
n
j
j
n
j
j
i
j
j
i
� �
� �
� �
� �
�
�
�
�
�
�
�
�
�
1 1
1 1
,
,
�
� � �j n j t i nN j t j t N i N� � � � � �, , , , è P A A( ) ( )� vert
.
130 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
Êîëè÷åñòâî òðàíñïîçèöèé ýëåìåíòîâ êîìáèíàòîðíîãî ìíîæåñòâà â ìíîãî-
ãðàííèêå ïåðåñòàíîâîê îïðåäåëÿåòñÿ ïî ôîðìóëå [24]
C
n n
pn
2 1
2
�
�
�
( )
. (2)
Ðàññìîòðèì îïòèìèçàöèîííóþ çàäà÷ó âèäà
Z P A a a P A( , ( )): { ( ) | ( )}� �extr � ,
êîòîðîå ñîñòîèò â íàõîæäåíèè ýêñòðåìóìà ôóíêöèè �( )a íà eâêëèäîâîì êîì-
áèíàòîðíîì ìíîæåñòâå ïåðåñòàíîâîê.
Îñóùåñòâèì áèåêòèâíîå îòîáðàæåíèå ìíîæåñòâà P An ( ) â ïðîñòðàíñòâî R n ,
ïîñòàâèâ êàæäîìó ýëåìåíòó a Pn� â ñîîòâåòñòâèå âåêòîð x R n� . Îáðàç ìíîæå-
ñòâà P An ( ) îáîçíà÷èì E Rn
n� . Â ðåçóëüòàòå èìååì çàäà÷ó êîìáèíàòîðíîé îïòè-
ìèçàöèè â åâêëèäîâîé ïîñòàíîâêå
Z F E F a X D En n( , ): ( )| }extr{ � � (3)
ñ îãðàíè÷åíèÿìè
D x E R Gx bn
n� � � � �{ | ( ) }, (4)
ãäå
�( ) ( )a F x� ïðè a Pn� , x En� ;
F x c x a x xj j
j
n
ij i j
j
n
i
n
( ) � �
� ��
� ��2
1 11
, (5)
ãäå G R m n� � , b R m� , X — íåïóñòîå ìíîæåñòâî â R n , êîòîðîå îïðåäåëÿåòñÿ
ñëåäóþùèì îáðàçîì:
X A� vert
( ),
� conv P A( ) .
Åñòåñòâåííî ïîëàãàòü, ÷òî ýêñòðåìóì êâàäðàòè÷íîé ôóíêöèè ÿâëÿåòñÿ îäíîé
èç âåðøèí ìíîãîãðàííèêà ïåðåñòàíîâêè, à âåðøèíû ìíîãîãðàííèêà ïåðåñòàíî-
âîê P An ( ) áóäóò ñîâïàäàòü ñ âåðøèíàìè ãðàôà ïåðåñòàíîâîê G Pn( ) [23, 26].
ÌÅÒÎÄ ÐÅØÅÍÈß ÏÎÑÒÀÂËÅÍÍÎÉ ÇÀÄÀ×È
Ðàññìàòðèâàåìûé ìåòîä ïðåäíàçíà÷åí äëÿ ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷
ñ êâàäðàòè÷íîé ôóíêöèåé öåëè íà êîìáèíàòîðíîì ìíîæåñòâå ïåðåñòàíîâîê
è âêëþ÷àåò äâà ýòàïà. Íà ïåðâîì ýòàïå ôîðìèðóåòñÿ ìíîæåñòâî îïîðíûõ ðå-
øåíèé, à íà âòîðîì ýòàïå îñóùåñòâëÿåòñÿ íàõîæäåíèå îïòèìàëüíîãî ðåøåíèÿ.
1. Íàõîæäåíèå ìíîæåñòâà îïîðíûõ ðåøåíèé çàäà÷è
1.1. Ñîñòàâëåíèå çàäà÷ ñ äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè. Äëÿ êàæäîé
òðàíñïîçèöèè ýëåìåíòîâ ìíîæåñòâà ïåðåñòàíîâîê â êîëè÷åñòâå p ñîñòàâëÿåì
êâàäðàòè÷íóþ ôóíêöèþ öåëè (5) â âèäå
F x x a x a x a xij i j ij i ij j k k� � � � �( )( )� .
Îòñþäà ïðè òðàíñïîçèöèè ñîîòâåòñòâóþùèõ ýëåìåíòîâ ìíîæåñòâà ïåðåñòàíî-
âîê ôóíêöèÿ öåëè â êàæäîì ÷àñòíîì ñëó÷àå èìååò âèä
x x i ki1 2� �( , ..., ) ;
x x1 2� : F x x a x a x a xk k12 1 2 12 1 12 2 2� � � � �( )( );�
x x1 3� : F x x a x a x a x a xk k13 1 3 13 1 23 2 13 3 3� � � � �( )( );�
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
x xk1 � : F x x a x a x a xk k k k k k1 1 1 1 2 2 1� � � � �( )( );� (6)
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
x x i kk2 3� �( , ..., ) : F x x a x a x a xk k k k k k2 2 1 1 2 2 2� � � � � � � �( )( );�
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
x xk k� �1 : F x x a x a x a x ak k k k k k kk k k� � � � � �� � � � � � � � � �1 1 1 1 1 2 1 2 1 1( )( � k kx�1 ) .
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 131
Ñîñòàâëÿåì çàäà÷è, äîïîëíèòåëüíûå îãðàíè÷åíèÿ êîòîðûõ ôîðìèðóþòñÿ íà
îñíîâàíèè ôîðìóë (6):
x xk k� �1 : extr F x x a x a x a xk k k k k k kk k� � � � � �� � � � � � � �1 1 1 1 1 2 1 2 1 1( )( � � � �a xkk k1 ) ,
x x
x x
x x
x x
x x
k
k k
1 2
1 3
1
2 3
1
�
�
�
�
�
�
�
( ) ,
( ) ,
( ) ,
( ) ,
( ) .
�
�
�
�
�
�
�
�
�
�
(7)
1.2. Íàõîæäåíèå ìíîæåñòâà îïîðíûõ ðåøåíèé. Ââåäåì ñëåäóþùèå ïîÿñ-
íåíèÿ. Çàäà÷à (3)–(5) ðàññìàòðèâàåòñÿ íà ìíîæåñòâå ïåðåñòàíîâîê P An ( ) ; ñîîò-
âåòñòâåííî äàííîå ìíîæåñòâî ÿâëÿåòñÿ ìíîæåñòâîì äîïóñòèìûõ ðåøåíèé.
Ïðè ðåøåíèè p çàäà÷ âèäà (7) ïîëó÷àåì ìíîæåñòâî òî÷åê Z tr , êîòîðîå ôîð-
ìèðóåòñÿ ïðè ðàññìîòðåíèè òðàíñïîçèöèé ýëåìåíòîâ ìíîæåñòâà P An ( ) :
Z Z Z Z q ptr tr tr
q
tr� � � � �
1 2
1 2� , [ , , ..., ] ,
ãäå Zq
tr — ìíîæåñòâî òî÷åê, êîòîðîå ñôîðìèðîâàëîñü ïðè ðåøåíèè ñîîòâåò-
ñòâóþùåé çàäà÷è âèäà (7).
Åñòåñòâåííî ïîëàãàòü, ÷òî ìíîæåñòâî Z tr ÿâëÿåòñÿ ïîäìíîæåñòâîì ìíîæå-
ñòâà äîïóñòèìûõ ðåøåíèé P An ( ) :
Z P Atr
n� ( ) .
Íà êàæäîì ïîäìíîæåñòâå îñóùåñòâëÿåòñÿ ïðîâåðêà äîïîëíèòåëüíûõ îãðàíè÷å-
íèé çàäà÷è (3)–(5). Ïðè ïðîâåðêå ïåðâîé òî÷êè ìíîæåñòâà ïåðåñòàíîâîê ôîð-
ìèðóåì îãðàíè÷åíèÿ:
� � � � � � ��g x x x x b b
n n1 1
1
2
1
1
1 1
1 1( , , ) ( ) ,
...............
�
...............................
( ,� � � �g x x xi
i i
n
i
1 2 1
� , ) ( ) .x b bn
i
i i� � � �
�
�
�
�
�
Cîñòàâëÿåì íåîáõîäèìûå óñëîâèÿ äëÿ ïðèðîñòîâ îãðàíè÷åíèé:
� � � � � � �g b b b b1 11 11 1 1( ) , ,
...................................
( ) , .� � � � � � �
�
�
�
�� g b b b bi ii ii i i
Ïîñëåäóþùèå òî÷êè ïðîâåðÿþòñÿ ñ èñïîëüçîâàíèåì ôîðìóëû ðàñ÷åòà ïðè-
ðîñòà îãðàíè÷åíèé:
� � �g g g� � �2 1 c x x c x xj i
g
j
g
i j
g
i
g
( ) ( )2 1 2 1� � � . (8)
Äëÿ âû÷èñëåíèÿ ïðèðîñòà öåëåâîé ôóíêöèè �f íóæíî èñïîëüçîâàòü íåîáõîäè-
ìóþ ôîðìóëó öåëåâîé ôóíêöèè â âèäå (6) â çàâèñèìîñòè îò òðàíñïîçèöèè ýëåìåí-
òîâ ìíîæåñòâà â ðàññìàòðèâàåìîé òî÷êå ìíîæåñòâà ïåðåñòàíîâîê â çàäà÷àõ âèäà (7).
Åñëè îãðàíè÷åíèÿ íå âûïîëíÿþòñÿ, íî ïðèðîñòû öåëåâîé ôóíêöèè âîçðàñòà-
þò ïðè ìàêñèìèçàöèè (5) èëè óáûâàþò ïðè ìèíèìèçàöèè (5), òî ïðîâåðêà ïðî-
äîëæàåòñÿ.  ïðîòèâíîì ñëó÷àå íåîáõîäèìî ïåðåéòè ê ñëåäóþùåé çàäà÷å
âèäà (7) ñîãëàñíî òðàíñïîçèöèè ýëåìåíòîâ ìíîæåñòâà ïåðåñòàíîâîê. Òàêæå ñëå-
äóåò îòìåòèòü, ÷òî åñëè îãðàíè÷åíèÿ âûïîëíÿþòñÿ, íî öåëåâàÿ ôóíêöèÿ óáûâàåò
(âîçðàñòàåò) ïðè ìàêñèìèçàöèè (ìèíèìèçàöèè), òî äàëüíåéøàÿ ïðîâåðêà òî÷åê
ìíîæåñòâà òàêæå ïðîäîëæàåòñÿ.
132 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
 ðåçóëüòàòå ðåøåíèÿ çàäà÷ âèäà (7) èìååì ìíîæåñòâî òî÷åê âèäà Z tr :
Z Z Ztr s ns� � ,
ãäå Z Z Z Z q ps s s
q
s� � � � �
1 2
1 2� , [ , , ..., ] , — ìíîæåñòâî òî÷åê, êîòîðûå óäîâëåò-
âîðÿþò îãðàíè÷åíèþ (4); Z Z Z Z q pns ns ns
q
ns� � � � �
1 2
1 2� , [ , , ..., ] , — ìíîæåñò-
âî òî÷åê, êîòîðûå íå óäîâëåòâîðÿþò îãðàíè÷åíèþ (4).
Âîçìîæåí âàðèàíò Z s � 0 , êîãäà íå ñóùåñòâóåò ìíîæåñòâà Z tr òî÷åê, êîòî-
ðûå óäîâëåòâîðÿëè áû (4).  ñëó÷àå Z ns � 0 âñå òî÷êè ìíîæåñòâà Z tr áóäóò óäîâ-
ëåòâîðÿòü (4), (5).
Ïîñêîëüêó çàäà÷à (3)–(5) ðàññìàòðèâàåòñÿ íà ìíîæåñòâå ïåðåñòàíîâîê, òî
íåðàññìîòðåííûå òî÷êè ìíîæåñòâà P An ( ) , êîòîðûå íå ïðèíàäëåæàò Z tr , áóäóò
îáðàçîâûâàòü ìíîæåñòâî äîïóñòèìûõ ðåøåíèé âèäà
Z P A Zcon
n
tr� ( ) \ .
Ìíîæåñòâî Z con ÿâëÿåòñÿ ïîäìíîæåñòâîì P An ( ) ñîîòâåòñòâåííî:
P A Z Zn
tr con( ) � � .
Èç ìíîæåñòâà Z s âûáèðàåòñÿ òî÷êà ýêñòðåìóìà xextr , ïðè êîòîðîé èìååì
extr extrF x( ) . Òîãäà ìíîæåñòâî îïîðíûõ ðåøåíèé Z opr áóäåò ñîñòîÿòü èç ìíîæå-
ñòâà íåðàññìîòðåííûõ òî÷åê Z con è òî÷êè ýêñòðåìóìà:
Z Z xopr con� � extr .
2. ÍÀÕÎÆÄÅÍÈÅ ÎÏÒÈÌÀËÜÍÎÃÎ ÐÅØÅÍÈß
Óïîðÿäî÷èì ìíîæåñòâî îïîðíûõ ðåøåíèé Z opr â ëåêñèêîãðàôè÷åñêîì ïîðÿä-
êå ñîãëàñíî îïðåäåëåíèþ 3. Çàòåì âûáèðàåì òî÷êó xextr è ðàññìàòðèâàåì ïî-
ñëåäîâàòåëüíî âñå òî÷êè ëåêñèêîãðàôè÷åñêè óïîðÿäî÷åííîãî ìíîæåñòâà Z opr ,
êîòîðûå íàõîäÿòñÿ ëåâåå èëè ïðàâåå äàííîé òî÷êè â çàâèñèìîñòè îò ýêñòðåìó-
ìà ôóíêöèè (5). Ñëåäóåò îòìåòèòü, ÷òî çíà÷åíèÿ öåëåâîé ôóíêöèè è îãðàíè÷å-
íèé âû÷èñëÿåòñÿ òîëüêî äëÿ ïåðâîé òî÷êè; äëÿ âñåõ ïîñëåäóþùèõ òî÷åê íåîá-
õîäèìî èñïîëüçîâàòü ôîðìóëû (6), (8).
Åñëè ðàññìàòðèâàåìàÿ òî÷êà ìíîæåñòâà Z opr óäîâëåòâîðÿåò îãðàíè÷åíè-
ÿì (4) è ôóíêöèÿ öåëè âîçðàñòàåò (ïðè ìàêñèìèçàöèè) èëè óáûâàåò (ïðè ìèíèìè-
çàöèè), òî îíà ÿâëÿåòñÿ îïòèìàëüíîé; â ïðîòèâíîì ñëó÷àå ïîèñê îïòèìàëüíîãî
ðåøåíèÿ ïðåêðàùàåòñÿ.
Ñëåäóåò îòìåòèòü, ÷òî åñëè îãðàíè÷åíèÿ (4) íå âûïîëíÿþòñÿ, íî çíà÷åíèå
ôóíêöèè öåëè âîçðàñòàåò ïðè ìàêñèìèçàöèè èëè óáûâàåò ïðè ìèíèìèçàöèè, òî
íåîáõîäèìî îñóùåñòâëÿòü äàëüíåéøèé ïîèñê îïòèìàëüíîãî ðåøåíèÿ. Ïîèñê ïðå-
êðàùåòñÿ òîëüêî â òîì ñëó÷àå, åñëè ôóíêöèÿ öåëè óáûâàåò (âîçðàñòàåò) ïðè âîç-
ðàñòàíèè (óáûâàíèè) è îãðàíè÷åíèÿ (4) íå âûïîëíÿþòñÿ.
Åñëè òî÷êà xextr ïîñëå ëåêñèêîãðàôè÷åñêîãî óïîðÿäî÷åíèÿ çàíèìàåò ïåðâîå
ìåñòî ïðè ìèíèìèçàöèè (4) èëè ïîñëåäíåå ìåñòî ïðè ìàêñèìèçàöèè (4), òî îíà
ÿâëÿåòñÿ îïòèìàëüíûì ðåøåíèåì.
Ðàññìîòðèì àëãîðèòì ðåøåíèÿ íà ïðèìåðå ñëåäóþùåé çàäà÷è.
Ïðèìåð. Íàéòè òî÷êó ìíîæåñòâà ïåðåñòàíîâîê èç ýëåìåíòîâ A = (1, 2, 3, 4),
â êîòîðîé äîñòèãàåòñÿ ìàêñèìàëüíîå çíà÷åíèå ôóíêöèè
max ( ) ( ) ( ) ( )F x x x x x x x x x x� � � � � � � � � �
1
2
2
1
2
21 2 3 4
2
2 3
2
3 2 4
2 2
4
2x
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 133
ïðè îãðàíè÷åíèÿõ
g x x x x
g x x x x
g x
1 1 2 3 4
2 1 2 3 4
3 1
7 2 7
5 2 3 4 15
3 6
� � � � �
� � � � �
� � �
,
,
x x x2 3 48 31� � �
�
�
�
�� .
Ðåøåíèå. Ñîãëàñíî ôîðìóëe (2) êîëè÷åñòâî âîçìîæíûõ òðàíñïîçèöèé ýëå-
ìåíòîâ ìíîæåñòâà ïåðåñòàíîâîê ñîñòàâëÿåò Ñ
4
2 6� .
Ðàññìîòðèì ïåðâóþ òðàíñïîçèöèþ ýëåìåíòîâ ìíîæåñòâà ïåðåñòàíîâîê
x x1 2� , ïðåäñòàâëÿÿ öåëåâóþ ôóíêöèþ â âèäå ïðîèçâåäåíèÿ
f x x x x x x12 1 2 1 2 3 46� � � � �( )( ) ;
ñîîòâåòñòâåííî ïðè ïîèñêå ïåðâîãî ðåøåíèÿ íåîáõîäèìî ó÷åñòü ñëåäóþùèå
óñëîâèÿ:
x x
x
1 2
3
�
�
�
�
,
min.
Ïîäìíîæåñòâî äîïóñòèìûõ ðåøåíèé Zq
tr äëÿ äàííîé òðàíñïîçèöèè ýëåìåíòîâ
èìååò âèä
Z x x x x x x x xtr
12 1 2 4 3 1 4 2 3� �(( , , , ) ( , , , )) .
Ðåøàåì çàäà÷ó, êîòîðàÿ âîçíèêëà ïðè äàííîé òðàíñïîçèöèè ýëåìåíòîâ,
îñóùåñòâëÿÿ ïðîâåðêó òî÷êè ( , , , )x x x x1 2 4 3 = ( , , , )4 3 1 2 : g1 4 3 1 2 25 7( , , , ) � � ,
g2 4 3 1 2 25 15( , , , ) � � , g3 4 3 1 2 12 31( , , , ) � � ; âñå îãðàíè÷åíèÿ âûïîëíÿþòñÿ. Òîãäà
F
12
1 4 3 1 2 40( , , , ) � . Ñîîòâåòñòâåííî äàííàÿ òî÷êà áóäåò ïðèíàäëåæàòü ìíîæåñòâó
òî÷åê, êîòîðûå óäîâëåòâîðÿþò îãðàíè÷åíèÿì çàäà÷è Z s
12
4 3 1 2� ( , , , ) .
Äëÿ ïðîâåðêè ñëåäóþùåé òî÷êè íåîáõîäèìî âûïîëíåíèå óñëîâèé
�g1 18� � , �g2 10� � , �g3 19� .
Âûïîëíèì ïðîâåðêó òî÷êè ( , , , )x x x x1 4 2 3 = ( , , , )4 2 1 3 , èñïîëüçóÿ ôîð-
ìóëó (8) äëÿ îãðàíè÷åíèé:
�g1 4 2 1 3 7 2 3 1 3 2 6( , , , ) ( ) ( )� � � � � � , �g1 4 2 1 3 6 18( , , , ) � � � � ,
ïåðâîå îãðàíè÷åíèå âûïîëíÿåòñÿ;
�g2 4 2 1 3 2 2 3 4 3 2 6( , , , ) ( ) ( )� � � � � , �g2 4 2 1 3 6 10( , , , ) � � � ,
âòîðîå îãðàíè÷åíèå âûïîëíÿåòñÿ;
�g3 4 2 1 3 6 2 3 1 3 2 7( , , , ) ( ) ( )� � � � � � , �g3 4 2 1 3 7 19( , , , ) � � � ,
òðåòüå îãðàíè÷åíèå âûïîëíÿåòñÿ.
Ïîñêîëüêó òî÷êó ( , , , )4 2 1 3 ïîëó÷èëè òðàíñïîçèöèåé ýëåìåíòîâ x x2 4� èç
òî÷êè ( , , , )4 3 1 2 , òî äëÿ íàõîæäåíèÿ ïðèðîñòà öåëåâîé êâàäðàòè÷íîé ôóíêöèè íå-
îáõîäèìî èñïîëüçîâàòü ôîðìóëû (6):
�f x x x x x x24 2 4 2 1 3 4
1
2
8 14� � � � �( )( ) ,
�f 24 4 2 1 3
1
2
2 3 2 8 4 14 1 3 6 5( , , , ) ( )( ) ,� � � � � � � � .
Òîãäà F F f
12
2
12
1
24 40 6 5 46 5� � � � �� , , , ôóíêöèÿ âîçðàñòàåò; ñëåäîâàòåëüíî,
Z ns
12
4 3 1 2 4 2 1 3� �( , , , ) ( , , , ) .
Ðàññìîòðèì ñëåäóþùóþ òðàíñïîçèöèþ ýëåìåíòîâ x x1 3� :
f x x x x x x13 1 3 1 2 3 46 5� � � � �( )( ) ,
134 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
íåîáõîäèìûå óñëîâèÿ:
x x
x
1 3
2
�
�
�
�
,
min.
Ïðè ðàññìîòðåíèè äàííîé òðàíñïîçèöèè ýëåìåíòîâ èìååì
Z x x x x x x x xtr
13 1 3 4 2 1 4 3 2� �( , , , ) ( , , , ) .
Âûïîëíèì ïðîâåðêó òî÷êè ( , , , )x x x x1 3 4 2 = ( , , , )4 1 3 2 : g1 4 1 3 2 7 7( , , , ) � � ,
g2 4 1 3 2 35 15( , , , ) � � , g3 4 1 3 2 16 31( , , , ) � � , îòêóäà ñëåäóåò, ÷òî âñå îãðàíè÷åíèÿ
âûïîëíÿþòñÿ; F
13
1 4 1 3 2 24( , , , ) � . Ñîîòâåòñòâåííî äàííàÿ òî÷êà áóäåò ïðèíàäëå-
æàòü ìíîæåñòâó òî÷åê, êîòîðûå óäîâëåòâîðÿþò îãðàíè÷åíèÿì çàäà÷è
Z s
13
4 1 3 2� ( , , , ) .
Äëÿ ïðîâåðêè ñëåäóþùåé òî÷êè íåîáõîäèìî âûïîëíåíèå óñëîâèé
�g1 0� , �g2 20� � , �g3 15� .
Âûïîëíèì ïðîâåðêó òî÷êè ( , , , )x x x x1 4 3 2 = ( , , , )4 1 2 3 , èñïîëüçóÿ ôîðìóëó (8)
äëÿ îãðàíè÷åíèé (6):
�g1 4 1 2 3 3 0( , , , ) � � , ïåðâîå îãðàíè÷åíèå âûïîëíÿåòñÿ;
�g2 4 1 2 3 1 20( , , , ) � � � , âòîðîå îãðàíè÷åíèå âûïîëíÿåòñÿ;
�g3 4 1 2 3 9 15( , , , ) � � � , òðåòüå îãðàíè÷åíèå âûïîëíÿåòñÿ.
Òî÷êó ( , , , )4 1 2 3 ïîëó÷èëè òðàíñïîçèöèåé ýëåìåíòîâ x x3 4� èç òî÷êè
( , , , )4 1 3 2 . Ïîýòîìó äëÿ íàõîæäåíèÿ ïðèðîñòà öåëåâîé êâàäðàòè÷íîé ôóíêöèè íå-
îáõîäèìî èñïîëüçîâàòü ôîðìóëó èç (6):
�f x x x x x x34 3 4 2 1 3 4
1
2
6 8� � � � �( )( ) ,
�f 34 4 1 2 3
1
2
2 3 6 8 4 2 3 10 5( , , , ) ( )( ) ,� � � � � � � .
Òîãäà F F f
13
2
13
1
24 24 10 5 34 5� � � � �� , , , ôóíêöèÿ âîçðàñòàåò; ñëåäîâàòåëüíî,
Z ns
13
4 1 3 2 4 1 2 3� �( , , , ) ( , , , ) .
Ðàññìàòðèâàåì ñëåäóþùóþ òðàíñïîçèöèþ ýëåìåíòîâ x x1 4� :
f x x x x x x14 1 4 1 2 3 4
1
2
3 6 2 3� � � � �( )( ) ,
íåîáõîäèìûå óñëîâèÿ:
x x
x
1 4
2
�
�
�
�
,
min .
Òîãäà Z x x x x x x x x Ztr tr
14 1 3 4 2 1 4 3 2 13
� � �(( , , , ) ( , , , )) , ïîýòîìó íåò íåîáõîäèìî-
ñòè ðàññìàòðèâàòü äàííóþ çàäà÷ó.
Ðàññìîòðèì òðàíñïîçèöèþ ýëåìåíòîâ x x2 3� : f x x x23 2 3 44� �( ) ; ñîîòâåò-
ñòâåííî ïðè ïîèñêå ïåðâîãî ðåøåíèÿ íåîáõîäèìî ó÷èòûâàòü åäèíñòâåííîå óñëî-
âèå: x x2 3
.
Ìíîæåñòâî òî÷åê ïðè ðàññìîòðåíèè äàííîé òðàíñïîçèöèè èìååò âèä
Z x x x x x x x x x x x xtr
23 1 2 3 4 1 2 4 3 2 1 3 4� � � �(( , , , ) ( , , , ) ( , , , )
� � � �( , , , ) ( , , , ) ( , , , )x x x x x x x x x x x x2 1 4 3 2 3 1 4 2 3 4 1
� �( , , , ) ( , , , ))x x x x x x x x2 4 3 1 2 4 1 3 .
Âûïîëíèì ïðîâåðêó òî÷êè ( , , , )x x x x1 2 3 4 = ( , , , )4 3 2 1 : g1 4 3 2 1 22 7( , , , ) � � ,
g2 4 3 2 1 24 15( , , , ) � � , g3 4 3 2 1 21 31( , , , ) � � , âñå îãðàíè÷åíèÿ âûïîëíÿþòñÿ;
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 135
F
23
1 4 3 2 1 34 5( , , , ) ,� . Ñîîòâåòñòâåííî äàííàÿ òî÷êà áóäåò ïðèíàäëåæàòü ìíîæåñòâó
òî÷åê, êîòîðûå óäîâëåòâîðÿþò îãðàíè÷åíèÿì çàäà÷è Z s
23
4 3 2 1� ( , , , ) .
Äëÿ ïðîâåðêè ñëåäóþùåé òî÷êè íåîáõîäèìî âûïîëíåíèå óñëîâèé
�g1 15� � , �g2 9� � , �g3 10� . Ïîñêîëüêó òî÷êà ( , , , )x x x x Z tr
1 2 4 3 12
� , òî íåò íå-
îáõîäèìîñòè â åå ðàññìîòðåíèè.
Âûïîëíèì ïðîâåðêó òî÷êè ( , , , )x x x x2 1 3 4 = ( , , , )3 4 2 1 , èñïîëüçóÿ ôîð-
ìóëó (8) äëÿ îãðàíè÷åíèé �g1 3 4 2 1 6 15( , , , ) � � � , �g2 3 4 2 1 7 9( , , , ) � � � � ,
�g3 3 4 2 1 9 10( , , , ) � � , îãðàíè÷åíèÿ âûïîëíÿþòñÿ. Òîãäà �g1 3 4 2 1 21( , , , ) � � ,
�g2 3 4 2 1 2( , , , ) � � , �g3 3 4 2 1 1( , , , ) � .
Òî÷êó ( , , , )3 4 2 1 ïîëó÷èëè òðàíñïîçèöèåé ýëåìåíòîâ x x2 4� èç òî÷êè
( , , , )4 3 2 1 . Ïîýòîìó äëÿ íàõîæäåíèÿ ïðèðîñòà öåëåâîé êâàäðàòè÷íîé ôóíêöèè íå-
îáõîäèìî èñïîëüçîâàòü ôîðìóëó èç (6):
�f x x x x x x12 1 2 1 2 3 46� � � � �( )( ) , �f12 3 4 2 1 3 4 3 4 6 2 1 4( , , , ) ( )( )� � � � � � � .
Òîãäà F F f
23
2
13
1
12 34 5 4 38 5� � � � �� , , , ôóíêöèÿ âîçðàñòàåò; ñëåäîâàòåëüíî,
Z s
23
4 3 2 1 3 4 2 1� �( , , , ) ( , , , ) .
Âûïîëíèì ïðîâåðêó òî÷êè ( , , , )x x x x2 1 4 3 = ( , , , )3 4 1 2 ñ èñïîëüçîâàíèåì ôîð-
ìóëû (8) äëÿ îãðàíè÷åíèé �g1 3 4 1 2 3 21( , , , ) � � � , �g2 3 4 1 2 1 2( , , , ) � � � ,
�g3 3 4 1 2 9 1( , , , ) � � � ; îãðàíè÷åíèÿ âûïîëíÿþòñÿ. Ñîîòâåòñòâåííî �g1 3 4 1 2 24( , , , ) � � ,
�g2 3 4 1 2 3( , , , ) � � , �g3 3 4 1 2 10( , , , ) � .
Òî÷êó ( , , , )3 4 1 2 ïîëó÷èëè òðàíñïîçèöèåé ýëåìåíòîâ x x3 4� èç òî÷êè
( , , , )4 3 2 1 . Ïîýòîìó äëÿ íàõîæäåíèÿ ïðèðîñòà öåëåâîé êâàäðàòè÷íîé ôóíêöèè íå-
îáõîäèìî èñïîëüçîâàòü ôîðìóëó èç (6):
�f x x x x x x34 3 4 2 1 3 4
1
2
6 8� � � � �( )( ),
�f 34 3 4 1 2
1
2
1 2 6 4 8 3 1 2 1 5( , , , ) ( )( ) ,� � � � � � � � � .
Òîãäà F F f
23
3
13
2
34 38 5 1 5 37� � � � �� , , ; ôóíêöèÿ óáûâàåò, íî âñå îãðàíè÷åíèÿ
âûïîëíÿþòñÿ, ïîýòîìó íåîáõîäèìî ïðîäîëæàòü èññëåäîâàíèå:
Z s
23
4 3 2 1 3 4 2 1 3 4 1 2� � �( , , , ) ( , , , ) ( , , , ) .
Äëÿ òî÷êè ( , , , )x x x x2 3 1 4 = ( , , , )2 4 3 1 ñ èñïîëüçîâàíèåì ôîðìóëû (8) èìååì
�g1 2 4 3 1 3 21( , , , ) � � � � , �g2 2 4 3 1 2 2( , , , ) � � � � , �g3 2 4 3 1 11 1( , , , ) � � ; ïîñëåäíåå
îãðàíè÷åíèå íå âûïîëíÿåòñÿ. Òîãäà �g1 2 4 3 1 18( , , , ) � � , �g2 2 4 3 1 0( , , , ) � ,
�g3 2 4 3 1 10( , , , ) � � .
Òî÷êó ( , , , )2 4 3 1 ïîëó÷èëè òðàíñïîçèöèåé ýëåìåíòîâ x x1 3� èç òî÷êè
( , , , )3 4 2 1 . Ïîýòîìó äëÿ íàõîæäåíèÿ ïðèðîñòà öåëåâîé êâàäðàòè÷íîé ôóíêöèè íå-
îáõîäèìî èñïîëüçîâàòü ôîðìóëó èç (6):
�f x x x x x x13 1 3 1 2 3 46 5� � � � �( )( ), �f13 2 3 2 6 4 3 5 1 14� � � � � � � �( )( ) .
Òîãäà F F f
23
4
23
2
13 38 5 14 52 5� � � � �� , , , ôóíêöèÿ âîçðàñòàåò, íî ïîñëåäíåå
îãðàíè÷åíèå íå âûïîëíÿåòñÿ, ïîýòîìó äàííàÿ òî÷êà ïðèíàäëåæèò ìíîæåñòâó
Z ns
23
2 4 3 1� ( , , , ) .
Äëÿ òî÷êè ( , , , )x x x x2 3 4 1 = ( , , , )1 4 3 2 èìååì �g1 1 4 3 2 0 18( , , , ) � � � ,
�g2 1 4 3 2 1 0( , , , ) � � � , âòîðîå îãðàíè÷åíèå íå âûïîëíÿåòñÿ.
Òî÷êó ( , , , )1 4 3 2 ïîëó÷èëè òðàíñïîçèöèåé ýëåìåíòîâ x x1 4� èç òî÷êè
( , , , )2 4 3 1 . Ïîýòîìó äëÿ íàõîæäåíèÿ ïðèðîñòà öåëåâîé êâàäðàòè÷íîé ôóíêöèè íå-
îáõîäèìî èñïîëüçîâàòü ñëåäóþùóþ ôîðìóëó èç (6):
�f x x x x x x14 1 4 1 2 3 4
1
2
3 6 2 3� � � � �( )( ) , �f14
1
2
1 2 3 1 6 4 2 3 3 2 4 5� � � � � � � � � �( )( ) , .
136 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
Òîãäà F F f
23
5
23
4
14 52 5 4 5 57� � � � �� , , ; ôóíêöèÿ âîçðàñòàåò, íî âòîðîå îãðàíè-
÷åíèå íå âûïîëíÿåòñÿ, ïîýòîìó äàííàÿ òî÷êà ïðèíàäëåæèò ìíîæåñòâó
Z ns
23
2 4 3 1 1 4 3 2� �( , , , ) ( , , , ) .
Âûïîëíèì ïðîâåðêó òî÷êè ( , , , )x x x x2 4 3 1 = ( , , , )1 4 2 3 ; èìååì �g1 1 4 2 3( , , , ) �
� � �0 21, �g2 1 4 2 3 2 2( , , , ) � � � � , �g3 1 4 2 3 4 1( , , , ) � � , òðåòüå îãðàíè÷åíèå íå
âûïîëíÿåòñÿ.
Òî÷êó ( , , , )1 4 2 3 ïîëó÷èëè òðàíñïîçèöèåé ýëåìåíòîâ x x1 4� èç òî÷êè
( , , , )3 4 2 1 . Ïîýòîìó äëÿ íàõîæäåíèÿ ïðèðîñòà öåëåâîé êâàäðàòè÷íîé ôóíêöèè íå-
îáõîäèìî èñïîëüçîâàòü ñëåäóþùóþ ôîðìóëó èç (6):
�f x x x x x x14 1 4 1 2 3 4
1
2
3 6 2 3� � � � �( )( ) , �f14
1
2
1 3 3 1 6 4 2 2 3 3 8� � � � � � � � � �( )( ) .
Òîãäà F F f
23
6
23
2
14 38 5 8 46 5� � � � �� , , ; ôóíêöèÿ âîçðàñòàåò, íî òðåòüå îãðàíè-
÷åíèå íå âûïîëíÿåòñÿ, ïîýòîìó äàííàÿ òî÷êà ïðèíàäëåæèò ìíîæåñòâó
Z ns
23
2 4 3 1 1 4 3 2 1 4 2 3� � �( , , , ) ( , , , ) ( , , , ) .
Ïîñêîëüêó â òî÷êå ( , , , )x x x x2 4 3 1 = ( , , , )1 4 2 3 òðåòüå îãðàíè÷åíèå íå âûïîë-
íÿåòñÿ è ôóíêöèÿ öåëè óáûâàåò, òî íåò íåîáõîäèìîñòè ðàññìàòðèâàòü òî÷êó
( , , , )x x x x2 4 1 3 .
Ñîñòàâèì ñëåäóþùóþ òðàíñïîçèöèþ ýëåìåíòîâ x x2 4� :
f x x x x x x24 2 4 2 1 3 4
1
2
8 14� � � � �( )( ) ;
íåîáõîäèìûå óñëîâèÿ:
x x
x
2 4
1
�
�
�
�
,
min.
Òîãäà Z x x x x x x x x Ztr tr
24 2 4 3 1 2 3 4 1 23
� � �(( , , , ) ( , , , )) , ïîýòîìó íåò íåîáõîäèìî-
ñòè ðàññìàòðèâàòü äàííóþ ïîäçàäà÷ó.
Ñîñòàâèì òðàíñïîçèöèþ ýëåìåíòîâ x x3 4� :
f x x x x x x34 3 4 2 1 3 4
1
2
6 8� � � � �( )( ) ;
íåîáõîäèìûå óñëîâèÿ:
x x
x
3 4
1
�
�
�
�
,
min.
Òîãäà Z x x x x x x x xtr
34 3 4 2 1 3 2 4 1� �(( , , , ) ( , , , )).
Âûïîëíèì ïðîâåðêó òî÷êè ( , , , )x x x x3 4 2 1 = ( , , , )1 2 4 3 ; èìååì �g1 1 2 4 3( , , , ) �
� � �9 12, �g2 1 2 4 3 6 4( , , , ) � � � � ; âòîðîå îãðàíè÷åíèå íå âûïîëíÿåòñÿ. Òî÷êó
( , , , )1 2 4 3 ïîëó÷èëè ïóòåì òðàíñïîçèöèè ýëåìåíòîâ x x1 3� èç òî÷êè ( , , , )4 2 1 3 :
�f x x x x x x13 1 3 1 2 3 46 5� � � � �( )( ), �f13 1 4 1 12 4 15 24� � � � � � �( )( ) .
Òîãäà F F f
34
7
12
2
13 46 5 24 22 5� � � � �� , , ; ïîñêîëüêó ôóíêöèÿ öåëè óáûâàåò è
âòîðîå îãðàíè÷åíèå íå âûïîëíÿåòñÿ, òî íåò íåîáõîäèìîñòè ðàññìàòðèâàòü òî÷-
êó ( , , , )x x x x3 2 4 1 . Ñîîòâåòñòâåííî îáå òî÷êè ïðèíàäëåæàò ìíîæåñòâó
Z ns
34
1 2 4 3 1 3 4 2� �( , , , ) ( , , , ) .
 ðåçóëüòàòå ðåøåíèÿ øåñòè çàäà÷ ïîëó÷àåì ñëåäóþùèå ìíîæåñòâà:
Z Z Z Z Z Z Zs s s s s s s� � � � � �
12 13 14 23 24 34
.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 137
Òàê êàê Z Z Zns ns ns
14 24 34
� � � �, òî
Z Z Z Zs s s s� � � � � � �
12 13 23
4 3 1 2 4 2 1 3 4 1 3 2 4( , , , ) ( , , , ) ( , , , ) ( , , , )1 2 3 ,
Z Z Z Z Z Z Zns ns ns ns ns ns ns� � � � � �
12 13 14 23 24 34
.
Ïîñêîëüêó Z Z Z Zns ns ns ns
12 13 14 24
� � � � � , òî
Z Z Zns ns ns� � � � � �
23 34
2 4 3 1 1 4 3 2 1 4 2 3 1 2( , , , ) ( , , , ) ( , , , ) ( , , , ) ( , , , )4 3 1 3 4 2� .
Èç ìíîæåñòâà Z s âûáèðàåì òî÷êó x � ( , , , )4 2 1 3 , â êîòîðîé öåëåâàÿ ôóíêöèÿ
ïðèíèìàåò ìàêñèìàëüíîå çíà÷åíèå max ( , , , ) ,F 4 2 1 3 46 5� .
Ïîñêîëüêó Z Z Ztr s ns� � è Z P A Zcon
n
tr� ( ) \ , òî ìíîæåñòâî îïîðíûõ ðåøå-
íèé èìååò âèä Z Z xopr con� � .
Óïîðÿäî÷èì òî÷êè ìíîæåñòâà Z opr â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå, òîãäà
ñëåäóþùåé ïîñëå òî÷êè x � ( , , , )4 2 1 3 áóäåò òî÷êà x � ( , , , )4 2 3 1 .
Òî÷êà ( , , , )4 2 3 1 ïîëó÷åíà òðàíñïîçèöèåé ýëåìåíòîâ x x3 4� èç òî÷êè
( , , , )4 2 1 3 :
�f x x x x x x34 3 4 2 1 3 4
1
2
6 8� � � � �( )( ) ,
�f 34 4 2 3 1
1
2
3 21 6 2 8 4 3 1 16( , , , ) ( )( )� � � � � � � � � .
Òîãäà F F f
34
8
12
2
34 46 5 16 30 5� � � � �� , , . Ïîñêîëüêó ôóíêöèÿ öåëè óáûâàåò è
ñîãëàñíî ëåêñèêîãðàôè÷åñêîãî ïîðÿäêà íå ñóùåñòâóåò òî÷åê, çíà÷åíèÿ êîòî-
ðûõ áîëüøå x � ( , , , )4 2 1 3 , òî òî÷êà x � ( , , , )4 2 1 3 áóäåò îïòèìàëüíûì ðåøåíèåì.
Òàêèì îáðàçîì, ïîëó÷èëè max ( , , , ) ,F 4 2 1 3 46 5� .
ÇÀÊËÞ×ÅÍÈÅ
Èññëåäîâàíà çàäà÷à íà ìíîæåñòâå ïåðåñòàíîâîê ñ êâàäðàòè÷íîé ôóíêöèåé öåëè
è äîïîëíèòåëüíûìè ëèíåéíûìè îãðàíè÷åíèÿìè. Ïðåäëîæåí ìåòîä ðåøåíèÿ
ñôîðìóëèðîâàííîé çàäà÷è, êîòîðûé âêëþ÷àåò äâà ýòàïà. Íà ïåðâîì ýòàïå àëãî-
ðèòìà íàõîäèòñÿ ìíîæåñòâî îïîðíûõ ðåøåíèé. Ñîñòàâëÿåòñÿ êâàäðàòè÷íàÿ
ôóíêöèÿ äëÿ ñîîòâåòñòâóþùåé òðàíñïîçèöèè ýëåìåíòîâ ìíîæåñòâà ïåðåñòàíî-
âîê è ôîðìèðóþòñÿ çàäà÷è ñ äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè. Êîëè÷åñòâîì
òðàíñïîçèöèé ìíîæåñòâà ïåðåñòàíîâîê ýëåìåíòîâ îïðåäåëÿåòñÿ ÷èñëî çàäà÷.
 ðåçóëüòàòå ðåøåíèÿ íàõîäèòñÿ ìíîæåñòâî îïîðíûõ ðåøåíèé, óäîâëåòâîðÿþ-
ùèõ îãðàíè÷åíèÿì îñíîâíîé çàäà÷è. Ñëåäóåò ó÷èòûâàòü, ÷òî ïðîâåðêå ïîäëå-
æèò ëèøü ïåðâàÿ òî÷êè ìíîæåñòâà ïåðåñòàíîâîê, à ïîñëåäóþùèå òî÷êè ïðîâå-
ðÿþòñÿ ñ èñïîëüçîâàíèåì ôîðìóëû ðàñ÷åòà ïðèðîñòîâ îãðàíè÷åíèé �g è öåëå-
âîé ôóíêöèè �f . Ìíîæåñòâî îïîðíûõ ðåøåíèé âêëþ÷àåò òî÷êó ìíîæåñòâà
äîïóñòèìûõ ðåøåíèé ïðè ðàññìîòðåíèè òðàíñïîçèöèè ýëåìåíòîâ, êîòîðàÿ îáåñïå÷èâà-
åò ýêñòðåìàëüíîå çíà÷åíèå êâàäðàòè÷íîé öåëåâîé ôóíêöèè, è âñå òî÷êè ìíî-
æåñòâà ïåðåñòàíîâîê, êîòîðûå íå áûëè ðàññìîòðåíû â çàäà÷àõ âèäà (7).
Íà âòîðîì ýòàïå îñóùåñòâëÿåòñÿ ëåêñèêîãðàôè÷åñêîå óïîðÿäî÷åíèå ìíî-
æåñòâà îïîðíûõ ðåøåíèé è ïðîâîäèòñÿ ïðîâåðêà òîëüêî òåõ òî÷åê, êîòîðûå áîëü-
øå ýêñòðåìàëüíîé òî÷êè (ïðè ìàêñèìèçàöèè öåëåâîé êâàäðàòè÷íîé ôóíêöèè)
èëè ìåíüøå ýêñòðåìàëüíîé òî÷êè (ïðè ìèíèìèçàöèè).  ñòàòüå ðàññìîòðåí ÷èñ-
ëîâîé ïðèìåð ðåàëèçàöèè äàííîãî ìåòîäà.
Äàëüíåéøåå èññëåäîâàíèå áóäåò íàïðàâëåíî íà ðàññìîòðåíèå çàäà÷ ñ äðóãè-
ìè âèäàìè öåëåâûõ ôóíêöèé è íà äðóãèõ êîìáèíàòîðíûõ ìíîæåñòâàõ
ñ óâåëè÷åíèåì èõ ìîùíîñòè.
138 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Gulianitsky L.F., Sergienko I.V. Meta-evolutionary method of deformed polyhedron in
combinatorial optimization. Cybernetics and Systems Analysis. 2007. Vol. 44, N 6. Ð. 70–79.
2. Äîíåö Ã.À., Ñåðãèåíêî È.Â. Ìåòîä ìîäåëèðîâàíèÿ ñòðóêòóðû èñõîäíûõ äàííûõ è ïîäêëàññû
ðàçðåøàåìûõ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2014.
Ò. 50, ¹ 1. Ñ. 3–11.
3. Shor N.Z., Stetsyuk P.I. Lagrangian bounds in multiextremal polynomial and discrete optimization
problems. Journal of Global Optimization. 2002. N 23. P. 1–41.
4. Äîíåöü Ã.Ï., Êîëº÷ê³íà Ë.Ì. Åêñòðåìàëüí³ çàäà÷³ íà êîìá³íàòîðíèõ êîíô³ãóðàö³ÿõ. Ïîëòàâà:
ÏÓÅÒ, 2011. 362 ñ.
5. Ñåìåíîâà Í.Â., Êîëº÷ê³íà Ë.Ì. Âåêòîðí³ çàäà÷³ äèñêðåòíî¿ îïòèì³çàö³¿ íà êîìá³íàòîðíèõ
êîíô³ãóðàö³ÿõ: ìåòîäè äîñë³äæåííÿ òà ðîçâ’ÿçàííÿ. Êè¿â: Íàóê. äóìêà, 2009. 266 ñ.
6. Koliechkina L.N., Dvirna O.A. Solving extremum problems with linear fractional objective functions
on the combinatorial configuration of permutations under multicriteriality. Cybernetics and Systems
Analysis. 2017. Vol. 53, N 4. P. 590–599.
7. Koliechkina L., Pichugina O. Multiobjective optimization on permutations with applications. destech
transactions on computer science and engineering, 2018. P. 61–75. https://doi.org/10.12783/
dtcse/optim2018/27922.
8. Korte B., Vygen J. Combinatorial optimization: Theory and Algorithms. Heidelberg; New York:
Springer, 2012. 660 p.
9. 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.
10. 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.
11. Yakovlev S. Convex extensions in combinatorial optimization and their applications. Optimization
and Applications. P. Pardalos, S. Butenco, V. Shilo (Eds.). New York: Springer, 2017. P. 501–517.
12. Chase P. Transposition graphs. SIAM Journal on Computing. 1973. Vol. 2, N 2. P. 128–133.
https://doi.org/10.1137/0202011.
13. Ehrgott M. Multicriteria Optimization. Berlin; New York: Springer, 2005. 315 p.
14. Ehrgott M., Gandibleux X. Multiobjective combinatorial optimization — theory, methodology, and
applications. M. Ehrgott, X. Gandibleux (Eds.). Multiple Criteria Optimization: State of the Art
Annotated Bibliographic Surveys. 2003. Vol. 52. P. 369–444. Springer US. https://doi.org/
10.1007/0-306-48107-3_8.
15. Ganesan A. Automorphism group of the complete transposition graph. Journal of Algebraic
Combinatorics. 2015. Vol. 42, N 3. P. 793–801. https://doi.org/10.1007/s10801-015-0602-5.
16. Onwubolu G.C., Davendra D. Differential evolution: A handbook for global permutation–based
combinatorial optimization. Berlin; Heidelberg: Springer-Verlag, 2009. 213 p.
17. Pardalos P.M., Du D., Graham R.L. Handbook of combinatorial optimization. New York: Springer,
2013. 648 p.
18. Stoyan Y.G., Yakovlev S.V., Parshin O.V. Quadratic optimization on combinatorial sets in Rn.
Cybernetics and Systems Analysis. 1991. Vol. 27, N 4. Ð. 561–567.
19. ßêîâëåâ Ñ.Â., Ãèëü Í.È., Êîìÿê Â.Ì., Àðèñòîâà Í.Â. Ýëåìåíòû òåîðèè ãåîìåòðè÷åñêîãî ïðî-
åêòèðîâàíèÿ. Êè¿â: Íàóê. äóìêà, 1995. 241 ñ.
20. ϳ÷óã³íà Î.Ñ. Ìåòîä ïîáóäîâè îïóêëèõ ïðîäîâæåíü êâàäðàòíèõ ïîë³íîì³â íà êîìá³íàòîðíèõ
ìíîæèíàõ. ³ñíèê ÆÄÒÓ. Òåõí³÷í³ íàóêè. 2010. Ò. 53, ¹ 2. Ñ. 141–150.
21. Semenova N.V., Kolechkina L.N. A polyhedral approach to solving multicriterion combinatorial
optimization problems over sets of polyarrangements. Cybernetics and Systems Analysis. 2009.
Vol. 45, N 3. P. 438–445.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2 139
22. Koliechkina L., Nahirna A., Dvirna O. Quadratic optimization problem on permutation set with
simulation of applied tasks. Proceedings of the Second International Workshop on Computer Modeling
and Intelligent Systems (CMIS-2019). Zaporizhzhia, Ukraine, April 15–19, 2019. P. 651–663 (CEUR
Workshop Proceedings, Vol. 2353). URL: http://ceur-ws.org/Vol-2353/paper52.pdf.
23. Donets G.A., Kolechkina L.N. Method of ordering the values of a linear function on a set of
permutations. Cybernetics and Systems Analysis. 2009. Vol. 45, N 2, P. 204–213.
24. Donec G.A., Kolechkina L.M. Construction of Hamiltonian paths in graphs of permutation
polyhedra. Cybernetics and Systems Analysis. 2010. Vol. 46, N 1. P. 7–13.
25. Koliechkina L.N., Dvernaya O.A., Nagornaya A.N. Modified coordinate method to solve
multicriteria optimization problems on combinatorial configurations. Cybernetics and Systems
Analysis. 2014. Vol. 50, N 4. P. 620–626.
26. Ñòîÿí Þ.Ã., ªìåöü Î.Î. Òåîð³ÿ ³ ìåòîäè åâêë³äîâî¿ êîìá³íàòîðíî¿ îïòèì³çàö³¿. Êè¿â: ²íñòèòóò
ñèñòåìíèõ äîñë³äæåíü îñâ³òè, 1993. 188 ñ.
27. Burkard R.E. Quadratic assignment problems. P.M. Pardalos, D.-Z. Du, R.L Graham (Eds.).
Handbook of combinatorial optimization. New York: Springer, 2013. P. 2741–2814.
https://doi.org/10.1007/978-1-4419-7997-1_22.
Íàä³éøëà äî ðåäàêö³¿ 25.10.2019
Ã.Ï. Äîíåöü, Ë.Ì. Êîëº÷ê³íà, À.Ì. Íàã³ðíà
ÌÅÒÎÄ ÐÎÇÂ’ßÇÓÂÀÍÍß ÇÀÄÀײ ÓÌÎÂÍί ÎÏÒÈ̲ÇÀÖ²¯ Ç ÊÂÀÄÐÀÒÈ×ÍÎÞ
ÔÓÍÊÖ²ªÞ ֲ˲ ÍÀ ÌÍÎÆÈͲ ÏÅÐÅÑÒÀÍÎÂÎÊ
Àíîòàö³ÿ. Ðîçãëÿíóòî çàäà÷ó íà ìíîæèí³ ïåðåñòàíîâîê ç êâàäðàòè÷íîþ
ôóíêö³ºþ ö³ë³ ³ äîäàòêîâèìè ë³í³éíèìè îáìåæåííÿìè. Çàïðîïîíîâàíî ìåòîä
ðîçâ'ÿçàííÿ ñôîðìóëüîâàíî¿ çàäà÷³, ÿêèé ñêëàäàºòüñÿ ç äâîõ åòàï³â. Íà ïåð-
øîìó åòàï³ çä³éñíþºòüñÿ çíàõîäæåííÿ ìíîæèíè îïîðíèõ ðîçâ’ÿçê³â. Ñêëà-
äàºòüñÿ êâàäðàòè÷íà ôóíêö³ÿ äëÿ â³äïîâ³äíî¿ òðàíñïîçèö³¿ ³ ôîðìóþòüñÿ
ï³äçàäà÷³ ç äîäàòêîâèìè îáìåæåííÿìè. Äëÿ ¿õíüîãî ðîçâ’ÿçàííÿ çíàõîäÿòü
ìíîæèíó îïîðíèõ ðîçâ’ÿçê³â, ùî çàäîâîëüíÿº îáìåæåííÿ îñíîâíî¿ çàäà÷³.
Äðóãèé åòàï ïîëÿãຠâ çíàõîäæåíí³ îïòèìàëüíîãî ðîçâ’ÿçêó ç ï³äìíîæèíè
îïòèìàëüíèõ ðîç’ÿçê³â ³ ìíîæèíè äîïóñòèìèõ ðîçâ’ÿçê³â.
Êëþ÷îâ³ ñëîâà: óìîâíà îïòèì³çàö³ÿ, êâàäðàòè÷íà ôóíêö³ÿ, ìíîæèíà ïåðåñòà-
íîâîê, òðàíñïîçèö³ÿ åëåìåíò³â, ïðèð³ñò ôóíêö³¿, ïðèð³ñò îáìåæåííÿ, ìíîæèíà
äîïóñòèìèõ ðîçâ'ÿçê³â, ìíîæèíà îïîðíèõ ðîçâ'ÿçê³â, îïòèìàëüíèé ðîçâ’ÿçîê.
G.P. Donets, L.M. Koliechkina, A.M. Nahirna
A METHOD TO SOLVE THE CONDITIONAL OPTIMIZATION PROBLEM WITH
A QUADRATIC OBJECTIVE FUNCTION ON THE SET OF PERMUTATIONS
Abstract. The problem with a quadratic objetive function and additional linear
constraints is considered on the set of permutations. A solution method is
proposed, which consists of two stages. At the first stage, the set of support
solutions is found. A quadratic function is composed for the corresponding
transposition and sub-problems are generated with additional constraints. A set
of supporting solutions that satisfy the constraints of the main problem can be
found in the course of their solution. The second stage is to find the optimal
solution from the subset of optimal solutions and the set of feasible solutions.
Keywords: conditional optimization, quadratic function, set of permutations,
transposition of elements, increase in function, increase in constraint, set of
feasible solutions, set of support solutions, optimal solution.
Äîíåö Ãåîðãèé Àôàíàñüåâè÷,
äîêòîð ôèç.-ìàò. íàóê, çàâåäóþùèé îòäåëîì Èíñòèòóòà êèáåðíåòèêè èìåíè Â.Ì. Ãëóøêîâà, Êèåâ.
Êîëå÷êèíà Ëþäìèëà Íèêîëàåâíà,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð Ëîäçèíñêîãî óíèâåðñèòåòà, Ïîëüøà,
e-mail: liudmyla.koliechkina@wmii.uni.lodz.pl; lkoliechkina@gmail.com
Íàãîðíàÿ Àëëà Íèêîëàåâíà,
äîöåíò êàôåäðû Íàöèîíàëüíîãî óíèâåðñèòåòà «Êèåâî-Ìîãèëÿíñêàÿ àêàäåìèÿ», Êèåâ,
e-mail: naghirnaalla@ukr.net.
140 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 2
|
| id | nasplib_isofts_kiev_ua-123456789-190366 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T13:38:50Z |
| publishDate | 2020 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донец, Г.А. Колечкина, Л.Н. Нагорная, А.Н. 2023-06-03T13:21:10Z 2023-06-03T13:21:10Z 2020 Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок / Г.А. Донец, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и системный анализ. — 2020. — Т. 56, № 2. — С. 129–140. — Бібліогр.: 27 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190366 519.85 Рассмотрена задача на множестве перестановок с квадратичной функцией цели и дополнительными линейными ограничениями. Предложен метод решения сформулированной задачи, который включает два этапа. На первом этапе находится множество опорных решений. Составляется квадратичная функция для соответствующей транспозиции и формируются подзадачи с дополнительными ограничениями. При их решении находится множество опорных решений, удовлетворяющих ограничениям основной задачи. Второй этап заключается в нахождении оптимального решения из подмножества оптимальных решений и множества допустимых решений. Розглянуто задачу на множині перестановок з квадратичною функцією цілі і додатковими лінійними обмеженнями. Запропоновано метод розв'язання сформульованої задачі, який складається з двох етапів. На першому етапі здійснюється знаходження множини опорних розв’язків. Складається квадратична функція для відповідної транспозиції і формуються підзадачі з додатковими обмеженнями. Для їхнього розв’язання знаходять множину опорних розв’язків, що задовольняє обмеження основної задачі. Другий етап полягає в знаходженні оптимального розв’язку з підмножини оптимальних розв'язків і множини допустимих розв’язків. The problem with a quadratic objective function and additional linear constraints is considered on the set of permutations. A solution method is proposed, which consists of two stages. At the first stage, the set of support solutions is found. A quadratic function is composed for the corresponding transposition and sub-problems are generated with additional constraints. A set of supporting solutions that satisfy the constraints of the main problem can be found in the course of their solution. The second stage is to find the optimal solution from the subset of optimal solutions and the set of feasible solutions. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок Метод розв’язування задачі умовної оптимізації з квадратичною функцією цілі на множині перестановок A method to solve the conditional optimization problem with a quadratic objective function on the set of permutations Article published earlier |
| spellingShingle | Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок Донец, Г.А. Колечкина, Л.Н. Нагорная, А.Н. Системний аналіз |
| title | Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок |
| title_alt | Метод розв’язування задачі умовної оптимізації з квадратичною функцією цілі на множині перестановок A method to solve the conditional optimization problem with a quadratic objective function on the set of permutations |
| title_full | Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок |
| title_fullStr | Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок |
| title_full_unstemmed | Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок |
| title_short | Метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок |
| title_sort | метод решения задачи условной оптимизации с квадратичной функцией цели на множестве перестановок |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/190366 |
| work_keys_str_mv | AT donecga metodrešeniâzadačiuslovnoioptimizaciiskvadratičnoifunkcieicelinamnožestveperestanovok AT kolečkinaln metodrešeniâzadačiuslovnoioptimizaciiskvadratičnoifunkcieicelinamnožestveperestanovok AT nagornaâan metodrešeniâzadačiuslovnoioptimizaciiskvadratičnoifunkcieicelinamnožestveperestanovok AT donecga metodrozvâzuvannâzadačíumovnoíoptimízacíízkvadratičnoûfunkcíêûcílínamnožiníperestanovok AT kolečkinaln metodrozvâzuvannâzadačíumovnoíoptimízacíízkvadratičnoûfunkcíêûcílínamnožiníperestanovok AT nagornaâan metodrozvâzuvannâzadačíumovnoíoptimízacíízkvadratičnoûfunkcíêûcílínamnožiníperestanovok AT donecga amethodtosolvetheconditionaloptimizationproblemwithaquadraticobjectivefunctiononthesetofpermutations AT kolečkinaln amethodtosolvetheconditionaloptimizationproblemwithaquadraticobjectivefunctiononthesetofpermutations AT nagornaâan amethodtosolvetheconditionaloptimizationproblemwithaquadraticobjectivefunctiononthesetofpermutations |