Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений
Продовжено дослідження в галузі багатокритеріальної комбінаторної оптимізації. Побудовано та обурунтовано один із можливих підходів до розв'язання багатокритеріальних задач. Розроблено та реалізовано алгоритм. Описано деякі властивості ефективних розв'язків багатокритеріальних задач....
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2008 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/72006 |
| 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: | Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений / Л.Н. Колечкина, Е.А. Родионова // Кибернетика и системный анализ. — 2008. — № 2. — С. 152-160. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860214295995875328 |
|---|---|
| author | Колечкина, Л.Н. Родионова, Е.А. |
| author_facet | Колечкина, Л.Н. Родионова, Е.А. |
| citation_txt | Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений / Л.Н. Колечкина, Е.А. Родионова // Кибернетика и системный анализ. — 2008. — № 2. — С. 152-160. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Продовжено дослідження в галузі багатокритеріальної комбінаторної оптимізації. Побудовано та обурунтовано один із можливих підходів до розв'язання багатокритеріальних задач. Розроблено та реалізовано алгоритм. Описано деякі властивості ефективних розв'язків багатокритеріальних задач.
|
| first_indexed | 2025-12-07T18:15:49Z |
| format | Article |
| fulltext |
ÓÄÊ 519.85
Ë.Í. ÊÎËÅ×ÊÈÍÀ, Å.À. ÐÎÄÈÎÍÎÂÀ
ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÛÅ ÊÎÌÁÈÍÀÒÎÐÍÛÅ ÇÀÄÀ×È
ÎÏÒÈÌÈÇÀÖÈÈ ÍÀ ÌÍÎÆÅÑÒÂÅ ÏÎËÈÐÀÇÌÅÙÅÍÈÉ
Êëþ÷åâûå ñëîâà: ìíîãîêðèòåðèàëüíûå êîìáèíàòîðíûå çàäà÷è, ïîëèðàçìåùå-
íèÿ, ýôôåêòèâíàÿ àëüòåðíàòèâà, Ïàðåòî-îïòèìàëüíûå ðåøåíèÿ.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåå âðåìÿ àêòóàëüíûì ñòàíîâèòñÿ èññëåäîâàíèå ñâîéñòâ äèñêðåòíûõ çàäà÷
[1–8] è ðàçðàáîòêà ìåòîäîâ èõ ðåøåíèÿ. Äîñòàòî÷íî âàæíûì ïðè ýòîì ÿâëÿåòñÿ èñ-
ñëåäîâàíèå êëàññà êîìáèíàòîðíûõ çàäà÷, âûäåëÿåìûõ èç äèñêðåòíûõ.
Ïðè ðåøåíèè ïðàêòè÷åñêèõ çàäà÷ ÷àñòî èñïîëüçóþòñÿ ìàòåìàòè÷åñêèå ìîäåëè
êîìáèíàòîðíûõ îïòèìèçàöèîííûõ çàäà÷ [3, 4, 8]. Â çàâèñèìîñòè îò ñëîæíîñòè ïðè-
êëàäíîé çàäà÷è îäíîâðåìåííî ìîæåò ðàññìàòðèâàòüñÿ íå îäèí, à íåñêîëüêî êðèòåðèåâ
îïòèìèçàöèè, êîòîðûå íå ìîãóò áûòü îáúåäèíåíû â îäèí. ×àñòî âîçíèêàåò íåîáõîäè-
ìîñòü ó÷èòûâàòü êîìáèíàòîðíûå ñâîéñòâà ìíîæåñòâà äîïóñòèìûõ çíà÷åíèé. Òàêèì
îáðàçîì, ÿâëÿåòñÿ öåëåñîîáðàçíûì îáúåäèíåíèå ïîèñêà ðåøåíèé çàäà÷ ìíîãîêðèòåðè-
àëüíîé îïòèìèçàöèè ñ ó÷åòîì êîìáèíàòîðíûõ ñâîéñòâ îáëàñòè äîïóñòèìûõ çíà÷åíèé.
Âûøåóïîìÿíóòûå ïðîáëåìû ÿâëÿþòñÿ ñëîæíûìè è ìàëîèññëåäîâàííûìè, ïîýòîìó
âîïðîñ èõ èçó÷åíèÿ àêòóàëåí.
Èññëåäîâàíèÿ îòíîñèòåëüíî ìîäåëèðîâàíèÿ çàäà÷ â îáëàñòè ýêîíîìèêè è
òåõíèêè, èñïîëüçîâàíèå ìîäåëåé äèñêðåòíîé ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè
áûëè ïðîâåäåíû â ðàáîòàõ [1, 2, 5, 7]. Èçó÷åíû ñâîéñòâà êîìáèíàòîðíûõ îïòèìè-
çàöèîííûõ çàäà÷ ñ âåêòîðíûì êðèòåðèåì, âîïðîñû èõ ñëîæíîñòè, ðåøàåìîñòè,
óñòîé÷èâîñòè, àëãîðèòìè÷åñêèå ïðîáëåìû èõ ðåøåíèÿ. Îäíàêî òåîðåòè÷åñêèå
èññëåäîâàíèÿ è ïîëó÷åííûé îïûò ïîêàçàëè áîëüøóþ ñëîæíîñòü çàäà÷
äèñêðåòíîé, â ÷àñòíîñòè êîìáèíàòîðíîé, îïòèìèçàöèè.
 íàñòîÿùåå âðåìÿ èññëåäóþòñÿ ñâîéñòâà êîìáèíàòîðíûõ ìíîæåñòâ è ðàçðàáà-
òûâàþòñÿ ìåòîäû ðåøåíèÿ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè. Îäíàêî îáû÷íî èñ-
ñëåäîâàííûìè ÿâëÿþòñÿ âîçìîæíîñòè èõ ïðèìåíåíèÿ ê îïðåäåëåííîìó êëàññó çà-
äà÷. Âîïðîñ ïîèñêà îáùèõ ïîäõîäîâ è ìåòîäîâ ðåøåíèÿ çàäà÷ ñî ìíîãèìè êðèòåðè-
ÿìè íà êîìáèíàòîðíîì ìíîæåñòâå, â ÷àñòíîñòè íà ìíîæåñòâå ïîëèðàçìåùåíèé,
ñ÷èòàåòñÿ íåèññëåäîâàííûì, à ïîýòîìó àêòóàëüíûì.
Ñòàòüÿ ÿâëÿåòñÿ ïðîäîëæåíèåì èññëåäîâàíèé, êîòîðûå îòîáðàæåíû â ðàáî-
òàõ [1–8], è ïîñâÿùåíà ðàññìîòðåíèþ êëàññà çàäà÷ ìíîãîêðèòåðèàëüíîé îïòèìè-
çàöèè íà êîìáèíàòîðíîì ìíîæåñòâå ïîëèðàçìåùåíèé è ðàçðàáîòêå ïîäõîäà ê èõ
ðåøåíèþ.
I. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ðàññìîòðèì ìíîãîêðèòåðèàëüíûå çàäà÷è ñ ó÷åòîì êîìáèíàòîðíûõ ñâîéñòâ îá-
ëàñòè äîïóñòèìûõ ðåøåíèé. Íà ïðàêòèêå òàêèå çàäà÷è âîçíèêàþò ïðè íåîáõî-
äèìîñòè ôîðìàëèçàöèè îòäåëüíûõ óñëîâèé â âèäå êðèòåðèåâ (îáúåäèíåíèå
152 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
© Ë.Í. Êîëå÷êèíà, Å.À. Ðîäèîíîâà, 2008
ýòèõ êðèòåðèåâ ÿâëÿåòñÿ íåâîçìîæíûì), îïòèìàëüíûå çíà÷åíèÿ êîòîðûõ
íåîáõîäèìî íàéòè.
Ðàññìîòðèì ìíîãîêðèòåðèàëüíóþ áåçóñëîâíóþ çàäà÷ó íà ïîëèðàçìåùåíèÿõ.
Îáîçíà÷èì N Nm s, ìíîæåñòâî m è s ïåðâûõ íàòóðàëüíûõ ÷èñåë ñîîòâåòñòâåííî:
N mm � { }1, . . . , , N ss � { }1, . . . , . Îïòèìèçèðóåìûå êðèòåðèè ïðåäñòàâëÿþòñÿ
íàáîðîì ôóíêöèé:
f x c x
j
k
j j1
1
1( ) min� �
�
�
f x c x
j
k
j j2
1
2( ) min� �
�
�
. . . . . . . . . . . . . . . . (1)
f x c xs
j
k
j
s
j( ) min� �
�
�
1
f x c xs
j
k
j
s
j�
�
�� ��1
1
1
( ) max
. . . . . . . . . . . . . . . .
f x c xm
j
k
j
m
j( ) max� �
�
�
1
Ñëåäîâàòåëüíî, s ôóíêöèé èç m äîëæíû ìèíèìèçèðîâàòüñÿ è m s� ôóíêöèé
ìàêñèìèçèðîâàòüñÿ, õîòÿ ïðè ðåøåíèè ïðàêòè÷åñêèõ çàäà÷ ÷àñòî âîçíèêàåò íåîá-
õîäèìîñòü â óìåíüøåíèè îäíèõ êðèòåðèåâ è óâåëè÷åíèè äðóãèõ.  ÷àñòíîì ñëó-
÷àå âîçìîæíà ñèòóàöèÿ, êîãäà âñå ôóíêöèè ìàêñèìèçèðóþòñÿ èëè
ìèíèìèçèðóþòñÿ.
Íàáîð ôóíêöèé (1) öåëåñîîáðàçíî ïðåäñòàâèòü â âèäå âåêòîð-ôóíêöèè
F f f f fs s m( , . . . , , , . . . , )� � �1 1 , (2)
ìàêñèìóì êîòîðîé íåîáõîäèìî íàéòè.
Óñëîâèå ïðèíàäëåæíîñòè ðåøåíèé êîìáèíàòîðíîìó ìíîæåñòâó ìîæåò âîç-
íèêàòü èç äîïîëíèòåëüíûõ óñëîâèé, êîòîðûå íàëàãàþòñÿ íà ïåðåìåííûå â ñàìîé
ïîñòàíîâêå çàäà÷è.  ìàòåìàòè÷åñêîé ìîäåëè çàäà÷è (1) íà ðåøåíèå íàëàãàåòñÿ
óñëîâèå ïðèíàäëåæíîñòè ìíîæåñòâó ïîëèðàçìåùåíèé â âèäå
x x x E G Hk n
ks� �( , . . . , ) ( , )1 � . (3)
Êàê èçâåñòíî [8], ìíîæåñòâî ïîëèðàçìåùåíèé ðàâíî ìíîæåñòâó âåðøèí
ìíîãîãðàííèêà ïîëèðàçìåùåíèé: E G H G Hn
ks
n
ks
� �( , ) ( , )� vert � , âûïóêëàÿ îáîëî÷-
êà êîòîðîãî ��n
ks G H( , ) îïèñûâàåòñÿ â âèäå
j
j j
M
j
j j
M i
i
i
i
i
i
i
i
i
x g
x g M i N
�
�
� �
� �
� �
� � � �
�
�
�
�
�
�
| |
| |
,
1 s .
�
�
�
�
�
�
(4)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 153
Ñ ó÷åòîì âñåõ âûøåóêàçàííûõ óñëîâèé çàäà÷ó ìîæíî ñôîðìóëèðîâàòü ñëå-
äóþùèì îáðàçîì: íàéòè ìíîæåñòâî çíà÷åíèé (3), êîòîðûå ÿâëÿåòñÿ îïòèìàëüíû-
ìè äëÿ ôóíêöèé (2). Òàêàÿ çàäà÷à íàçûâàåòñÿ êîìáèíàòîðíîé ìíîãîêðèòåðèàëü-
íîé áåçóñëîâíîé çàäà÷åé íà ìíîæåñòâå ïîëèðàçìåùåíèé. Åñëè íà ìíîæåñòâî äî-
ïóñòèìûõ ðåøåíèé íàëàãàþòñÿ äîïîëíèòåëüíûå óñëîâèÿ D âèäà
A x b i N j Nij j j m k
� �, ,ãäå , (5)
òî çàäà÷à (2), (3), (5) ÿâëÿåòñÿ êîìáèíàòîðíîé ìíîãîêðèòåðèàëüíîé íà ïîëè-
ðàçìåùåíèÿõ ñ äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè:
X D G Hn
ks� � �� ( , ). (6)
2. ÏÎÄÕÎÄ Ê ÐÅØÅÍÈÞ ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÛÕ ÇÀÄÀ×
Ïðè ðåøåíèè ìíîãîêðèòåðèàëüíûõ êîìáèíàòîðíûõ çàäà÷ âîçíèêàåò âîïðîñ
îïðåäåëåíèÿ ýôôåêòèâíîãî ðåøåíèÿ, êîòîðûé îáóñëîâëåí ñðàâíåíèåì àëüòåð-
íàòèâ íà ìíîæåñòâå öåëåâûõ ôóíêöèé. Ñëåäóåò îòìåòèòü, ÷òî òàêîå ðåøåíèå
ìîæåò îêàçàòüñÿ íåîïòèìàëüíûì íè äëÿ îäíîé èç öåëåâûõ ôóíêöèé, îäíàêî
îíî ÿâëÿåòñÿ íàèëó÷øèì êîìïðîìèññíûì ðåøåíèåì ñ ó÷åòîì âñåõ öåëåâûõ
ôóíêöèé îäíîâðåìåííî.
Îïðåäåëåíèå 1[5]. Ðåøåíèå ÿâëÿåòñÿ ýôôåêòèâíûì, åñëè íà ìíîæåñòâå äî-
ïóñòèìûõ ðåøåíèé, êîòîðûå îïðåäåëÿþòñÿ óñëîâèåì (4), (5), íå ñóùåñòâóåò òà-
êîãî ðåøåíèÿ x, äëÿ êîòîðîãî áûëè áû ñïðàâåäëèâû íåðàâåíñòâà
f x f x i Ii i( ) ( ) � �0 1, ( )7
f x f x i Ii i( ) ( )
� �0 2
è õîòÿ áû îäíî èç íèõ áûëî ñòðîãèì.
Ýòî îçíà÷àåò, ÷òî íè îäíî èç äîïóñòèìûõ ðåøåíèé íå ìîæåò óëó÷øèòü çíà-
÷åíèå íåêîòîðîé öåëåâîé ôóíêöèè, íå óõóäøàÿ ïðè ýòîì õîòÿ áû îäíó èç îñòàâ-
øèõñÿ öåëåâûõ ôóíêöèé. Ýôôåêòèâíóþ àëüòåðíàòèâó íàçûâàþò òàêæå îïòèìàëü-
íîé ïî Ïàðåòî [5]. Âñå òàêèå àëüòåðíàòèâû ñîñòàâëÿþò P F X( , ) — ìíîæåñòâî
Ïàðåòî-îïòèìàëüíûõ ðåøåíèé [6, 7]. Ñîãëàñíî [7] äëÿ ëþáîãî x X� ñïðàâåäëèâî
óòâåðæäåíèå
x P F X y X F y F x F y F x� � � � � �( , ) | ( ) ( ), ( ) ( ){ } ,
ãäå F — âåêòîð-ôóíêöèÿ (2), à X — ìíîæåñòâî äîïóñòèìûõ çíà÷åíèé ôóíê-
öèè, êîòîðîå îïðåäåëÿåòñÿ óñëîâèÿìè (6) çàäà÷è.
Äëÿ îïðåäåëåíèÿ ìíîæåñòâà ýôôåêòèâíûõ ðåøåíèé çàäà÷è êîìáèíàòîðíîé
ìíîãîêðèòåðèàëüíîé îïòèìèçàöèè èñïîëüçóåì ñëåäóþùóþ òåîðåìó.
Òåîðåìà 1 [8] . Åñëè x x x X X Xl i s
* * * * * *( , . . . , ) ( , . . . , , . . . , )� �1 1 , ãäå
X x xj m m kj j j
* * *( , . . . , )� � �1 , òî âûïîëíÿþòñÿ óñëîâèÿ
g g
M Mi
i
i
1
. . .
�
, (8)
c c c cm m s m s m kj j j j j j j� � � � � � 1 10. . . . . . , (9)
m k m m k j Nj j j s0 0 1 10 0� � � � � �� �, , . (10)
154 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
Òîãäà ìèíèìóì ôóíêöèè f x c x
j
k
j j( ) �
�
�
1
íà ìíîæåñòâå ïîëèðàçìåùåíèé
E G Hn
ks
� ( , ) äîñòèãàåòñÿ â òî÷êå x x x E G Hk n
ks* ( , . . . , ) ( , )� �1 � , êîòîðàÿ óäîâëåò-
âîðÿåò óñëîâèÿì
x g i N x g i M j Nm i
M
s m s r i
M
r sj
j
j j j i j
j
j� � � � �
� � � � � � � �1 1
* *; ,
�
, (11)
ãäå r sj j, óäîâëåòâîðÿþò óñëîâèÿì
r s N r s k j Nj j k j j j s
j
, ,� � � � �0 . (12)
Êàê ñëåäñòâèå ïðåäûäóùåé òåîðåìû, ñôîðìóëèðóåì â âèäå òåîðåìû êðèòå-
ðèé îïòèìàëüíîñòè áåçóñëîâíîé ìíîãîêðèòåðèàëüíîé çàäà÷è íà ìíîæåñòâå
ïîëèðàçìåùåíèé.
Òåîðåìà 2. Ïóñòü Bi — ìíîæåñòâî ïåðåñòàíîâîê � � �i i
k
i� ( , . . . , )
1
, ïðèíàä-
ëåæàùèõ ìíîæåñòâó E Nk k( ), êîòîðûå óäîâëåòâîðÿþò óñëîâèþ
C C C C C
i i
s
i
s
i
k
i
i i i i i
� � � � �1 2 1
0 �
�
. . . . . . .
Òîãäà ìíîæåñòâî ðåøåíèé áåçóñëîâíîé ìíîãîêðèòåðèàëüíîé çàäà÷è íåïóñ-
òî, åñëè íåïóñòî ìíîæåñòâî, ÿâëÿþùååñÿ ïåðåñå÷åíèåì ìíîæåñòâ Bi , íàéäåííûõ
äëÿ êðèòåðèåâ (1):
� � � �
�i
m
iB B
1
. ( )13
Äëÿ ëþáîé ïåðåñòàíîâêè � � �� �( , , )1 � k B òî÷êà x x xk
* ( , . . . , )� �1
�E G Hn
ks
� ( , ) â âèäå (11) ïðè óñëîâèÿõ (8)—(10), (12) ïðèíàäëåæèò ìíîæåñòâó
ðåøåíèé.
Ðàññìîòðèì ñëåäóþùèé ïðèìåð, èëëþñòðèðóþùèé òåîðåìó 2.
Ïóñòü äàíî ìóëüòèìíîæåñòâî G � { }1 2 3 3 3 4 5 6 7, , , , , , , , , ñîñòîÿùåå èç � � 9
ýëåìåíòîâ. Ñëåäîâàòåëüíî, N 9 1 2 3 4 5 6 7 8 9� { }, , , , , , , , . Ïóñòü s � 3, âûáåðåì ðàçáè-
åíèå N 9 íà ìíîæåñòâà K1 1 2 3� { }, , , K2 4 6� { }, , K3 5 7 8 9� { }, , , , çàäàäèì k � 4,
k1 1� , k2 1� , k3 2� . Òîãäà ìíîæåñòâî ïîëèðàçìåùåíèé ïðåäñòàâëÿåòñÿ êàê
E G H
97
43 ( , ).
Çàäàí ñëåäóþùèé íàáîð ôóíêöèé:
f x x x x
f x x x x
f x
1 1 2 3 4
2 1 2 3 4
3 1
5 10
2 3 2
3
� � � � �
� � � � �
�
min,
min,
� � � �
� � � � �
�
�
��
�
�
�
�
2 4
7 5 7 3
2 3 4
4 1 2 3 4
x x x
f x x x x
min,
min.
Î÷åâèäíî, ÷òî C C C Ci i i i
3 1 2 4
0 �. . . � �i N 4 . Óñëîâèå òåîðåìû 2 âû-
ïîëíÿåòñÿ, à ñëåäîâàòåëüíî, òî÷êà x E G H* ( , , , ) ( , )� �3 3 1 7
97
43 ÿâëÿåòñÿ îïòèìàëü-
íîé äëÿ êàæäîé èç ôóíêöèé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 155
ÊÎÌÁÈÍÈÐÎÂÀÍÍÛÉ ÌÅÒÎÄ ÄËß ÐÅØÅÍÈß ÊÎÌÁÈÍÀÒÎÐÍÎÉ
ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÎÉ ÇÀÄÀ×È ÎÏÒÈÌÈÇÀÖÈÈ
Êàê óïîìèíàëîñü ðàíåå, êîìáèíàòîðíûå ìíîãîêðèòåðèàëüíûå çàäà÷è ÿâëÿþòñÿ
äîñòàòî÷íî àêòóàëüíûìè ïðè ðåøåíèè ðÿäà ïðèêëàäíûõ çàäà÷, íî ñóùåñòâóþ-
ùèå ðàçðàáîòàííûå ìåòîäû íå ïîëíîñòüþ àäåêâàòíî ìîãóò äàòü ðåøåíèå òà-
êèõ çàäà÷. Íåîáõîäèì íîâûé ïîäõîä ê èõ ðåøåíèþ. Ðàññìîòðèì îäèí èç âîç-
ìîæíûõ ïîäõîäîâ ê ðåøåíèþ òàêèõ çàäà÷, ÿâëÿþùèéñÿ êîìáèíàöèåé äâóõ ðà-
íåå ðàññìîòðåííûõ ìåòîäîâ: ìåòîäà îãðàíè÷åíèé [2] è ìåòîäà êîìáèíàòîðíîãî
îòñå÷åíèÿ [3].
Ïóñòü çàäàíî íåêîòîðîå ìíîæåñòâî öåëåâûõ ôóíêöèé, çàïèñàííîå â âèäå
âåêòîð-ôóíêöèè (2),
f x c x j Ni
j
k
ij j m( ) ,� �
�
�
1
, (14)
ïðè÷åì s ïåðâûõ ôóíêöèé íóæíî ìèíèìèçèðîâàòü, à ñëåäóþùèå m s� ôóíê-
öèé — ìàêñèìèçèðîâàòü. Íà ðåøåíèå íàëîæåíû îãðàíè÷åíèÿ âèäà (5), à òàêæå
óñëîâèå ïðèíàäëåæíîñòè ìíîæåñòâó ïîëèðàçìåùåíèé (3).
Àëãîðèòì ðåøåíèÿ çàäà÷è
1. Ââîäèì öåëî÷èñëåííóþ ïåðåìåííóþ q, ïîëàãàÿ q � 0.
2. Çàïèñûâàåì óñëîâèå ïðèíàäëåæíîñòè ìíîæåñòâó ïîëèðàçìåùåíèé â âèäå
ñèñòåìû íåðàâåíñòâ (4).
3. Îáúåäèíÿåì ñèñòåìó (4) ñ ñèñòåìîé ëèíåéíûõ äîïîëíèòåëüíûõ îãðàíè÷å-
íèé çàäà÷è (5).
4. Ñ èñïîëüçîâàíèåì òåîðåìû 1 îïðåäåëÿåì xi
0 — ðåøåíèå, êîòîðûå ïðèíàä-
ëåæàò ìíîæåñòâó ïîëèðàçìåùåíèé, è îïòèìèçèðóåì i-þ öåëåâóþ ôóíêöèþ
x xi imax min( ) — ðåøåíèÿ, êîòîðûå ìàêñèìèçèðóþò (ìèíèìèçèðóþò) ñîîòâåòñòâó-
þùèé êðèòåðèé íà äîïóñòèìîì ìíîæåñòâå ðåøåíèé.
5. Çàïèñûâàåì ñëåäóþùèå îòîáðàæåíèÿ:
à) äëÿ ôóíêöèé èç íàáîðà (1), êîòîðûå ìèíèìèçèðóþòñÿ:
W f X
c x c x
c x
i i
j
k
ij j
j
k
ij j
j
k
ij i
j
k
( ( ))
max
�
�
�
� �
� �
� �
�
1 1
0
1 1
�
� �
c x
i N
ij j
0
; (15)
á) äëÿ ôóíêöèé èç íàáîðà (1), êîòîðûå ìàêñèìèçèðóþòñÿ:
W f X
c x c x
c x c
i i
j
k
ij j
j
k
ij j
j
k
ij j
j
k
( ( )) �
�
�
� �
� �
� �
� �
1
0
1
1
0
1
ij i
m s
x
i N
min
� � � . (16)
Êîììåíòàðèè. Êîìïðîìèññíûì ðåøåíèåì äàííîé ìíîãîêðèòåðèàëüíîé çà-
äà÷è áóäåò òàêîå ýôôåêòèâíîå ðåøåíèå x, äëÿ êîòîðîãî îòíîñèòåëüíûå îòêëîíå-
íèÿ îäèíàêîâûå è ìèíèìàëüíûå, ò.å. âûïîëíÿåòñÿ óñëîâèå
� � �1 1 2 2 0W X W X W X km m( ) ( ) . . . ( ) min� � � � . (17)
6. Çàïèñûâàåì ñëåäóþùóþ îäíîêðèòåðèàëüíóþ çàäà÷ó ëèíåéíîãî ïðîãðàì-
ìèðîâàíèÿ:
k xn0 1� �� min
156 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
ïðè óñëîâèÿõ
j
k
ij j
j
k
ij j
i j
k
ij i
j
k
ijc x c x
k
c x c x
� � � �
� � � �
� �
1 1
0 0
1 1�
max j s
j
k
ij j
j
k
ij j
i j
k
i
i N
c x c x
k
c
0
1 1
0 0
1
�
�
�
�
�
�
�
�
� �
�
� � �
� � �
,
�
j j
j
k
ij i m s
ij j j n
j
x c x i N
a x b i J
0
1
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
� min ,
, ,
�
�
�
�
�
i
i
i
i
i
i
i
x g
x g
j j
N
j
j j
N
� �
� �
�
�
�
�
�
�
�
�
�
�
�
� �
| |
| |
,
.
1
�
�
�
�
�
�
(18)
7. Ðåøàåì çàäà÷ó (18) äâîéñòâåííûì ñèìïëåêñíûì ìåòîäîì.
8. Ïðîâåðÿåì ïðèíàäëåæíîñòü âåêòîðà-ðåøåíèÿ x x xk� ( , . . . , )1 ìíîæåñòâó
(4). Åñëè x x x E G Hk n
ks� �( , . . . , ) ( , )1 � , òî ðåøåíèå íàéäåíî è àëãîðèòì çàâåðøåí,
èíà÷å ïåðåõîäèì ê ï. 9.
9. Ïðîâåðÿåì çíà÷åíèå q. Åñëè q �1, òî ñäåëàòü ïåðåõîä íà øàã 11, èíà÷å —
ïåðåõîä íà øàã 10.
10. Óâåëè÷èòü q íà åäèíèöó. Äîáàâèòü ê ñèñòåìå îãðàíè÷åíèé (18) ñôîðìè-
ðîâàííîå íåðàâåíñòâî-îòñå÷åíèå ñîãëàñíî [3]
x x xi
i
i
i
i
i
r
r
1
1
2
2
1
� � �
� � � . . . (19)
â âèäå óðàâíåíèÿ
� � � � � � ��
x x x
x
i
i
i
i
i
i
n q
r
r
1
1
2
2
1
� � �
. . . , (20)
ââåäÿ âñïîìîãàòåëüíóþ ïåðåìåííóþ xn q� 0, ãäå i i1, . . . , � — íîìåðà íåáàçèñ-
íûõ ïåðåìåííûõ â ïîñëåäíåé òî÷êå x * , � — èõ êîëè÷åñòâî, à �ij � �j N r
îïðåäåëÿåòñÿ ïî ôîðìóëå
�ij
j a
i
ij
i
ijij
b
a
b
a
� �
�
min
: 0
.
(21)
Ïåðåõîäèì íà øàã 6.
11. Ïðîâåðÿåì çíà÷åíèå �n q� � 1 (�n q� � 1 îïðåäåëÿåòñÿ ïî ôîðìóëå (21)).
Åñëè �n q� � �1 0, ïåðåõîäèì íà øàã 10. Åñëè �n q� � �1 0, òî â óðàâíåíèè (20),
ïðèñîåäèíåííîì ê ñèñòåìå óðàâíåíèè (4), (5), çàìåíèòü ââåäåííóþ âñïîìîãà-
òåëüíóþ ïåðåìåííóþ íóëåì. Ïåðåéòè íà øàã 6 àëãîðèòìà.Äëÿ èëëþñòðàöèè
ïðåäëîæåííîãî àëãîðèòìà ðåøèì ñëåäóþùèå çàäà÷è.
Ïðèìåð 1. Ïóñòü çàäàíî ìóëüòèìíîæåñòâî G � { }2 2 3 3 4, , , , , êîòîðîå ñîñòîèò
èç ïÿòè ýëåìåíòîâ. Ñëåäîâàòåëüíî, N 5 1 2 3 4 5� { }, , , , . Ïóñòü çàäàíî s � 2, âûáåðåì
ðàçáèåíèå N 5 íà ìíîæåñòâà K1 1 3 5� { }, , , K2 2 4� { }, . Ïóñòü çàäàíî k � 2 è âûáðà-
íû k1 1� , k2 1� . Òîãäà ìíîæåñòâî ôîðìèðóåòñÿ â âèäå
H � { }( , ); ( , ); ( , ); ( , ); ( , ); ( , )1 2 1 4 3 2 3 4 5 2 5 4 . Ïîýòîìó ìíîæåñòâî ïîëèðàçìåùåíèé
áóäåò èìåòü ñëåäóþùèé âèä: E G H
53
22 2 2 2 3 3 2( , ) ( , ); ( , ); ( , )� { ; ( , ); ( , ); ( , )3 3 4 2 4 3 }.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 157
Ìàòåìàòè÷åñêàÿ ïîñòàíîâêà. Íàéòè ìíîæåñòâî çíà÷åíèé x E G H�
53
22 ( , ),
êîòîðûå ÿâëÿþòñÿ îïòèìàëüíûìè äëÿ ôóíêöèé
F x x1 1 23 5� � � max,
F x x2 1 22 3� � � � min.
Ðåøåíèå. Çàïèøåì óñëîâèå ïðèíàäëåæíîñòè ðåøåíèÿ ìíîæåñòâó
ïîëèðàçìåùåíèé â âèäå íåðàâåíñòâ x1 2 ; � �x1 4; x2 2 ; � �x2 3;
x x1 2 4� ; � � �x x1 2 7.
Ñîãëàñíî ôîðìóëàì (15), (16) ïðåîáðàçóþòñÿ öåëåâûå ôóíêöèè. Òîãäà îïðå-
äåëÿþòñÿ ìèíèìàëüíîå è ìàêñèìàëüíîå çíà÷åíèÿ êàæäîé èç íèõ. Äëÿ êîýô-
ôèöèåíòîâ ïåðâîãî êðèòåðèÿ F1 ñïðàâåäëèâî ñîîòíîøåíèå êîýôôèöèåíòîâ
0 1 2
c c , à ñëåäîâàòåëüíî, F x F1 1
0
1 4 3 27( ) ( , )� � , F x1 1( )min � F1 2 2 16( , ) � .
Àíàëîãè÷íî îïðåäåëÿåì ìàêñèìàëüíîå çíà÷åíèå äëÿ ôóíêöèè
F F x2 2 2
0 17: ( ) � � , F x2 2 10( )max � � .
 ðåçóëüòàòå ïðåîáðàçîâàíèÿ èìååì ñëåäóþùèå ôóíêöèè:
W
x x x x
x1
1 2 1 2
3
1
2
27 3 5
27 16
27 3 5
22
�
� �
�
�
� �
,
W
x x x x
x2
1 2 1 2
3
1
2
2 3 17
10 17
2 3 17
14
�
� � �
� �
�
� � �
.
Ñîãëàñíî âûøåèçëîæåííîìó ìåòîäó âûïîëíÿåòñÿ ïåðåõîä ê ñëåäóþùåé
çàäà÷å:
ìèíèìèçèðîâàòü x3 ïðè óñëîâèÿõ 3 5 22 271 2 3x x x� � ; 2 31 2x x� �
� 14 173x ; x1 2 ; � �x1 4; x2 2 ; � �x2 3; x x1 2 4� ; � � x x1 2 � 7.
Ïåðåõîä ê äâîéñòâåííîé çàäà÷å:
27 17 2 4 2 3 4 71 2 3 4 5 6 7 8y y y y y y y y� � � � � � � � max
ïðè îãðàíè÷åíèÿõ
3 2 0
5 3 0
22 1
1 2 3 4 7 8
1 2 5 6 7 8
1
y y y y y y
y y y y y y
y
� � � � �
� � � � �
�
,
,
4 12y
�
��
�
�
� .
 ðåçóëüòàòå ðåøåíèÿ çàäà÷è äâîéñòâåííûì ñèìïëåêñ-ìåòîäîì ïîëó÷àåì
ñëåäóþùèå çíà÷åíèÿ: x1 4� , x2 3� ; x3 0� ; x E� �( , )4 3
54
22 — èñêîìîå ðåøåíèå.
Ïðèìåð 2. Çàäàíî ìóëüòèìíîæåñòâî G � { }2 2 2 3 3 4, , , , , , äëÿ êîòîðîãî
N 6 1 2 3 4 5 6� { }, , , , , . Âûáèðàþòñÿ K1 1 2 4 6� { }, , , , K2 3 5� { }, , k1 2� , k2 1� . Òîãäà
H � {( , , ); ( , , ); ( , , ); ( , , ); ( , , ); ( , , )1 2 3 1 2 5 2 1 3 2 1 5 1 4 3 1 4 5 ; ( , , ); ( , , )4 1 3 4 1 5 ;
( , , ); ( , , ); ( , , ); ( , , ); ( , , ); ( , , ); (1 6 3 1 6 5 6 1 3 6 1 5 2 4 3 2 4 5 2, , ) ( , , )4 3 4 2 5 ;
( , , ); ( , , ); ( , , ); ( , , ); ( , , ); ( , , ); (2 6 3 2 6 5 2 6 3 6 2 5 4 6 3 4 6 5 6, , ); ( , , )4 3 6 4 5 }.
Ìíîæåñòâî ïîëèðàçìåùåíèé èìååò âèä
E G H
63
32 2 2 2 2 2 3 2 2 2 2 2 3 2 3 2( , ) ( , , ); ( , , ); ( , , ); ( , , ); ( , ,� { ); ( , , ); ( , , )2 3 3 3 2 2 ;
( , , ); ( , , ); ( , , ); ( , , ); ( , , ); ( , , ); (3 2 3 2 4 2 2 4 3 4 2 2 2 4 3 2 3 2 2, , ); ( , , )3 3 3 2 2 ;
158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
( , , ); ( , , ); ( , , ); ( , , ); ( , , ); ( , , ); (3 2 3 2 4 2 2 4 3 4 2 2 4 2 3 3 4 2 3, , ); ( , , )4 3 4 3 3 } �
� {( , , ); ( , , ); ( , , ); ( , , ); ( , , ); ( , , );2 2 2 2 2 3 2 3 2 2 3 3 3 2 2 3 2 3 ( , , ); ( , , )2 4 2 2 4 3 ;
( , , ); ( , , ); ( , , ); ( , , ); ( , , )4 2 2 4 2 3 3 4 2 3 4 3 4 3 3 }.
Ìàòåìàòè÷åñêàÿ ïîñòàíîâêà. Íàéòè ìíîæåñòâî çíà÷åíèé x E G H�
63
32 ( , ),
êîòîðûå ÿâëÿþòñÿ îïòèìàëüíûìè äëÿ ôóíêöèé
F x x x1 1 2 32� � � � max,
F x x x1 1 2 33 3� � � � max.
Ðåøåíèå. Ïðèíàäëåæíîñòü ðåøåíèÿ ìíîæåñòâó E G H
63
32 ( , ) ïðåäñòàâëÿåì â
âèäå ñëåäóþùåé ñèñòåìû: x1 2 ; � �x1 4; x2 2 ; � �x2 4; x3 2 ; � �x3 3;
x x1 2 4� ; � � �x x1 2 8; x x1 3 4� ; � � �x x1 3 7; x x2 3 4� ;
� � �x x2 3 7; x x x1 2 3 6� � , � � � �x x x1 2 3 11.
Èñïîëüçóÿ òåîðåìó 1 è ôîðìóëû (15), (16), ïðåîáðàçóåì ôóíêöèè ê âèäó
W F
x x x x x x
x( )1
1 2 3 1 2 3
4
1
2
14 2
14 8
14 2
12
� �
� � �
�
�
� � �
,
W F
x x x x x x
x( )2
1 2 3 1 2 3
4
1
2
7 3 3
7 4
7 3 3
22
� �
� � �
�
�
� � �
.
Ïåðåõîäèì ê ñëåäóþùåé çàäà÷å: f x� �4 min ïðè óñëîâèÿõ
x x x x1 2 3 42 12 14� � � ; x x x x1 2 3 43 3 22 7� � � ; x1 2 ; � �x1 4; x2 2 ;
� �x2 4; x3 2 ; � �x3 3; x x1 2 4� ; � � �x x1 2 8; x x1 3 4� ;
� � �x x1 3 7; x x2 3 4� ; � � �x x2 3 7; x x x1 2 3 6� � ; � � � �x x x1 2 3 11.
Ïåðåéäåì ê äâîéñòâåííîé çàäà÷å
14 7 2 4 2 4 2 3 4 81 2 3 4 5 6 7 8 9 10y y y y y y y y y y� � � � � � � � � �
� � � � � � �4 7 4 7 6 1111 12 13 14 15 16y y y y y y max
ïðè óñëîâèè
y y y y y y y y y y
y y y y
1 2 3 4 9 10 11 12 15 16
1 2 5 6
0
2 3
� � � � � � � � �
� � �
,
� � � � � �
� � � � � �
y y y y y y
y y y y y y y
9 10 13 14 15 16
1 2 7 8 11 12 13
0
3
,
� � �
�
�
�
�
�
�
�
y y y
y y
14 15 16
1 2
0
12 22 1
,
.
 ðåçóëüòàòå ðåøåíèÿ çàäà÷è ñèìïëåêñíûì ìåòîäîì èìååì x1 4� ; x2 2 8� , ;
x3 3� ; x4 0 1� , .
Âûïîëíåíî îòñå÷åíèå è ïîëó÷åíà òî÷êà x * ( , , )� 4 3 3 , îïòèìàëüíàÿ äëÿ
ôóíêöèé.
Çàìå÷àíèå. Îïèñàííûé àëãîðèòì ñõîäèòñÿ ê îïòèìàëüíîìó ðåøåíèþ çà êî-
íå÷íîå ÷èñëî øàãîâ. Ïîñêîëüêó ìíîæåñòâî äîïóñòèìûõ ðåøåíèé X îãðàíè÷åíî,
òî çàäà÷à (2), (4), (5) èìååò êîíå÷íîå îïòèìàëüíîå ðåøåíèå.
Òàêèì îáðàçîì, ïîñòðîåí è îáîñíîâàí îäèí èç âîçìîæíûõ ïîäõîäîâ ê ðåøå-
íèþ ìíîãîêðèòåðèàëüíûõ çàäà÷. Ðàçðàáîòàí è ðåàëèçîâàí àëãîðèòì ðåøåíèÿ. Ïðî-
âåäåíû ÷èñëåííûå ýêñïåðèìåíòû. Ïîñëåäóþùèå èññëåäîâàíèÿ äàííîé ðàáîòû
ïëàíèðóåòñÿ ïðîâîäèòü â íàïðàâëåíèè èçó÷åíèÿ ýôôåêòèâíîñòè ñóùåñòâóþùåãî
ìåòîäà ðåøåíèÿ ìíîãîêðèòåðèàëüíûõ çàäà÷ è ðàçðàáîòêè íîâûõ ìåòîäîâ ðåøåíèÿ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2 159
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ å ð ã è å í ê î È .  . , Ø è ë î  . Ï . Çàäà÷è äèñêðåòíîé îïòèìèçàöèè: ïðîáëåìû, ìåòîäû
ðåøåíèÿ, èññëåäîâàíèÿ. — Ê.: Íàóê. äóìêà, 2003. — 260 ñ.
2. Ç à é ÷ å í ê î Þ . Ï . Èññëåäîâàíèå îïåðàöèé. Íå÷åòêàÿ îïòèìèçàöèÿ: Ó÷åá. ïîñîáèå. — Êèåâ:
Âèùà øê., 1991. — 198 ñ.
3. ª ì å ö ü Î . Î . , Ê î ë º ÷ ê ³ í à Ë . Ì . Çàäà÷Ÿ êîìáŸíàòîðíî îïòèìŸçàöŸÂ ç äðîáîâî-ëŸíŸéíèìè
öŸëüîâèìè ôóíêöŸÿìè. — Ê.: Íàóê. äóìêà, 2005. — 113 ñ.
4. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . ÒåîðŸÿ Ÿ ìåòîäè åâêëŸäîâî êîìáŸíàòîðíî îïòèìŸçàöŸÂ. —
ÊèÂâ, 1993. — 188 ñ.
5. Ï î ä è í î â ñ ê è é Â . Â . , Í î ã è í Â . Ä . Ïàðåòî-îïòèìàëüíûå ðåøåíèÿ ìíîãîêðèòåðèàëüíûõ
çàäà÷. — Ì.: Íàóêà, 1982. — 256 ñ.
6. Ñ å ð ã è å í ê î È .  . , Ê î ç å ð à ö ê à ÿ Ë . Í . , Ë å á å ä å â à Ò . Ò . Èññëåäîâàíèå óñòîé÷èâîñòè
è ïàðàìåòðè÷åñêèé àíàëèç äèñêðåòíûõ îïòèìèçàöèîííûõ çàäà÷. — Êèåâ: Íàóê. äóìêà, 1995. — 170 ñ.
7. Ë å á å ä å â à Ò . Ò . , Ñ å ì å í î â à Í .  . , Ñ å ð ã è å í ê î Ò . È . Óñòîé÷èâîñòü âåêòîðíûõ
çàäà÷ öåëî÷èñëåííîé îïòèìèçàöèè: âçàèìîñâÿçü ñ óñòîé÷èâîñòüþ ìíîæåñòâ îïòèìàëüíûõ è
íåîïòèìàëüíûõ ðåøåíèé // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 4. — Ñ. 90—100.
8. Ñ ò î ÿ í Þ . à . , ª ì å ö ü Î . Î . , ª ì å ö ü ª . Ì . ÎïòèìŸçàöŸÿ íà ïîëŸðîçìŸùåííÿõ: òåîðŸÿ òà
ìåòîäè. — Ïîëòàâà: ÐÂÖ ÏÓÑÊÓ, 2005. — 103 ñ.
Ïîñòóïèëà 05.04.2007
160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 2
|
| id | nasplib_isofts_kiev_ua-123456789-72006 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| language | Russian |
| last_indexed | 2025-12-07T18:15:49Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Колечкина, Л.Н. Родионова, Е.А. 2014-12-15T22:24:48Z 2014-12-15T22:24:48Z 2008 Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений / Л.Н. Колечкина, Е.А. Родионова // Кибернетика и системный анализ. — 2008. — № 2. — С. 152-160. — Бібліогр.: 8 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/72006 519.85 Продовжено дослідження в галузі багатокритеріальної комбінаторної оптимізації. Побудовано та обурунтовано один із можливих підходів до розв'язання багатокритеріальних задач. Розроблено та реалізовано алгоритм. Описано деякі властивості ефективних розв'язків багатокритеріальних задач. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений Article published earlier |
| spellingShingle | Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений Колечкина, Л.Н. Родионова, Е.А. Системный анализ |
| title | Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений |
| title_full | Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений |
| title_fullStr | Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений |
| title_full_unstemmed | Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений |
| title_short | Многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений |
| title_sort | многокритериальные комбинаторные задачи оптимизации на множестве полиразмещений |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/72006 |
| work_keys_str_mv | AT kolečkinaln mnogokriterialʹnyekombinatornyezadačioptimizaciinamnožestvepolirazmeŝenii AT rodionovaea mnogokriterialʹnyekombinatornyezadačioptimizaciinamnožestvepolirazmeŝenii |