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

Работа выполнена при поддержке Государственного фонда фундаментальных исследований Украины (проект Ф25.1/094).

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
Hauptverfasser:	Семенова, Н.В., Колечкина, Л.Н., Нагорная, А.Н.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2008
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы идентификации и адаптивного управления
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/209396
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Решение и исследование векторных задач комбинаторной оптимизации на множестве полиперестановок / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Проблемы управления и информатики. — 2008. — № 6. — С. 26-41. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-209396
record_format	dspace
spelling	irk-123456789-2093962025-11-21T01:15:21Z Решение и исследование векторных задач комбинаторной оптимизации на множестве полиперестановок Розв’язання та дослідження векторних задач комбінаторної оптимізації на множині поліперестановок Solution and investigation of vector problems of combinatorial optimization on a set of polypermutations Семенова, Н.В. Колечкина, Л.Н. Нагорная, А.Н. Методы идентификации и адаптивного управления Работа выполнена при поддержке Государственного фонда фундаментальных исследований Украины (проект Ф25.1/094). Досліджено складні векторні задачі на комбінаторній множині поліперестановок. Вивчено деякі властивості допустимої області комбінаторної багатокритеріальної задачі, що розв’язується в арифметичному евклідовому просторі. Отримано необхідні і достатні умови оптимальності різних видів ефективних розв’язків. Побудовано та обґрунтовано метод відшукання Парето-оптимальних розв’язків розглянутого класу задач. The complex vector problems of combinatorial optimization on a set of polipermutations are investigated. Some properties of feasible domain of combinatorial multicriteria problem in arithmetic Euclidian space are considered. The necessary and sufficient conditions of optimality of different types of efficient solutions are obtained. The method of finding of Pareto-optimum solutions of the considered class of problems is constructed and substantiated. 2008 Article Решение и исследование векторных задач комбинаторной оптимизации на множестве полиперестановок / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Проблемы управления и информатики. — 2008. — № 6. — С. 26-41. — Бібліогр.: 15 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/209396 519.8 10.1615/JAutomatInfScien.v40.i12.30 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы идентификации и адаптивного управления Методы идентификации и адаптивного управления
spellingShingle	Методы идентификации и адаптивного управления Методы идентификации и адаптивного управления Семенова, Н.В. Колечкина, Л.Н. Нагорная, А.Н. Решение и исследование векторных задач комбинаторной оптимизации на множестве полиперестановок Проблемы управления и информатики
description	Работа выполнена при поддержке Государственного фонда фундаментальных исследований Украины (проект Ф25.1/094).
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/209396
citation_txt	Решение и исследование векторных задач комбинаторной оптимизации на множестве полиперестановок / Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная // Проблемы управления и информатики. — 2008. — № 6. — С. 26-41. — Бібліогр.: 15 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT semenovanv rešenieiissledovanievektornyhzadačkombinatornojoptimizaciinamnožestvepoliperestanovok AT kolečkinaln rešenieiissledovanievektornyhzadačkombinatornojoptimizaciinamnožestvepoliperestanovok AT nagornaâan rešenieiissledovanievektornyhzadačkombinatornojoptimizaciinamnožestvepoliperestanovok AT semenovanv rozvâzannâtadoslídžennâvektornihzadačkombínatornoíoptimízacíínamnožinípolíperestanovok AT kolečkinaln rozvâzannâtadoslídžennâvektornihzadačkombínatornoíoptimízacíínamnožinípolíperestanovok AT nagornaâan rozvâzannâtadoslídžennâvektornihzadačkombínatornoíoptimízacíínamnožinípolíperestanovok AT semenovanv solutionandinvestigationofvectorproblemsofcombinatorialoptimizationonasetofpolypermutations AT kolečkinaln solutionandinvestigationofvectorproblemsofcombinatorialoptimizationonasetofpolypermutations AT nagornaâan solutionandinvestigationofvectorproblemsofcombinatorialoptimizationonasetofpolypermutations
first_indexed	2025-11-21T02:16:25Z
last_indexed	2025-11-22T02:17:03Z
_version_	1849455094576185344
fulltext	© Н.В. СЕМЕНОВА, Л.Н. КОЛЕЧКИНА, А.Н. НАГОРНАЯ, 2008 26 ISSN 0572-2691 МЕТОДЫ ИДЕНТИФИКАЦИИ И АДАПТИВНОГО УПРАВЛЕНИЯ УДК 519.8 Н.В. Семенова, Л.Н. Колечкина, А.Н. Нагорная РЕШЕНИЕ И ИССЛЕДОВАНИЕ ВЕКТОРНЫХ ЗАДАЧ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ НА МНОЖЕСТВЕ ПОЛИПЕРЕСТАНОВОК  Введение Многокритериальные задачи оптимизации на различных допустимых множе- ствах продолжают привлекать внимание многих исследователей [110]. Модели комбинаторной оптимизации широко применяются при решении важных задач геометрического проектирования, экономики, управления процессом обработки данных, проектирования и размещения объектов, планирования эксперимента, анализа и оптимизации функционирования систем массового обслуживания, при- нятия решений и других. В последнее время в области исследования различных классов комбинаторных моделей, разработки новых методов их решения большое внимание уделяется методам, основанным на использовании структурных свойств комбинаторных множеств [13, 815]. В данной работе формулируется и исследуется качественно новая и актуаль- ная задача, которая объединяет многокритериальность альтернатив и допустимые множества решений, имеющие различные комбинаторные свойства. Как известно, большинство комбинаторных оптимизационных задач могут быть сведены к задачам целочисленного программирования, но это не всегда оп- равдано, поскольку при этом теряется возможность учета комбинаторных свойств задач [2]. Систематическому изучению свойств евклидовых комбинаторных мно- жеств и их исследованию посвящено много работ. Наряду с хорошо известными евклидовыми комбинаторными множествами перестановок, размещений, сочета- ний, разбиений выделяются более сложные структуры — поликомбинаторные множества. Интерес к таким множествам обусловлен разными прикладными зада- чами, поскольку значительное их количество хорошо описывается с помощью по- ликомбинаторных конструкций [12, 14]. Следует отметить, что задачи евклидовой комбинаторной оптимизации на поликомбинаторных множествах неотъемлемо связаны с комбинаторными много- гранниками и их свойствами, которые представляют собой выпуклые оболочки таких множеств. Повышенный интерес к комбинаторным и поликомбинаторным конфигурациям обусловлен исследованиями последних лет в области компьютер- ных технологий при создании современных алгоритмов и программ для решения оптимизационных задач. Следовательно, рассмотрение новых задач на поликом- бинаторных множествах со многими критериями предопределено потребностями практики.  Работа выполнена при поддержке Государственного фонда фундаментальных исследований Украи- ны (проект Ф25.1/094). Проблемы управления и информатики, 2008, № 6 27 Настоящая работа продолжает исследования многокритериальных задач на комбинаторных множествах перестановок и сочетаний, содержащиеся в рабо- тах [8, 9]. 1. Основные понятия и определения Рассмотрим основные понятия и определения, необходимые для постановки задачи и изложения основных результатов данной работы. Мультимножество }...,,,{ 21 qaaaA  определяется основанием },...,,,{)( 21 keeeАS  т.е. множест- вом всех его различных элементов, и их кратностью jj rek )( — числом повто- рений каждого j-го элемента основания, },...,,2,1{ kNj k  ....21 qrrr k  Определение 1. Упорядоченной n-выборкой из мультимножества A называет- ся набор ),,,,( 21 niii aaaa  где Аa ji  ,nj Ni  ,nNj если ts  ,nNs .nNt  Определение 2. Множество упорядоченных n-выборок из мультимножества A при условии kqn  называется множеством перестановок с повторениями из n действительных чисел, среди которых k различных, либо общим множеством перестановок и обозначается ).(APnk При kqn  имеем множество )(APnn перестановок без повторений. Пред- ставим множество nN в виде упорядоченного разбиения на s, ,ns  непустых попарно непересекающихся подмножеств ,...,,1 sJJ т.е. для них выполняются ус- ловия , ji JJ ,iJ jJ ., sNji  Обозначим H множество всех элементов вида ),...,,())(...,),1(( 1 shhnhhh  где ,,)( nn NjNjh  а ih — произвольная перестановка элементов множества .si NiJ  Пусть подмуль- тимножество iA мультимножества A состоит из тех элементов A, номера которых принадлежат множеству },...,,,{: 21 i n iii i i aaaAJ  .ii nJ  Определение 3. Множество },)...,,{(),( )()()1( HhNiAaaaHAP nihnhh s nk  называется общим множеством полиперестановок. Не теряя общности, упорядочим элементы мультимножества A по неубыва- нию: .21 naaa   Очевидно, что это упорядочение сохраняется и для каж- дого подмультимножества ,iA ,sNi из A. 2. Свойства евклидова множества полиперестановок Как известно [11, 12], комбинаторные множества приобретают интересные свойства при погружении в арифметическое евклидово пространство. Эти свойст- ва, с одной стороны, позволяют предложить оригинальные подходы к решению соответствующих оптимизационных задач. С другой стороны, использование свойств погруженных комбинаторных множеств может повысить эффективность традиционных методов комбинаторной оптимизации. Будем рассматривать эле- менты множества полиперестановок как точки арифметического евклидова про- странства .nR Пусть вектор ), ,,( 21 niii aaaa  — элемент евклидова комбинаторного мно- жества ).(AE 28 ISSN 0572-2691 Определение. 4. Отображение nRAEAE   )()(: называется погружени- ем множества )(AE в арифметическое евклидово пространство, если  задает вза- имно однозначное соответствие nRAE  )( по правилу: )(ax  для ),(AEa ),(),,( 1 AExxx n   jij ax  .nNj Известно [12, 14], что выпуклой оболочкой множества полиперестановок ),( HAРs nk является общий полиперестановочный многогранник  ),( HAs nk ),,(conv HAPs nk множество вершин которого составляют элементы множества полиперестановок: ).,(),(vert HAРHA s nk s nk  Теорема 1. Множество ),( HAs nk определяется совокупностью всех реше- ний системы ,, 11 s n j i j n j j Niax ii    (1) ,,, 1 11 sijni m j i j m j NiJNmax i ii j      (2) .,,, itj Jtjtj  Многогранник ),( HAs nk будем называть общим многогранником евклидо- вого множества полиперестановок. Рассмотрим некоторые его свойства и связь с общим множеством полиперестановок. Очевидно, что из системы линейных неравенств (1), (2) можно выделить s подсистем линейных неравенств, описывающих перестановочные многогранни- ки ),(П i kn A ii представляющие собой выпуклую комбинацию множества переста- новок ,ih a .sNi Следовательно, ,,)(П 1111              ii j ii i ii m j i j m j n j i j n j j ni kn axaxRxA .,,,,,,1 sitjijni NiJtjtjJNm i   Определение 5. Под произведением многогранников sMM ...,,1 понимают множество },),...,,({ 1 ... 1 1 siis dd i S i NiMxxxxRxM s    где iM — di-мерный многогранник. Воспользуемся следующей леммой [15]. Лемма. 1. Произведение многогранников является многогранником. 2.             S i ii S i MM 11 ,dimdim где Mdim — размерность множества M. 3. k-мерные грани многогранника i S i M 1  образуют множество с элементами вида , 1 i S i F   где iF — ki-мерная грань многогранника iM и ....1 kkk s  Проблемы управления и информатики, 2008, № 6 29 Каждый из многогранников )(П i kn A ii представляет собой перестановочный многогранник. Cогласно лемме, справедливо равенство },)(П),...,,({)(П 1 ... 1 1 s i knis ddi kn s i NiAxxxxRxA ii s ii    т.е. точка )( 1 i kn s i Ax ii   удовлетворяет каждой из s подсистем системы (1), (2). Следовательно, можно утверждать, что если ih a — вершина многогранника ),(П i kn A ii то ih s i aha 1 )(   и соответственно ),...,,()( 1 shh aaha  где )(ha ).,( HAPs nk Справедливы следующие теоремы [12]. Теорема 2. ).(П),(П 1 i kn s i s nk AHA ii   Теорема 3. Множество полиперестановок ),( HAP s nk совпадает с множест- вом вершин многогранника ).,(П HAs nk Теорема 4. Вершина ),(vert)( HAha s nk смежная с вершиной )(za ),(Πvert HAs nk тогда и только тогда, когда )(za образуется из )(ha перестанов- кой двух неравных друг другу компонент i ia и ,i ja .,1 sn NiJj i   Следует отметить, что общее количество p линейных неравенств, которые входят в систему (1), (2), описывающую полиперестановочный многогранник ),,(П HAs nk очень велико. Согласно [11], совокупность неравенств подсистемы для некоторого подмно- жества ,, si NiJ  системы (1), (2), имеющих одинаковое значение im верхнего предела суммирования, будем называть mi-й группой неравенств этой подсистемы, .sNi В частности, в каждую mi-ю группу входит i i m n C неравенств. Отсюда по- лучаем общее количество неравенств, описывающих многогранник ),(П i kn A ii равное    i ii i n i nm ni Cp 0 ,2 .sNi Поскольку из in координат ,i ja ,iJj ik раз- личны, то из подсистемы неравенств (1), (2) можно исключить некоторые нера- венства. С учетом выполнения условия naaa  21 ,1 imNj ,ii nm  ,sNi  выполняется равенство .1 i j i j aa  В этом случае при выполнении нера- венств первой группы в подсистеме (1), (2) будут также справедливы неравенст- ва второй, третьей, …, mi-й, ,sNi групп. Действительно, поскольку ,1 i j ax  ,iJj ,sNi то для любого ni Nm  выполняется условие .1 1 i i m j amx j i    Следовательно, из каждой подсистемы системы (1), (2), описывающей полипере- становочный многогранник ),,(П HAs nk можно исключить неравенства второй, третьей, …, mi-й, ,sNi групп и общее количество неравенств в mi-й подсистеме будет составлять ,1 1    i i n ij j ni i CnN а следовательно, количество неравенств, 30 ISSN 0572-2691 которые можно исключить из системы (1), (2), будет равно . 1    s i iNN Если набор чисел )...,,,( 21 i n ii aaa обладает свойством i j i j aa 1 ,\1 iii mnn NNj  ,sNi то в подсистеме системы (1), (2) достаточно оставить только неравенства первой, второй, …, (m i – j)-й групп. 3. Постановка задачи Рассмотрим многокритериальные комбинаторные задачи вида )},,()(Ф{max:)),(,Ф( HAPaaHAPZ s nk s nk  состоящие в максимизации векторного критерия )(Ф a на евклидовом комбина- торном множестве полиперестановок, где )),(Ф...,),(Ф),(Ф()(Ф 21 aааа l .,)(:Ф 1 li NiRAE  Отобразив множество полиперестановок ),( HAРs nk в евклидово пространст- во ,nR сформулируем задачу ),( XFZ максимизации некоторого векторного критерия )(xF на множестве X, причем каждой точке ),( HAРa s nk будет соот- ветствовать точка Xx такая, что :)()( axF  }.\|)({max:),( XxxFXFZ  Здесь )),(...,),(),(()( 21 xfxfxfxF l )(xfi соответствует функционалу ),(Ф ai ,: 1RRf n i  ,lNi X — непустое множество в ,nR которое определяется сле- дующим образом: ),,(vert HAX s nk где ).,(conv),( HAPHA s nk s nk  Под со- ответствием векторной функции F вектору функционалов  будем понимать со- отношение ).,())(()( HAРaaFa s nk Задача ),( XFZ может содержать также дополнительные линейные огра- ничения, образующие выпуклое многогранное множество nRD  вида D },{ dBхRx n  где ,nmRB  .mRd Таким образом, задачу ),( XFZ будем рассматривать на допустимом множестве, имеющем вид .),(Пvert DHAX s nk  Разработано множество различных принципов принятия решений в много- критериальных задачах. Рассмотрим наиболее традиционные, связанные с выде- лением из всего множества }),()({ DHAxxFyY s nk  множеств неулуч- шаемых или оптимальных по Парето, оптимальных по Слейтеру, оптимальных по Смейлу векторов. Под решением задачи ),( XFZ будем понимать отыскание эле- ментов одного из следующих множеств: ),(P XF — множества Парето- оптимальных (эффективных) решений, ),(Sl XF — оптимальных по Слейтеру (слабо эффективных) решений, ),(Sm XF — оптимальных по Смейлу (строго эффективных) решений. Согласно [47], для каждого Xx справедливы утвер- ждения: ,)}()({),(Sl  xFyFXyXFx (3) ,)}()(),()({),(P  xFyFxFyFXyXFx (4) Проблемы управления и информатики, 2008, № 6 31 ,)}()(,{),(Sm  xFyFxyXyXFx (5) ).,(Sl),(P),(Sm XFXFXF  (6) Поскольку допустимая область X ограничена, то множество ),(P XF непусто и внешне устойчиво [10]: Xy ).()(:),(P yFxFXFx  В случае бесконеч- ного мультимножества A вопрос о существовании элементов множества ),(P XF требует отдельного исследования. 4. Структурные свойства и условия оптимальности различных множеств эффективных решений Теорема 5. Элементы множеств ),(Sm XF — строго эффективных, ),(P XF — Парето-оптимальных, ),(Sl XF — слабо эффективных решений многокритери- альной комбинаторной задачи ),( XFZ на полиперестановках находятся в верши- нах полиперестановочного многогранника ).,(П HAs nk Доказательство. На основании соотношения (6) между множествами различных видов эффективных решений, теоремы 1 и того факта, что множество допустимых решений X представляет собой подмножество множества вершин общего полипере- ставновочного многогранника ),,(П HAs nk т.е. ),,(vert HAX s nk а ),(П HAs nk ),,(conv HAPs nk получим цепочку включений  ),(Sl),(P),(Sm XFXFXF ),,(vert nk HAs что и требовалось доказать. Предположим, что функции ),(xfi ,lNi векторного критерия )(xF линей- ные, т.е. .,,)( lii Nixcxf  Структурные свойства допустимой области X и множеств разных видов эффективных решений, отмеченные в теореме 5, а также линейность функций векторного критерия позволяют свести решение задачи ),( XFZ к решению задачи ),,( GFZ определенной на непрерывном допустимом множестве .),(П DHAG s nk  Обозначим lnRC  матрицу, вектор-строки ,jc ,lNj которой содержат коэффициенты линейных векторных критериев .),( li Nixf  Многогранник ),(П HAs nk представим в виде },,,{),(П pii ns nk NixRxHA  сведя все неравенства к одному знаку ).( Рассмотрим конус }0{  CxRxK n пер- спективных направлений [4] задачи ),,( XFZ а также выпуклые замкнутые кону- сы )},(,0{)(Π0 yNixRxy i n  где },{)( iiq yNiyN  которые могут быть построены для всех точек ).,(Пvert HAy s nk Очевидно, что ,)( yN ).(0 yyX   Обозначим }0{0  CxRxK n ядро отображения ,: ln RRC  }0{int  CxRxK n — внутренность конуса K. В соответствии с [6] из формул (3)(5) Xx следуют утверждения ,)int(),(Sl  XKxXCx  (7) ,))\((),(P 0  XKKxXCx  (8) .}{\)(),(Sm  xXKxXCx  (9) 32 ISSN 0572-2691 Справедливы следующие теоремы. Теорема 6. ),,(P),(vert),(P XFHAGF s nk  ),,(Sl),(Пvert),(Sl XFHAGF s nk  ).,(Sm),(Пvert),(Sm XFHAGF s nk  Доказательство. Поскольку ,),(Пvert GDHAs nk  то ).,()),(Пvert,(),(Пvert),( XFPDHAGFPDHAGFP s nk s nk   Аналогично можно доказать соотношения ),,(Пvert),(Sm)),(Пvert,(Sm),(Sm HAGFHADFXF s nk s nk   ).,(Пvert),(Sl)),(Пvert,(Sl),(Sl HAGFDHAFXF s nk s nk   Теорема 7. Если допустимое множество X задачи ),( XFZ не содержит огра- ничений, которые описывают выпуклое многогранное множество D, или ,),(П DHAs nk  т.е. ),,(Пvert HAX s nk то nRx справедливы утверждения: ),,(Пvert)),(П,(Sl),(Sl HAHAFxXFx s nk s nk  ),,(Пvert)),(П,(P),(P HAHAFxXFx s nk s nk  ).,(Пvert)),(П,(Sm),(Sm HAHAFxXFx s nk s nk  Доказательство. Из условий этой теоремы и теоремы 6 следует, что nRx справедливы утверждения: ),,(Sl),(Пvert)),(П,(Sl XFxHAHAFx s nk s nk   ),,(P),(Пvert)),(П,(P XFxHAHAFx s nk s nk   ).,(Sm),(Пvert)),(П,(Sm XFxHAHAFx s nk s nk   Докажем обратные импликации. Пусть ),,(Sl XFx тогда, согласно теоре- ме 5, ).,(Пvert HAx s nk Предположим, от противного, что )).,(П,(Sl HAFx s nk Учитывая линейность функций ,),( li Nixf  векторного критерия ),(xF соглас- но теореме 5 из [6] получаем, что выполняется условие ,))((int  xxK  т.е. в конусе )int( Kx  лежат некоторые точки границы многогранника ).,(П HAs nk Следовательно, существует точка, которая принадлежит этому конусу. Последнее в силу формулы (7) означает, что ),,(Sl XFx а это приводит к противоречию с условием теоремы. Остальные утверждения данной теоремы доказываются аналогично. Следствие. При условиях теоремы 3 справедливы равенства ),,(P),(Пvert)),(П,(P XFHAHAF s nk s nk  Проблемы управления и информатики, 2008, № 6 33 ),,(Sl),(Пvert)),(П,(Sl XFHAHAF s nk s nk  ).,(Sm),(Пvert)),(П,(Sm XFHAHAF s nk s nk  Если в задаче ),( XFZ допустимая область ),,(Пvert HAX s nk то для лю- бой точки ),(Пvert HAx s nk выполняются необходимые и достаточные усло- вия оптимальности всех указанных видов эффективных решений, полученные в работе [6]. Если допустимая область X задачи ),( XFZ содержит дополни- тельные ограничения, которые описывают выпуклый многогранник D, т.е. DHAX s nk ),(Пvert и ),,(П),(П HADHA s nk s nk  то выполняются лишь достаточные условия оптимальности решения. Теорема 8. ),,(P)),(П,(P:),(Пvert XFxDHAFxHAx s nk s nk   ),,(Sl)),(П,(Sl XFxDHAFx s nk   ).,(Sm)),(П,(Sm XFxDHAFx s nk   Доказательство. Поскольку ,DG  то ),(Пvert HAx s nk  справедли- вы импликации:  DHAFx s nk )),(П,(P ),,(P),(P)),(П,(P XFxGFDHAFx s nk   ),,(Sl)),(П,(Sl XFxDHAFx s nk   ).,(Sm)),(П,(Sm XFxDHAFx s nk   Таким образом, теоремы 5–8 устанавливают взаимосвязь между задачей ),( XFZ и задачей ),,( GFZ определенной на непрерывном допустимом множест- ве. Это дает возможность применять классические методы непрерывной оптими- зации к решению векторных комбинаторных задач на полиперестановках и на этой основе развивать новые оригинальные методы решения, используя свойства комбинаторных множеств и их выпуклых оболочек. Анализируя теоремы 6 и 8, приходим к соотношениям, существующим между задачами ),( XFZ и :),( GFZ если ),,(Пvert),( HAGFRx s nk то ),,( XFRx если ),,(Пvert),( HAGFRx s nk то из этого не следует, что ),,( XFRx где ),( XFR — множество ),(Sm),,(P XFXF или ).,(Sl XF Если задача ),( XFZ не содержит линейных ограничений, образующих вы- пуклое многогранное множество ,nRD  либо ,D т.е. ,vertX то с уче- том необходимых и достаточных условий оптимальности (теорема 7) ее решение сводится к поиску эффективных решений задачи ),( GFZ на непрерывном допус- тимом множестве ),(П HAG s nk с последующим выбором из них лишь тех, которые являются вершинами полиперестановочного многогранника ).,(П HAs nk 34 ISSN 0572-2691 5. Решение векторных задач на комбинаторном множестве полиперестановок. Общий подход Если задача ),( XFZ содержит дополнительные линейные ограничения, то предлагается следующий подход к ее решению. 1. Находим эффективные решения задачи )).,(П,( HAFZ s nk 2. Проверяем, принадлежат ли они множеству D. Если )),(П,(P HAFx s nk  ,D то ).,(P XFx 3. Рассмотрим допустимые решения Xx задачи ),,( XFZ которые не яв- ляются Парето-оптимальными, т.е. ),)),(П,(P(\ DHAFXx s nk  и проверяем их эффективность. Для этого можно воспользоваться необходимыми и достаточны- ми условиями, сформулированными в [10]. Утверждение 1. Допустимое решение 0x эффективно тогда и только тогда, когда оно является оптимальным решением задачи .),()(,)(max:),( 0 1 1           miii m i NixfxfXxxfXFZ Если решение 0x не эффективно, то в результате решения этой задачи на- ходим эффективное решение ,x более предпочтительнее, чем ,0x т.е. ).()( 0xFxF  В данной статье в развитие работ [1, 5, 6, 813], предложен и обоснован под- ход к решению задачи ),,( XFZ основанный на развитии метода главного крите- рия для рассматриваемого класса векторных задач. Метод решения однокритери- альных задач основан на идеях декомпозиции, отсекающих плоскостей Келли, ре- лаксации. При его реализации учитывается тот факт, что количество ограничений довольно большое. При разработке метода на начальном этапе необходимо определить исходное решение. Рассмотрим однокритериальную задачу без ограничений, описывающих многогранник D. Утверждение 2. Если для элементов мультимножества A и коэффициентов ,, nj Njc  целевой функции задачи            ),(Пvert)(extr 1 HAxxcxf s nk n j jj выполняются соответственно условия naaa  21 и ,... 21 niii сcс  ,nn Ni  то максимум функции )(xf на допустимом множестве достигается в точке ),,(Пvert)...,,( 1 HAxxx s nkii n   которая определяется как ,nji Njax j  (10) а минимум — соответственно в точке ),...,,,( 21 niii yyyy  где jni ay j  1 }.0{1  nNj Справедливость этого утверждения очевидна, так как наибольшее значение суммы попарных произведений достигается при сопоставлении возрастающих по- Проблемы управления и информатики, 2008, № 6 35 следовательностей значений ic и ,ix а наименьшее значение суммы — соответ- ственно при сопоставлении возрастающей последовательности значений ic и убывающей последовательности значений .iy При построении метода решения многокритериальной задачи ),( XFZ сле- дует учитывать структурные особенности ее допустимой области. Для рассматриваемого класса векторных задач на комбинаторном множестве полиперестановок предлагается метод главного критерия. Он состоит в том, что исходная многокритериальная задача сводится к задаче оптимизации по одному критерию ,),( lr Nrxf  который объявляется главным, или основным, при усло- вии, что значения всех остальных критериев должны быть не меньше некоторых установленных величин (пороговых значений) }.{\, rNit li  Таким образом, по- лучаем задачу }.}),{\(,)()({max:))(,( XxrNitxfxftXfZ liirir  Оптимальное решение 0x этой задачи всегда слабо эффективное, а если оно единственно (с точностью до эквивалентности ),f то и эффективное. Ес- ли решение 0x эффективное, то оно единственное (с точностью до эквивалент- ности )f решение задачи ))(,( ir tXfZ при любом фиксированном lNr и }).{\(),( 0 rNixft lii  Выбор одного из критериев в качестве главного никак не уменьшает свободы выбора оптимального решения. Для определения пороговых значений },{\, rNit li  можно воспользоваться утверждением 2, которое позво- ляет установить верхние и нижние границы значений критериев ,),( li Nixf  на множестве полиперестановок. Предлагаются два подхода к решению исходной задачи ).,( XFZ Первый со- стоит в назначении порогам },{\, rNit li  максимально возможных значений критериев ,),( li Nixf  на множестве полиперестановок с последующим расши- рением допустимого множества задачи )),(,( ir tXfZ если исходная задача ока- жется недопустимой, а в случае ее допустимости — в отыскании эффективного ли- бо слабо эффективного решения. Второй подход предполагает поиск оптимального решения задачи ))(,( ir tXfZ при назначении минимальных значений критериев ,),( li Nixf  при которых она всегда допустима, с последующим сужением до- пустимой области посредством выбора значений порогов ,it }),{\( rNi l упоря- доченных по возрастанию и следующих за минимальными значениями критериев. Процедура назначения (определения) серии пороговых величин ,it }),{\( rNi l ограничений и при первом, и при втором подходе очень проста, так как, с учетом утверждения 2, она сводится после упорядочения коэффициентов критериев к вычислению скалярного произведения двух векторов, т.е. к опреде- лению значений линейных функций критериев. При этом, учитывая структурные особенности множества полиперестановок, величины it можно вычислять более эффективно, используя перестановки элементов каждого i-го, ,sNi подмноже- ства мультимножества A. 36 ISSN 0572-2691 Для описания и обоснования метода решения задачи ),( XFZ введем сле- дующие обозначения. Допустимую область задачи ),( GFZ запишем в виде G },{ gHxRx n  ),...,,,( 21 ugggg  ,nuRH  H — матрица, которая исполь- зуется для матрично-векторной формы записи ограничений вида (1), (2) и линей- ных неравенств, описывающих многогранник D, где все ограничения сведены к одному )( виду неравенств. Обозначим uN множество, элементы которого определяют номера ограничений системы (1), (2) и дополнительных ограничений, описывающих выпуклое многогранное множество D: }.2...,,2,1{ mN n u  Учитывая, что количество ограничений, описывающих допустимую область задачи, велико, целесообразно использовать процедуру релаксации, т.е. времен- ного отбрасывания некоторых ограничений и решения задачи с более широкой допустимой областью. Определим множества ;},,{ uii n i NigxhRxG  для произвольного nv Rx  определим множества активных },{)( i v iu va gxhNixN  и неак- тивных — },{)( j v ju vn gxhNjxN  ограничений в точке ;vx ,n i Rh  ,Rgi  ,uNi — соответственно i-я вектор-строка матрицы H и i-я компонента вектора g. Рассмотрим задачу },)({max:),( vv GxxFGFZ  где nv RxG  { },,, uvii NQigxh  vQ — множество индексов ограни- чений, описывающих допустимую область задачи ),,( vGFZ которая решается на v-м шаге алгоритма, ,\ vqv RNQ  vR — множество номеров ограничений, которые не были включены в эту задачу на v-м шаге. Определение 6. Величина ,,,)( uiii Nigxhxr  называется отклонением точки nRx от границы множества ,iG а величина })({max)( ui Nixrxr  — отклонением точки nRx от границы множества G. Очевидно, что для pNi ,)( 11     i j i j i j i axxr j (11) а для )\( pu NNi ,,)( iii dxbxr  (12) где ib — i-я вектор-строка матрицы ., RdB i  Теорема 9. Эффективное (Парето-оптимальное, слабо, строго эффективное) решение 0x задачи ),( vGFZ является эффективным в том же смысле решением задачи ),( GFZ тогда и только тогда, когда выполняется условие .0)( xr Доказательство. Необходимость этого утверждения очевидна, поскольку допустимое решение 0x задачи ),( vGFZ является допустимым решением задачи ),( GFZ тогда и только тогда, когда выполняется условие .0)( xr Достаточ- ность утверждения следует из построения задачи ),( GFZ и определения ).(xr Проблемы управления и информатики, 2008, № 6 37 Основная идея предлагаемого метода решения задачи ),( XFZ состоит в сле- дующем. 1. Сводим многокритериальную задачу ),( GFZ к однокритериальной задаче ),( GfZ методом главного критерия. Полагаем .0v 2. Выбираем ограничения начальной системы, которая определяет область ,GGv  решаем задачу ),( vGfZ с помощью симплекс-метода и находим опти- мальное решение .vx 3. Если полученное оптимальное решение представляет собой полипереста- новку, т.е. вершину полиперестановочного многогранника, то в найденной точ- ке vx проверяем выполнение ограничений, которые не были учтены. Очевидно, ими могут быть лишь те ограничения, которые описывают выпуклое многогран- ное множество D. Если решение vx не удовлетворяет этим ограничениям, то к ограничениям допустимой области задачи ),( vGfZ следует добавить наиболее нарушенное из ограничений многогранного множества D. Если решение vx удов- летворяет указанным ограничениям, то оно является эффективным решением за- дачи ),( GFZ и, следовательно, задачи ).,( XFZ 4. Если полученное решение vx не является полиперестановкой, то строим отсечение, проходящее через смежные вершины и отсекающее вершину, которая не является допустимой (полиперестановкой). Прибавляем это отсечение к огра- ничениям задачи ).,( vGfZ 5. Сравниваем значение )( vxf со значением целевой функции, найденным на предыдущем шаге. Если оно уменьшается, то отбрасываем неактивные (несу- щественные) ограничения в точке .vx Если значение )( vxf не изменяется, то ни- какие ограничения не отбрасываем. С измененной допустимой областью задачи ),( vGfZ переходим к п. 2 для решения этой задачи. То обстоятельство, что ни одно из ограничений не отбрасывается, если )( vxf остается равным предыдущему значению, гарантирует, что решается толь- ко конечное число задач вида ).,( vGfZ Общая идея предложенного метода состоит в последовательном включении ограничений задачи, которые описывают область допустимых решений. Важно правильно организовать на первом этапе решения задачи выбор ак- тивных ограничений — неравенств. Для решения задачи ),( XFZ необходимо учесть на начальном этапе лишь часть ограничений, которые определяют область X. Поскольку определение эффективных решений задачи ),( XFZ важ- нее, чем построение всего множества ограничений, описывающих допустимую область G, то достаточно построить только те ограничения множества G, которые определяют эффективные решения данной задачи. Рассматриваемый здесь метод предназначен для получения таких ограничений. Реализация метода в виде алгоритма описывается в следующем разделе. Для проверки принадлежности точки множеству полиперестановок ),( HAP s nk целесообразно воспользоваться следующей теоремой [11, 13]. Теорема 10. Если )...,,,( 21 iniii xxxx  sNi — точка, координаты которой упорядочены, si NiJjxx jj   , 1 и выполняется ограничение 38 ISSN 0572-2691 ,,...... 2121 s i i ii Niaaaxxx i   принадлежащее i-й группе неравенств системы (1), (2), то в точке x выполняются и все остальные неравенства і-й груп- пы этой системы. Сформулированные теоремы дают возможность при реализации алгоритма решения задачи ),( XFZ минимизировать затраты времени на проверку принад- лежности найденной точки комбинаторным ограничениям и уменьшить количе- ство ограничений в исходной системе. Предлагаемый алгоритм можно использовать для решения задачи ),( XFZ без учета всех ее ограничений. 6. Алгоритм решения многокритериальных комбинаторных задач на множестве полиперестановок Начальный шаг. Полагаем ,0v .0 Выбираем главный критерий ),(xf r .lNr  На основании утверждения 2 назначаем величины ,it }),{\(  rNi l для ограничений на остальные критерии. Для этого определяем, используя утвер- ждение 2, }),{\()},(Пvert,)({max  rNiAxxcxf l i knii ii и решаем задачу :))(,( i v r tGfZ  })}.{\(,)(,,)({max   rNitxfRGxxcxf lii nv rr Если она недопустима, то находим новые значения порогов }),{\(,  rNit li огра- ничений, которые являются следующими при упорядочении в порядке убывания их значений. Так поступаем до тех пор, пока задача ))(,( i v r tGfZ  не станет до- пустимой. В дальнейшем для простоты записи вместо индекса r используем r. Основная часть. 1. Выбираем произвольно начальную точку vx как элемент общего множест- ва полиперестановок либо, согласно утверждению 2, упорядочивая элементы век- тора rc коэффициентов целевой функции ,,)(  xcxf rr вычисляем значение ).( v rr xff  2. Точке vx соответствуют ограничения, описывающие вершину общего поли- перестановочного многогранника ),,(П HAs nk где ),,(П HAx v nk v  ),(П HAsv nk ).(П As nk Полагаем .pv NQ  3. Находим отклонения )( v i xr sqv QNRi \ по формулам (11), (12). 4. Выбираем })({max)( v v i v Rixrxr  и номер ограничения ,vRi при котором это отклонение достигается. 5. Проверяем неравенства .0)( vxr Если ,0)( vxr то переходим к следую- щему пункту алгоритма, иначе — находим эффективное решение задачи ).,( XFZ Для отыскания следующего эффективного решения переходим на начальный шаг алгоритма, выбрав в качестве главного другой критерий —   1),(1 rxf r ,\                  rN l и положив .1 Проблемы управления и информатики, 2008, № 6 39 6. Прибавляем полученное ограничение с номером vRi к ограничениям за- дачи ),,( vGfZ т.е. формируем допустимое множество подзадачи ),( vGfZ сле- дующим образом: }.,{1 ii nvv gxhRxGG   (13) 7. Если ,)( r v r fxf  (14) то определяем множество ,)( v vn QxN  заменяем множество vQ на vQ ),(\ vn v xNQ полагаем .1),(  vvxff v rr 8. Решаем задачу :))(,( i v r tGfZ })}{\(,)(,,)({max rNitxfGxxcxf lii v rr  двойственным симплекс-методом. Если эта задача не имеет решений, то неразре- шима и задача ).,( GFZ Иначе получаем оптимальное решение vx этой задачи. Если оно не является элементом общего множества полиперестановок ),,( HAP s nk то переходим к п. 9. Иначе, полагая ,pv NQ  переходим к п. 3 алгоритма. 9. Находим смежные с точкой vx вершины полиперестановочного много- гранника и строим отсечение, проходящее через эти вершины, вида ,, ii gxh  (15) которому не удовлетворяет полученная точка .vx Формируем систему ограниче- ний, описывающую множество ,vG по формуле (13) и переходим к п. 7. Замечание 1 (к п. 7 алгоритма). Если vx — элемент общего множества поли- перестановок ),,( HAP s nk то к множеству )( vn xN неактивных ограничений, ко- торые исключаются из множества ,vQ следует отнести все ограничения много- гранника ),,(П HAsv nk кроме тех, которые определяют точку .vx Замечание 2 (к п. 9 алгоритма). Определение смежной вершины полипере- становочного многогранника и построение ограничения, отсекающего точку ,vx выполняем таким же образом, как и в [8, 13]. Алгоритм решения задачи ),( XFZ с использованием второго подхода отли- чается от первого начальным шагом, на котором назначаются минимальные зна- чения порогам }),{\(, rNit li  ограничений критериев .),( li Nixf  Если эти ограничения при определении эффективного решения vx не активны, то в даль- нейшем допустимая область последующих задач ))(,( i v r tGfZ сужается посред- ством выбора среди значений порогов }),{\(, rNit li  следующих упорядочен- ных по возрастанию значений критериев. Теорема 11. Работа алгоритма заканчивается после решения конечного числа подзадач ))(,( i v r tGfZ и приводит к получению эффективного решения задачи ),( XFZ или к построению такого множества ограничений, при котором текущая подзадача ))(,( i v r tGfZ неразрешима. 40 ISSN 0572-2691 Доказательство. Поскольку X — конечное множество, то оно имеет конеч- ное число подмножеств. При уменьшении  xcxf rr ,max)( от одного шага к другому ни одно подмножество не может повториться. Поскольку ни одно огра- ничение не отбрасывается, если ,)( fxf v  и в крайнем случае одно или два ограничения добавляются, то значения )( vxf могут оставаться постоянными лишь на протяжении конечного числа итераций. Итак, за конечное число шагов алгоритм заканчивается. Заключение В статье исследованы сложные многокритериальные задачи на комбина- торном множестве полиперестановок. Изучены некоторые свойства допустимой области комбинаторной многокритериальной задачи, погруженной в арифмети- ческое евклидово пространство. Получены необходимые и достаточные условия оптимальности различных видов эффективных решений. Построен и обоснован метод решения рассмотренного класса задач. Программная реализация предло- женного подхода предоставляет возможность исследовать и найти элементы множества Парето-оптимальных решений многокритериальных комбинаторных задач с учетом других комбинаторных свойств области допустимых решений. Разработанный подход может успешно применяться для решения многокрите- риальных задач на комбинаторном множестве полиперестановок. Н.В. Семенова, Л.М. Колєчкіна, А.М. Нагірна РОЗВ’ЯЗАННЯ ТА ДОСЛІДЖЕННЯ ВЕКТОРНИХ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ НА МНОЖИНІ ПОЛІПЕРЕСТАНОВОК Досліджено складні векторні задачі на комбінаторній множині поліпереста- новок. Вивчено деякі властивості допустимої області комбінаторної багаток- ритеріальної задачі, що розв’язується в арифметичному евклідовому просто- рі. Отримано необхідні і достатні умови оптимальності різних видів ефектив- них розв’язків. Побудовано та обґрунтовано метод відшукання Парето-опти- мальних розв’язків розглянутого класу задач. N.V. Semenova, L.N. Kolechkina, A.N. Nagornaya SOLUTION AND INVESTIGATION OF VECTOR PROBLEMS OF COMBINATORIAL OPTIMIZATION ON A SET POLIPERMUTATIONS The complex vector problems of combinatorial optimization on a set of polipermutations are investigated. Some properties of feasible domain of combinato- rial multicriteria problem in arithmetic Euclidian space are considered. The necessary and sufficient conditions of optimality of different types of efficient solutions are ob- tained. The method of finding of Pareto-optimum solutions of the considered class of problems is constructed and substantiated. Проблемы управления и информатики, 2008, № 6 41 1. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. — Киев : Наук. думка, 1988. — 472 с. 2. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных за- дач оптимизации. — Киев : Наук. думка, 1981. — 287 с. 3. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. — Киев : Наук. думка, 2003. — 264 с. 4. Сергиенко И.В., Козерацкая Л.Н., Лебедева Т.Т. Исследование устойчивости и параметри- ческий анализ дискретных оптимизационных задач. — Киев : Наук. думка, 1995. — 170 с. 5. Сергиенко И.В., Лебедева Т.Т., Семенова Н.В. О существовании решений в задачах вектор- ной оптимизации // Кибернетика и системный анализ. — 2000. — № 6. — С. 39–46. 6. Лебєдєва Т.Т., Семенова Н.В., Сергієнко Т.І. Умови оптимальності та розв’язуваності в за- дачах лінійної векторної оптимізації з опуклою допустимою множиною // Доп. НАН України. — 2003. — № 10. — С. 80–85. 7. Лебедева Т.Т., Семенова Н.В Сергиенко Т.И. Устойчивость векторных задач целочисленной оптимизации: взаимосвязь с устойчивостью множеств оптимальных и неоптимальных ре- шений // Кибернетика и системный анализ. — 2005. — № 4. — С. 90–100. 8. Семенова Н.В., Колечкина Л.Н., Нагорная А.Н. Подход к решению векторных задач дис- кретной оптимизации на комбинаторном множестве перестановок // Там же. — 2008. — № 3. — С. 158–172. 9. Semenova N.V., Kolechkina L.M., Nagirna A.M. Vector combinatorial problems in a space of combinations with linear fractional functions of criteria // Intern. J. Information Theories and Applications. — 2008. — 15. — P. 240245. 10. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. — М. : Наука, 1982. — 256 с. 11. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометри- ческого проектирования. — Киев : Наук. думка, 1986. — 265 с. 12. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. — К. : Ін-т систем. досліджень освіти, 1993. — 188 с. 13. Ємець О.О., Колєчкіна Л.М. Задачі комбінаторної оптимізації з дробово-лінійними цільовими функціями. — К. : Наук. думка. — 2005. — 118 с. 14. Ємець О.О., Роскладка О.В. Задачі оптимізації на полікомбінаторних множинах: властивості та розв’язання. — Полтава : Ред.-вид. центр Полтавського ун-ту споживчої ко- операції України, 2006. — 130 с. 15. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. — М. : Наука, 1981. — 344 с. Получено 18.08.2008 Статья представлена к публикации членом редколлегии А.А. Чикрием.

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

Institution

Ähnliche Einträge