Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок

Досліджено складні дискретні багатокритеріальні задачі на комбінаторній множині перестановок. Розглянуто деякі властивості допустимої області комбінаторної багатокритеріальної задачі, що занурена в арифметичний евклідів простір. Установлено умови оптимальності різних видів ефективних розв'язків...

Full description

Saved in:

Bibliographic Details
Date:	2008
Main Authors:	Семенова, Н.В., Колечкина, Л.Н., Нагорная, А.Н.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2008
Series:	Кибернетика и системный анализ
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

id	nasplib_isofts_kiev_ua-123456789-72216
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-722162025-02-10T01:14:41Z Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок Семенова, Н.В. Колечкина, Л.Н. Нагорная, А.Н. Системный анализ Досліджено складні дискретні багатокритеріальні задачі на комбінаторній множині перестановок. Розглянуто деякі властивості допустимої області комбінаторної багатокритеріальної задачі, що занурена в арифметичний евклідів простір. Установлено умови оптимальності різних видів ефективних розв'язків. Побудовано й обгрунтовано новий підхід розв'язання сформульованих задач. Настоящая работа поддержана Фондом фундаментальных исследований Украины (проект № Ф251/094). 2008 Article Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок/ Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и системный анализ. — 2008. — № 3. — С. 158-172. — Бібліогр.: 15 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/72216 519.8 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
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	2008
topic_facet	Системный анализ
url	https://nasplib.isofts.kiev.ua/handle/123456789/72216
citation_txt	Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок/ Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Кибернетика и системный анализ. — 2008. — № 3. — С. 158-172. — Бібліогр.: 15 назв. — рос.
series	Кибернетика и системный анализ
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
first_indexed	2025-12-02T10:42:38Z
last_indexed	2025-12-02T10:42:38Z
_version_	1850392873699115008
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

Подход к решению векторных задач дискретной оптимизации на комбинаторном множестве перестановок

Institution

Similar Items