Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок
Досліджено складні дискретні багатокритеріальні задачі на комбінаторній множині перестановок. Розглянуто деякі властивості допустимої області комбінаторної багатокритеріальної задачі, що занурена в арифметичний евклідів простір. Установлено умови оптимальності різних видів ефективних розв'язків...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2008 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/72216 |
| 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: | Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок/ Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и системный анализ. — 2008. — № 3. — С. 158-172. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859786401089847296 |
|---|---|
| author | Семенова, Н.В. Колечкина, Л.Н. Нагорная, А.Н. |
| author_facet | Семенова, Н.В. Колечкина, Л.Н. Нагорная, А.Н. |
| citation_txt | Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок/ Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и системный анализ. — 2008. — № 3. — С. 158-172. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Досліджено складні дискретні багатокритеріальні задачі на комбінаторній множині перестановок. Розглянуто деякі властивості допустимої області комбінаторної багатокритеріальної задачі, що занурена в арифметичний евклідів простір. Установлено умови оптимальності різних видів ефективних розв'язків. Побудовано й обгрунтовано новий підхід розв'язання сформульованих задач.
|
| first_indexed | 2025-12-02T10:42:38Z |
| format | Article |
| fulltext |
ÓÄÊ 519.8
Í.Â. ÑÅÌÅÍÎÂÀ, Ë.Í. ÊÎËÅ×ÊÈÍÀ, À.Í. ÍÀÃÎÐÍÀß
ÏÎÄÕÎÄ Ê ÐÅØÅÍÈÞ ÂÅÊÒÎÐÍÛÕ ÇÀÄÀ×
ÄÈÑÊÐÅÒÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
ÍÀ ÊÎÌÁÈÍÀÒÎÐÍÎÌ ÌÍÎÆÅÑÒÂÅ ÏÅÐÅÑÒÀÍÎÂÎÊ1
Êëþ÷åâûå ñëîâà: ìíîãîêðèòåðèàëüíàÿ îïòèìèçàöèÿ, êîìáèíàòîðíûå ìíî-
æåñòâà, ìíîæåñòâà ïåðåñòàíîâîê, Ïàðåòî-îïòèìàëüíûå ðåøåíèÿ.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåå âðåìÿ ïóáëèêàöèè ìíîãèõ çàðóáåæíûõ è îòå÷åñòâåííûõ ó÷åíûõ
ïîñâÿùåíû ïîñòðîåíèþ ýôôåêòèâíûõ ìåòîäîâ ðåøåíèÿ è èññëåäîâàíèþ ðàçíî-
îáðàçíûõ àñïåêòîâ òåîðèè ìíîãîêðèòåðèàëüíûõ çàäà÷ îïòèìèçàöèè, âêëþ÷àÿ
äèñêðåòíûå [1–8].
Èíòåðåñ ê èññëåäîâàíèþ ìíîãîêðèòåðèàëüíûõ ìîäåëåé äèñêðåòíîé îïòèìèçà-
öèè îáóñëîâëåí èõ øèðîêèì ïðèìåíåíèåì ïðè ðåøåíèè âàæíûõ çàäà÷ ýêîíîìèêè,
ïðîåêòèðîâàíèÿ ñëîæíûõ ñèñòåì, äëÿ ïðèíÿòèÿ ðåøåíèé â óñëîâèÿõ íåîïðåäåëåí-
íîñòè è äðóãèõ. Ïðè ðåøåíèè ðàçëè÷íûõ íàðîäíîõîçÿéñòâåííûõ ïðîáëåì, â òîì
÷èñëå ïðîåêòèðîâàíèÿ è ðàçìåùåíèÿ îáúåêòîâ, ïëàíèðîâàíèÿ ýêñïåðèìåíòà,
óïðàâëåíèÿ ïðîöåññîì îáðàáîòêè äàííûõ, âàæíóþ ðîëü èãðàþò ðàçíîîáðàçíûå
îïòèìèçàöèîííûå çàäà÷è íà êîìáèíàòîðíûõ ìíîæåñòâàõ. Íà ñåãîäíÿøíèé äåíü â
îáëàñòè èññëåäîâàíèÿ ðàçëè÷íûõ êëàññîâ êîìáèíàòîðíûõ ìîäåëåé è ðàçðàáîòêè
íîâûõ ìåòîäîâ èõ ðåøåíèÿ ïîëó÷åíû ñóùåñòâåííûå ðåçóëüòàòû.
Êàê èçâåñòíî, áîëüøèíñòâî êîìáèíàòîðíûõ îïòèìèçàöèîííûõ çàäà÷ ìîãóò
áûòü ñâåäåíû ê çàäà÷àì öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ, íî ýòî íå âñåãäà
îïðàâäàíî, ïîñêîëüêó â ýòîì ñëó÷àå òåðÿåòñÿ âîçìîæíîñòü ó÷åòà êîìáèíàòîðíûõ
ñâîéñòâ çàäà÷è [2].
 ìîíîãðàôèÿõ [9–11] ïîêàçàíî, ÷òî âûïóêëîé îáîëî÷êîé ìíîæåñòâà ïåðå-
ñòàíîâîê ÿâëÿåòñÿ îáùèé ïåðåñòàíîâî÷íûé ìíîãîãðàííèê, ìíîæåñòâî âåðøèí
êîòîðîãî ðàâíî ìíîæåñòâó ïåðåñòàíîâîê. Äàííîå ñâîéñòâî ïåðåñòàíîâî÷íîãî
ìíîãîãðàííèêà äàåò âîçìîæíîñòü ñâåñòè ðåøåíèå çàäà÷è, îïðåäåëåííîé íà äèñ-
êðåòíîì êîìáèíàòîðíîì ìíîæåñòâå, ê ðåøåíèþ çàäà÷è íà íåïðåðûâíîì
äîïóñòèìîì ìíîæåñòâå.
Íà îñíîâàíèè óñòàíîâëåííîé àâòîðàìè âçàèìîñâÿçè ìåæäó ìíîãîêðèòåðè-
àëüíûìè çàäà÷àìè íà êîìáèíàòîðíûõ ìíîæåñòâàõ è îïòèìèçàöèîííûìè çàäà÷à-
ìè íà íåïðåðûâíîì äîïóñòèìîì ìíîæåñòâå ïîÿâëÿåòñÿ âîçìîæíîñòü ïðèìåíÿòü
êëàññè÷åñêèå ìåòîäû íåïðåðûâíîé îïòèìèçàöèè ê ðåøåíèþ âåêòîðíûõ êîìáèíà-
òîðíûõ çàäà÷ íà ðàçëè÷íûõ êîìáèíàòîðíûõ ìíîæåñòâàõ, à òàêæå ðàçâèâàòü íî-
âûå îðèãèíàëüíûå ìåòîäû ðåøåíèÿ, èñïîëüçóÿ ñâîéñòâà êîìáèíàòîðíûõ
ìíîæåñòâ è èõ âûïóêëûõ îáîëî÷åê.
 íàñòîÿùåå âðåìÿ ñóùåñòâóåò ìíîãî ìåòîäîâ ðåøåíèÿ ìíîãîêðèòåðèàëü-
íûõ çàäà÷, íî íè îäèí èç íèõ â îáùåì âèäå íå ïðèìåíèì ê êîìáèíàòîðíûì çàäà-
÷àì íà ïåðåñòàíîâêàõ, ïîýòîìó äîñòàòî÷íî âàæíûì ÿâëÿåòñÿ ðàçðàáîòêà ñïåöè-
àëüíûõ ìåòîäîâ è ïîäõîäîâ ê ðåøåíèþ ìíîãîêðèòåðèàëüíûõ çàäà÷ íà
êîìáèíàòîðíîì ìíîæåñòâå ïåðåñòàíîâîê.
 äàííîé ñòàòüå óñòàíîâëåíû íåêîòîðûå õàðàêòåðèñòèêè ñòðîåíèÿ äîïóñòè-
ìîé îáëàñòè, à òàêæå ñôîðìóëèðîâàíî è äîêàçàíî ðÿä òåîðåì î ñâîéñòâàõ ðàçëè÷-
158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
1Íàñòîÿùàÿ ðàáîòà ïîääåðæàíà Ôîíäîì ôóíäàìåíòàëüíûõ èññëåäîâàíèé Óêðàèíû (ïðîåêò
¹ Ô251/094).
© Í.Â. Ñåìåíîâà, Ë.Í. Êîëå÷êèíà, À.Í. Íàãîðíàÿ, 2008
íûõ âèäîâ ýôôåêòèâíûõ ðåøåíèé ðàññìàòðèâàåìûõ çàäà÷. Äëÿ âåêòîðíûõ çàäà÷
êîìáèíàòîðíîãî òèïà íà ïåðåñòàíîâêàõ ïðåäëîæåí îäèí èç âîçìîæíûõ ïîäõîäîâ
ê èõ ðåøåíèþ.
1. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß È ÎÏÐÅÄÅËÅÍÈß
Äëÿ ïîñòàíîâêè çàäà÷è èñïîëüçóåì ïîíÿòèå ìóëüòèìíîæåñòâà A, êîòîðîå
îïðåäåëÿåòñÿ îñíîâàíèåì S A( ) è êðàòíîñòüþ åãî ýëåìåíòîâ k a( ) [9–11].
Ïóñòü çàäàíû ìóëüòèìíîæåñòâî A a a aq� { }1 2, , ,� , åãî îñíîâàíèå
S A e e ek( ) , , ,� { }1 2 � , ãäå e R j N kj k� � � �1 1{ }, ,� , è êðàòíîñòü ýëåìåíòîâ
k e rj j( ) � , j N k� , r r r qk1 2� � � �� .
Óïîðÿäî÷åííîé n-âûáîðêîé èç ìóëüòèìíîæåñòâà A íàçûâàåòñÿ íàáîð
a a a ai i in
� ( , , , )
1 2
� , (1)
ãäå a A i N j N i ii j n n s tj
� � � � � �, , , åñëè s t s N t Nn n� � � � �, .
Îïðåäåëåíèå 1 [9–11]. Ìíîæåñòâî E A( ), ýëåìåíòàìè êîòîðîãî ÿâëÿþòñÿ
n-âûáîðêè âèäà (1) èç ìóëüòèìíîæåñòâà A, íàçûâàåòñÿ åâêëèäîâûì êîìáèíàòîð-
íûì ìíîæåñòâîì, åñëè äëÿ ïðîèçâîëüíûõ åãî ýëåìåíòîâ a a a an� � � � �( , , , )1 2 � ,
a a a an� � � � � � � � �( , , , )1 2 � âûïîëíÿþòñÿ óñëîâèÿ ( ) ( :a a j N n� � � � � �
a aj j� � � � ). Èíûìè ñëîâàìè, äâà ýëåìåíòà ìíîæåñòâà E A( ) îòëè÷íû îäèí îò äðó-
ãîãî, åñëè îíè ïîìèìî äðóãèõ îòëè÷èé èìåþò ðàçíûå ïîðÿäêè ðàçìåùåíèÿ
ñèìâîëîâ, êîòîðûå èõ îáðàçîâûâàþò.
Ìíîæåñòâî P Ank ( ) ïåðåñòàíîâîê ñ ïîâòîðåíèÿìè èç n äåéñòâèòåëüíûõ ÷è-
ñåë, ñðåäè êîòîðûõ k ðàçëè÷íûõ, íàçûâàåòñÿ îáùèì ìíîæåñòâîì ïåðåñòàíîâîê,
ò.å. ìíîæåñòâîì óïîðÿäî÷åííûõ n-âûáîðîê âèäà (1) èç ìóëüòèìíîæåñòâà A ïðè
óñëîâèè n q k�
.
Ïðè n k q� � èìååì ìíîæåñòâî ïåðåñòàíîâîê áåç ïîâòîðåíèé. Îáîçíà÷èì
åãî Pn . Î÷åâèäíî, ÷òî P A P An nn( ) ( )� . Îáîçíà÷èì P A( ) ìíîæåñòâî ïåðåñòàíîâîê
â ñëó÷àå, êîãäà êîíêðåòíî íå óêàçàí âèä ïåðåñòàíîâîê. Ðàññìîòðèì ìíîãîêðèòå-
ðèàëüíûå êîìáèíàòîðíûå çàäà÷è âèäà
Z P A a a P Ank nk( , ( )) : max ( ) | ( )� �{ }� ,
êîòîðûå ñîñòîÿò â ìàêñèìèçàöèè âåêòîðíîãî êðèòåðèÿ � ( )a íà åâêëèäîâîì êîì-
áèíàòîðíîì ìíîæåñòâå ïåðåñòàíîâîê P Ank ( ), ãäå � �( ) ( ( )a a� 1 , �2 ( ),a � ,
� l a( )), � i lE A R i N: ( ) ,� �1 .
Ñóùåñòâóåò ìíîæåñòâî ðàçëè÷íûõ ïðèíöèïîâ ïðèíÿòèÿ ðåøåíèé â ñèòóàöèÿõ òà-
êîãî ðîäà. Ðàññìîòðèì íåêîòîðûå èç íàèáîëåå òðàäèöèîííûõ ïðèíöèïîâ, ñâÿçàííûå ñ
âûäåëåíèåì èç âñåãî ìíîæåñòâà Y y a a P ank� � �{ }� ( ) | ( ) ìíîæåñòâ, íå óëó÷øàå-
ìûõ èëè îïòèìàëüíûõ ïî Ïàðåòî, îïòèìàëüíûõ ïî Ñëåéòåðó, îïòèìàëüíûõ ïî
Ñìåéëó âåêòîðîâ. Òàêèì îáðàçîì, ïîä ðåøåíèåì çàäà÷è Z P Ank( , ( ))� áóäåì ïî-
íèìàòü íàõîæäåíèå ýëåìåíòîâ îäíîãî èç ñëåäóþùèõ ìíîæåñòâ: P ( , ( ))� P Ank —
ìíîæåñòâà Ïàðåòî-îïòèìàëüíûõ (ýôôåêòèâíûõ) ðåøåíèé, Sl ( , ( ))� P Ank — îïòè-
ìàëüíûõ ïî Ñëåéòåðó (ñëàáî ýôôåêòèâíûõ) ðåøåíèé, Sm ( , ( ))� P Ank — îïòè-
ìàëüíûõ ïî Ñìåéëó (ñòðîãî ýôôåêòèâíûõ) ðåøåíèé. Çàäà÷è ïîèñêà ýëåìåíòîâ èç
ìíîæåñòâ P ( , ( ))� P Ank , Sl ( , ( ))� P Ank èëè Sm ( , ( ))� P Ank îáîçíà÷èì ñîîòâå-
òñòâåííî Z P AnkP ( , ( ))� , Z P AnkSl ( , ( ))� èëè Z P AnkSm ( , ( ))� . Ñîãëàñíî [3, 7, 8]
äëÿ ëþáîãî a P Ank� ( ) èñòèííû óòâåðæäåíèÿ
a P A y P A y ank nk� � �
�
Sl { }( , ( )) ( ) | ( ) ( )� � � , (2)
a P A y P A y a y ank nk� � � � � �
P { }( , ( )) ( ) | ( ) ( ), ( ) ( )� � � � � , (3)
a P A y P A y a y ank nk� � � � � �
Sm { }( , ( )) ( ) | ( ) ( ),� � � . (4)
Î÷åâèäíî, ÷òî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 159
Sm P Sl( , ( )) ( , ( )) ( , ( ))� � �P A P A P Ank nk nk� � . (5)
Êîíå÷íîñòü äîïóñòèìîé îáëàñòè ïåðåñòàíîâîê P Ank ( ) îáåñïå÷èâàåò íåïóñ-
òîòó ìíîæåñòâà P ( , ( ))� P Ank è åãî âíåøíþþ óñòîé÷èâîñòü [8]:
� � � �y P A a P A a ynk nk( ) ( , ( )) : ( ) ( )P � � � .  ñëó÷àå áåñêîíå÷íîãî ìíîæåñ-
òâà A âîïðîñ î ñóùåñòâîâàíèè ýëåìåíòîâ ìíîæåñòâà P ( , ( ))� P Ank òðåáóåò
îòäåëüíîãî èññëåäîâàíèÿ.
2. ÑÂÎÉÑÒÂÀ ÌÍÎÆÅÑÒÂÀ ÄÎÏÓÑÒÈÌÛÕ ÐÅØÅÍÈÉ
Áóäåì ðàññìàòðèâàòü ýëåìåíòû ìíîæåñòâà ïåðåñòàíîâîê ñ ïîâòîðåíèÿìè êàê
òî÷êè àðèôìåòè÷åñêîãî åâêëèäîâà ïðîñòðàíñòâà R n .
Ïóñòü âåêòîð a âèäà (1) — ýëåìåíò åâêëèäîâà êîìáèíàòîðíîãî ìíîæåñòâà
E A( ). Îòîáðàæåíèå � �: ( ) ( )E A E A R n� � íàçûâàåòñÿ ïîãðóæåíèåì ìíîæåñ-
òâà E A( ) â àðèôìåòè÷åñêîå åâêëèäîâî ïðîñòðàíñòâî, åñëè � çàäàåò âçàèìíî îä-
íîçíà÷íîå ñîîòâåòñòâèå E A R n
� ( )� ïî ñëåäóþùåìó ïðàâèëó: äëÿ a �
� �( , , ) ( )a a E Ai in1
� , x a� � ( ), x x x E An� �( , , ) ( )1 � � èìååì x aj i j
�
� �j N n .
 [9, 10] ïîêàçàíî, ÷òî âûïóêëîé îáîëî÷êîé ìíîæåñòâà ïåðåñòàíîâîê ÿâëÿåòñÿ
ïåðåñòàíîâî÷íûé ìíîãîãðàííèê Ï A P Ank nk( ) ( )� conv , ìíîæåñòâî âåðøèí êîòîðî-
ãî ðàâíî ìíîæåñòâó P Ank ( ) ïåðåñòàíîâîê: vert Ï A P Ank nk( ) ( )� .
Íå òåðÿÿ îáùíîñòè, óïîðÿäî÷èì ýëåìåíòû ìóëüòèìíîæåñòâà A ïî íåóáûâà-
íèþ:
a a an1 2� � �� , (6)
è ýëåìåíòû åãî îñíîâàíèÿ — ïî âîçðàñòàíèþ: e e ek1 2� � �� . Òîãäà âûïóê-
ëîé îáîëî÷êîé îáùåãî ìíîæåñòâà ïåðåñòàíîâîê P Ank ( ) ÿâëÿåòñÿ îáùèé ïåðå-
ñòàíîâî÷íûé ìíîãîãðàííèê Ï Ank ( ), êîòîðûé îïèñûâàåòñÿ ñëåäóþùåé
ñèñòåìîé ëèíåéíûõ íåðàâåíñòâ:
j
n
j
j
n
j
j
i
j
i
j
x a
x a
j
� �
� �
� �
� �
�
�
�
�
�
�
�
�
�
1 1
1 1
,
,�
(7)
(8)
� j nN� , � j ta j t� � � , � �j t N i, , � � �i N n 1, à P A Ï Ank nk( ) ( )� vert .
Ñèñòåìó îãðàíè÷åíèé (7), (8) îáùåãî ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà
Ï Ank ( ) ìîæíî çàïèñàòü â âèäå ðàâíîñèëüíîé åé ñèñòåìû
i
i
i
i t n
i
n
i
i
n
i
t
t
x a N
x a
� �
� �
� �
� �
� � �
�
�
�
�
�
�
1
1 1
9
10
| |
; ( )
, ( )
�
�
�
�
�
ãäå | |� t — êîëè÷åñòâî ýëåìåíòîâ ìíîæåñòâà èíäåêñîâ �, îïðåäåëåííûõ êàê
| |� t t� , t�{ }1 2, ,� .
Ïðè îòîáðàæåíèè ìíîæåñòâà ïåðåñòàíîâîê P Ank ( ) â åâêëèäîâî ïðîñòðà-
íñòâî R n ìîæíî ñôîðìóëèðîâàòü çàäà÷ó Z F X( , ) ìàêñèìèçàöèè íåêîòîðîãî âåê-
òîðíîãî êðèòåðèÿ F x( ) íà ìíîæåñòâå X , ïðè÷åì êàæäîé òî÷êå a P Ank� ( ) áóäåò
ñîîòâåòñòâîâàòü òî÷êà x X� òàêàÿ, ÷òî F x a( ) ( )� � ,
Z F X F x x X( , ) : max ( ) |{ }� ,
160 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
ãäå F x f x f x f xl( ) ( ( ), ( ), , ( ))� 1 2 � , f xi ( ) ñîîòâåòñòâóåò ôóíêöèîíàëó �i a( ),
f R Ri
n: � 1, i N l� ; X — íåïóñòîå ìíîæåñòâî â R n , îïðåäåëåííîå ñëåäóþ-
ùèì îáðàçîì: X Ï Ank� vert ( ), Ï A P Ank nk( ) ( )� conv . Ïîä ñîîòâåòñòâèåì âåê-
òîðíîé ôóíêöèè F âåêòîðó ôóíêöèîíàëîâ � ïîäðàçóìåâàåòñÿ ñîîòíîøåíèå
� ( ) ( ( )) ( )a F a a P Ank� � �� .
Çàäà÷à Z F X( , ) ìîæåò ñîäåðæàòü òàêæå äîïîëíèòåëüíûå ëèíåéíûå îãðàíè-
÷åíèÿ, îáðàçóþùèå âûïóêëîå ìíîãîãðàííîå ìíîæåñòâî D R n� âèäà
D x R Bx dn� � �{ }| , ãäå d R m� , B R m n� � . Òàêèì îáðàçîì, äîïóñòèìîå ìíî-
æåñòâî èìååò âèä
X Ï A Dnk� �vert ( ) .
Êàê ïðàâèëî, ââåäåíèå äîïîëíèòåëüíûõ îãðàíè÷åíèé óñëîæíÿåò çàäà÷ó,
îäíàêî óìåíüøàåò äîïóñòèìóþ îáëàñòü, ÷òî âàæíî ó÷èòûâàòü ïðè ïîñòðîåíèè
ðåøåíèé.
3. ÓÑËÎÂÈß ÎÏÒÈÌÀËÜÍÎÑÒÈ È ÍÅÊÎÒÎÐÛÅ ÑÂÎÉÑÒÂÀ
ÌÍÎÆÅÑÒÂ ÝÔÔÅÊÒÈÂÍÛÕ ÐÅØÅÍÈÉ
Îáîçíà÷èì ìíîæåñòâà ðåøåíèé çàäà÷è Z F X( , ) ñëåäóþùèì îáðàçîì: P ( , )F X
— ìíîæåñòâî Ïàðåòî-îïòèìàëüíûõ (ýôôåêòèâíûõ) ðåøåíèé, Sl ( , )F X —
îïòèìàëüíûõ ïî Ñëåéòåðó (ñëàáî ýôôåêòèâíûõ) ðåøåíèé, Sm ( , )F X — îïòè-
ìàëüíûõ ïî Ñìåéëó (ñòðîãî ýôôåêòèâíûõ) ðåøåíèé. Äëÿ ëþáîãî x X� èñòèí-
íû óòâåðæäåíèÿ âèäà (2)–(5), çàïèñàííûå ïðèìåíèòåëüíî ê çàäà÷å Z F X( , ):
x F X y X F y F x� � �
�
Sl { }( , ) | ( ) ( ) , (11)
x F X y X F y F x F y F x� � � � � �
P { }( , ) | ( ) ( ), ( ) ( ) , (12)
x F X y X y x F y F x� � � � � �
Sm { }( , ) | , ( ) ( ) . (13)
Sm P Sl( , ) ( , ) ( , )F X F X F X� � . (14)
Ïîñêîëüêó äîïóñòèìàÿ îáëàñòü X îãðàíè÷åíà, òî ìíîæåñòâî P ( , )F X íå
ïóñòî è âíåøíå óñòîé÷èâî.
Òåîðåìà 1. Ýëåìåíòû ìíîæåñòâ Sm ( , )F X — ñòðîãî ýôôåêòèâíûõ, P ( , )F X
— Ïàðåòî-îïòèìàëüíûõ, Sl ( , )F X — ñëàáî ýôôåêòèâíûõ ðåøåíèé ìíîãîêðèòå-
ðèàëüíîé êîìáèíàòîðíîé çàäà÷è íà ïåðåñòàíîâêàõ âèäà Z F X( , ) íàõîäÿòñÿ
â âåðøèíàõ ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà Ï Ank ( ).
Äîêàçàòåëüñòâî. Ó÷èòûâàÿ ñîîòíîøåíèÿ (14) ìåæäó ââåäåííûìè ìíîæåñòâàìè
ýôôåêòèâíûõ ðåøåíèé, à òàêæå â ñîîòâåòñòâèè ñ [9, 10] òîò ôàêò, ÷òî ìíîæåñòâî äîïóñ-
òèìûõ ðåøåíèé X ÿâëÿåòñÿ ïîäìíîæåñòâîì ìíîæåñòâà âåðøèí îáùåãî ïåðåñòàíîâî÷-
íîãî ìíîãîãðàííèêà Ï Ank ( ), ò.å. P Ank ( ) � vert Ï Ank ( ), ïðèõîäèì ê ñïðàâåäëèâîñòè
öåïî÷êè âêëþ÷åíèé: Sm P( , ) ( , )F X F X� � Sl vert( , ) ( )F X Ï Ank� . Òåîðåìà
äîêàçàíà.
Ïóñòü ôóíêöèè f xi ( ), i N l� , âåêòîðíîãî êðèòåðèÿ F x( ) ÿâëÿþòñÿ ëèíåéíû-
ìè, ò.å. f x c xi i( ) ,� , c Ri
n� , i N l� . Âàæíûå ñâîéñòâà äîïóñòèìîé îáëàñòè X
è ìíîæåñòâ ðàçëè÷íûõ âèäîâ ýôôåêòèâíûõ ðåøåíèé, óêàçàííûå â òåîðåìå 1, à
òàêæå ëèíåéíîñòü ôóíêöèé âåêòîðíîãî êðèòåðèÿ ïîçâîëÿþò ñâåñòè ðåøåíèå çà-
äà÷è Z F X( , ) ê ðåøåíèþ çàäà÷è Z F G( , ) íà íåïðåðûâíîì äîïóñòèìîì
ìíîæåñòâå G Ï A Dnk� �( ) .
Ïóñòü C R n l� � — ìàòðèöà, ci — åå âåêòîð-ñòðîêà, i N l� . Ìíîãîãðàííèê
Ï Ank ( ) ïðåäñòàâèì â âèäå Ï A x R x i Nnk
n
i i p( ) | , ,� � � �{ }� � , ñâåäÿ âñå íå-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 161
ðàâåíñòâà ê îäíîìó âèäó (�), è áóäåì îáîçíà÷àòü Ï . Àíàëèç çàäà÷è Z F X( , ) áó-
äåì ïðîâîäèòü ñ ó÷åòîì ñâîéñòâ êîíóñà K x R n� �{ |Cx � 0} ïåðñïåêòèâíûõ íà-
ïðàâëåíèé [3] çàäà÷è Z F X( , ) è âûïóêëûõ çàìêíóòûõ êîíóñîâ 0� Ï y( )
� � � �{ }x R x i N yn
i| , , ( )� 0 , ãäå N y( ) � { }i N yp i i� �| ,� � , êîòîðûå ìî-
ãóò áûòü ïîñòðîåíû äëÿ âñåõ òî÷åê y Ï�vert . Î÷åâèäíî, ÷òî N y( ) �
,
X y Ï y� � �0 ( ). Îáîçíà÷èì K x R Cxn
0 0� � �{ }| ÿäðî îòîáðàæåíèÿ
C R Rn l: � , int { }K x R Cxn� �
| 0 — âíóòðåííîñòü êîíóñà K. Èç ôîðìóë
(11)–(13) ñëåäóåò, ÷òî � �x X ñïðàâåäëèâû óòâåðæäåíèÿ
x C X x K X� � � � �
Sl int( , ) ( ) , (15)
x C X x K K X� � � � �
P ( , ) ( \ )0 , (16)
x C X x K X x� � � � �
Sm { }( , ) ( ) \ . (17)
Ñïðàâåäëèâû ñëåäóþùèå òåîðåìû.
Òåîðåìà 2. P vert P( , ) ( , )F G Ï F X� � , Sl vert Sl( , ) ( , )F G Ï F X� � ,
Sm vert Sm( , ) ( , )F G Ï F X� � .
Äîêàçàòåëüñòâî. Ïîñêîëüêó vert Ï D G� � , òî P vert( , )F G Ï D� � �
� � � �P vert P( , ) ( , )F G Ï D F X . Ñîîòíîøåíèÿ Sl Sl vert( , ) ( , )F X F Ï D� � �
� � �Sl vert( , )F G Ï D, Sm ( , )F X � � �Sm vert( , )F D Ï Sm vert( , )F G Ï�
äîêàçûâàþòñÿ àíàëîãè÷íî.
Òåîðåìà 3. Åñëè äîïóñòèìîå ìíîæåñòâî X çàäà÷è Z F X( , ) íå ñîäåðæèò
îãðàíè÷åíèé, îïèñûâàþùèõ âûïóêëîå ìíîãîãðàííîå ìíîæåñòâî D, ëèáî Ï D� ,
ò.å. X Ï� vert , òî � �x R n ñïðàâåäëèâû óòâåðæäåíèÿ
x� Sl Sl vert( , ) ( , )F X x F Ï Ï� � � ,
x F X x F Ï Ï� � � �P P vert( , ) ( , ) ,
x� Sm Sm vert( , ) ( , )F X x F Ï Ï� � � .
Äîêàçàòåëüñòâî. Èç òåîðåìû 2 ñ ó÷åòîì óñëîâèé òåîðåìû 3 ñëåäóåò, ÷òî
� �x R n èñòèííû âûñêàçûâàíèÿ x F Ï Ï x F X� � � �Sl vert Sl( , ) ( , ),
x F Ï Ï x F X� � � �P vert P( , ) ( , ), x F Ï Ï F X� � �Sm vert Sm( , ) ( , ). Äîêà-
æåì îáðàòíûå èìïëèêàöèè. Ïóñòü x F X�Sl ( , ), îòêóäà ñîãëàñíî òåîðåìå 1 ñëå-
äóåò, ÷òî x Ï�vert . Ïðåäïîëîæèì îò ïðîòèâíîãî, ÷òî x F Ï�Sl ( , ). Ó÷èòûâàÿ ëè-
íåéíîñòü ôóíêöèé f x i Ni l( ), � , âåêòîðíîãî êðèòåðèÿ F x( ), ïî òåîðåìå 1 èç [5]
âûïîëíÿåòñÿ óñëîâèå int K Ï x� �
�0 ( ) , ò.å. â êîíóñå ( )x K� int ëåæàò íåêîòî-
ðûå òî÷êè ãðàíèöû ìíîæåñòâà Ï , ñëåäîâàòåëüíî ñóùåñòâóåò òî÷êà x Ï1 �vert ,
ïðèíàäëåæàùàÿ ýòîìó êîíóñó. Ïîñëåäíåå â ñèëó ôîðìóëû (12) îçíà÷àåò, ÷òî
x F X�Sl ( , ) è ïðèâîäèò ê ïðîòèâîðå÷èþ ñ óñëîâèåì òåîðåìû. Îñòàëüíûå
óòâåðæäåíèÿ äàííîé òåîðåìû äîêàçûâàþòñÿ àíàëîãè÷íî. Äîêàçàòåëüñòâî
çàâåðøåíî.
Ñëåäñòâèå. Ïðè óñëîâèÿõ òåîðåìû 3 ñïðàâåäëèâû ðàâåíñòâà
P vert P( , ) ( , )F Ï Ï F X� � , Sl vert Sl( , ) ( , )F Ï Ï F X� � ,
Sm vert Sm( , ) ( , )F Ï Ï F X� � .
Åñëè â çàäà÷å Z F X( , ) äîïóñòèìàÿ îáëàñòü X Ï Ank� vert ( ), òî äëÿ ëþáîé
òî÷êè x Ï Ank�vert ( ) ñïðàâåäëèâû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ îïòè-
ìàëüíîñòè âñåõ óêàçàííûõ âûøå âèäîâ ýôôåêòèâíûõ ðåøåíèé, ïîëó÷åíûå â ðà-
áîòå [5].
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
Åñëè äîïóñòèìàÿ îáëàñòü X çàäà÷è Z F X( , ) ñîäåðæèò äîïîëíèòåëüíûå îãðàíè÷åíèÿ,
îïèñûâàþùèå âûïóêëûé ìíîãîãðàííèê D, ò.å. X Ï D� �vert è Ï D Ï� � , òî ñïðà-
âåäëèâû ëèøü äîñòàòî÷íûå óñëîâèÿ îïòèìàëüíîñòè ðåøåíèé.
Òåîðåìà 4. � � � � � �x Ï x F Ï D x F Xvert P P: ( , ) ( , ), x F Ï� �Sl( , )
� � �D x F XSl ( , ), x F Ï D x F X� � � �Sm Sm( , ) ( , ).
Äîêàçàòåëüñòâî.Ïîñêîëüêó G Ï D� � , òî ñïðàâåäëèâû èìïëèêàöèè
� �x Ïvert : x F Ï D x F Ï D F G x P F X� � � � � � � �P P P( , ) ( , ) ( , ) ( , ), x�
Sl Sl( , ) ( , )F Ï D x F X� � � , x F Ï D x F X� � � �Sm Sm( , ) ( , ).
Òàêèì îáðàçîì, òåîðåìû 1–4 óñòàíàâëèâàþò âçàèìîñâÿçü ìåæäó çàäà÷åé
Z F X( , ) è çàäà÷åé Z F G( , ), îïðåäåëåííîé íà íåïðåðûâíîì äîïóñòèìîì ìíîæåñ-
òâå. Ýòî äàåò âîçìîæíîñòü ïðèìåíÿòü êëàññè÷åñêèå ìåòîäû íåïðåðûâíîé îïòè-
ìèçàöèè ê ðåøåíèþ âåêòîðíûõ êîìáèíàòîðíûõ çàäà÷ íà ïåðåñòàíîâêàõ è íà ýòîé
îñíîâå ðàçâèâàòü íîâûå îðèãèíàëüíûå ìåòîäû ðåøåíèÿ, èñïîëüçóÿ ñâîéñòâà
êîìáèíàòîðíûõ ìíîæåñòâ è èõ âûïóêëûõ îáîëî÷åê.
Ïðè óñòàíîâëåíèè ðàçëè÷íûõ âèäîâ ýôôåêòèâíîñòè ðåøåíèé ñëåäóåò ó÷è-
òûâàòü, ÷òî åñëè âûïîëíÿþòñÿ íåîáõîäèìûå óñëîâèÿ îïòèìàëüíîñòè ðàññìàòðè-
âàåìîãî ðåøåíèÿ, òî ãàðàíòèðîâàòü åãî ýôôåêòèâíîñòü íåëüçÿ, îäíàêî åñëè ýòè
óñëîâèÿ íå âûïîëíÿþòñÿ, òî ðåøåíèå íåýôôåêòèâíî. Åñëè èñïîëüçóþòñÿ äîñòà-
òî÷íûå óñëîâèÿ, òî ðåøåíèå, óäîâëåòâîðÿþùåå èì, ýôôåêòèâíî, â ïðîòèâíîì
ñëó÷àå âîïðîñ îá ýôôåêòèâíîñòè ðåøåíèÿ îñòàåòñÿ îòêðûòûì. Åñëè æå ïðèìåíÿ-
þòñÿ íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ, òî âîïðîñ ðåøàåòñÿ îäíîçíà÷íî:
ðåøåíèå ýôôåêòèâíî òîãäà è òîëüêî òîãäà, êîãäà îíî óäîâëåòâîðÿåò ýòèì
óñëîâèÿì.
Åñëè çàäà÷à Z F X( , ) íå ñîäåðæèò ëèíåéíûõ îãðàíè÷åíèé, îáðàçóþùèõ âû-
ïóêëîå ìíîãîãðàííîå ìíîæåñòâî D R n� , ëèáî Ï D� , ò.å. X Ï� vert , òî ñ ó÷å-
òîì íåîáõîäèìûõ è äîñòàòî÷íûõ óñëîâèé îïòèìàëüíîñòè (òåîðåìà 3) ïðîöåññ åå
ðåøåíèÿ ñâîäèòñÿ ê ïîèñêó ýôôåêòèâíûõ ðåøåíèé çàäà÷è Z F G( , ) íà íåïðåðûâ-
íîì äîïóñòèìîì ìíîæåñòâå G Ï� ñ ïîñëåäóþùèì âûáîðîì èç íèõ ëèøü òåõ, êî-
òîðûå ÿâëÿþòñÿ âåðøèíàìè ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà Ï .
Àíàëèçèðóÿ òåîðåìû 2 è 4, ïðèõîäèì ê ñîîòíîøåíèÿì, ñóùåñòâóþùèì ìåæ-
äó çàäà÷àìè Z F X( , ) è Z F G( , ): åñëè x F G Ï� �R vert( , ) , òî x F X�R ( , ); åñëè
x F G Ï� �R vert( , ) , òî èç ýòîãî íå ñëåäóåò, ÷òî x F X�R ( , ), ãäå R ( , )F X îáî-
çíà÷àåò ìíîæåñòâî P ( , )F X , Sm ( , )F X ëèáî Sl ( , )F X .
4. ÎÁÙÈÉ ÏÎÄÕÎÄ Ê ÐÅØÅÍÈÞ ÂÅÊÒÎÐÍÛÕ ÇÀÄÀ×
ÍÀ ÊÎÌÁÈÍÀÒÎÐÍÎÌ ÌÍÎÆÅÑÒÂÅ ÏÅÐÅÑÒÀÍÎÂÎÊ
Åñëè çàäà÷à Z F X( , ) ñîäåðæèò äîïîëíèòåëüíûå ëèíåéíûå îãðàíè÷åíèÿ, òî
ïðåäëàãàåòñÿ ñëåäóþùèé ïîäõîä ê åå ðåøåíèþ.
1. Íàõîäèì ýôôåêòèâíûå ðåøåíèÿ çàäà÷è Z F Ï( , ).
2. Ïðîâåðÿåì èõ íà ïðèíàäëåæíîñòü ìíîæåñòâó D. Åñëè x F Ï D� �P ( , ) , òî
x F X�P ( , ).
3. Ðàññìîòðèì äîïóñòèìûå ðåøåíèÿ x X� çàäà÷è Z F X( , ), ÿâëÿþùèåñÿ íå-
ýôôåêòèâíûìè â çàäà÷å Z F Ï( , ), ò.å. x X F Ï D� �\ ( ( , ) )P , è ïðîâåðÿåì èõ íà
ýôôåêòèâíîñòü. Äëÿ ýòîãî âîñïîëüçóåìñÿ íåîáõîäèìûìè è äîñòàòî÷íûìè óñëî-
âèÿìè, ñôîðìóëèðîâàííûìè â [8, ñ. 187, 188].
Óòâåðæäåíèå 1. Äîïóñòèìîå ðåøåíèå x 0 ýôôåêòèâíî òîãäà è òîëüêî òîãäà,
êîãäà îíî ÿâëÿåòñÿ îïòèìàëüíûì ðåøåíèåì çàäà÷è
Z f X f x x X f x f x i N
i
l
i i i l
1
1
0( , ) : max ( ) | , ( ) ( ),
�
� � � �
�
�
�
��
�
�
�
��
.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 163
Åñëè ðåøåíèå x 0 íeýôôåêòèâíî, òî â ðåçóëüòàòå ðåøåíèÿ ýòîé çàäà÷è íàõî-
äèì ýôôåêòèâíîå ðåøåíèå x * , êîòîðîå áîëåå ïðåäïî÷òèòåëüíî, ÷åì x 0 , ò.å.
F x F x( ) ( )* � 0 .
Ïðîäîëæàÿ èññëåäîâàíèÿ è ðàçâèâàÿ ðåçóëüòàòû ðàáîò [1, 4–6, 9–13], ïðåä-
ëîæèì ïîäõîä ê ðåøåíèþ çàäà÷è Z F X( , ), îñíîâàííûé íà ëèíåéíîé ñâåðòêå (àã-
ðåãàöèè) åå ÷àñòè÷íûõ êðèòåðèåâ è äàëüíåéøåì ñâåäåíèè ïîèñêà ðåøåíèé íà-
÷àëüíîé çàäà÷è ê ðåøåíèþ ñåðèè ñêàëÿðíûõ (îäíîêðèòåðèàëüíûõ) çàäà÷, ïðîâåð-
êå îïòèìàëüíîñòè ïîëó÷åííûõ ðåøåíèé. Ìåòîä ðåøåíèÿ îäíîêðèòåðèàëüíûõ
çàäà÷ îñíîâàí íà èäåÿõ äåêîìïîçèöèè, îòñåêàþùèõ ïëîñêîñòåé Êåëëè, ðåëàêñà-
öèè. Äàëåå ðàññìàòðèâàåì ìåòîä, ïðè ðåàëèçàöèè êîòîðîãî ó÷èòûâàåòñÿ òîò
ôàêò, ÷òî ÷èñëî îãðàíè÷åíèé äîâîëüíî áîëüøîå. Òîãäà öåëåñîîáðàçíûì ÿâëÿåòñÿ
èñïîëüçîâàíèå ïðîöåäóðû ðåëàêñàöèè — âðåìåííîãî îòáðàñûâàíèÿ íåêîòîðûõ
îãðàíè÷åíèé è ðåøåíèÿ çàäà÷è íà áîëåå øèðîêîé îáëàñòè, ò.å. ïðè îñòàâøèõñÿ
îãðàíè÷åíèÿõ.
Äëÿ ïîñòðîåíèÿ àëãîðèòìà, íà íà÷àëüíîì ýòàïå íåîáõîäèìî îïðåäåëèòü èñ-
õîäíóþ òî÷êó. Ðàññìîòðèì îäíîêðèòåðèàëüíóþ çàäà÷ó áåç îãðàíè÷åíèé, îïèñû-
âàþùèõ ìíîãîãðàííèê D, êîòîðûå áóäåì íàçûâàòü äîïîëíèòåëüíûìè
îãðàíè÷åíèÿìè.
Óòâåðæäåíèå 2. Åñëè äëÿ ýëåìåíòîâ ìóëüòèìíîæåñòâà A è êîýôôèöèåíòîâ
c j Nj n, � , öåëåâîé ôóíêöèè çàäà÷è extr vertf x c x x Ï A
j
n
j j nk( ) | ( )� �
�
�
�
��
�
�
�
���
�
1
âû-
ïîëíÿþòñÿ ñîîòâåòñòâåííî óñëîâèÿ (6) è c c ci i in1 2
� � �� , i Nn n� , òî ìàêñèìóì
ôóíêöèè f x( ) íà äîïóñòèìîì ìíîæåñòâå äîñòèãàåòñÿ â òî÷êå
x x x x Ï A
i i i nk
n
* ( , , , ) ( )* * *� �
1 2
� vert , êîòîðàÿ çàäàåòñÿ êàê
x a j N
i j n
j
* � � � , (18)
à ìèíèìóì — ñîîòâåòñòâåííî â òî÷êå y y y yi i in
� ( , , , )
1 2
� , ãäå
y a j Ni n j nj �
� � � � �1 1 0{ }.
Ñëåäóåò îòìåòèòü, ÷òî îáùåå ÷èñëî p ëèíåéíûõ íåðàâåíñòâ, âõîäÿùèõ â ñèñ-
òåìó (7), (8), îïèñûâàþùóþ ïåðåñòàíîâî÷íûé ìíîãîãðàííèê Ï Ank ( ), î÷åíü âå-
ëèêî. Ñîãëàñíî [9–11] ñîâîêóïíîñòü íåðàâåíñòâ ñèñòåìû (7), (8), èìåþùèõ
îäèíàêîâîå çíà÷åíèå i âåðõíåãî ïðåäåëà ñóììèðîâàíèÿ, áóäåì íàçûâàòü i-é
ãðóïïîé íåðàâåíñòâ ýòîé ñèñòåìû.  ÷àñòíîñòè, â êàæäóþ i-þ ãðóïïó âõîäèò
C n
i íåðàâåíñòâ. Îòñþäà èìååì îáùåå ÷èñëî íåðàâåíñòâ p C
i
n
n
i n� �
�
�
0
2 .
Ïîñêîëüêó èç n êîîðäèíàò a j Nj n, � , òîëüêî k ðàçëè÷íû, òî èç ñèñòåìû íåðà-
âåíñòâ (7), (8) ìîæíî èñêëþ÷èòü íåêîòîðûå íåðàâåíñòâà. Ñ ó÷åòîì âûïîëíå-
íèÿ óñëîâèÿ (6) äëÿ ëþáîãî j N i ni� �� 1, , èìååò ìåñòî ðàâåíñòâî a aj j� � 1.
 ýòîì ñëó÷àå ïðè âûïîëíåíèè íåðàâåíñòâ ïåðâîé ãðóïïû â ñèñòåìå (7), (8)
áóäóò òàêæå ñïðàâåäëèâû íåðàâåíñòâà âòîðîé, òðåòüåé, …, in -é ãðóïï. Äå-
éñòâèòåëüíî, ïîñêîëüêó x aj � 1, j N n� , òî äëÿ ëþáîãî i N n� âûïîëíÿåòñÿ
óñëîâèå
j
i
x ia
j
�
� �
1
1� . Ñëåäîâàòåëüíî, èç ñèñòåìû (7), (8), îïèñûâàþùåé ïåðå-
ñòàíîâî÷íûé ìíîãîãðàííèê, ìîæíî èñêëþ÷èòü íåðàâåíñòâà ãðóïï âòîðîé,
òðåòüåé,..., i-é è îáùåå ÷èñëî íåðàâåíñòâ áóäåò ñîñòàâëÿòü
N n C
j i
n
n
j� � �
� �
�1
1
. Åñëè íàáîð ÷èñåë ( , , , )a a an1 2 � îáëàäàåò ñâîéñòâîì
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
a a j N Nj j n n i� � �� � �1 1 \ , òî â ñèñòåìå (7), (8) äîñòàòî÷íî îñòàâèòü òîëüêî
íåðàâåíñòâà ïåðâîé, âòîðîé, …, ( )n j� -é ãðóïï.
Âàæíî ïðàâèëüíî îðãàíèçîâàòü íà ïåðâîì ýòàïå ðåøåíèÿ çàäà÷è âûáîð àêòèâíûõ
îãðàíè÷åíèé-íåðàâåíñòâ. Äëÿ ðåøåíèÿ çàäà÷è Z F X( , ) íåîáõîäèìî ó÷åñòü íà íà÷àëü-
íîì ýòàïå ëèøü ÷àñòü îãðàíè÷åíèé, êîòîðûå îïðåäåëÿþò îáëàñòü X . Ïîñêîëüêó îïðå-
äåëåíèå ýôôåêòèâíûõ ðåøåíèé çàäà÷è Z F X( , ) ÿâëÿåòñÿ áîëåå âàæíûì, ÷åì ïîñòðî-
åíèå âñåãî ìíîæåñòâà îãðàíè÷åíèé, îïèñûâàþùèõ äîïóñòèìóþ îáëàñòü G, ïîýòîìó
äîñòàòî÷íî ïîñòðîèòü òîëüêî òå îãðàíè÷åíèÿ ìíîæåñòâà G, êîòîðûå îïðåäåëÿþò ýô-
ôåêòèâíûå ðåøåíèÿ äàííîé çàäà÷è. Ðàññìàòðèâàåìûé çäåñü ìåòîä ïðåäíàçíà÷åí äëÿ
ïîëó÷åíèÿ òàêèõ îãðàíè÷åíèé.
Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ. Äîïóñòèìóþ îáëàñòü çàäà÷è Z F G( , ) çàïè-
øåì â âèäå G x R Hx gn� � �{ }| , g g g gq� ( , , , )1 2 � , H R q n� � , H — ìàòðèöà,
êîòîðàÿ èñïîëüçóåòñÿ äëÿ ìàòðè÷íî-âåêòîðíîé ôîðìû çàïèñè îãðàíè÷åíèé âèäà
(7), (8) è ëèíåéíûõ íåðàâåíñòâ, îïèñûâàþùèõ ìíîãîãðàííèê D, ãäå âñå îãðàíè÷å-
íèÿ ñâåäåíû ê îäíîìó ( � ) âèäó íåðàâåíñòâ. Îáîçíà÷èì N q ìíîæåñòâî, ýëåìåí-
òû êîòîðîãî îïðåäåëÿþò íîìåðà îãðàíè÷åíèé ñèñòåìû (7), (8) è äîïîëíèòåëüíûõ
îãðàíè÷åíèé, îïèñûâàþùèõ âûïóêëîå ìíîãîãðàííîå ìíîæåñòâî
D N mq
n: , , ,� �{ }1 2 2� .
Îïðåäåëèì ìíîæåñòâà G x R h x g i Ni
n
i i q� � � �{ }| , , , äëÿ ïðîèçâîëüíîãî
x Rs n� îïðåäåëèì ìíîæåñòâà N x i N h x ga s
q i
s
i( ) | ,� � �{ } è
N x j N h x gn s
q j
s
j( ) | ,� � �{ } — ñîîòâåòñòâåííî àêòèâíûõ è íåàêòèâíûõ
îãðàíè÷åíèé â òî÷êå x s; h Ri
n� , g Ri � , i N q� , — ñîîòâåòñòâåííî i-ÿ âåê-
òîð-ñòðîêà ìàòðèöû H è i-ÿ êîìïîíåíòà âåêòîðà g.
Ââåäåì â ðàññìîòðåíèå çàäà÷ó
Z F G F x x Gs s( , ) : max ( ) |{ }� ,
ãäå G x R h x g i Q Ns n
i i s q� � � � �{ }| , , ,
Qs — ìíîæåñòâî èíäåêñîâ îãðàíè÷åíèé, îïèñûâàþùèõ äîïóñòèìóþ îáëàñòü çàäà÷è
Z F G s( , ), êîòîðàÿ ðåøàåòñÿ íà s-ì øàãå àëãîðèòìà, Q N Rs q s� \ ; Rs — ìíîæåñ-
òâî íîìåðîâ îãðàíè÷åíèé, êîòîðûå íå áûëè âêëþ÷åíû â ýòó çàäà÷ó íà s-ì øàãå.
Îïðåäåëåíèå 2. Âåëè÷èíà r x h x gi i i( ) ,� � , i N q� , íàçûâàåòñÿ îòêëîíåíèåì
òî÷êè x R n� îò ãðàíèöû ìíîæåñòâà Gi , à âåëè÷èíà r x( ) �max ( ) |{r xi i N q� } — îò-
êëîíåíèåì òî÷êè x R n� îò ãðàíèöû ìíîæåñòâà G.
Î÷åâèäíî, ÷òî äëÿ i N p�
r x x ai
j
i
j
i
jj
( ) � �
� �
� �
1 1
� , (19)
à äëÿ i N Nq p� \ èìååì
r x b x di i i( ) ,� � , (20)
ãäå bi — i-ÿ âåêòîð-ñòðîêà ìàòðèöû B, d Ri � .
Òåîðåìà 5. Ýôôåêòèâíîå (Ïàðåòî-îïòèìàëüíîå, ñëàáî ýôôåêòèâíîå, ñòðîãî
ýôôåêòèâíîå) ðåøåíèå x0 çàäà÷è Z F G s( , ) ÿâëÿåòñÿ ýôôåêòèâíûì â òîì æå
ñìûñëå ðåøåíèåì çàäà÷è Z F G( , ) òîãäà è òîëüêî òîãäà, êîãäà âûïîëíÿåòñÿ óñëî-
âèå r x( ) � 0.
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü ýòîãî óòâåðæäåíèÿ î÷åâèäíà, ïîñêîëüêó
äîïóñòèìîå ðåøåíèå x0 çàäà÷è Z F G s( , ) ÿâëÿåòñÿ äîïóñòèìûì ðåøåíèåì çàäà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 165
÷è Z F G( , ) òîãäà è òîëüêî òîãäà, êîãäà âûïîëíÿåòñÿ óñëîâèå r x( ) � 0. Äîñòàòî÷íîñòü
óòâåðæäåíèÿ ñëåäóåò èç ïîñòðîåíèÿ çàäà÷è Z F G( , ) è îïðåäåëåíèÿ r x( ).
Îñíîâíàÿ èäåÿ ïðåäëàãàåìîãî ìåòîäà ðåøåíèÿ çàäà÷è Z F X( , ) ñîñòîèò â
ñëåäóþùåì.
1. Ñâîäèì ìíîãîêðèòåðèàëüíóþ çàäà÷ó Z F G( , ) ê îäíîêðèòåðèàëüíîé çàäà-
÷å Z f G( , ) ìåòîäîì ëèíåéíîé ñâåðòêè. Ïîëàãàåì s � 0.
2. Âûáèðàåì îãðàíè÷åíèÿ íà÷àëüíîé ñèñòåìû, êîòîðàÿ îïðåäåëÿåò îáëàñòü
G Gs � , ðåøàåì çàäà÷ó Z f G s( , ) ñ ïîìîùüþ ñèìïëåêñ-ìåòîäà è íàõîäèì îïòè-
ìàëüíîå ðåøåíèå x s.
3. Åñëè ïîëó÷åííîå îïòèìàëüíîå ðåøåíèå ÿâëÿåòñÿ ïåðåñòàíîâêîé, ò.å. âåðøè-
íîé ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà Ï , òî â íàéäåííîé òî÷êå x s ïðîâåðÿåì âû-
ïîëíåíèå îãðàíè÷åíèé, êîòîðûå íå áûëè ó÷òåíû. Î÷åâèäíî, èìè ìîãóò áûòü ëèøü
òå îãðàíè÷åíèÿ, êîòîðûå îïèñûâàþò âûïóêëîå ìíîãîãðàííîå ìíîæåñòâî D. Åñëè ðå-
øåíèå x s íå óäîâëåòâîðÿåò ýòèì îãðàíè÷åíèÿì (äîïîëíèòåëüíûì), òî ñëåäóåò äîáà-
âèòü ê îãðàíè÷åíèÿì äîïóñòèìîé îáëàñòè çàäà÷è Z f G s( , ) íàèáîëåå íàðóøåííîå
èç îãðàíè÷åíèé ìíîãîãðàííîãî ìíîæåñòâà D. Åñëè ðåøåíèå x s óäîâëåòâîðÿåò óêà-
çàííûì îãðàíè÷åíèÿì, òî îíî ÿâëÿåòñÿ ýôôåêòèâíûì ðåøåíèåì çàäà÷è Z F G( , ) è,
ñëåäîâàòåëüíî, çàäà÷è Z F X( , ) .
4. Åñëè ïîëó÷åííîå ðåøåíèå x s íå ÿâëÿåòñÿ ïåðåñòàíîâêîé, òî ñòðîèì îòñå-
÷åíèå, ïðîõîäÿùåå ÷åðåç ñìåæíûå âåðøèíû è îòñåêàþùåå âåðøèíó, êîòîðàÿ íå
ÿâëÿåòñÿ äîïóñòèìîé (ïåðåñòàíîâêîé). Ïðèáàâëÿåì ýòî îòñå÷åíèå ê
îãðàíè÷åíèÿì çàäà÷è Z f G s( , ) .
5. Ñðàâíèâàåì çíà÷åíèå f x s( ) ñî çíà÷åíèåì öåëåâîé ôóíêöèè, íàéäåííûì íà
ïðåäûäóùåì øàãå. Åñëè îíî óìåíüøàåòñÿ, òî èñêëþ÷àåì íåàêòèâíûå (íåñóùåñòâåííûå)
îãðàíè÷åíèÿ â òî÷êå x s. Åñëè çíà÷åíèå f x s( ) íå èçìåíÿåòñÿ, òî íèêàêèå îãðàíè÷åíèÿ
íå èñêëþ÷àåì. Ñ èçìåíåííîé îïèñàííûì îáðàçîì äîïóñòèìîé îáëàñòüþ çàäà÷è
Z f G s( , ) ïåðåõîäèì ê ïóíêòó 2 äëÿ ðåøåíèÿ ýòîé çàäà÷è.
Òî îáñòîÿòåëüñòâî, ÷òî íè îäíî èç îãðàíè÷åíèé íå îòáðàñûâàåòñÿ, åñëè
f x s( ) îñòàåòñÿ ðàâíûì ïðåäûäóùåìó çíà÷åíèþ, ãàðàíòèðóåò ðåøåíèå òîëüêî
êîíå÷íîãî ÷èñëà çàäà÷ âèäà Z f G s( , ).
Îáùàÿ èäåÿ ïðåäëîæåííîãî ìåòîäà ñîñòîèò â ïîñëåäîâàòåëüíîì âêëþ÷åíèè
îãðàíè÷åíèé çàäà÷è, îïèñûâàþùèõ îáëàñòü äîïóñòèìûõ ðåøåíèé. Ðåàëèçàöèÿ
ìåòîäà â âèäå àëãîðèòìà îïèñàíà íèæå.
Äëÿ ïðîâåðêè ïðèíàäëåæíîñòè òî÷êè ìíîæåñòâó ïåðåñòàíîâîê P Ank ( ) öåëå-
ñîîáðàçíî âîñïîëüçîâàòüñÿ ñëåäóþùèìè òåîðåìàìè [9, 10].
Òåîðåìà 6. Åñëè x x x xn� ( , , , )1 2 � — òî÷êà, êîîðäèíàòû êîòîðîé óïîðÿäî÷å-
íû ñëåäóþùèì îáðàçîì: x x j N
j j n� �� � �
� �1 1, è âûïîëíÿåòñÿ îãðàíè÷åíèå
x x x a a a
i i� � �1 2 1 2� � � � � � �� � ,
ïðèíàäëåæàùåå i-é ãðóïïå íåðàâåíñòâ ñèñòåìû (7), (8), òî â òî÷êå x âûïîëíÿ-
þòñÿ è âñå îñòàëüíûå íåðàâåíñòâà i-é ãðóïïû ýòîé ñèñòåìû.
Òåîðåìà 7. Òî÷êà x x x xn� ( , , , )1 2 � òîãäà è òîëüêî òîãäà ÿâëÿåòñÿ âåðøèíîé
ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà Ï Ank ( ), êîãäà âûïîëíÿþòñÿ ñëåäóþùèå
óñëîâèÿ:
{ } { } { } { }� � � � � � �
1
1
1
2
2
2
1
1
1
1
1
� � � � ��
�
�
, , , , ,� � �
n
n
n n
n
n
nN ,
t
i
t
i
t nx a i N
t
i
� �
� �� � �
1 1
�
.
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
Ñôîðìóëèðîâàííûå âûøå òåîðåìû äàþò âîçìîæíîñòü ïðè ðåàëèçàöèè àëãî-
ðèòìà äëÿ ðåøåíèÿ çàäà÷è Z F X( , ) ìèíèìèçèðîâàòü çàòðàòû âðåìåíè íà ïðîâåð-
êó ïðèíàäëåæíîñòè íàéäåííîé òî÷êè êîìáèíàòîðíûì îãðàíè÷åíèÿì è óìåíü-
øèòü êîëè÷åñòâî îãðàíè÷åíèé â èñõîäíîé ñèñòåìå.
Ïðåäëîæåííûé àëãîðèòì ìîæíî èñïîëüçîâàòü äëÿ ðåøåíèÿ çàäà÷è Z F G( , )
áåç ó÷åòà âñåõ åå îãðàíè÷åíèé.
Ïåðåéäåì ê èçëîæåíèþ àëãîðèòìà ðåøåíèÿ.
5. ÀËÃÎÐÈÒÌ ÐÅØÅÍÈß ÌÍÎÃÎÊÐÈÒÅÐÈÀËÜÍÛÕ
ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÇÀÄÀ× ÍÀ ÏÅÐÅÑÒÀÍÎÂÊÀÕ
Íà÷àëüíûé øàã
Ïîëàãàåì s � 0. Ñâåäåì ìíîãîêðèòåðèàëüíóþ êîìáèíàòîðíóþ çàäà÷ó
Z F G( , ) ê îäíîêðèòåðèàëüíîé ñ ïîìîùüþ ëèíåéíîé ñâåðòêè: çàäàåì âåñîâûå íå-
îòðèöàòåëüíûå êîýôôèöèåíòû � j lj N, � , êîòîðûå îïðåäåëÿþò ñòåïåíü âàæíîñòè
êàæäîãî êðèòåðèÿ, è ìàêñèìèçèðóåì ëèíåéíóþ êîìáèíàöèþ öåëåâûõ ôóíêöèé,
ò.å. ðåøàåì çàäà÷ó
Z f G s( , ): {max f x c x
i
l
i i( ) ,�
�
�
1
� | � i � 0, i N l� ,
i
l
i
�
� �
1
1� , x G s� }.
 ñëó÷àå, åñëè êàêîé-ëèáî èç êîýôôèöèåíòîâ � i �1, à âñå äðóãèå � j � 0, i j� ,
i j N l, � , òî ðàññìàòðèâàåòñÿ îäíîêðèòåðèàëüíàÿ çàäà÷à ñ i-é öåëåâîé ôóíêöèåé.
Ïðè ïåðâîì âûïîëíåíèè ýòîãî øàãà ïîëàãàåì G Rs n� è f �!.
Îñíîâíàÿ ÷àñòü
1. Âûáèðàåì íà÷àëüíóþ òî÷êó x s ïðîèçâîëüíûì îáðàçîì, êàê ýëåìåíò îá-
ùåãî ìíîæåñòâà ïåðåñòàíîâîê, ëèáî ñîãëàñíî óòâåðæäåíèþ 2, óïîðÿäî÷èâàÿ êî-
ýôôèöèåíòû � i i lc i N" �, , öåëåâîé ôóíêöèè f x c x
i
l
i i( ) ,�
�
�
1
� , âû÷èñëÿåì
çíà÷åíèå f f x s� ( ).
2. Îïèøåì îãðàíè÷åíèÿ, ñîîòâåòñòâóþùèå òî÷êå x s è îïðåäåëÿþùèå âåðøèíó
îáùåãî ïåðåñòàíîâî÷íîãî ìíîãîãðàííèêà Ï Ank ( ), x Ï As
nk
s� ( ),
Ï A Ï A
nk
s
nk( ) ( )� . Ïîëàãàåì Q Ns p� .
3. Íàõîäèì îòêëîíåíèÿ r x i R N Qi
s
s q s( ) \� � � ïî ôîðìóëàì (19), (20).
4. Âûáèðàåì r x r x i Rs
i
s
s( ) max ( ) |� �{ } è íîìåð i Rs s� , ïðè êîòîðîì äîñ-
òèãàåòñÿ ìàêñèìóì.
5. Ïðîâåðÿåì íåðàâåíñòâî r x s( ) � 0. Åñëè r x s( )
0, òî ïåðåõîäèì ê ñëåäóþ-
ùåìó ïóíêòó àëãîðèòìà, èíà÷å — íàõîäèì ýôôåêòèâíîå ðåøåíèå çàäà÷è
Z F X( , ). Äëÿ íàõîæäåíèÿ ñëåäóùåãî ýôôåêòèâíîãî ðåøåíèÿ ïåðåõîäèì íà íà-
÷àëüíûé øàã àëãîðèòìà, çàäàâ äðóãèå âåñîâûå êîýôôèöèåíòû � j , � j � 0, j N l� ,
j
l
i
�
� �
1
1� .
6. Ïðèáàâëÿåì ïîëó÷åííîå îãðàíè÷åíèå ñ íîìåðîì i Rs s� ê îãðàíè÷åíèÿì çà-
äà÷è Z f G s( , ), ò.å. ôîðìèðóåì äîïóñòèìîå ìíîæåñòâî ïîäçàäà÷è Z f G s( , ) ñëåäó-
þùèì îáðàçîì:
G G x R h x gs s n
i is s
� � � � �1 { }| , . (21)
7. Åñëè
f x fs( )� , (22)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 167
òî îïðåäåëÿåì ìíîæåñòâî N x Qn s
s( ) � è çàìåíÿåì ìíîæåñòâî Qs íà
Q N xs
n s\ ( ), ïîëàãàåì f f x s� ( ), s s� �1 .
8. Ðåøàåì çàäà÷ó
Z f G f x c x x Gs
i
l
i i
s( , ) : max ( ) , |� �
�
�
�
��
�
�
�
���
�
1
�
äâîéñòâåííûì ñèìïëåêñ-ìåòîäîì. Åñëè ýòà çàäà÷à íå èìååò ðåøåíèé, òî íå-
ðàçðåøèìà è çàäà÷à Z F G( , ). Èíà÷å ïîëó÷àåì îïòèìàëüíîå ðåøåíèå x s ýòîé
çàäà÷è. Åñëè îíî íå ÿâëÿåòñÿ ýëåìåíòîì îáùåãî ìíîæåñòâà ïåðåñòàíîâîê
P Ank ( ), òî ïåðåõîäèì ê ï. 8. Èíà÷å, ïîëàãàÿ Q Ns p� , ïåðåõîäèì ê ï. 3
àëãîðèòìà.
9. Íàõîäèì ñìåæíûå ñ òî÷êîé x s âåðøèíû ïåðåñòàíîâî÷íîãî ìíîãîãðàííè-
êà è ñòðîèì îòñå÷åíèå, ïðîõîäÿùåå ÷åðåç ýòè âåðøèíû, âèäà
h x gi i, � , (23)
êîòîðîìó íå óäîâëåòâîðÿåò ïîëó÷åííàÿ òî÷êà x s. Ôîðìèðóåì ñèñòåìó îãðàíè÷å-
íèé, îïèñûâàþùóþ ìíîæåñòâî G s, ïî ôîðìóëå (21) è ïåðåõîäèì ê ï. 7.
Çàìå÷àíèå 1 (ê ï. 7 àëãîðèòìà). Åñëè x s ÿâëÿåòñÿ ýëåìåíòîì îáùåãî ìíîæåñ-
òâà ïåðåñòàíîâîê P Ank ( ), òî ê ìíîæåñòâó N xn s( ) íåàêòèâíûõ îãðàíè÷åíèé, êîòî-
ðûå èñêëþ÷àþòñÿ èç ìíîæåñòâà Qs, ñëåäóåò îòíåñòè âñå îãðàíè÷åíèÿ ìíîãîãðàííèêà
Ï Ank ( ), êðîìå òåõ, êîòîðûå îïðåäåëÿþò òî÷êó x s.
Çàìå÷àíèå 2 (ê ï. 9 àëãîðèòìà). Ðàññìîòðèì áîëåå äåòàëüíî îïðåäåëåíèå
ñìåæíîé âåðøèíû è ïîñòðîåíèå îòñå÷åíèÿ.
Ñîãëàñíî òåîðèè ëèíåéíîãî ïðîãðàììèðîâàíèÿ [15] íà îñíîâàíèè ñèì-
ïëåêñ-òàáëèöû, êîòîðàÿ îïðåäåëÿåò íåêîòîðóþ âåðøèíó x s ìíîãîãðàííèêà ðå-
øåíèé, äëÿ ïîëó÷åíèÿ ñìåæíîé ñ íåé âåðøèíû íåîáõîäèìî âûáðàòü íåáàçèñíóþ
ïåðåìåííóþ x j â çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ, âåêòîð Pj êîòîðîé èìååò
õîòÿ áû îäíó ïîëîæèòåëüíóþ êîìïîíåíòó, âûáðàòü t-þ ñòðîêó
ñèìïëåêñ-òàáëèöû èç óñëîâèÿ
g
h
g
h
t
ij i h
i
ij
j
ij
� �
min
: 0
# , (24)
ãäå hij — êîýôôèöèåíòû ïðè íåèçâåñòíûõ x j â ñòðîêå i; gi — ñâîáîäíûé
÷ëåí â ñîîòâåòñòâóþùèõ îãðàíè÷åíèÿõ çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ
Z f G( , ). Äàëåå íóæíî ââåñòè â áàçèñ âåêòîð Pj âìåñòî Pt , ïîëó÷èâ ñèì-
ïëåêñ-òàáëèöó äëÿ íåêîòîðîé ñìåæíîé ñ x s âåðøèíû.
Ïîñòðîåíèå îòñå÷åíèé [11]. Îáîçíà÷èì J ñîâîêóïíîñòü íîìåðîâ íåáàçèñ-
íûõ ïåðåìåííûõ, äëÿ êîòîðûõ ìîæíî îïðåäåëèòü ñîîòíîøåíèå (24), à I — ìíî-
æåñòâî íîìåðîâ áàçèñíûõ ïåðåìåííûõ. Íà îñíîâå ïîñëåäíåé ñèìïëåêñ-òàáëèöû
çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ çàïèøåì îãðàíè÷åíèå, êîòîðîå
îïðåäåëÿåòñÿ áàçèñíîé ïåðåìåííîé (ñ íîìåðîì i),
x h x h x gi i j i j i� � � �� �, ( ) , ( )� � � �1 1
� ,
ãäå i I� , � � | |I , � � | |J , I J N n � � 1, � �� � �n 1, j J N � � � � .
Ïóñòü x x x n
* * *)( , ,� 1 � — îïòèìàëüíîå ðåøåíèå çàäà÷è ëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ, êîòîðîìó ñîîòâåòñòâóåò ïîñëåäíÿÿ ñèìïëåêñ-òàáëèöà. Êàê èç-
âåñòíî [15], åñëè j j J N ( )� � � — íîìåðà íåáàçèñíûõ ïåðåìåííûõ â ðåøå-
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
íèè çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ Z f G s( , ), à âåëè÷èíà # j âû÷èñëÿåòñÿ
ïî ôîðìóëå (24), òî âñå ñìåæíûå ñ x * âåðøèíû äîïóñòèìîé îáëàñòè
óäîâëåòâîðÿþò íåðàâåíñòâî
x x x
j
j
j
j
j
j
1
1
2
2
1
# # #
� � � ��
�
�
(25)
êàê ðàâåíñòâî, à òî÷êà x * íåðàâåíñòâó (25) íå óäîâëåòâîðÿåò.
Ñîãëàñíî èçëîæåííîìó âûøå ñòðîèì îòñå÷åíèå (23) â âèäå (25). Ãèïåðïëîñ-
êîñòü, ÿâëÿþùàÿñÿ ãðàíèöåé îòñå÷åíèÿ (25), ïðîõîäèò ÷åðåç ñìåæíûå âåðøèíû ê
îòñåêàåìîé òî÷êå x * . Ïîñòðîåííàÿ ãèïåðïëîñêîñòü ïåðåñåêàåò ãðàíè äîïóñòè-
ìîé îáëàñòè G s òîëüêî ïî åå âåðøèíàì. Òàêèì îáðàçîì, íîâûõ âåðøèí â îáëàñ-
òè íå îáðàçóåòñÿ, à ÷èñëî âåðøèí îáëàñòè óìåíüøàåòñÿ íà îäíó.
Òåîðåìà 8. Ðàáîòà àëãîðèòìà çàêàí÷èâàåòñÿ ïîñëå ðåøåíèÿ êîíå÷íîãî ÷èñëà
ïîäçàäà÷ Z f G s( , ) è ïðèâîäèò ê ýôôåêòèâíîìó ðåøåíèþ çàäà÷è Z F X( , ) èëè ê
ïîñòðîåíèþ òàêîãî ìíîæåñòâà îãðàíè÷åíèé, ïðè êîòîðîì òåêóùàÿ ïîäçàäà÷à
Z f G s( , ) áóäåò íåðàçðåøèìîé.
Äîêàçàòåëüñòâî. Òàê êàê X — êîíå÷íîå ìíîæåñòâî, òî îíî èìååò êîíå÷íîå
÷èñëî ïîäìíîæåñòâ. Ïðè óìåíüøåíèè çíà÷åíèÿ öåëåâîé ôóíêöèè
f x c x
i
l
i i( ) max ,�
�
�
1
� îò îäíîãî øàãà ê äðóãîìó íè îäíî ïîäìíîæåñòâî íå
ìîæåò ïîâòîðèòüñÿ. Ïîñêîëüêó íè îäíî îãðàíè÷åíèå íå îòáðàñûâàåòñÿ, åñëè
f x fs( ) � , è â êðàéíåì ñëó÷àå îäíî èëè äâà îãðàíè÷åíèÿ äîáàâëÿþòñÿ, òî çíà÷å-
íèÿ f x s( ) ìîãóò îñòàâàòüñÿ ïîñòîÿííûìè ëèøü íà ïðîòÿæåíèè êîíå÷íîãî ÷èñëà
èòåðàöèé. Èòàê, çà êîíå÷íîå ÷èñëî øàãîâ ïðîöåäóðà çàêàí÷èâàåòñÿ.
Îòìåòèì, ÷òî ìåòîä ðåøåíèÿ çàäà÷è íà ïåðåñòàíîâêàõ íå äàåò îòâåòà íà âîï-
ðîñ, ÿâëÿåòñÿ ëè íàéäåííîå ðåøåíèå ñòðîãî ýôôåêòèâíûì. Ýòî ìîæíî ïðîâåðèòü,
ïîëüçóÿñü ñîîòíîøåíèåì (17).
6. ÌÀÒÅÌÀÒÈ×ÅÑÊÈÅ ÌÎÄÅËÈ ÍÅÊÎÒÎÐÛÕ ÏÐÈÊËÀÄÍÛÕ ÇÀÄÀ×
Çàäà÷à 1 (ìàêñèìèçàöèÿ ñêîðîñòè ïåðåäà÷è èíôîðìàöèè è êà÷åñòâà îòî-
áðàæåíèÿ). Ðàññìîòðèì ñèñòåìó, êîòîðàÿ îñóùåñòâëÿåò íàêîïëåíèå èíôîðìà-
öèè ïî ïðåäìåòíûì îáëàñòÿì (ïîðòàë) è ïåðåìåùåíèå èíôîðìàöèè íà ïåðñî-
íàëüíûå êîìïüþòåðû (ñåðâåðû, ðàáî÷èå ñòàíöèè, òåðìèíàëû è äð.). Èìååì m
ïðåäìåòíûõ îáëàñòåé A i Ni m, � , â êàæäîé èç êîòîðûõ íàêîïëåíî îïðåäåëåí-
íîå êîëè÷åñòâî åäèíèö èíôîðìàöèè ai
k k-ãî âèäà, k N p� , a Ai
k � , ò.å. a i
k ÿâ-
ëÿåòñÿ ýëåìåíòîì ìóëüòèìíîæåñòâà A a as� { }1, ,� , s mp� . Èíôîðìàöèÿ ðàñ-
ïðåäåëÿåòñÿ ìåæäó n ïåðñîíàëüíûìè êîìïüþòåðàìè B j , j N n� , íà êàæäîì èç
êîòîðûõ âûäåëåíî íå ìåíüøå, ÷åì b j
k åäèíèö èíôîðìàöèè îïðåäåëåííîé
ïðåäìåòíîé îáëàñòè k-ãî âèäà. Ñêîðîñòü ïåðåäà÷è åäèíèöû k-ãî âèäà èíôîð-
ìàöèè èç Ai , i N m� , îïðåäåëåííîé ïðåäìåòíîé îáëàñòè íà ïåðñîíàëüíûõ êîì-
ïüþòåðàõ B j , j N n� , ðàâíà
ij
k , à êîýôôèöèåíò êà÷åñòâà ïðåäñòàâëåíèÿ åäè-
íèöû k-ãî âèäà èíôîðìàöèè îïðåäåëåííîé ïðåäìåòíîé îáëàñòè Ai , i N m� ,
ïðè óñëîâèè, ÷òî îíà îòîáðàæàåòñÿ êà÷åñòâåííî íà ïåðñîíàëüíûõ
êîìïüþòåðàõ B j , j N n� , ðàâåí d ij
k .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 169
Íåîáõîäèìî îïðåäåëèòü òàêîé ïëàí ïåðåäà÷è è çàãðóçêè îáúåìà xij
k èíôîð-
ìàöèè k-ãî âèäà, k N p� , èç ïðåäìåòíûõ îáëàñòåé Ai , i N m� , íà ïåðñîíàëüíûå
êîìïüþòåðû B j , j N n� , ÷òîáû ñóììàðíûå ñêîðîñòè ïåðåäà÷è áûëè ìàêñèìàëü-
íûìè è ìàêñèìèçèðîâàëñÿ ñóììàðíûé êà÷åñòâåííûé êîýôôèöèåíò çàãðóçêè.
Ìàòåìàòè÷åñêàÿ ìîäåëü. Òðåáóåòñÿ îïðåäåëèòü
f x x
k
p
i
m
j
n
ij
k
ij
k
1
1 1 1
( ) max�
� � �
� � �
, f x d x
k
p
i
m
j
n
ij
k
ij
k
2
1 1 1
( ) max�
� � �
� � �
ïðè êîìáèíàòîðíûõ óñëîâèÿõ, êîòîðûå ó÷èòûâàþò ïåðåñòàíîâî÷íûå ñâîéñòâà
îáëàñòè äîïóñòèìûõ ðåøåíèé çàäà÷è
x x x x x x x P A
n p
p
mp
p
s s� � �( , , , , , , ) ( , , ) ( )
11
1
1
1
1 1� � � � � ,
è îãðàíè÷åíèÿõ íà îáúåìû çàãðóçêè îïðåäåëåííîãî âèäà èíôîðìàöèè íà êàæ-
äûé ïåðñîíàëüíûé êîìïüþòåð
i
m
ij
k
j
kx b
�
� �
1
, j N n� , k N p� .
Çàäà÷à 2 (âû÷èñëåíèÿ íà ñóïåðêîìïüþòåðå). Ðàññìîòðèì êëàñòåðíûé ñó-
ïåðêîìïüþòåð, êîòîðûé îñóùåñòâëÿåò áîëüøîé îáúåì ïàðàëëåëüíûõ âû÷èñëå-
íèé ïî îïðåäåëåííûì ïðîãðàììàì. Îñíîâíûìè õàðàêòåðèñòèêàìè êëàñòåðà áó-
äåì ñ÷èòàòü ïðîèçâîäèòåëüíîñòü ïðîöåññîðà è îïåðàòèâíóþ ïàìÿòü. Îïðåäåëåí-
íûå ïðîãðàììû òðåáóþò äëÿ îáðàáîòêè äàííûõ ñîîòâåòñòâóþùèé îáúåì
îïåðàòèâíîé ïàìÿòè è ñêîðîñòü âûïîëíåíèÿ. Íåîáõîäèìî òàê ðàñïðåäåëèòü ïðî-
ãðàììû ïî êëàñòåðàì, ÷òîáû îáùàÿ ïðîèçâîäèòåëüíîñòü è çàãðóæåííîñòü
êëàñòåðíîãî ñóïåðêîìïüþòåðà áûëè ìàêñèìàëüíûìè è êàæäàÿ ïðîãðàììà
âûïîëíÿëàñü íà îòäåëüíîì êëàñòåðå.
Ìàòåìàòè÷åñêàÿ ìîäåëü. Ïóñòü èìååì êëàñòåðíûé ñóïåðêîìïüþòåð, êîòî-
ðûé ñîñòîèò èç m êëàñòåðîâ Ai , êàæäûé èç êîòîðûõ õàðàêòåðèçóåòñÿ îáúåìîì îïå-
ðàòèâíîé ïàìÿòè èëè ïðîèçâîäèòåëüíîñòüþ (òàêòîâîé ÷àñòîòîé) ai , i N m� . Òðåáó-
åòñÿ îäíîâðåìåííî çàãðóçèòü íà âûïîëíåíèå n ïðîãðàììíûõ êîìïëåêñîâ B j ,
j N n� , êàæäûé èç êîòîðûõ õàðàêòåðèçóåòñÿ îáúåìîì îïåðàòèâíîé ïàìÿòè èëè
ñêîðîñòüþ âûïîëíåíèÿ b j .
Ïðîèçâîäèòåëüíîñòü p ij
k , i N m� , j N n� , êëàñòåðíîãî ñóïåðêîìïüþòåðà
îïðåäåëÿåòñÿ êîëè÷åñòâîì îïåðàöèé, îñóùåñòâëåííûõ çà ñåêóíäó êàæäûì ïðî-
öåññîðîì ñîîòâåòñòâóþùèõ êëàñòåðîâ ïðè âûïîëíåíèè k-é ïðîãðàììû j-ãî
ïðîãðàììíîãî êîìïëåêñà.
Çàíÿòûì áóäåì íàçûâàòü i-é êëàñòåð ïðè âûïîëíåíèè k-é ïðîãðàììû j-ãî
ïðîãðàììíîãî êîìïëåêñà, çàãðóæåííûé íà 100%. Òîãäà çàãðóæåííîñòü îïðåäåëÿ-
åòñÿ êàê ðàçíîñòü d dij
k
ij
ç� �100 , ãäå dij
ç — òåêóùàÿ çàíÿòîñòü êëàñòåðà (â ïðîöåí-
òàõ) ïðè âûïîëíåíèè k-é ïðîãðàììû j-ãî ïðîãðàììíîãî êîìïëåêñà íà i-ì
êëàñòåðå, i N m� , j N n� .
Ïåðåìåííàÿ xij
k , k N p� , i N m� , j N n� , õàðàêòåðèçóåò îáúåì îïåðàòèâíîé
ïàìÿòè, íåîáõîäèîé äëÿ âûïîëíåíèÿ k-é ïðîãðàììû j-ãî ïðîãðàììíîãî êîìïëåê-
ñà íà i-ì êëàñòåðå, è ìîæåò ïðèíèìàòü ëþáîå çíà÷åíèå èç ìóëüòèìíîæåñòâà A,
ãäå A a as� { }1, ,� , s pmn� ; P As� ( ) — îáùåå ìíîæåñòâî ïåðåñòàíîâîê âñåõ ýëå-
ìåíòîâ èç ìóëüòèìíîæåñòâà A, ãäå � — ÷èñëî ðàçëè÷íûõ ýëåìåíòîâ A. Îòìåòèì,
÷òî íåêîòîðûå ýëåìåíòû A ìîãóò áûòü íóëåâûìè.
Ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è ìîæåò áûòü ïðåäñòàâëåíà ñëåäóþùèì
îáðàçîì:
ìàêñèìèçèðîâàòü çàãðóæåííîñòü ðàáîòû êîìïüþòåðà
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
f x d x
k
p
i
m
j
n
ij
k
ij
k
1
1 1 1
( ) max�
� � �
� � �
è ïðîèçâîäèòåëüíîñòü
f x p x
k
p
i
m
j
n
ij
k
ij
k
2
1 1 1
( ) max�
� � �
� � �
ïðè îãðàíè÷åíèÿõ íà ðàçìåðû îïåðàòèâíîé ïàìÿòè çàãðóæåííûõ ïðîãðàìì ïî
êàæäîìó ïðîãðàììíîìó êîìïëåêñó è êàæäîìó êëàñòåðó
i
m
k
p
ij
k
jx b
� �
� � �
1 1
,
j N n� ,
j
n
k
p
ij
k
ix a
� �
� � �
1 1
, i N m� .
Äàííàÿ ìîäåëü îáåñïå÷èâàåò ìàêñèìàëüíîå èñïîëüçîâàíèå ðåñóðñîâ êëàñ-
òåðíîãî ñóïåðêîìïüþòåðà.
Ïðèìåð. Ïóñòü äåéñòâóþùèé êëàñòåðíûé ñóïåðêîìïüþòåð äëÿ ïàðàëëåëü-
íûõ âû÷èñëåíèé ñîñòîèò èç òðåõ êëàñòåðîâ ñ îïðåäåëåííûìè õàðàêòåðèñòèêàìè
(òàáë. 1). Íåîáõîäèìî îäíîâðåìåííî çàãðóçèòü íà âûïîëíåíèå òðè ïðîãðàììû,
êîòîðûå òðåáóþò 80, 35 è 95 Ãá îïåðàòèâíîé ïàìÿòè.
Ðåøåíèå. Âîçìîæíàÿ çàãðóæåííîñòü êëàñòåðîâ áóäåò ñîñòàâëÿòü ñîîòâå-
òñòâåííî 80, 60 è 50%. Ñîñòàâèì ìîäåëü çàäà÷è:
max , , ,F x x x1 1 2 34 2 2 2 1 2� � � ,
max , , ,F x x x2 1 2 30 8 0 6 0 5� � � ,
x x x1 2 3 100 150 70� � � � � .
Ðàññìîòðèì ìíîæåñòâî A � { }35 80 95; ; . Î÷åâèäíî, ÷òî ïåðåñòàíîâêà
x x x x� �( , , ) ( , , )1 2 3 95 80 35 ÿâëÿåòñÿ îïòèìàëüíûì ðåøåíèåì çàäà÷è ñî çíà÷åíè-
ÿìè ÷àñòè÷íûõ êðèòåðèåâ, ðàâíûìè
max , , ,F1 4 2 95 2 2 80 1 2 35 617� " � " � " � ,
max , , , ,F2 0 8 95 0 6 80 0 5 35 141 5� " � " � " � .
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå èññëåäîâàíû ñëîæíûå êîìáèíàòîðíûå ìíîãîêðèòåðèàëü-
íûå çàäà÷è íà ìíîæåñòâå ïåðåñòàíîâîê. Ðàññìîòðåíû íåêîòîðûå ñâîéñòâà äî-
ïóñòèìîé îáëàñòè êîìáèíàòîðíîé ìíîãîêðèòåðèàëüíîé çàäà÷è, ïîãðóæåííîé â
àðèôìåòè÷åñêîå åâêëèäîâî ïðîñòðàíñòâî. Ïîñòðîåí è îáîñíîâàí ìåòîä ðåøå-
íèÿ ñôîðìóëèðîâàííûõ çàäà÷. Ïðåäëîæåííûé ïîäõîä ìîæåò ïðèìåíÿòüñÿ äëÿ
ðåøåíèÿ ìíîãîêðèòåðèàëüíûõ çàäà÷ íà êîìáèíàòîðíîì ìíîæåñòâå ïåðåñòàíî-
âîê. Ïðîãðàììíàÿ ðåàëèçàöèÿ äàííîãî ïîäõîäà ïðåäîñòàâëÿåò âîçìîæíîñòü èñ-
ñëåäîâàòü è íàéòè ýëåìåíòû ìíîæåñòâà Ïàðåòî-îïòèìàëüíûõ ðåøåíèé
ìíîãîêðèòåðèàëüíûõ êîìáèíàòîðíûõ çàäà÷ ñ ó÷åòîì äðóãèõ êîìáèíàòîðíûõ
ñâîéñòâ îáëàñòè äîïóñòèìûõ ðåøåíèé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 171
Íîìåð
êëàñòåðà
Îïåðàòèâíàÿ
ïàìÿòü, Ãá
Ïðîèçâîäèòåëüíîñòü,
Ãôëîï/c
Çàíÿòîñòü êëàñòåðà íà
òåêóùèé ïåðèîä, %
1 100 4.2 20
2 150 2.2 40
3 70 1.2 50
Òàáëèöà 1
Äàëüíåéøåå ðàçâèòèå äàííîé ðàáîòû áóäåò íàïðàâëåíî íà ðåàëèçàöèþ è
àäàïòàöèþ ïðåäëîæåííîãî àëãîðèòìà, à òàêæå íà ðàçðàáîòêó íîâûõ ìåòîäîâ ðå-
øåíèÿ âåêòîðíûõ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñ å ð ã è å í ê î È .  . Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòèìèçà-
öèè. — Êèåâ: Íàóê. äóìêà, 1988. — 472 ñ.
2. Ñ å ð ã è å í ê î È . Â . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ êîìáèíà-
òîðíûõ çàäà÷ îïòèìèçàöèè. — Êèåâ: Íàóê. äóìêà, 1981. — 287 ñ.
3. Ñ å ð ã è å í ê î È .  . , Ê î ç å ð à ö ê à ÿ Ë . Í . , Ë å á å ä å â à Ò . Ò . Èññëåäîâàíèå óñòîé÷èâîñ-
òè è ïàðàìåòðè÷åñêèé àíàëèç äèñêðåòíûõ îïòèìèçàöèîííûõ çàäà÷. — Êèåâ: Íàóê. äóìêà,
1995. — 170 ñ.
4. Ñ å ð ã è å í ê î È . Â . , Ë å á å ä å â à Ò . Ò . , Ñ å ì å í î â à Í . Â . Î ñóùåñòâîâàíèè ðåøåíèé â
çàäà÷àõ âåêòîðíîé îïòèìèçàöèè //Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2000. — ¹ 6. —
Ñ. 39–46.
5. Ë å á º ä º â à Ò . Ò . , Ñ å ì å í î â à Í . Â . , Ñ å ð ã i º í ê î Ò . I . Óìîâè îïòèìàëüíîñòi òà ðîç-
â’ÿçóâàíîñòi â çàäà÷àõ ëiíiéíî¿ âåêòîðíî¿ îïòèì³çàö³¿ ç îïóêëîþ äîïóñòèìîþ ìíîæèíîþ //
Äîï. ÍÀÍÓ. — 2003. — ¹ 10. — Ñ. 80–85.
6. Ñ å ð ã è å í ê î È .  . , Ð î ù è í  . À . , Ñ å ì å í î â à Í .  . Íåêîòîðûå çàäà÷è öåëî÷èñëåí-
íîãî ïðîãðàììèðîâàíèÿ ñ íåîäíîçíà÷íî çàäàííûìè äàííûìè è èõ ðåøåíèå // Ïðîáëåìû
óïðàâëåíèÿ è èíôîðìàòèêè. — 1998. — ¹ 6. — Ñ. 116–123.
7. Ë å á å ä å â à Ò . Ò . , Ñ å ì å í î â à Í . Â Ñ å ð ã è å í ê î Ò . È . Óñòîé÷èâîñòü âåêòîðíûõ çàäà÷
öåëî÷èñëåííîé îïòèìèçàöèè: âçàèìîñâÿçü ñ óñòîé÷èâîñòüþ ìíîæåñòâ îïòèìàëüíûõ è íåîïòè-
ìàëüíûõ ðåøåíèé // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 4. — Ñ. 90–100.
8. Ï î ä è í î â ñ ê è é Â . Â . , Í î ã è í Â . Ä . Ïàðåòî-îïòèìàëüíûå ðåøåíèÿ ìíîãîêðèòåðèàëü-
íûõ çàäà÷. — Ì.: Íàóêà, 1982. — 256 ñ.
9. Ñ ò î ÿ í Þ . à . , ß ê î â ë å â Ñ .  . Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû ãåî-
ìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ. — Êèåâ: Íàóê. äóìêà, 1986. — 265 ñ.
10. Ñ ò î ÿ í Þ . Ã . , ª ì å ö ü Î . Î . Òåîðiÿ i ìåòîäè åâêëiäîâî¿ êîìáiíàòîðíî¿ îïòèìiçàöi¿. — Ê.:
Ií-ò ñèñòåì. äîñëiäæåíü îñâiòè, 1993. — 188 ñ.
11. ª ì å ö ü Î . Î . , Ê î ë º ÷ ê i í à Ë . Ì . Çàäà÷i êîìáiíàòîðíî¿ îïòèìiçàöi¿ ç äðîáîâî-ëiíiéíèìè
öiëüîâèìè ôóíêöiÿìè. — Ê.: Íàóê. äóìêà. — 2005. — 118 ñ.
12. Ð î ù è í Â . À . , Ñ å ì å í î â à Í . Â . , Ñ å ð ã è å í ê î È . Â . Âîïðîñû ðåøåíèÿ è èññëåäîâà-
íèÿ îäíîãî êëàññà çàäà÷ íåòî÷íîãî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ // Êèáåðíåòèêà. —
1989. — ¹ 2. — Ñ. 42–47.
13. Ð î ù è í Â . À . , Ñ å ì å í î â à Í . Â . , Ñ å ð ã è å í ê î È . Â . Äåêîìïîçèöèîííûé ïîäõîä ê
ðåøåíèþ íåêîòîðûõ çàäà÷ öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ ñ íåòî÷íûìè äàííûìè // Æóðí.
âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 1990. — 29, ¹ 5. — Ñ. 786–791.
14. Ë ý ñ ä î í Ë . Ñ . Îïòèìèçàöèÿ áîëüøèõ ñèñòåì. — Ì.: Ìèð, 1975. — 432 ñ.
15. Å ð ì î ë ü å â Þ . Ì . , Ë ÿ ø ê î È . È . , Ì è õ à ë å â è ÷ Â . Ñ . , Ò þ ï ò ÿ Â . È . Ìàòåìàòè-
÷åñêèå ìåòîäû èññëåäîâàíèÿ îïåðàöèé. — Êèåâ: Âèùà øêîëà, 1979. — 312 ñ.
Ïîñòóïèëà 11.01.2008
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
|
| id | nasplib_isofts_kiev_ua-123456789-72216 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| language | Russian |
| last_indexed | 2025-12-02T10:42:38Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Семенова, Н.В. Колечкина, Л.Н. Нагорная, А.Н. 2014-12-19T22:19:45Z 2014-12-19T22:19:45Z 2008 Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок/ Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и системный анализ. — 2008. — № 3. — С. 158-172. — Бібліогр.: 15 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/72216 519.8 Досліджено складні дискретні багатокритеріальні задачі на комбінаторній множині перестановок. Розглянуто деякі властивості допустимої області комбінаторної багатокритеріальної задачі, що занурена в арифметичний евклідів простір. Установлено умови оптимальності різних видів ефективних розв'язків. Побудовано й обгрунтовано новий підхід розв'язання сформульованих задач. Настоящая работа поддержана Фондом фундаментальных исследований Украины (проект № Ф251/094). 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/72216 |
| work_keys_str_mv | AT semenovanv podhodkrešeniûvektornyhzadačdiskretnoioptimizaciinakombinatornommnožestveperestanovok AT kolečkinaln podhodkrešeniûvektornyhzadačdiskretnoioptimizaciinakombinatornommnožestveperestanovok AT nagornaâan podhodkrešeniûvektornyhzadačdiskretnoioptimizaciinakombinatornommnožestveperestanovok |