О полных и квазиполных двухкритериальных задачах на графах
Изучаются достаточные условия наличия свойства полноты или квазиполноты в двухкритериальных задачах дискретной оптимизации с одинаковыми и различными критериями весового вида. Вычислена оценка мощностей множеств допустимых решений, паретовского множества и полного множества альтернатив для ряда зада...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/144869 |
| 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: | О полных и квазиполных двухкритериальных задачах на графах / В.А. Перепелица, Э.В. Терещенко // Кибернетика и системный анализ. — 2018. — Т. 54, № 3. — С. 51–57. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-144869 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1448692019-01-09T01:23:00Z О полных и квазиполных двухкритериальных задачах на графах Перепелица, В.А. Терещенко, Э.В. Кібернетика Изучаются достаточные условия наличия свойства полноты или квазиполноты в двухкритериальных задачах дискретной оптимизации с одинаковыми и различными критериями весового вида. Вычислена оценка мощностей множеств допустимых решений, паретовского множества и полного множества альтернатив для ряда задач с двумя критериями. Вивчаються достатні умови наявності властивості повноти або квазіповноти у двокритерійних задачах дискретної оптимізації з однаковими і різними критеріями вагового вигляду. Обчислено оцінку потужностей множин допустимих розв'язків, паретовської множини і повної множини альтернатив для низки задач з двома критеріями. This article is devoted to the study of sufficient conditions for using the completeness or quasicompleteness properties in two-criteria discrete optimization problems with the same and different weight-type criteria. The authors evaluated the cardinalities of sets of acceptable solutions, the Pareto set, and a complete set of alternatives for several two-criteria problems. 2018 Article О полных и квазиполных двухкритериальных задачах на графах / В.А. Перепелица, Э.В. Терещенко // Кибернетика и системный анализ. — 2018. — Т. 54, № 3. — С. 51–57. — Бібліогр.: 8 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/144869 519.176 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 |
2018 |
| topic_facet |
Кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/144869 |
| citation_txt |
О полных и квазиполных двухкритериальных задачах на графах / В.А. Перепелица, Э.В. Терещенко // Кибернетика и системный анализ. — 2018. — Т. 54, № 3. — С. 51–57. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT perepelicava opolnyhikvazipolnyhdvuhkriterialʹnyhzadačahnagrafah AT tereŝenkoév opolnyhikvazipolnyhdvuhkriterialʹnyhzadačahnagrafah |
| first_indexed |
2025-07-10T20:23:55Z |
| last_indexed |
2025-07-10T20:23:55Z |
| _version_ |
1837292891195572224 |
| fulltext |
ÓÄÊ 519.176
Â.À. ÏÅÐÅÏÅËÈÖÀ, Ý.Â. ÒÅÐÅÙÅÍÊÎ
Î ÏÎËÍÛÕ È ÊÂÀÇÈÏÎËÍÛÕ ÄÂÓÕÊÐÈÒÅÐÈÀËÜÍÛÕ
ÇÀÄÀ×ÀÕ ÍÀ ÃÐÀÔÀÕ
Àííîòàöèÿ. Èçó÷àþòñÿ äîñòàòî÷íûå óñëîâèÿ íàëè÷èÿ ñâîéñòâà ïîëíîòû
èëè êâàçèïîëíîòû â äâóõêðèòåðèàëüíûõ çàäà÷àõ äèñêðåòíîé îïòèìèçàöèè
ñ îäèíàêîâûìè è ðàçëè÷íûìè êðèòåðèÿìè âåñîâîãî âèäà. Âû÷èñëåíà îöåíêà
ìîùíîñòåé ìíîæåñòâ äîïóñòèìûõ ðåøåíèé, ïàðåòîâñêîãî ìíîæåñòâà è ïîëíî-
ãî ìíîæåñòâà àëüòåðíàòèâ äëÿ ðÿäà çàäà÷ ñ äâóìÿ êðèòåðèÿìè.
Êëþ÷åâûå ñëîâà: ìíîãîêðèòåðèàëüíàÿ îïòèìèçàöèÿ, ïàðåòîâñêîå ìíîæåñò-
âî, ïîëíîå ìíîæåñòâî àëüòåðíàòèâ, ïîëíàÿ çàäà÷à, êâàçèïîëíàÿ çàäà÷à.
 ðàçëè÷íûõ îáëàñòÿõ äåÿòåëüíîñòè ÷åëîâåêà ïðèíèìàåìîå ðåøåíèå ïðèõîäèòñÿ
îöåíèâàòü ìíîãèìè êðèòåðèÿìè êà÷åñòâà, âñëåäñòâèå ÷åãî âîçíèêàåò íåîáõîäèìîñòü
â ðàññìîòðåíèè ìíîæåñòâà àëüòåðíàòèâ. Ýòî â îáùåì ñëó÷àå ïðèâîäèò ê ñèòóàöèè,
êîãäà äëÿ êàæäîãî ðåøåíèÿ ñóùåñòâóþò àëüòåðíàòèâû, ò.å. äðóãèå ðåøåíèÿ, êàæ-
äîå èç êîòîðûõ ëó÷øå ðàññìàòðèâàåìîãî õîòÿ áû ïî îäíîìó êðèòåðèþ [1–3].
Îòëè÷èå ìíîãîêðèòåðèàëüíîé çàäà÷è îò îäíîêðèòåðèàëüíîé ñîñòîèò â òîì,
÷òî â ïåðâîì ñëó÷àå ïîëó÷àåì íå îäíî ðåøåíèå, à ìíîæåñòâî ðåøåíèé (ìíîæåñ-
òâî àëüòåðíàòèâ) [2, 4]. Îêîí÷àòåëüíûé âûáîð íàèáîëåå öåëåñîîáðàçíîãî ðåøå-
íèÿ äåëàåò ÷åëîâåê. Âîïðîñ î ïðèíÿòèè ðåøåíèé âûõîäèò çà ðàìêè ôîðìàëüíîãî
îïðåäåëåíèÿ ïîíÿòèÿ «îïòèìóì», «îïòèìàëüíîå ðåøåíèå» â ñâÿçè ñ òåì, ÷òî ýòî
ïîíÿòèå ìîæåò îòíîñèòüñÿ ê íå ìåíåå ÷åì äâóì ðàçëè÷íûì ýëåìåíòàì (â îáùåì
ñëó÷àå). Îòñþäà âîçíèêàåò ìàòåìàòè÷åñêàÿ íåîäíîçíà÷íîñòü ïðîáëåìû îïðåäå-
ëåíèÿ «îïòèìàëüíîãî ðåøåíèÿ» â ñëó÷àå ÷èñëà êðèòåðèåâ íå ìåíüøå äâóõ.
Ñèìâîëîì Z� , � �1 7, , îáîçíà÷èì ñôîðìóëèðîâàííóþ íà n-âåðøèííîì ãðàôå
G V E� ( , ) îäíîêðèòåðèàëüíóþ çàäà÷ó îïðåäåëåíèÿ ñîîòâåòñòâóþùåãî ìèíèìóìà
ñóììû âåñîâ ðåáåð. Ðàññìîòðèì ñëåäóþùèå çàäà÷è: Z1 — î ñîâåðøåííûõ ïàðî-
ñî÷åòàíèÿõ, Z2 — îá îñòîâíûõ äåðåâüÿõ, Z3 — î ðàçìåùåíèÿõ, Z4 — î ñîâåð-
øåííûõ ïàðîñî÷åòàíèÿõ íà äâóäîëüíîì ãðàôå ñ ðàâíûìè äîëÿìè, Z5 — î ãà-
ìèëüòîíîâûõ öèêëàõ, Z6 — î ãàìèëüòîíîâûõ öåïÿõ, Z7 — î íàçíà÷åíèÿõ. Ìíî-
æåñòâî âñåõ äîïóñòèìûõ ðåøåíèé (ÌÄÐ) çàäà÷è Z� ñ èíäèâèäóàëüíûì
êðèòåðèåì F x� ( ) îáîçíà÷èì X x� �� { }, ãäå x� — ïîäãðàô ( , )V E� ãðàôà G,
E E� � , � — èíäèâèäóàëüíûé íîìåð êðèòåðèÿ. Íàïðèìåð, åñëè â çàäà÷å î ãà-
ìèëüòîíîâûõ öèêëàõ Z5 äîáàâèòü îãðàíè÷åíèå «ïåðååçä èç ãîðîäà â ãîðîä íå
äîëæåí ïðåâûøàòü l åäèíèö», òî ïîëó÷èì íîâóþ çàäà÷ó Z�0
, ãäå � 0 7� .
Ñèìâîëîì Z� �1 2, îáîçíà÷èì äâóõêðèòåðèàëüíóþ çàäà÷ó íà äâóâçâåøåííîì
n-âåðøèííîì m-ðåáåðíîì ãðàôå ñ ìèíèìèçèðóåìûìè êðèòåðèÿìè F x
i�
( ) min� ,
i �1 2, , âåêòîðíîé öåëåâîé ôóíêöèè F x� � � �1 2 1 2, ,( ). Èíäåêñû � i , i �1 2, , îáîçíà÷à-
þò èíäèâèäóàëüíûå íîìåðà êðèòåðèåâ, ïðè÷åì ïîðÿäîê êðèòåðèåâ F x
i� ( ) îïðå-
äåëÿåò î÷åðåäíîñòü ðåøåíèÿ çàäà÷ Z
i� . Òàê, â ñëó÷àå Z1 2, ðåøåíèå íà÷èíàåòñÿ
ñ ðàññìîòðåíèÿ çàäà÷è î ñîâåðøåííûõ ïàðîñî÷åòàíèÿõ, à â ñëó÷àå Z6 1, — ñ íà-
õîæäåíèÿ ãàìèëüòîíîâûõ öåïåé.
Ìíîæåñòâî äîïóñòèìûõ ðåøåíèé çàäà÷è Z
� �1 2,
ïðåäñòàâëÿåò ñîáîé äîïóñòè-
ìîå ìíîæåñòâî ïàð X x x
� � � �
1 2 1 2,
( , )� { }, ãäå x X� �1 1
� , x X� �2 2
� , ñôîðìèðîâàí-
íîå íà îñíîâå èíôîðìàöèè î ãðàôå G è âèäà êðèòåðèåâ F x
i� ( ), i �1 2, .
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3 51
� Â.À. Ïåðåïåëèöà, Ý.Â. Òåðåùåíêî, 2018
Äàëåå èñïîëüçóåì ñëåäóþùèå îáîçíà÷åíèÿ: X x x� � � �1 2 1 2, ( , )� { } — ÌÄÐ çà-
äà÷è Z� �1 2, , ãäå ( , )x x� �1 2
— äîïóñòèìîå ðåøåíèå çàäà÷è Z� �1 2, , ïðåäñòàâëÿþùåå
ñîáîé äâà ïîäãðàôà x V E
i i� �� ( , ), i �1 2, , äàííîãî ãðàôà G V E� ( , ) ,
E E X
i� � �� : | |,1 2
— ìîùíîñòü ìíîæåñòâà X � �1 2, ;
~
,X � �1 2
— ïàðåòîâñêîå ìíî-
æåñòâî (ÏÌ) äâóõêðèòåðèàëüíîé çàäà÷è Z
� �1 2,
,
~
, ,X X� � � �1 2 1 2
� ; X
� �1 2
0
,
—
ïîëíîå ìíîæåñòâî àëüòåðíàòèâ (ÏÌÀ), îïðåäåëÿåìîå êàê ïîäìíîæåñòâî ÏÌ
X X
� � � �
1 2 1 2
0
, ,
~
� ìèíèìàëüíîé ìîùíîñòè | |
,
X
� �1 2
0 è òàêîå, ÷òî F X� � � �1 2 1 2
0
, ,
( ) �
� F X� � � �1 2 1 2, ,(
~
) [3–5].
Ðàññìîòðèì ñïîñîáû ïåðå÷èñëåíèÿ ÌÄÐ X x� � � �1 2 1 2, ,� { }, ÏÌ
~
,X � �1 2
, ÏÌÀ
X
� �1 2
0
,
è îïðåäåëåíèÿ ìîùíîñòåé ýòèõ ìíîæåñòâ íà îñíîâàíèè ÌÄÐ X �1
è X �2
ñîîòâåòñòâóþùèõ îäíîêðèòåðèàëüíûõ çàäà÷ Z�1
è Z�2
ñ öåëåâûìè ôóíêöèÿìè
F x� �1 1
( ), F x� �2 2
( ). Èíäåêñû � 1 è � 2 óñëîâèìñÿ íå èñïîëüçîâàòü òîãäà, êîãäà
ññûëàåìñÿ íà èçâåñòíûé îáùèé ñëó÷àé îáîçíà÷åíèÿ ïðèìåíÿåìûõ êðèòåðèåâ, ò.å.
áóäåì ïèñàòü F Z X X X, , ,
~
, 0 .
Ìíîãîêðèòåðèàëüíóþ çàäà÷ó Z íàçîâåì ïîëíîé, åñëè äëÿ ÌÄÐ X x� { } ñó-
ùåñòâóþò òàêèå ïàðàìåòðû âåêòîðíîé öåëåâîé ôóíêöèè F x( ), ïðè êîòîðûõ âû-
ïîëíÿåòñÿ ðàâåíñòâî X X X0 � �
~
.
Ïóñòü R S — åâêëèäîâî ïðîñòðàíñòâî ðàçìåðíîñòè S � 2. Èç îïðåäåëåíèÿ
ÏÌ è ÏÌÀ âûòåêàåò ñïðàâåäëèâîñòü ñëåäóþùåãî óòâåðæäåíèÿ [3].
Ëåììà 1. Äëÿ ëþáîé çàäà÷è ñ âåêòîðíîé öåëåâîé ôóíêöèåé âèäà
F X R S: � âûïîëíÿåòñÿ ðàâåíñòâî ìîùíîñòåé | | | (
~
)|X F X0 � , ò.å. ìîùíîñòü
ÏÌÀ ñîâïàäàåò ñ ìîùíîñòüþ îáðàçà ÏÌ F X(
~
) â S-êðèòåðèàëüíîì ïðîñòðàíñòâå.
Ïîëíîå ìíîæåñòâî àëüòåðíàòèâ ÿâëÿåòñÿ íàèáîëåå èíòåðåñíûì ìàòåìàòè-
÷åñêèì îáúåêòîì, ïîñêîëüêó ïðåäñòàâëÿåò ñîáîé îáîáùåíèå êëàññè÷åñêîãî ïîíÿ-
òèÿ «ðåøåíèå îïòèìèçàöèîííîé çàäà÷è». Íàéòè ÏÌÀ ïðè íàëè÷èè îäíîãî êðè-
òåðèÿ — çíà÷èò íàéòè êàêîé-ëèáî îïòèìóì. Åñëè êîëè÷åñòâî êðèòåðèåâ íå ìåíü-
øå äâóõ, òî äëÿ S-êðèòåðèàëüíîé çàäà÷è ìîùíîñòü ÏÌ è ÏÌÀ ðàâíà èëè áîëüøå
åäèíèöû: |
~
| | |X X� �0 1. Â [4, 5] äàíî íàèáîëåå ðàííåå îïðåäåëåíèå ÏÌÀ äëÿ äèñ-
êðåòíûõ ìíîãîêðèòåðèàëüíûõ çàäà÷. Â òåîðèè ìíîãîêðèòåðèàëüíûõ çàäà÷ ïðîâå-
äåíî ñèñòåìàòè÷åñêîå èññëåäîâàíèå âû÷èñëèòåëüíîé ñëîæíîñòè íàõîæäåíèÿ
ÏÌÀ äëÿ äâóõêðèòåðèàëüíûõ çàäà÷ [4–8]. Åñëè âåêòîðíàÿ öåëåâàÿ ôóíêöèÿ çàäà-
÷è ñîäåðæèò íå ìåíåå äâóõ êðèòåðèåâ âåñîâîãî âèäà, òî ïîëó÷àåì íå òîëüêî ýêñ-
ïîíåíöèàëüíóþ òðóäîåìêîñòü, íî è ýêñïîíåíöèàëüíóþ ïàìÿòü, ò.å. íîâîå
(òðåòüå) ñâîéñòâî, êîòîðîãî íå áûëî â îäíîêðèòåðèàëüíîì ñëó÷àå [4].
Ðàññìàòðèâàåì êëàññ K äâóõêðèòåðèàëüíûõ çàäà÷ íà n-âåðøèííûõ ãðàôàõ
G V E� ( , ), | |E m� , êàæäîìó ðåáðó e Et � , t m�1, , êîòîðîãî ïðèñâîåíà ïàðà âåñîâ
� i te( ), i �1 2, , t m�1, . Êàæäîå äîïóñòèìîå ðåøåíèå i �1 2, â îòäåëüíîñòè ñîñòîèò
èç îäíîãî âèäà êîìïîíåíò ñâÿçíîñòè, òàêèõ êàê ðåáðî, ãàìèëüòîíîâ öèêë, îñòîâ-
íîå äåðåâî è äð. Êëàññ çàäà÷, óäîâëåòâîðÿþùèõ ýòîìó óñëîâèþ, îáîçíà÷èì K 0 ,
ïðè÷åì K K0 .  äàëüíåéøèõ èññëåäîâàíèÿõ îãðàíè÷èìñÿ äâóõêðèòåðèàëüíû-
ìè çàäà÷àìè èç êëàññà K 0 .
Îïðåäåëèì åùå «ñïåöèàëüíîå äâóâçâåøèâàíèå» m-ðåáåðíîãî ãðàôà
G V E� ( , ), èëè, ÷òî òî æå ñàìîå, äâóõ n-âåðøèííûõ m-ðåáåðíûõ êîïèé ãðàôà G.
Ýòè îäíîâçâåøåííûå ãðàôû ðàçëè÷àþòñÿ òîëüêî âåñàìè ðåáåð. Âñå ðåáðà e E� ïðî-
íóìåðóåì ÷èñëàìè t m�1, . Êàæäîå ðåáðî et èìååò äâà âåñà — �1 ( )et , � 2 ( )et , òà-
êèõ, ÷òî èõ ñóììà ðàâíà ÷èñëó r0 , íàïðèìåð r m
0
12�
äëÿ êàæäîãî çíà÷åíèÿ t m�1, .
52 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3
Òåîðåìà 1. Ëþáàÿ äâóõêðèòåðèàëüíàÿ çàäà÷à Z K� �1 2
0, � ÿâëÿåòñÿ ïîëíîé,
åñëè åå âåêòîðíàÿ öåëåâàÿ ôóíêöèÿ F x F x F x� � � � � � � �1 2 1 2 1 1 2 2, ,( ) ( ( ), ( ))� , x
i� �
� ( , )V E
i�
, ñîñòîèò èç âåñîâûõ êðèòåðèåâ F x x e
i i i i
i
i
e E
� � � �� �
�
( ) ( ) ( ) min� � �
�
� ,
i �1 2, , îäíîãî òèïà � � �1 2� � .
Äîêàçàòåëüñòâî. Ïóñòü âûïîëíÿþòñÿ óñëîâèÿ òåîðåìû 1. Íà ÌÄÐ
X x x� � � �1 2 1 2, ( , )� { } îïðåäåëåíà âåêòîðíàÿ öåëåâàÿ ôóíêöèÿ, ñîñòîÿùàÿ èç äâóõ
âåñîâûõ êðèòåðèåâ îäíîãî òèïà F x x e
i i i i
i
i
e E
� � � �� �
�
( ) ( ) ( ) min� � �
�
� , i �1 2, ,
êîòîðûå ðàçëè÷àþòñÿ òîëüêî ÷èñëîâûìè çíà÷åíèÿìè. Äëÿ òðèâèàëüíûõ ñëó÷àåâ
(X � �1 2, � � èëè | |,X � �1 2
1� ) óòâåðæäåíèå òåîðåìû î÷åâèäíî. Ïóñòü ìîùíîñòü
ÌÄÐ | |
,
X
� �1 2
2� .  ãðàôå G V E� ( , ) ðåáðà e E� ïåðåíóìåðóåì ÷èñëàìè
t t e m� �( ) ,1 , m E� | |. Äëÿ êàæäîãî ðåáðà e Et � îïðåäåëèì ïåðâûé è âòîðîé âåñ
ñëåäóþùèì îáðàçîì:
�1 2( )t t� , � �2 0 1( ) ( )t r t�
, t t e m� �( ) ,1 , m E� | | , r m
0
12�
. (1)
Ñ ó÷åòîì òîãî, ÷òî Z K� �1 2
0, � è îáà êðèòåðèÿ èìåþò îäèí òèï, âûïîëíÿåòñÿ
ðàâåíñòâî | | ( )E C n C
i� � � �0 0 const äëÿ âñåõ äîïóñòèìûõ ðåøåíèé x
i� , i �1 2, ,
äâóõêðèòåðèàëüíîé çàäà÷è Z� �1 2
, . Ñëåäîâàòåëüíî,
F x F x C r Cm
� �1 2 0 0
1
02( ) ( )
� �
� �x X
i i� � , i �1 2, . (2)
Îáîçíà÷èì ðàçíîñòü R E E
i i i
k l k l
� � �
, \� äëÿ ïàðû x x X
i i i
k l
� � �, � , 1 � � �k l m,
i �1 2, . Òîãäà äëÿ ëþáûõ x x X
i i i
k l
� � �, � èìååì
R R
i i
l k k l
� �
, ,
� � �, | | | |, ,R R
i i
l k k l
� �
� , i �1 2, . (3)
Ïóñòü ñðåäè ýëåìåíòîâ ìíîæåñòâà R R
i i
l k k l
� �
, ,
� ðåáðî et ñ íàèáîëüøèì íîìå-
ðîì t ïðèíàäëåæèò R
i
k l
�
, . Òîãäà èç (1)–(3) âûòåêàþò íåðàâåíñòâà F x k
� �1 1
( ) �
� F x l
� �1 1
( ) , F x F xk l
� � � �2 2 2 2
( ) ( )� , îçíà÷àþùèå, ÷òî ëþáàÿ ïàðà ðåøåíèé
x x X
i i i
k l
� � �, � ÿâëÿåòñÿ âåêòîðíî-íåñðàâíèìîé ïî âåêòîðíîé öåëåâîé ôóíêöèè,
ïðèíÿòîé â óñëîâèÿõ òåîðåìû 1. Ïîñëåäíåå ñ ó÷åòîì ëåììû 1 îçíà÷àåò âûïîëíå-
íèå ðàâåíñòâà X X X
� � � � � �
1 2 1 2 1 2
0
, , ,
~
� � .
Òåîðåìà 1 äîêàçàíà.
Èññëåäóåì äâóõêðèòåðèàëüíûå çàäà÷è Z K� �1 2
0
, � , îáúåäèíÿþùèå íå ñîâïà-
äàþùèå ïî êðèòåðèÿì îäíîêðèòåðèàëüíûå çàäà÷è íà ãðàôàõ Z�1
è Z�2
. Âíà÷àëå
ðàññìîòðèì ïîñòàíîâêó, êîãäà êðèòåðèè F x
�1
( ), F x�2
( ) òàêîâû, ÷òî îäèí ÿâëÿåò-
ñÿ ÷àñòíûì ñëó÷àåì äðóãîãî. Ïðèìåðîì ìîæåò ñëóæèòü çàäà÷à Z2 6, îá îòûñêà-
íèè ìèíèìàëüíîãî îñòîâíîãî äåðåâà è ìèíèìàëüíîé ãàìèëüòîíîâîé öåïè. Ôîð-
ìóëèðîâêà çàäà÷è Z2 6, îáúåäèíÿåò äâå ïîñòàíîâêè çàäà÷ Z2 è Z6 . Íà ïåðâîì ýòà-
ïå ðàññìàòðèâàåì çàäà÷ó Z2 , êîãäà åå ÌÄÐ X 2 ïðåäñòàâëÿåò ñîáîé îáúåäèíåíèå
äâóõ íåïóñòûõ ïîäìíîæåñòâ X X X2 2
6
2
2� � , ãäå X
2
6 — ïîäìíîæåñòâî ãàìèëü-
òîíîâûõ öåïåé, X
2
2 — ïîäìíîæåñòâî îñòîâíûõ äåðåâüåâ, íå ÿâëÿþùèõñÿ ãà-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3 53
ìèëüòîíîâûìè öåïÿìè. Ó ïîäìíîæåñòâà X
2
2 íåò «ïàðòíåðîâ» â ìíîæåñòâå X 6 ,
ò.å. äëÿ ýëåìåíòîâ x X
2
2
2
2� íåò ñîîòâåòñòâóþùèõ èì ýëåìåíòîâ â ìíîæåñòâå
x X6 6� äëÿ îáðàçîâàíèÿ ïàð (x x
2
2
6, ). Òàêèì îáðàçîì, ýëåìåíòû x X
2
2
2
2� èñêëþ-
÷àþòñÿ èç ðàññìîòðåíèÿ. ×òî êàñàåòñÿ ýëåìåíòîâ x X
2
6
2
6� , òî ïî óñëîâèþ çàäà÷è
Z2 6, èõ êîëè÷åñòâî ñîâïàäàåò ñ ìîùíîñòüþ ìíîæåñòâà X 6 : | | | |X X
2
6
6� . Íà âòî-
ðîì ýòàïå ïîäìíîæåñòâî X
2
6 è ìíîæåñòâî X 6 îáðàçóþò ÌÄÐ X 2 6, çàäà÷è Z2 6, ,
ñîñòîÿùåå èç ñîîòâåòñòâóþùèõ ïàð x X
2
6
2
6� è x X6 6� ãàìèëüòîíîâûõ öåïåé
x X2 6 2 6, ,� , { }x x
2
6
6, , ïðè÷åì max | |
!
,X
n
2 6
2
� . Ñ èñïîëüçîâàíèåì âçâåøèâàíèÿ (1)
äëÿ ãðàôîâ x V E
2
6
2
6� ( , ), x V E6 6� ( , ) è ó÷åòîì (2), (3) äîêàçàíà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 2. Çàäà÷à Z2 6, ÿâëÿåòñÿ ïîëíîé. Ìàêñèìàëüíûå ìîùíîñòè ÌÄÐ,
ÏÌ è ÏÌÀ äâóõêðèòåðèàëüíîé çàäà÷è Z2 6, «îá îñòîâíîì äåðåâå è ãàìèëüòîíî-
âîé öåïè» ðàâíû | | |
~
| | |
!
, , ,
X X X
n
2 6 2 6 2 6
0
2
� � � , ò.å. ñîâïàäàþò ñ ìàêñèìóìîì äâóõ-
êðèòåðèàëüíîé çàäà÷è Z6 6, «î ãàìèëüòîíîâîé öåïè».
Äàëåå ðàññìîòðèì çàäà÷ó Z3 5, «î ðàçìåùåíèè è êîììèâîÿæåðå». Êðèòåðèé
«ðàçìåùåíèå» îòëè÷àåòñÿ îò êðèòåðèÿ «íàçíà÷åíèå» Z7 , ðàññìàòðèâàåìîãî íà
êâàäðàòíûõ ìàòðèöàõ, òîëüêî òåì, ÷òî ïîä çàïðåò ïîïàäàþò êëåòêè ãëàâíîé äèà-
ãîíàëè, ò.å. ñòàâèòñÿ çàäà÷à î ðàçìåùåíèè n ðåáåð íà n-âåðøèííîì ãðàôå.
Äîêàçàòåëüñòâî ñôîðìóëèðîâàííîé äàëåå òåîðåìû 3 ïîâòîðÿåò äîêàçàòåëüñòâî
òåîðåìû 2 ñ íåçíà÷èòåëüíûìè îòëè÷èÿìè: âìåñòî ( )n
1 ðåáåð ôèãóðèðóþò n ðå-
áåð, êîòîðûå íà ïåðâîì ýòàïå îáðàçóþò k-öèêëû, k n� . Äëÿ k n� ãàìèëüòîíîâû
öèêëû èñ÷åðïûâàþò âñå ìíîæåñòâî äîïóñòèìûõ ðåøåíèé çàäà÷è «î ðàçìåùåíèè
è êîììèâîÿæåðå». Ìàòðèöà ñìåæíîñòè çàäà÷è î êîììèâîÿæåðå Z5 ÿâëÿåòñÿ
÷àñòíûì ñëó÷àåì çàäà÷è î ðàçìåùåíèè.
Çàìåòèì, ÷òî ïàðà êðèòåðèåâ � �1 2 3 5, ,� íå òîëüêî ïðåäñòàâëÿåò ïîëíóþ
äâóõêðèòåðèàëüíóþ çàäà÷ó «î ðàçìåùåíèè è êîììèâîÿæåðå» Z3 5, , íî è îäíîâðå-
ìåííî âëå÷åò çà ñîáîé ïîëíîòó çàäà÷è Z2 6, «îá îñòîâíîì äåðåâå è ãàìèëüòîíî-
âîé öåïè». Îáðàòíîå íåâåðíî.
Òåîðåìà 3. Çàäà÷à Z3 5, ÿâëÿåòñÿ ïîëíîé. Ìàêñèìàëüíûå ìîùíîñòè ÌÄÐ,
ÏÌ è ÏÌÀ äâóõêðèòåðèàëüíîé çàäà÷è «î ðàçìåùåíèè è êîììèâîÿæåðå» Z3 5,
ðàâíû | | |
~
| | |
( )!
, , ,
X X X
n
3 5 3 5 3 5
0 1
2
� � �
, ò.å. ñîâïàäàþò ñ ñîîòâåòñòâóþùèìè ìàê-
ñèìóìàìè äâóõêðèòåðèàëüíîé çàäà÷è Z5 5, «î êîììèâîÿæåðå».
Îáîáùèì ïîëó÷åííûå ðåçóëüòàòû, ñôîðìóëèðîâàâ äîñòàòî÷íîå óñëîâèå íà-
ëè÷èÿ ñâîéñòâà ïîëíîòû çàäà÷è Z� �1 2
, .
Òåîðåìà 4. Äëÿ òîãî ÷òîáû äâóõêðèòåðèàëüíàÿ çàäà÷à Z� �1 2
, ñ âåêòîðíîé
öåëåâîé ôóíêöèåé F x F x F x� � � � � � � �1 2 1 2 1 1 2 2, ,( ) ( ( ), ( ))� áûëà ïîëíîé, äîñòàòî÷íî,
÷òîáû åå ÌÄÐ X � �1 2, ñîñòîÿëî èç òàêèõ ïîäãðàôîâ x x x� � � �1 2 1 2, ( , )� , äëÿ êîòî-
ðûõ âûïîëíÿåòñÿ ðàâåíñòâî ìàòðèö ñìåæíîñòè ïîäãðàôîâ x�1
è x�2
:
X x x x x x� � � � � � � �1 2 1 2 1 2 1 2, , ( , ),� � �{ }, ò.å. X X X� � � �1 2 1 2, � � . Ìîùíîñòü ÌÄÐ,
ÏÌ è ÏÌÀ äâóõêðèòåðèàëüíîé çàäà÷è Z� �1 2, ðàâíà | |X X� �1 2
� .
Äîêàçàòåëüñòâî àíàëîãè÷íî ïðèâåäåííûì äëÿ òåîðåì 2 è 3.
Äàëåå ðàññìîòðèì äâóõêðèòåðèàëüíûå çàäà÷è Z� �1 2, , � �1 2 7, � , ñ ÌÄÐ
X � �1 2, âèäà
X x x x x x x� � � � � � � � � �1 2 1 2 1 2 1 2 1 2, , ,: ( , ),� � { èëè x x� �1 2
� }.
Îñîáåííîñòü ýòèõ çàäà÷ â òîì, ÷òî äîïóñòèìûå ðåøåíèÿ x
�1
è x�2
èìåþò ðàç-
ëè÷íîå êîëè÷åñòâî ðåáåð | | | |E E� �1 2
� , ïðè÷åì | | max | |,
,
E E
i
� � �1 2 11 2
�
�
.
54 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3
Ðàññìîòðèì çàäà÷ó Z5 6, «î ãàìèëüòîíîâîì öèêëå–ãàìèëüòîíîâîé öåïè» íà
ãàìèëüòîíîâîì n-âåðøèííîì ãðàôå G V E� ( , ), â êîòîðîì ðåáðó et , t m�1, , ïðè-
ñâîåí âåêòîð âåñîâ � � �( ) ( ( ), ( ))e e et t t� 1 2 ñîãëàñíî (1). Íà ïåðâîì ýòàïå àëãî-
ðèòìà ðåøàåì çàäà÷ó Z5 5, .  ðåçóëüòàòå ïîëó÷àåì äâà ñïàðåííûõ ìíîæåñòâà ãà-
ìèëüòîíîâûõ öèêëîâ X X X5 5 5
1
5
2
, ( , )� , èç êîòîðûõ ïðåäñòàâëÿåò èíòåðåñ ïåðâîå:
X x
5
1
5
1� { },� , � �1, M , M X� | |
5
1 , ãäå x
5
1,� — n-âåðøèííûé ãàìèëüòîíîâ öèêë. Ñîã-
ëàñíî òåîðåìå 1 èìååò ìåñòî íåðàâåíñòâî | | | |,X X5 5 5
1� .
Íà âòîðîì ýòàïå àëãîðèòìà äëÿ êàæäîãî ãàìèëüòîíîâà öèêëà x
5
1,�, 1 � �� M ,
îñóùåñòâëÿåì n ïîñëåäîâàòåëüíûõ âû÷åðêèâàíèé îäíîãî ðåáðà k, k n�1, . Âû÷åð-
êèâàíèå ïðåâðàùàåò ãàìèëüòîíîâ öèêë x
5
1,� â ãàìèëüòîíîâó öåïü x k
6
2, ,� , 1 � �k n,
èç êîòîðûõ âûáèðàåì ãàìèëüòîíîâó öåïü x
6
2,� ñ ìèíèìàëüíîé äëèíîé. Îïðåäå-
ëèâ ýëåìåíò x
6
2,� äëÿ êàæäîãî �-ãî ãàìèëüòîíîâà öèêëà x
5
1,�, � �1, M , ôîðìèðó-
åì ïîëíîå ðåøåíèå X x x5 6 5
1
6
2
,
, ,( , )� { }� � , � �1, M , çàäà÷è Z5 6, .
Äàííàÿ çàäà÷à íå îáëàäàåò câîéñòâîì ïîëíîòû, òàê êàê åå ÌÄÐ íå ñîâïàäàåò
ñ ÏÌ è ÏÌÀ, ÷òî î÷åâèäíî ïî ðåçóëüòàòàì ïåðâîãî è âòîðîãî ýòàïîâ: äëÿ îäíîãî
äîïóñòèìîãî ðåøåíèÿ çàäà÷è î ãàìèëüòîíîâîì öèêëå ìîæíî ïîñòðîèòü n äîïóñ-
òèìûõ ðåøåíèé çàäà÷è î ãàìèëüòîíîâîé öåïè óäàëåíèåì îäíîãî ðåáðà öèêëà.
Ìíîãîêðèòåðèàëüíûå çàäà÷è, äëÿ êîòîðûõ ìàêñèìàëüíûå ìîùíîñòè ÌÄÐ, ÏÌ è
ÏÌÀ ïîä÷èíåíû ñîîòíîøåíèþ | | |
~
| | |
, , ,X X X
� � � � � �
1 2 1 2 1 2
0 � � , íàçîâåì êâàçèïîëíû-
ìè. Òàêèì îáðàçîì, äîêàçàíà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 5. Çàäà÷à Z5 6, «î ãàìèëüòîíîâîì öèêëå–ãàìèëüòîíîâîé öåïè» ÿâëÿ-
åòñÿ êâàçèïîëíîé. Ìàêñèìàëüíàÿ ìîùíîñòü ÌÄÐ çàäà÷è Z5 6, ðàâíà | |
!
,X
n
5 6
2
� è
íå ñîâïàäàåò ñ ìîùíîñòÿìè ÏÌ è ÏÌÀ, ðàâíûìè ìåæäó ñîáîé:
|
~
| | | | |, , ,X X X5 6 5 6
0
5 6� � . Ìàêñèìàëüíûå ìîùíîñòè ÏÌ è ÏÌÀ çàäà÷è Z5 6, ðàâíû
|
~
| | |
( )!
, ,
X X
n
5 6 5 6
0 1
2
� �
, ò.å. ñîâïàäàþò ñ ñîîòâåòñòâóþùèì ìàêñèìóìîì äâóõ-
êðèòåðèàëüíîé çàäà÷è Z5 5, î ãàìèëüòîíîâîì öèêëå.
Äàëåå ðàññìîòðèì çàäà÷ó Z1 2, «î ñîâåðøåííîì ïàðîñî÷åòàíèè è îñòîâíîì
äåðåâå», äîïóñòèìîå ðåøåíèå x1 êîòîðîé èìååò
n n
2 2
�
��
�
��
� êîìïîíåíò ñâÿçíîñòè,
à äîïóñòèìîå ðåøåíèå x2 ïðåäñòàâëÿåò ñîáîé îäíîñâÿçíûé ãðàô. Ïóñòü âûïîëíÿ-
þòñÿ ñîîòíîøåíèÿ | | | |E E1 2� , | |E
n n
1
2 2
� �
�
��
�
��
, à | |E n2 � .
Ïðèâåäåì áåç äîêàçàòåëüñòâà äâå ëåììû.
Ëåììà 2. Åñëè â äåðåâå ìîæíî âûäåëèòü ñîâåðøåííîå ïàðîñî÷åòàíèå, òî
îíî åäèíñòâåííî.
Ëåììà 3. Åñëè â ïðîèçâîëüíîì ñâÿçíîì ãðàôå ìîæíî âûäåëèòü ñîâåðøåííîå
ïàðîñî÷åòàíèå, òî îíî ÿâëÿåòñÿ ðåáåðíîïîðîæäåííûì ïîäãðàôîì íå ìåíåå îäíî-
ãî îñòîâíîãî äåðåâà.
Ëåììû 2, 3 ïîçâîëÿþò ïîñòðîèòü òðåõýòàïíûé àëãîðèòì ðåøåíèÿ çàäà÷è Z1 2, .
Äëÿ ýòîãî ïåðåíóìåðóåì âñå ðåáðà äàííîãî G V E� ( , ) ÷èñëàìè t m�1, , m E� | | ,
è êàæäîìó ðåáðó e Et � ïî àíàëîãèè ñ òåîðåìîé 1 ïðèïèñûâàåì äâà ñïåöèàëüíûõ
âåñà: �1 2( )et
t� , � 2
12 2( )et
m t�
, ÷òî â ñóììå äàåò êîíñòàíòó C m
0
12�
.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3 55
Íà ïåðâîì ýòàïå íà ãðàôå G V E� ( , ) ðåøàåòñÿ çàäà÷à Z1 1, î íàõîæäåíèè ìíî-
æåñòâà ñîâåðøåííûõ ïàðîñî÷åòàíèé X x x x V E1 1 1 1 1
1
1
2
1
1
, ,
, , ,( , ) ( , ),� � �{ } { } {� � � �
( , ),V E
1
2� }, � �1, M , M X� | |,1 1 . Ìíîæåñòâî ñîâåðøåííûõ ïàðîñî÷åòàíèé X 1 1, ïîíàäî-
áèòñÿ äëÿ âûäåëåíèÿ «ëåâîé» ÷àñòè X x1 1
1� { }�, , � �1, M , êîòîðàÿ ñîåäèíèòñÿ ñ ïðàâîé
÷àñòüþ X x2 2
2� { }�, ìíîæåñòâà ïàð îñòîâíûõ äåðåâüåâ íà âòîðîì ýòàïå àëãîðèòìà. Ìàê-
ñèìàëüíàÿ ìîùíîñòü ÌÄÐ X 1 1, äîñòèãàåòñÿ íà ïîëíîì ãðàôå è ðàâíà M n0 1�
( )!! .
Ïåðåéäåì êî âòîðîìó ýòàïó ðåøåíèÿ. Ñîãëàñíî ëåììå 3 êàæäîé �-é ïàðå ñî-
âåðøåííûõ ïàðîñî÷åòàíèé ( , ), ,
,x x X
1
1
1
2
1 1
� � � ñîîòâåòñòâóåò ìíîæåñòâî ïàð
îñòîâíûõ äåðåâüåâ X X X x x
2 2 2
1
2
2
2
1
2
2
,
, , , , , , , , ,( , ) ( , )� � � � � � � � � �� � { }, � �1, M , � �1, N .
Òàêèì îáðàçîì, ïðè ôèêñèðîâàííîì � åäèíñòâåííîìó ýëåìåíòó x
1
1�, (ò.å. «ëåâî-
ìó» ðåáðó �-ãî ïàðîñî÷åòàíèÿ) ñòàâèòñÿ â ñîîòâåòñòâèå «ïðàâîå» �-å ìíîæåñòâî
X x
2
2
2
2� � � �, , , ,� { }. Äëÿ ôèêñèðîâàííîãî � ðåøàåòñÿ çàäà÷à íàõîæäåíèÿ ìèíèìóìà
x
2
2� �, , ñðåäè ýëåìåíòîâ x
2
2� �, , ìíîæåñòâà X
2
2� �, , . Íàéäåííûé ìèíèìóì x
2
2� �, ,
â ïàðå ñ ôèêñèðîâàííûì ýëåìåíòîì x
1
1�, äàåò ðåøåíèå Z1 2, äëÿ îäíîé òî÷êè
( , ), , ,x x
1
1
2
2� � � , ñîîòâåòñòâóþùåé íîìåðó �, � �[ , ]1 M . Ïðàâàÿ ÷àñòü ýòîé òî÷êè äëÿ
ôèêñèðîâàííîãî � ñêëàäûâàåòñÿ èç äâóõ ñîñòàâëÿþùèõ: «ôèêñèðîâàííàÿ ÷àñòü»,
ñîñòîÿùàÿ èç
n n
2 2
�
�
��
�
��
ýëåìåíòîâ âèäà ( ( ))2 1
N
te
� , ãäå âåñ ðåáðà et îïðåäåëÿåò-
ñÿ íà ïåðâîì ýòàïå, è «ïåðåìåííàÿ ÷àñòü» — ðåçóëüòàò ðàáîòû âòîðîãî ýòàïà, çà
n
2
1–
�
�
�
�
�
� øàãîâ äîïîëíÿþùåãî «ôèêñèðîâàííóþ ÷àñòü». Ñîåäèíåíèå ýëåìåíòîâ
x
1
1�, è x
2
2� �, , , 1 � �� N , äàåò äîïóñòèìîå ðåøåíèå ( , ), , ,x x
1
1
2
2� � � çàäà÷è Z1 2, äëÿ
ôèêñèðîâàííîãî �. Ðåàëèçàöèÿ àëãîðèòìà äëÿ êàæäîãî � �[ , ]1 M ïðèâîäèò ê ïî-
ñòðîåíèþ ÌÄÐ çàäà÷è Z1 2, . Ñðàâíèâàÿ äâå «ôèêñèðîâàííûå ÷àñòè» ó ëþáûõ
äâóõ òî÷åê, îáíàðóæèâàåì èõ íåñîâïàäåíèå õîòÿ áû ïî îäíîìó ðåáðó, ÷òî, ïðè
âûáðàííîì ñïîñîáå âçâåøèâàíèÿ, îäíîçíà÷íî ïðèâîäèò ê íåñîâïàäåíèþ âåñîâûõ
çíà÷åíèé ïàð ( , ), , ,x x
1
1
2
2� � � äëÿ ðàçëè÷íûõ � �[ , ]1 M .
Ïðè ðåàëèçàöèè òðåòüåãî ýòàïà, íà êîòîðîì âûäåëÿþòñÿ ïàðåòîâñêèå
ðåøåíèÿ è ÏÌÀ èç íàéäåííûõ äîïóñòèìûõ ðåøåíèé çàäà÷è Z1 2, , ïîëó÷èì
ñîâïàäàþùèå ìíîæåñòâà ÏÌ è ÏÌÀ. Ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà.
Òåîðåìà 6. Äâóõêðèòåðèàëüíàÿ çàäà÷à Z1 2, «î ñîâåðøåííîì ïàðîñî÷åòàíèè è
îñòîâíîì äåðåâå» ÿâëÿåòñÿ êâàçèïîëíîé. Ìàêñèìàëüíàÿ ìîùíîñòü ÌÄÐ çàäà÷è Z1 2,
«î ñîâåðøåííîì ïàðîñî÷åòàíèè è îñòîâíîì äåðåâå» ðàâíà | |,X nn
1 2
2�
. Ìîùíîñòè
ÏÌ è ÏÌÀ ðàâíû ìåæäó ñîáîé è íå ïðåâûøàþò ìîùíîñòè ÌÄÐ äâóõêðèòåðèàëü-
íîé çàäà÷è Z1 1, «î ñîâåðøåííîì ïàðîñî÷åòàíèè»: |
~
|,X 1 2 � | | ( )!!
,
X n
1 2
0 1�
.
Ñôîðìóëèðóåì äîñòàòî÷íîå óñëîâèå íàëè÷èÿ ñâîéñòâà êâàçèïîëíîòû
ó äâóõêðèòåðèàëüíîé çàäà÷è Z
� �1 2,
.
Òåîðåìà 7. Äëÿ òîãî ÷òîáû äâóõêðèòåðèàëüíàÿ çàäà÷à Z� �1 2, ñ âåêòîðíîé öå-
ëåâîé ôóíêöèåé F x F x F x� � � � � � � �1 2 1 2 1 1 2 2, ,
( ) ( ( ), ( ))� îáëàäàëà ñâîéñòâîì êâàçè-
ïîëíîòû, äîñòàòî÷íî, ÷òîáû åå ÌÄÐ X � �1 2, ñîñòîÿëî èç òàêèõ ïîäãðàôîâ x
� �1 2,
,
äëÿ êîòîðûõ âûïîëíÿåòñÿ îòíîøåíèå âêëþ÷åíèÿ äëÿ ïîäãðàôîâ x�1
è x�2
:
X � �1 2, � {x x x x x x� � � � � � � �1 2 1 2 1 2 1 2, ,: } ( , ),� èëè x x� �1 2
� , ãäå x�1
— äîïóñòè-
ìîå ðåøåíèå çàäà÷è Z�1
, x�2
— äîïóñòèìîå ðåøåíèå çàäà÷è Z�2
.
Äîêàçàòåëüñòâî àíàëîãè÷íî òåîðåìå 6.
56 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3
 ðàìêàõ ïðîâåäåííûõ èññëåäîâàíèé âûäåëåíû íîâûå âèäû ïîëíûõ è êâàçè-
ïîëíûõ çàäà÷ äâóõêðèòåðèàëüíîé äèñêðåòíîé îïòèìèçàöèè ñ ðàçíîòèïíûìè êðè-
òåðèÿìè âåñîâîãî âèäà.  ñòàòüå ñôîðìóëèðîâàíû è äîêàçàíû äîñòàòî÷íûå óñëî-
âèÿ íàëè÷èÿ ñâîéñòâà ïîëíîòû è ñâîéñòâà êâàçèïîëíîòû äëÿ äàííîãî êëàññà çàäà÷.
Ìîæíî ïîëàãàòü, ÷òî ïðîÿâëåíèå ñâîéñòâ ïîëíîòû è êâàçèïîëíîòû ÿâëÿåòñÿ
îñíîâíûì îòëè÷èåì ìíîãîêðèòåðèàëüíîãî ñëó÷àÿ îò îäíîêðèòåðèàëüíîãî è ïîä-
òâåðæäàåò íåîáõîäèìîñòü äàëüíåéøèõ èññëåäîâàíèé â ýòîì íàïðàâëåíèè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Pareto V. Manuel d’economic politique. Paris: Giard, 1909.
2. Cooper Ch.A., Cooper W.W. Management models and industrial applications of lineal programming. New
York: Wiley, 1961. Vol. 1.
3. Ïåðåïåëèöà Â.À. Ìíîãîêðèòåðèàëüíûå ìîäåëè è ìåòîäû äëÿ çàäà÷ îïòèìèçàöèè íà ãðàôàõ.
Saarbr��ucken: LAP LAMBERT Acad. Publ., 2013. 337 p.
4. Ïåðåïåëèöà Â.À. Îá îäíîì êëàññå ìíîãîêðèòåðèàëüíûõ çàäà÷ íà ãðàôàõ è ãèïåðãðàôàõ. Êèáåðíåòèêà.
1984. ¹ 4. Ñ. 62–67.
5. Ïåðåïåëèöà Â.À. Îá ýôôåêòèâíîñòè èñïîëüçîâàíèÿ ìåòîäîâ äèñêðåòíîé îïòèìèçàöèè äëÿ àíàëèçà
ñèñòåì. Òåîðèÿ, ìåòîäîëîãèÿ è ïðàêòèêà ñèñòåìíûõ èññëåäîâàíèé: Òåç. äîêë. Âñåñîþç. êîíô. Ìîñêâà:
ÂÍÈÈÑÈ ÃÊÍÒ è ÀÍ ÑÑÑÐ, 1984. Ñ. 198–200.
6. Ïåðåïåëèöà Â.À., Ìàêñèøêî Í.Ê. Î ìíîãîêðèòåðèàëüíîé çàäà÷å ïîêðûòèÿ îðèåíòèðîâàííîãî ãðàôà
êîíòóðàìè. Ìåòîäû è ïðîãðàììû ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ íà ãðàôàõ è ñåòÿõ: Òåç. äîêë.
3-ãî Âñåñîþç. ñîâ. (Òàøêåíò, 28–30 àâã. 1984 ã.). Íîâîñèáèðñê: ÂÖ ÑÎ ÀÍ ÑÑÑÐ, 1984. ×. 2. Ñ. 97–98.
7. Ñåðãèåíêî Â.À., Ïåðåïåëèöà Â.À. Ê ïðîáëåìå íàõîæäåíèÿ ìíîæåñòâ àëüòåðíàòèâ äèñêðåòíûõ ìíî-
ãîêðèòåðèàëüíûõ çàäà÷. Êèáåðíåòèêà. 1987. ¹ 5. Ñ. 85–93.
8. Åìåëè÷åâ Â.À., Ïåðåïåëèöà Â.À. Ñëîæíîñòü äèñêðåòíûõ ìíîãîêðèòåðèàëüíûõ çàäà÷. Äèñêðåòíàÿ ìà-
òåìàòèêà. 1994. Ò. 6, âûï. 1. Ñ. 3–33.
Íàä³éøëà äî ðåäàêö³¿ 07.07.2017
Â.Î. Ïåðåïåëèöÿ, Å.Â. Òåðåùåíêî
ÏÐÎ ÏÎÂͲ ² ÊÂÀDzÏÎÂͲ ÄÂÎÊÐÈÒÅвÉͲ ÇÀÄÀײ ÍÀ ÃÐÀÔÀÕ
Àíîòàö³ÿ. Âèâ÷àþòüñÿ äîñòàòí³ óìîâè íàÿâíîñò³ âëàñòèâîñò³ ïîâíîòè àáî
êâàç³ïîâíîòè ó äâîêðèòåð³éíèõ çàäà÷àõ äèñêðåòíî¿ îïòèì³çàö³¿ ç îäíàêîâèìè
³ ð³çíèìè êðèòåð³ÿìè âàãîâîãî âèãëÿäó. Îá÷èñëåíî îö³íêó ïîòóæíîñòåé
ìíîæèí äîïóñòèìèõ ðîçâ'ÿçê³â, ïàðåòîâñüêî¿ ìíîæèíè ³ ïîâíî¿ ìíîæèíè
àëüòåðíàòèâ äëÿ íèçêè çàäà÷ ç äâîìà êðèòåð³ÿìè.
Êëþ÷îâ³ ñëîâà: áàãàòîêðèòåð³éíà îïòèì³çàö³ÿ, ïàðåòîâñüêà ìíîæèíà, ïîâíà
ìíîæèíà àëüòåðíàòèâ, ïîâíà çàäà÷à, êâàç³ïîâíà çàäà÷à.
V.A. Perepelitsa, E.V. Tereschenko
ON COMPLETE AND QUASI-COMPLETE TWO-CRITERIA
OPTIMIZATION PROBLEMS ON GRAPHS
Abstract. This article is devoted to the study of sufficient conditions for using
the completeness or quasicompleteness properties in two-criteria discrete
optimization problems with the same and different weight-type criteria. The
authors evaluated the cardinalities of sets of acceptable solutions, the Pareto set,
and a complete set of alternatives for several two-criteria problems.
Keywords: vector optimization, Pareto set, complete set of alternatives,
complete problem, quasi-complete problem.
Ïåðåïåëèöà Âèòàëèé Àôàíàñüåâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð êàôåäðû Çàïîðîæñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà,
e-mail: vitalijperepelica2@gmail.com.
Òåðåùåíêî Ýëèíà Âàëåíòèíîâíà,
êàíäèäàò ôèç.-ìàò. íàóê, äîöåíò êàôåäðû Çàïîðîæñêîãî íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåðñèòåòà,
e-mail: elina_vt@ukr.net.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3 57
|