Достижимость оптимальных решений линейной задачи многокритериальной оптимизации с альтернативными критериями в транзитивной субординации

Достижимость оптимальных решений линейной задачи многокритериальной оптимизации с альтернативными критериями в транзитивной субординации

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

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2011
Автор: Брила, А.Ю.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Назва видання:Проблемы управления и информатики
Теми:
Оптимальное управление и методы оптимизации
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/207325
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Достижимость оптимальных решений линейной задачи многокритериальной оптимизации с альтернативными критериями в транзитивной субординации / А.Ю. Брила // Проблемы управления и информатики. — 2011. — № 4. — С. 68–72. — Бібліогр.: 3 назви. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-207325
record_format dspace
spelling irk-123456789-2073252025-10-07T00:17:39Z Достижимость оптимальных решений линейной задачи многокритериальной оптимизации с альтернативными критериями в транзитивной субординации Досяжність оптимальних розв’язків лінійної задачі багатокритеріальної оптимізації з альтернативними критеріями у транзитивній субординації Attainability of Optimum Solutions of Linear Problem of Multicriteria Optimization with Alternative Criteria in Transitive Subordination Брила, А.Ю. Оптимальное управление и методы оптимизации Розглянуто способи знаходження досяжних оптимальних розв’язків лінійної задачі багатокритеріальної оптимізації з альтернативними критеріями у транзитивній субординації. Досліджується також випадок, коли між критеріями є деяка залежність, що впливає на їх вибір при розв’язанні задачі. Для однієї часткової транзитивної субординації розглядається задача вибору такої послідовності критеріїв, якій відповідає лексикографічно найбільше оптимальне значення цільової функції, побудованої на основі цієї послідовності. The methods of finding of attainable optimal solutions of linear problem of multicriteria optimization with alternative criteria in transitive subordination is considered. A case is considered also, when between criteria there is some dependence which influences their choice in the process of solving the problem. For the special case of partial transitive subordination consideration is given to the problem of search of such sequence of dependent criteria, that lexicographic optimal value of objective function, built on the basis of this sequence, corresponds to it. 2011 Article Достижимость оптимальных решений линейной задачи многокритериальной оптимизации с альтернативными критериями в транзитивной субординации / А.Ю. Брила // Проблемы управления и информатики. — 2011. — № 4. — С. 68–72. — Бібліогр.: 3 назви. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207325 519.8 10.1615/JAutomatInfScien.v43.i8.50 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 2011
topic_facet Оптимальное управление и методы оптимизации
url https://nasplib.isofts.kiev.ua/handle/123456789/207325
citation_txt Достижимость оптимальных решений линейной задачи многокритериальной оптимизации с альтернативными критериями в транзитивной субординации / А.Ю. Брила // Проблемы управления и информатики. — 2011. — № 4. — С. 68–72. — Бібліогр.: 3 назви. — рос.
series Проблемы управления и информатики
work_keys_str_mv AT brilaaû dostižimostʹoptimalʹnyhrešenijlinejnojzadačimnogokriterialʹnojoptimizaciisalʹternativnymikriteriâmivtranzitivnojsubordinacii
AT brilaaû dosâžnístʹoptimalʹnihrozvâzkívlíníjnoízadačíbagatokriteríalʹnoíoptimízacíízalʹternativnimikriteríâmiutranzitivníjsubordinacíí
AT brilaaû attainabilityofoptimumsolutionsoflinearproblemofmulticriteriaoptimizationwithalternativecriteriaintransitivesubordination
first_indexed 2025-10-07T01:09:20Z
last_indexed 2025-10-08T01:04:02Z
_version_ 1845373637987663872
fulltext © А.Ю. БРИЛА, 2011 68 ISSN 0572-2691 УДК 519.8 А.Ю. Брила ДОСТИЖИМОСТЬ ОПТИМАЛЬНЫХ РЕШЕНИЙ ЛИНЕЙНОЙ ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ C АЛЬТЕРНАТИВНЫМИ КРИТЕРИЯМИ В ТРАНЗИТИВНОЙ СУБОРДИНАЦИИ Введение Многокритериальные задачи с ранжированными в транзитивной субордина- ции критериями часто возникают при принятии решений несколькими лицами разного ранга. Для решения таких задач в [1, 2] предложен подход, основанный на использовании линейных сверток критериев, которые позволяют получать дости- жимые решения как решения соответствующих однокритериальных задач. В данной статье результаты, полученные в [2], применяются для решения за- дач многокритериальной оптимизации с альтернативными критериями. В этих зада- чах поиск оптимального решения осуществляется на основании одного или не- скольких критериев, которые удовлетворяют определенным условиям. Этот под- ход используется и для решения многокритериальных задач с альтернативными зависимыми критериями. 1. Линейная задача многокритериальной оптимизации с альтернативными критериями в транзитивной субординации Рассматривается многокритериальная задача с линейными критериями ,...,,2,1,)( qkxck  (1) и множеством допустимых решений ,nRX  которое определяется системой линейных уравнений и неравенств. Пусть ....,,2,1,,0)( qkXxxck  Если оп- тимальную альтернативу многокритериальной задачи оптимизации можно полу- чить как оптимальное решение соответствующей однокритериальной задачи оп- тимизации с целевой функцией, которая является линейной сверткой критериев многокритериальной задачи, то считается, что эта оптимальная альтернатива до- стижима по взвешенной сумме критериев разной важности. Пусть на множестве линейных критериев (1) задана [3] некоторая транзитив- ная субординация S. Упорядоченную последовательность критериев, т.е. вектор ,),...,,,( 21 qrccch ppppp pr  называют цепью критериев [3], ранжированных в субординации S, если и только если: 1) во множестве критериев (1) не существует критерия, который не принад- лежит ph и которому в субординации S подчинен каждый критерий последова- тельности ph ; 2) во множестве критериев (1) не существует критерия, который не принад- лежит ph и который в субординации S подчинен каждому критерию последова- тельности ph ; 3) критерии последовательности ph в субординации S строго ранжированы в соответствии с порядком следования их номеров prppp ...,,, 21 так, что 1p -й Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 4 69 критерий имеет наивысший ранг, prp -й критерий имеет самый низкий ранг, ранг ip -го критерия больше ранга jp -го критерия, если и только если .ji  Для каждой из таких цепей критериев можно рассматривать соответствую- щую задачу лексикографической оптимизации .)),(...,),(),(()(max 21 Xxxcxcxcxh prpppp L  (2) Для векторного критерия )(xhp можно отыскать [2, 3] такие коэффициенты ,...,,2,1,0 p p k rk  что решение задачи (2) является решением задачи линей- ного программирования .,)()(max 1 XxxcxL p k r k p p k    (3) Критерий )(xc kp назовем допустимым, если он удовлетворяет условию }....,,2,1{,,)( pppp rkRmmxc kkk  (4) На основании задач (2), (3) построим задачу выбора единственного допусти- мого критерия как можно большего ранга и назовем ее задачей многокритериаль- ной оптимизации с альтернативными критериями в транзитивной субординации. Покажем, что ее можно свести к задаче ,,)(max 1 XxxcL p k r k p p k    (5) где ,...,,2,1},1,0{,1,,)( 1            pk r k kk p k p kkpp rkyyyymxcXxX p kk      .случаепротивномв0 ,...,,2,1),(критерийвыбираемесли,1 pp k rkxc y k Если необходимо выбрать p допустимых критериев как можно большего ран- га, то множество X в задаче (5) будет определяться следующим образом: ....,,2,1},1,0{,,,)( 1            pk r k kk p k p kkpp rkypyyymxcXxX p kk Если же количество допустимых критериев не ограничивается, то }....,,2,1},1,0{,,)({ pkk p k p kkpp rkyyymxcXxX kk  Таким образом, задача поиска достижимых оптимальных решений линейной задачи многокритериальной оптимизации с альтернативными критериями в тран- зитивной субординации может быть сведена к задаче (5). 2. Линейная задача многокритериальной оптимизации с альтернативными зависимыми критериями в транзитивной субординации Пусть в задаче (2) критерий ),(xc kp },...,,2,1{ prk зависит от критериев ,)(xc ip }....,,2,1{ qIi kp  Это значит, что для допустимости критерия ),(xc kp кроме условия (4), дополнительно требуется, чтобы этому условию удовлетворял хотя бы один из критериев .,)( ki pp Iixc  70 ISSN 0572-2691 На основании задач (2), (3) построим задачу выбора t допустимых зависимых критериев как можно большего ранга и назовем ее задачей многокритериальной оптимизации с альтернативными зависимыми критериями в транзитивной субор- динации. Покажем, что эта задача может быть сведена к задаче , ~ ,)(max 1 XxxcL p k r k p p k    (6) где ....,,2,1},1,0{, ,,,)( ~ 1              pkk Ii i r k kk p k p kkpp rkyyy tyyymxcXxX kp p kk Таким образом, задача поиска достижимых оптимальных решений линейной задачи многокритериальной оптимизации с альтернативными зависимыми крите- риями в транзитивной субординации может быть сведена к задаче (6). 3. Линейная задача многокритериальной оптимизации с альтернативными критериями в частичной транзитивной субординации Пусть на множестве линейных скалярных критериев (1) задана частичная транзитивная субординация ранжирования .S В этой субординации ранжирова- ния множество критериев разбивается на подмножества ,...,,2,1},...,,,{ 21 rjcccQ jqjjjj  (7) число которых равняется числу рангов, по которым ранжируются критерии (1). Каж- дое из подмножеств (7) — это множество попарно взаимно неподчиненных крите- риев. Критерии подмножества 1Q имеют наивысший ранг, а критерии подмноже- ства rQ — самый низкий ранг; ранг критериев подмножества lQ больше ранга критериев подмножества ,pQ если и только если .pl  Каждый критерий подмно- жества низшего ранга подчинен каждому критерию подмножества высшего ранга. Следовательно, любые два критерия с разными рангами в этой субординации связа- ны между собой подчиненностью. Пусть tlk ccc ,, ),,1( qtlk  — некоторые критерии с разными рангами. Если kc подчинен lc и lc подчинен ,tc то kc подчи- нен ,tc поскольку kc принадлежит подмножеству низшего ранга, а tc — подмно- жеству высшего ранга, следовательно, эта субординация — транзитивная суборди- нация на множестве критериев. Рассмотрим множество последовательностей критериев }....,,,)...,,,({ 21 2121 rppppppp QcQcQcccchQ rr  Очевидно, что критерии в ph строго ранжированы согласно порядку их следо- вания. Для каждой из таких последовательностей ph рассмотрим задачу лексико- графической оптимизации .,))(...,),(),(()(max 21 Xxxcxcxcxh rpppp L  (8) Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 4 71 Задача (8) может быть сведена [3] к задаче линейного программирования ,,)()(max 1 XxxcxL r k pk k    где ....,,2,1,0 rkk  Рассмотрим задачу поиска последовательности критериев ,),...,,( 21 Qccch rpppp  для которой ,** p L p hh  ,** Hhp  .},,)(max{ *** QhXxxhhhH pp L pp  Эту задачу назовем задачей многокритериальной оптимизации с альтернативными критериями в частичной транзитивной субординации. Для ее решения рассмот- рим задачу max,)( ~ 1 1    xcL r j q i jij j i (9) ,Xx (10) ,...,,2,1,...,,2,1, rjqiy jijjij  (11) ,...,,2,1,1 1 rjy jq i ij   (12) ....,,2,1,...,,2,1},1,0{ rjqiy iij  (13) Пусть )~,~,~( yx — решение задачи (9)–(13), где ),~...,,~,~(~ 21 nxxxx  ),~...,,~,~...,,~...,,~,~,~...,,~,~(~ 212221212111 21 rqrrqq r yyyyyyyyyy  ).~...,,~,~...,,~...,,~,~,~...,,~,~(~ 212221212111 21 rqrrqq r  Сформируем последовательность критериев )...,,,( ~ ~~~ 21 rpppp ccch  такую, что ....,,2,1,1~~ rjy jp j  Теорема. Последовательность критериев ph ~ является решением рассматри- ваемой задачи многокритериальной оптимизации с альтернативными критериями в частичной транзитивной субординации .,)~( ~ **** Hhhhxh pp L pp  Доказательство теоремы легко получить, учитывая правило выбора коэффи- циентов ....,,2,1,0 rkk  Заключение Рассмотренные многокритериальные задачи иллюстрируют преимущества использования коэффициентов линейной свертки, которая позволяет не только перейти от многокритериальной задачи оптимизации к однокритериальной, но и решить некоторые задачи многокритериальной оптимизации с альтернативными критериями. 72 ISSN 0572-2691 А.Ю. Брила ДОСЯЖНІСТЬ ОПТИМАЛЬНИХ РОЗВ’ЯЗКІВ ЛІНІЙНОЇ ЗАДАЧІ БАГАТОКРИТЕРІАЛЬНОЇ ОПТИМІЗАЦІЇ З АЛЬТЕРНАТИВНИМИ КРИТЕРІЯМИ У ТРАНЗИТИВНІЙ СУБОРДИНАЦІЇ Розглянуто способи знаходження досяжних оптимальних розв’язків лінійної задачі багатокритеріальної оптимізації з альтернативними критеріями у транзи- тивній субординації. Досліджується також випадок, коли між критеріями є де- яка залежність, що впливає на їх вибір при розв’язанні задачі. Для однієї част- кової транзитивної субординації розглядається задача вибору такої послідовно- сті критеріїв, якій відповідає лексикографічно найбільше оптимальне значення цільової функції, побудованої на основі цієї послідовності. A.Yu. Brila ATTAINABILITY OF OPTIMUM SOLUTIONS OF LINEAR PROBLEM OF MULTICRITERIA OPTIMIZATION WITH ALTERNATIVE CRITERIA IN TRANSITIVE SUBORDINATION The methods of finding of attainable optimal solutions of linear problem of mul- ticriteria optimization with alternative criteria in transitive subordination is consid- ered. A case is considered also, when between criteria there is some dependence which influences their choice in the process of solving the problem. For the special case of partial transitive subordination consideration is given to the problem of search of such sequence of dependent criteria, that lexicographic optimal value of objective function, built on the basis of this sequence, corresponds to it. 1. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критери- ям. — М. : Сов. радио, 1975. — 115 с. 2. Брила А.Ю. Достижимость оптимальных решений линейной задачи многокритериальной оптимизации по взвешенной сумме критериев разной важности в транзитивной субордина- ции // Кибернетика и системный анализ. — 2008. — № 5. — С. 135–138. 3. Червак Ю.Ю. Оптимізація. Непокращуваний вибір. — Ужгород : Ужгород. нац. ун-т, 2002. — 312 с. Получено 17.03.2011 Статья представлена к публикации членом редколлегии И.В. Сергиенко.

Схожі ресурси