Структура группы Парето в задаче многокритериальной оптимизации
Розглянуто проблему вибору за наявності багатьох критеріїв. Запропоновано розв’язання цієї проблеми на основі вимоги інваріантості розв’язку щодо певної групи перетворень. Досліджуються групи перетворень лінійного простору, що зберігають порядок Парето на цьому просторі. З точністю до ізоморфізму гр...
Gespeichert in:
| Datum: | 2010 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/45632 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Структура группы Парето в задаче многокритериальной оптимизации / И.В. Козин // Кибернетика и системный анализ. — 2010. — № 5. — С. 132-136. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-45632 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-456322013-06-17T03:17:28Z Структура группы Парето в задаче многокритериальной оптимизации Козин, И.В. Системный анализ Розглянуто проблему вибору за наявності багатьох критеріїв. Запропоновано розв’язання цієї проблеми на основі вимоги інваріантості розв’язку щодо певної групи перетворень. Досліджуються групи перетворень лінійного простору, що зберігають порядок Парето на цьому просторі. З точністю до ізоморфізму груп обчислено максимальну групу таких перетворень. Розглянуто найцікавіші дискретні й безперервні підгрупи групи Парето. A multicriteria choice problem is considered. It is offered to solve this problem on the basis of the requirement of invariance of the solution with respect to a certain group of transformations. Groups of transformations of a linear space that preserve the Pareto order in this space. are investigated The maximal group of such transformations is calculated to within isomorphism of groups. The most interesting discrete and continuous subgroups of the Pareto group are considered. 2010 Article Структура группы Парето в задаче многокритериальной оптимизации / И.В. Козин // Кибернетика и системный анализ. — 2010. — № 5. — С. 132-136. — Бібліогр.: 8 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/45632 519.876.2 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Козин, И.В. Структура группы Парето в задаче многокритериальной оптимизации Кибернетика и системный анализ |
| description |
Розглянуто проблему вибору за наявності багатьох критеріїв. Запропоновано розв’язання цієї проблеми на основі вимоги інваріантості розв’язку щодо певної групи перетворень. Досліджуються групи перетворень лінійного простору, що зберігають порядок Парето на цьому просторі. З точністю до ізоморфізму груп обчислено максимальну групу таких перетворень. Розглянуто найцікавіші дискретні й безперервні підгрупи групи Парето. |
| format |
Article |
| author |
Козин, И.В. |
| author_facet |
Козин, И.В. |
| author_sort |
Козин, И.В. |
| title |
Структура группы Парето в задаче многокритериальной оптимизации |
| title_short |
Структура группы Парето в задаче многокритериальной оптимизации |
| title_full |
Структура группы Парето в задаче многокритериальной оптимизации |
| title_fullStr |
Структура группы Парето в задаче многокритериальной оптимизации |
| title_full_unstemmed |
Структура группы Парето в задаче многокритериальной оптимизации |
| title_sort |
структура группы парето в задаче многокритериальной оптимизации |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2010 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/45632 |
| citation_txt |
Структура группы Парето в задаче многокритериальной оптимизации / И.В. Козин // Кибернетика и системный анализ. — 2010. — № 5. — С. 132-136. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT koziniv strukturagruppyparetovzadačemnogokriterialʹnojoptimizacii |
| first_indexed |
2025-07-04T04:30:05Z |
| last_indexed |
2025-07-04T04:30:05Z |
| _version_ |
1836689299006816256 |
| fulltext |
ÓÄÊ 519.876.2
È.Â. ÊÎÇÈÍ
ÑÒÐÓÊÒÓÐÀ ÃÐÓÏÏÛ ÏÀÐÅÒÎ Â ÇÀÄÀ×Å
ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Êëþ÷åâûå ñëîâà: ìíîãîêðèòåðèàëüíàÿ çàäà÷à, ìíîæåñòâî Ïàðåòî, ýôôåêòèâ-
íûå ïðàâèëà, ãðóïïà ïðåîáðàçîâàíèé.
ÂÂÅÄÅÍÈÅ
Ïðè ìîäåëèðîâàíèè áîëüøèíñòâà ñëîæíûõ òåõíè÷åñêèõ, ñîöèàëüíî-ýêîíîìè÷åñ-
êèõ, îðãàíèçàöèîííûõ ñèòóàöèé è ïðîöåññîâ, êàê ïðàâèëî, íå óäàåòñÿ ïîñòðîèòü
åäèíûé ñêàëÿðíûé êðèòåðèé êà÷åñòâà. Ñîîòâåòñòâóþùèå ìîäåëè èññëåäóþòñÿ
â ðàìêàõ òåîðèè ìíîãîêðèòåðèàëüíûõ çàäà÷ — àêòèâíî ðàçâèâàþùåãîñÿ íàïðàâ-
ëåíèÿ òåîðèè ïðèíÿòèÿ ðåøåíèé [1, 2]. Â óñëîâèÿõ ìíîãîêðèòåðèàëüíîé îïòèìè-
çàöèè ðåøåíèå äîëæíî ïðèíèìàòüñÿ íà îñíîâå îïòèìèçàöèè âåêòîðíîãî êðèòå-
ðèÿ F x F x F x F x X Rn
n( ) ( ( ), ( ),... , ( )) :� �1 2 , ãäå F x R Ri ( ) : ,1 1� i n�1 2, ,... , ,
n � 2. Âåêòîðíûé êðèòåðèé ïîðîæäàåò îòíîøåíèå ïîðÿäêà �F íà ìíîæåñòâå X .
À èìåííî: áóäåì ïîëàãàòü, ÷òî x yF� â òîì è òîëüêî â òîì ñëó÷àå, êîãäà
F x F yi i( ) ( )� , i n�1 2, ,... , . Ýòî îòíîøåíèå ïîðÿäêà, âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ
ëèíåéíûì ïðè n � 2. Ñëåäîâàòåëüíî, ìíîæåñòâî îïòèìàëüíûõ ðåøåíèé çàäà÷è
ìîæåò ñîñòîÿòü èç íåñðàâíèìûõ ïî âåêòîðíîìó êðèòåðèþ ýëåìåíòîâ. Ìíîæåñòâî
îïòèìàëüíûõ ðåøåíèé çàäà÷è ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè íàçûâàåòñÿ ìíî-
æåñòâîì Ïàðåòî. Îäíàêî è ñàì âûáîð âåêòîðíîãî êðèòåðèÿ íåîäíîçíà÷åí. Èçâåñ-
òíî, ÷òî äëÿ îäíîêðèòåðèàëüíûõ çàäà÷ êðèòåðèé îïðåäåëåí ñ òî÷íîñòüþ äî ïðîèç-
âîëüíîé ìîíîòîííîé ôóíêöèè. Âîçíèêàåò âîïðîñ: êàêîâà ñâîáîäà âûáîðà êðèòå-
ðèÿ äëÿ çàäà÷ âåêòîðíîé îïòèìèçàöèè?
Òàêàÿ ñâîáîäà õàðàêòåðèçóåòñÿ îïðåäåëåííûìè ïðåîáðàçîâàíèÿìè êðèòåðèàëü-
íîãî ïðîñòðàíñòâà R n , ïðè êîòîðûõ ìíîæåñòâî Ïàðåòî ðàññìàòðèâàåìîé îïòèìèçà-
öèîííîé çàäà÷è îñòàåòñÿ íåèçìåííûì. Ýòè ïðåîáðàçîâàíèÿ îáðàçóþò ãðóïïó
îòíîñèòåëüíî îïåðàöèè ñóïåðïîçèöèè.
Èíâàðèàíòíîñòü îòíîñèòåëüíî äåéñòâèÿ ãðóïïû ïðåîáðàçîâàíèé îçíà÷àåò íà-
ëè÷èå îïðåäåëåííûõ ñâîéñòâ ñèììåòðèè â êðèòåðèàëüíîì ïðîñòðàíñòâå. Íàñòîÿùàÿ
ðàáîòà ïîñâÿùåíà èññëåäîâàíèþ ýòèõ ñâîéñòâ è ìåõàíèçìîâ ïðèíÿòèÿ ðåøåíèé,
îáëàäàþùèõ ñâîéñòâàìè ñèììåòðèè.
ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÛÉ ÂÛÁÎÐ. ÝÔÔÅÊÒÈÂÍÎÑÒÜ ÏÐÀÂÈË
ÏÐÈÍßÒÈß ÐÅØÅÍÈÉ
Ðàññìîòðèì çàäà÷ó ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè [3, 4], ïðè÷åì äëÿ ïðîñòîòû
áóäåì ñ÷èòàòü, ÷òî ìíîæåñòâî X , íà êîòîðîì âåäåòñÿ ïîèñê ðåøåíèÿ, ñîâïàäàåò
ñ êðèòåðèàëüíûì ïðîñòðàíñòâîì F X( ) , ò.å. X R n� è çàäà÷à ñîñòîèò â îïòèìèçà-
öèè êàæäîé èç êîîðäèíàò íà ìíîæåñòâå X , xi � max, i n� �1 2, , , . Îòíîøåíèå ïî-
ðÿäêà � íà R n , ïîðîæäàåìîå òîæäåñòâåííûì îòîáðàæåíèåì, íàçîâåì êàíîíè÷åñ-
êèì îòíîøåíèåì ïîðÿäêà, èëè ïîðÿäêîì Ïàðåòî.
Íàïîìíèì, ÷òî òî÷êà x x x x Xn
� � � �� ( , , .... , )1 2 íàçûâàåòñÿ ïàðåòî-îïòèìàëüíîé
(ýôôåêòèâíîé), åñëè íå ñóùåñòâóåò âî ìíîæåñòâå X òî÷êè, ïðåâîñõîäÿùåé x� ïî
âñåì êðèòåðèÿì, ò.å. íå ñóùåñòâóåò òî÷êè x x x x Xn� ( , ,... , )1 2 òàêîé, ÷òî x x
� è
x xi i
� � , i n�1 2, ,... , . Ìíîæåñòâî âñåõ ýôôåêòèâíûõ òî÷åê íàçûâàåòñÿ ìíîæåñòâîì
Ïàðåòî ðàññìàòðèâàåìîé çàäà÷è.
132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
© È.Â. Êîçèí, 2010
Ïðàâèëî ïðèíÿòèÿ ðåøåíèé íàçûâàåòñÿ ýôôåêòèâíûì, åñëè ðåøåíèÿ, êîòîðûå
ïðèíèìàþòñÿ â ñîîòâåòñòâèè ñ ýòèì ïðàâèëîì íà ìíîæåñòâå X , ÿâëÿþòñÿ ïàðå-
òî-îïòèìàëüíûìè.
ÌÀÊÑÈÌÀËÜÍÀß ÃÐÓÏÏÀ ÏÎÐßÄÊÀ ÏÀÐÅÒÎ
Ãðóïïîé íàçûâàåòñÿ [5] ìíîæåñòâî G, íà êîòîðîì îïðåäåëåíà áèíàðíàÿ îïåðàöèÿ
«�», îáëàäàþùàÿ ñëåäóþùèìè ñâîéñòâàìè:
à) � � � � � �s t G s t s t, , ) ( )� � �( — àññîöèàòèâíîñòü;
á) � � 1 G s G s s s� � � �1 1 — íàëè÷èå íåéòðàëüíîãî (åäèíè÷íîãî) ýëåìåíòà;
â) � �
s G s G1 s s s s� � � �
1 1 1 — íàëè÷èå îáðàòíîãî ýëåìåíòà.
Âñå îáðàòèìûå ïðåîáðàçîâàíèÿ � ïðîñòðàíñòâà R n îáðàçóþò ãðóïïó îòíîñè-
òåëüíî îïåðàöèè ñóïåðïîçèöèè. Íåéòðàëüíûì (åäèíè÷íûì) ýëåìåíòîì ýòîé ãðóïïû
ñëóæèò òîæäåñòâåííîå ïðåîáðàçîâàíèå id ( )x x� � x R n . Ïîäìíîæåñòâî ïðåîáðà-
çîâàíèé, çàìêíóòîå îòíîñèòåëüíî îïåðàöèè ñóïåðïîçèöèè è îïåðàöèè îáðàòíîãî
ïðåîáðàçîâàíèÿ, ÿâëÿåòñÿ ïîäãðóïïîé ãðóïïû � . Òàêóþ ïîäãðóïïó íàçîâåì ãðóï-
ïîé ïðåîáðàçîâàíèé.
Îäíèì èç îñíîâíûõ òðåáîâàíèé ê ïðàâèëàì ïðèíÿòèÿ ðåøåíèé â êðèòåðèàëü-
íîì ïðîñòðàíñòâå ÿâëÿåòñÿ èõ ýôôåêòèâíîñòü, èëè ñîãëàñîâàííîñòü ñ êàíîíè÷åñêèì
ïîðÿäêîì Ïàðåòî â R n . Ïðèíöèï ýôôåêòèâíîñòè òðåáóåò âûáîðà ðåøåíèÿ èç ìíî-
æåñòâà Ïàðåòî. Ñîîòâåòñòâåííî â êðèòåðèàëüíîì ïðîñòðàíñòâå äîëæíà âûáèðàòüñÿ
òî÷êà, ïðèíàäëåæàùàÿ îáðàçó ìíîæåñòâà Ïàðåòî (ñëîâî «îáðàç» â äàëüíåéøåì
îïóñêàåòñÿ, îáðàç ìíîæåñòâà Ïàðåòî òàêæå áóäåì íàçûâàòü ìíîæåñòâîì Ïàðåòî).
Ñòðóêòóðà êðèòåðèàëüíîãî ïðîñòðàíñòâà è ìíîæåñòâà Ïàðåòî ìîæåò áûòü âåñüìà
ñëîæíîé. Îäíàêî åñëè ïðè íåêîòîðûõ ïðåîáðàçîâàíèÿõ ïðîñòðàíñòâà ìíîæåñòâî
Ïàðåòî ñîõðàíÿåòñÿ, òî ïðè ýòèõ ïðåîáðàçîâàíèÿõ âûáèðàåìàÿ òî÷êà â êðèòåðèàëü-
íîì ïðîñòðàíñòâå äîëæíà îñòàâàòüñÿ âî ìíîæåñòâå Ïàðåòî. Äðóãèìè ñëîâàìè, âû-
áîð äîëæåí áûòü èíâàðèàíòíûì îòíîñèòåëüíî ïðåîáðàçîâàíèé, êîòîðûå ñîõðàíÿþò
ìíîæåñòâî Ïàðåòî. Òàê êàê ðå÷ü èäåò î ìàññîâîé çàäà÷å, òî ýòî ïðåîáðàçîâàíèÿ,
ñîõðàíÿþùèå êàíîíè÷åñêèé ïîðÿäîê â R n .
Ïðåäñòàâëÿåò èíòåðåñ ìàêñèìàëüíàÿ ïî âêëþ÷åíèþ ãðóïïà G ïðåîáðàçîâàíèé
ïðîñòðàíñòâà R n , êîòîðàÿ ñîõðàíÿåò êàíîíè÷åñêîå îòíîøåíèå ïîðÿäêà � . Ôîðìàëü-
íî ýòî ñâîéñòâî ïðåîáðàçîâàíèé îïèñûâàåòñÿ ñëåäóþùèì ñîîòíîøåíèåì: � g G,
� x y R n, x y g x g y� � � � � . Çäåñü è äàëåå g x� áóäåò îáîçíà÷àòü çíà÷åíèå
îòîáðàæåíèÿ g x( ) .
Òåîðåìà 1. Äëÿ ëþáîãî ïðåîáðàçîâàíèÿ g G , ñîõðàíÿþùåãî îòíîøåíèå ïîðÿä-
êà � íà R n , íàéäóòñÿ äèàãîíàëüíîå îòîáðàæåíèå � � � �( ) ( ( ), ( ), , ( ))x x x xn n� 1 1 2 2 � ,
ãäå �i ix( ) — âîçðàñòàþùèå ôóíêöèè ñîîòâåòñòâóþùèõ êîîðäèíàò, è ïåðåñòàíîâêà êî-
îðäèíàò � �x x x xn( , , , )1 2 � S x x x xi i in
( ) ( , , , )�
1 2
� òàêèå, ÷òî � x Rn g x S x( ) ( ( ))� � .
Äîêàçàòåëüñòâî. Ðàññìîòðèì ãðóïïó ãëàäêèõ ïðåîáðàçîâàíèé, ò.å. òàêèõ ïðå-
îáðàçîâàíèé, êîòîðûå îïèñûâàþòñÿ íåïðåðûâíî äèôôåðåíöèðóåìûì îòîáðàæåíè-
åì ñ íåâûðîæäåííûì ÿêîáèàíîì.
Ðàññìîòðèì ïðîèçâîëüíóþ òî÷êó x x x Rn
n� � ( , , )1 è ïðåîáðàçîâàíèå g G .
Ó÷èòûâàÿ ñâîéñòâà ñîõðàíåíèÿ îòíîøåíèÿ � , ïîëó÷àåì äëÿ ïðîèçâîëüíîãî âåêòîðà
� R n , òàêîãî, ÷òî 0 � �, íåðàâåíñòâî g x g x( ) ( )� � � .
Òàê êàê g g x x g x x g x xn n n n� � � �( ( , , ), ( , , ), , ( , , ))1 1 2 1 1� — äèôôåðåíöèðóå-
ìîå îòîáðàæåíèå, ïîñëåäíåå íåðàâåíñòâî ïðèâîäèò ê âåêòîðíîìó ñîîòíîøåíèþ
0 � � �g x o( ) (|| || )� � ,
ãäå â êà÷åñòâå íîðìû || ||� ìîæíî èñïîëüçîâàòü åâêëèäîâó íîðìó íà R n . Çäåñü
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 133
�g x( ) îáîçíà÷åíà ìàòðèöà ßêîáè ïðåîáðàçîâàíèÿ g ,
� �
�
�
�
�
�
�
�
�
�
�
�
g x
g x
x
g x
x
g x
x
g x
x
n
n
n
n
( )
( ) ( )
( ) ( )
1
1 1
1
�
� � �
�
�
�
�
��
�
�
�
�
�
�
��
.
Ïîñëåäíåå íåðàâåíñòâî ñïðàâåäëèâî äëÿ ëþáîãî âåêòîðà � ñ íåîòðèöàòåëüíûìè
êîîðäèíàòàìè. Ó÷èòûâàÿ òî, ÷òî �— ïðîèçâîëüíûé âåêòîð ñ íåîòðèöàòåëüíûìè êîîð-
äèíàòàìè, ïðèõîäèì ê âûâîäó, ÷òî 0 � �g x( ) . Ïîñêîëüêó îáðàòíîå îòîáðàæåíèå g x
1 ( )
òàêæå ïðèíàäëåæèò ãðóïïå, ñïðàâåäëèâî íåðàâåíñòâî 0 1�
( ) ( )g x' . Îáîçíà÷èì
a
g x
x
ij
i
j
�
�
�
( )
ýëåìåíòû ìàòðèöû ßêîáè îòîáðàæåíèÿ g , à Aij — ýëåìåíòû ìàòðèöû
ßêîáè îáðàòíîãî ïðåîáðàçîâàíèÿ g x
1 ( ) . Ìàòðèöà ( )Aij ÿâëÿåòñÿ îáðàòíîé ê ìàò-
ðèöå ( )aij , ïîýòîìó ñïðàâåäëèâî ñîîòíîøåíèå
a Aik ik ij
k
n
�
�
� �
1
, ãäå � ij
i j
i j
�
�
�
�
�
1
0
ïðè
ïðè
,
.
Òàê êàê ýëåìåíòû ìàòðèö aij è Aij íåîòðèöàòåëüíû, ïîñëåäíåå ñîîòíîøåíèå
ïðèâîäèò ê ñèñòåìå ðàâåíñòâ
a Aik kj � 0 � �i j k n, , , , ,1 2 � , i j
.
Ïðåäïîëîæèì, ÷òî Akj
0 äëÿ íåêîòîðîé ïàðû èíäåêñîâ k j, . Òîãäà èç ïðèâå-
äåííûõ âûøå ðàâåíñòâ âûòåêàåò, ÷òî a
ik
� 0 � � �i n1 2, , , è i j
, ò.å. â ñòîëáöå
ñ íîìåðîì k ìàòðèöû ßêîáè íåò íåíóëåâûõ ýëåìåíòîâ êðîìå ýëåìåíòà a jk . Ïîñêîëü-
êó ìàòðèöà ( )Aij îáðàòíàÿ ê ìàòðèöå ßêîáè ( )aij , òî è A
ki
� 0� � �i n1 2, , , , i j
.
Òàêèì îáðàçîì, ìàòðèöà ßêîáè ïðåîáðàçîâàíèÿ g, ñîõðàíÿþùåãî îòíîøåíèå ïî-
ðÿäêà � íà R n , èìååò âèä
�
�
�
g x
x
a xi
j
i iki
( )
( )� , ãäå ( , , , )k k kn1 2 � — íåêîòîðàÿ ïåðå-
ñòàíîâêà ýëåìåíòîâ ( , , , )1 2 � n , ïðè÷åì a xi ( ) 0. Ýòî îçíà÷àåò, ÷òî g x xi i ki
( ) ( )� � ,
ãäå �i — ìîíîòîííûå ôóíêöèè îäíîé ïåðåìåííîé.
Äîêàçàòåëüñòâî ïðîâåäåíî â ïðåäïîëîæåíèè ãëàäêîñòè ïðåîáðàçîâàíèÿ g . Îäíàêî
ëþáîå íåïðåðûâíîå è îáðàòèìîå ïðåîáðàçîâàíèå ìîæíî ñ ëþáîé ñòåïåíüþ òî÷íîñòè
àïïðîêñèìèðîâàòü ãëàäêèì ïðåîáðàçîâàíèåì. Ñîîòíîøåíèå g x xi i ki
( ) ( )� � ñîõðàíÿ-
åòñÿ â ïðåäåëüíîì ïåðåõîäå, ïîýòîìó òåîðåìà ñïðàâåäëèâà äëÿ ëþáîãî íåïðåðûâ-
íîãî ïðåîáðàçîâàíèÿ.
Èç äîêàçàííîé òåîðåìû êàê î÷åâèäíîå ñëåäñòâèå, âûòåêàåò ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 2 (î ñòðóêòóðå ìàêñèìàëüíîé ãðóïïû ïðåîáðàçîâàíèé, ñîõðàíÿþùåé
êàíîíè÷åñêèé ïîðÿäîê � íà R n ). Ìàêñèìàëüíàÿ ãðóïïà ïðåîáðàçîâàíèé ïðîñòðà-
íñòâà R n , ñîõðàíÿþùàÿ êàíîíè÷åñêîå îòíîøåíèå ïîðÿäêà � , èçîìîðôíà ïðÿìîìó
ïðîèçâåäåíèþ ãðóïïû ïåðåñòàíîâîê S n è ãðóïïû äèàãîíàëüíûõ ïðåîáðàçîâàíèé
{ }� âèäà � � � �( ) ( ( ), ( ), , ( ))x x x xn n� �1 1 2 2 , ãäå êàæäàÿ ôóíêöèÿ �i ix( ) — âîç-
ðàñòàþùàÿ ôóíêöèÿ îäíîé ïåðåìåííîé xi , i n� �1 2, , , .
Ìàêñèìàëüíóþ ãðóïïó ïðåîáðàçîâàíèé, ñîõðàíÿþùóþ êàíîíè÷åñêèé ïîðÿäîê �
íà R n , â äàëüíåéøåì áóäåì íàçûâàòü ãðóïïîé Ïàðåòî.
Ïóñòü íåêîòîðîå ýôôåêòèâíîå ïðàâèëî ïðèíÿòèÿ ðåøåíèé èíâàðèàíòíî îòíîñè-
òåëüíî ãðóïïû ïðåîáðàçîâàíèé G. Òîãäà ìîæíî óòâåðæäàòü, ÷òî ãðóïïà G ÿâëÿåòñÿ
ïîäãðóïïîé ãðóïïû Ïàðåòî. Ñîîòâåòñòâåííî ýôôåêòèâíûå ïðàâèëà ïðèíÿòèÿ ðåøå-
íèé â óñëîâèÿõ ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè ìîæíî êëàññèôèöèðîâàòü ïî ïîä-
ãðóïïàì ãðóïïû Ïàðåòî, îòíîñèòåëüíî êîòîðûõ ïðàâèëî ÿâëÿåòñÿ èíâàðèàíòíûì.
134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5
ÏÎÄÃÐÓÏÏÛ ÃÐÓÏÏÛ ÏÀÐÅÒÎ
Ðàññìîòðèì íàèáîëåå èíòåðåñíûå äèñêðåòíûå è íåïðåðûâíûå ïîäãðóïïû ãðóïïû
Ïàðåòî.
Ñðåäè äèñêðåòíûõ ãðóïï ïðåîáðàçîâàíèé, ñîõðàíÿþùèõ êàíîíè÷åñêîå îòíî-
øåíèå ïîðÿäêà íà R n , âûäåëÿåòñÿ ïîäãðóïïà ïåðåñòàíîâîê êîîðäèíàò — äèñêðåò-
íàÿ ïîäãðóïïà ïðåîáðàçîâàíèé âèäà �i kx x
i
( ) � , ãäå ( , , )k k kn1 2 � — íåêîòîðàÿ ïå-
ðåñòàíîâêà ýëåìåíòîâ ( , , , )1 2 � n . Èíâàðèàíòíîñòü îòíîñèòåëüíî äåéñòâèÿ ïðåîáðà-
çîâàíèé ýòîé ïîäãðóïïû èíîãäà íàçûâàþò ñâîéñòâîì àíîíèìíîñòè. Òàêàÿ
èíâàðèàíòíîñòü îçíà÷àåò íåçàâèñèìîñòü ðåøåíèÿ îò òîãî, â êàêîé ïîñëåäîâàòåëü-
íîñòè ðàññìàòðèâàþòñÿ êîîðäèíàòû òî÷åê, ò.å. íåçàâèñèìîñòü îò ïðèíöèïîâ íóìå-
ðàöèè êîîðäèíàò.
Ñðåäè ïàðàìåòðè÷åñêèõ íåïðåðûâíûõ ïîäãðóïï íàèáîëüøèé èíòåðåñ ïðåä-
ñòàâëÿþò ãðóïïû Ëè.
Íàïîìíèì, ÷òî ãðóïïû Ëè — íåïðåðûâíûå äèôôåðåíöèðóåìûå ãðóïïû ïðåîá-
ðàçîâàíèé íà ïîäìíîæåñòâàõ R n , ò.å. òàêèå ãðóïïû ïðåîáðàçîâàíèé, êîòîðûå ÿâëÿ-
þòñÿ òîïîëîãè÷åñêèìè ïðîñòðàíñòâàìè. Ïðè÷åì îïåðàöèÿ ñóïåðïîçèöèè ïðåîáðà-
çîâàíèé ñîîòâåòñòâóåò íåêîòîðîé íåïðåðûâíîé ãðóïïîâîé îïåðàöèè íà ìíîæåñòâå
ïàðàìåòðîâ. Ïîäðîáíî òåîðèÿ ãðóïï Ëè èçëîæåíà â [8].
Îñòàíîâèìñÿ íà îäíîïàðàìåòðè÷åñêèõ ãðóïïàõ Ëè. Ýòî ìíîæåñòâî ãëàäêèõ ïðå-
îáðàçîâàíèé âèäà F X A X: ! � , A R� , ïðè÷åì äëÿ êàæäîãî äåéñòâèòåëüíîãî ÷èñëà
� A îòîáðàæåíèå F x( , )� — âçàèìíî îäíîçíà÷íîå îòîáðàæåíèå ìíîæåñòâà X è äëÿ
ëþáûõ x X è � �, R èìååò ìåñòî òîæäåñòâî F F x F x( ( , ), ) ( , )� � � �� " , ãäå " —
ãðóïïîâàÿ îïåðàöèÿ íà ïîäìíîæåñòâå A ìíîæåñòâà äåéñòâèòåëüíûõ ÷èñåë.
Ñðåäè îäíîïàðàìåòðè÷åñêèõ ïîäãðóïï ãðóïïû Ïàðåòî âûäåëÿþòñÿ äâå.
1. Ïîäãðóïïà îäíîíàïðàâëåííûõ ñäâèãîâ — ãðóïïà âñåõ ïðåîáðàçîâàíèé âèäà
�i i ix x b( ) � � , b — ïàðàìåòð. Ãðóïïà ñäâèãîâ èçîìîðôíà ãðóïïå R äåéñòâèòåëü-
íûõ ÷èñåë îòíîñèòåëüíî îïåðàöèè ñëîæåíèÿ. Èíâàðèàíòíîñòü îòíîñèòåëüíî äåéñò-
âèÿ ýòîé ãðóïïû ôàêòè÷åñêè îçíà÷àåò íåçàâèñèìîñòü ðåøåíèÿ îòíîñèòåëüíî
âûáîðà îáùåãî äëÿ âñåõ êîîðäèíàò íà÷àëà îòñ÷åòà.
2. Ïîäãðóïïà ãîìîòåòèé — ãðóïïà âñåõ ïðåîáðàçîâàíèé âèäà �i i i
ax x e( ) � ,
a — ïàðàìåòð. Ýòà ïîäãðóïïà òàêæå èçîìîðôíà ãðóïïå R îòíîñèòåëüíî îïåðàöèè
ñëîæåíèÿ. Èíâàðèàíòíîñòü îòíîñèòåëüíî äåéñòâèÿ ýòîé ãðóïïû îçíà÷àåò íåçàâèñè-
ìîñòü ðåøåíèÿ îò îäíîâðåìåííîãî èçìåíåíèÿ ìàñøòàáà äëÿ âñåõ êîîðäèíàò.
Ñðåäè ìíîãîïàðàìåòðè÷åñêèõ ïîäãðóïï ãðóïïû Ïàðåòî ìîæíî óêàçàòü äâå
àáåëåâû (êîììóòàòèâíûå) ãðóïïû.
1. Ïîäãðóïïà ñäâèãîâ — ãðóïïà âñåõ ïðåîáðàçîâàíèé âèäà �i i i ix x b( ) � � ,
bi — ïàðàìåòðû. Ýòî n-ïàðàìåòðè÷åñêàÿ ïîäãðóïïà. Ãðóïïà ñäâèãîâ èçîìîðôíà
R R R
n
! ! !�
� ��� ���
.
2. Ïîäãðóïïà ðàñòÿæåíèé — ãðóïïà âñåõ ïðåîáðàçîâàíèé âèäà �i i i
a
x x e i( ) � ,
ai — ïàðàìåòðû. Ýòî òàêæå n-ïàðàìåòðè÷åñêàÿ ïîäãðóïïà. Ãðóïïà èçîìîðôíà
R R R
n
! ! !�
� ��� ���
.
Ïðèìåðîì íåàáåëåâîé ãðóïïû Ëè ñðåäè ãðóïï ïðåîáðàçîâàíèé, ñîõðàíÿþùèõ
ìíîæåñòâî Ïàðåòî, ìîæåò ñëóæèòü ãðóïïà ëèíåéíûõ ïðåîáðàçîâàíèé
�i i i
a
ix x e bi( ) � � , ãäå a bi i, — ïàðàìåòðû, i n� �1 2, , , .
 çàêëþ÷åíèå îòìåòèì ñëåäóþùåå. Èíâàðèàíòíîñòü ìíîæåñòâà Ïàðåòî îòíî-
ñèòåëüíî äåéñòâèÿ ãðóïïû ïðåîáðàçîâàíèé íå îçíà÷àåò èíâàðèàíòíîñòè ïîäìíî-
æåñòâ ìíîæåñòâà Ïàðåòî îòíîñèòåëüíî äåéñòâèÿ ïðåîáðàçîâàíèé ýòîé ãðóïïû. Òà-
êèì îáðàçîì, ëþáîå ýôôåêòèâíîå ðåøåíèå, âûáðàííîå ïî êàêîìó-ëèáî ïðàâèëó âû-
áîðà èç ìíîæåñòâà Ïàðåòî, ìîæåò îêàçàòüñÿ íåèíâàðèàíòíûì îòíîñèòåëüíî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 5 135
äåéñòâèÿ òîé èëè èíîé ïîäãðóïïû ïðåîáðàçîâàíèé. Ïîýòîìó àïðèîðíîå çàäàíèå
ïîäãðóïïû ïðåîáðàçîâàíèé, ñîõðàíÿþùèõ âûáèðàåìîå ðåøåíèå, íàêëàäûâàåò ñåðü-
åçíûå îãðàíè÷åíèÿ íà ïðàâèëà âûáîðà ýôôåêòèâíûõ ðåøåíèé.
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå ïðåäïðèíÿòà ïîïûòêà äàòü îòâåò íà âîïðîñ, êîòîðûé ïîñòîÿííî âîçíè-
êàåò â çàäà÷àõ, ñâÿçàííûõ ñ ìíîãîçíà÷íûì âûáîðîì. Îñíîâíîé âûâîä — àëãî-
ðèòìû îòûñêàíèÿ ðåøåíèé çàäà÷ ìíîãîçíà÷íîãî âûáîðà äîëæíû ñòðîèòüñÿ íà
îñíîâàíèè ñâîéñòâ ñèììåòðèè, êîòîðûå ÿâëÿþòñÿ õàðàêòåðèñòè÷åñêèìè äëÿ ðàñ-
ñìàòðèâàåìîé çàäà÷è. Òàêèì îáðàçîì, ïðèîðèòåòíîé äëÿ èññëåäîâàíèé ÿâëÿåòñÿ
íå ïðîáëåìà ñîïîñòàâëåíèÿ ÷àñòíûõ êðèòåðèåâ, à ïðîáëåìà ïîèñêà ãðóïïû ïðå-
îáðàçîâàíèé, îòíîñèòåëüíî êîòîðîé ïðèíèìàåìîå ðåøåíèå äîëæíî áûòü èíâàðè-
àíòíûì.  ðàáîòå âû÷èñëåíà ïîëíàÿ ãðóïïà ïðåîáðàçîâàíèé, êîòîðàÿ ñîõðàíÿåò
îòíîøåíèå ïîðÿäêà Ïàðåòî è, ñëåäîâàòåëüíî, íå èçìåíÿåò ìíîæåñòâî Ïàðåòî
îïòèìàëüíûõ ðåøåíèé ìíîãîêðèòåðèàëüíîé çàäà÷è.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. × å ð í î ð ó ö ê è é È . à . Ìåòîäû ïðèíÿòèÿ ðåøåíèé. — ÑÏÁ: Á×Â-Ïåòåðáóðã, 2005. — 416 c.
2. à ë ó õ î â  .  . , Ì å ä í è ê î â Ì . Ä . , Ê î ð î á ê î Ñ . Á . Ìàòåìàòè÷åñêèå ìåòîäû è ìîäåëè äëÿ
ìåíåäæìåíòà. — ÑÏÁ: Ëàíü, 2000. — 256 c.
3. Ï å ð å ï å ë è ö à  . À . Ìíîãîêðèòåðèàëüíûå çàäà÷è òåîðèè ãðàôîâ. — Êèåâ: ÓÌÊ, 1989. — 67 c.
4. Ä ó á î â Þ . À . , Ò ð à â ê è í Ñ . È . , ß ê è ì å ö Â . Í . Ìíîãîêðèòåðèàëüíûå ìîäåëè ôîðìèðîâàíèÿ
è âûáîðà âàðèàíòîâ ñèñòåì. — Ì.: Íàóêà, 1986. — 296 c.
5. Ê ó ð î ø À . Ã . Ëåêöèè ïî îáùåé àëãåáðå. — Ì.: Íàóêà, 1973. — 400 c.
6. Ï î í ò ð ÿ ã è í Ë . Ñ . Íåïðåðûâíûå ãðóïïû. — Ì.: Íàóêà, 1984. — 527 c.
7. È á ð à ã è ì î â Í . X . Àçáóêà ãðóïïîâîãî àíàëèçà. — Ì.: Çíàíèå, 1989. — 48 c.
8. È á ð à ã è ì î â Í . Õ . Ãðóïïû ïðåîáðàçîâàíèé â ìàòåìàòè÷åñêîé ôèçèêå. — Ì.: Íàóêà, 1983. — 282 c.
Ïîñòóïèëà 19.11.2007
Ïîñëå äîðàáîòêè 01.06.2009
|