Относительная важность критериев и её при менение в многокритериальной оптимизации тема автореферата и диссертации по математике, 01.01.11 ВАК РФ

г» г- г. п П

с, у '

САШП'-ПЕТНРРУРГСВД"! ГОСШРСГВЕННЫЧ УНИВЕРСИТЕТ

На правах рукописи

НОТ11Н Владимир Дмитриевич,

откоатгатя вмгаосгь критериев

И ЕЕ ПРИМЩНИЕ В МНОГОКРИТЕРИАЛЬНО« ОПТИМИЗАЦИИ nl.ol.IT - Системный анализ я автоматическое утоавление

Автореферат

дассетэтагаи на соискание ученей! степени доктора (¡тгзико-иатемаягческях яаук

Санкт-Петербург

2°Рг

Работа выполнена в Санкт-Пе те рбуогс к см государственна.'.

Техническая Университете.

Сйяшалыше сппоиенти: - доктор технических наук,

профессор Гаврилов В.М.;

- доктор (Физико-математических наук, профессор Федоров В.В.;

- доктор (физико-математических наук, доцент Чистяков C.B.

Ведущая сгогвнизадая: институт системного анализа РАН.

Зашита состоится " 1Д-" ^¿^ в час.

на заседании диссертационного Совета по защите

диссертаций на ссисгсание"ученей степени доктора ({мзико-матема-тгчеоких наук а Санкт-Петербургскал государственна* университете по адресу: Санкт-Петербург, 10 линия В.О., кем ял, аул.

С диссертацией могло оэнакалиться в +ундаментал1лоН бислиотеке Санкт-Петербургского государственного университета /Университетов наб., дал 7/р/.

Автореферат разослан " Ю " _1ро -¿Гг.

Ученый секретарь диссеотаиионного Совета доктор <5из.-маг. наук

Кябко А .И.

СТТАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Известно, что процессы управления сложными системами характеризуются наличием, как правило, нескольких (нередко -взаим(противоречивых) целей, или показателей качестзв . Учет одновременно нескольких целей ведет к необходимости использования результатов и методов теории многокритериальной оптимизации, которая к настоящему времени получила статуо самостоятельного, богатого идеями и приложениями научного направления в рамках системного анализа.

Возникновению и развитию интереса к многокритериальной оптимизации и ее многочисленным приложениям во многом способствовала деятельность таких зарубежных ученых, какЛ.ГУРВии, Л .Заде, А.ДжвофЗщон, С.Карлин, Р.Кнни и Х.РайЗе, Х.Кун и А.Таккер, Т.Купманс, Б.Руа, Т.Саати, С. СМейл, А.Чарнс и у.кулер, К-Зрроу. В нашей стране период становления итого научного направления связан с именами В.И.Борисова, Ю.Е.Гермей-ера, С .В .Емельянова ^ А.МЛетова, Н.НЛоисеева и др.

На взгляд автора, развитие многокритериальной оптимизации осуществлялось в двух основных направлениях. С одной стороны, под давлением практики появлялись различные метода и процедуры решения много критериальных задач, которые, в основном, носили эвристический характер (см., например, обзорные работы о .И Ларичева). С другой стороны, крепла математическая база теории за счет обобщения соответствующих результат® обычной теории оптимизации. Здесь, в первую очередь, имеются в виду различного рода необходимые и достаточные условия оптимальности, уо-ловия существования и вопросы двойственности. К сожалению, следует сг-метить, что и к настояшему времени связи между двумя указанными направлениями весьма слабые. В частности, исключительно актуальными представляются вопросы строгого математического обоснования палого ряда известных процедур многокритериального выбора с целью получения четких граяип логически обоснованного их применения на практике.

Большое количество известных методов многокритериального выбора в той или иной форме предполагают использование различного рода информация об относительно» важности критериев. Однако, пожалуй, никто крене В.В.Подиновского не предпринимал серьезных попыток логического обоснования использования этой информации на основе введения строгах

математических спределагай таких высказываний, как "один критерий важнее другого критерия" и "один критерий равноценен другое.ту критерию" ,

Необходимо выделить два типа информации о важности критериев - качественная и количественная. Что касается икфсрмаши первого типа, то здеоь к настоящему времени самим В.В.Подиногским, его учениками и коллегами сяубликовано значительное количество работ, в которых подробно исследованы вопроси непротиворечивости и учета этой информации в различных конкретных ситуациях. Работ, связанных с количественной информацией о важности критериев, совсем немного. Саш не носят общего характера и круг вопросов, изучаемых в них, довольно ограничен, хотя следует отметить, что именно количественная информация через козсйн-шенты относительной важности чаще всего используется в практике решения многокритериальных задач.

Цель работы заключается в следующем

- сформировать общую математическую модель, предоставляющую возможность при решении широкого класса задач обоснованно учитывать количественную информацию об относительной важности критериев;

- в рамках указанной модели строго ввести понятия относительной важности и равноценности критериев, а также коэф&ишенгы относительной важности;

- разработать методы и .алгоритмы учета количественной информанта об относительной важности критериев;

- изучить вопросы полнош.и непротиворечивости конечного набора информации оо относительной, важности.

Методы исследования, в работе используется аппарат теории множеств и теории нечетких мнсиаств, выпуклого анализа и теории размерности частично упорядоченных множеств. '

Научная ровизна. Результаты работы являются новыми и получены лично соискателем.

Теоретическая и практическая ценность. Совокупность полученных в диссертации результатов можно рассматривать как решение крупней иаучнз£ проблемы, связанной с уточнением понятия количественной информации об относительной важности критериев в рамках общей математической модели, разработкой строгих методов и алгоритмов учета этой информации, а также исследованию вопросов ее полноты и непротиворечивости.

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

- ñ -

ления слокнши объектами и системами.

В частности, результаты работы были использованы при разработке годовой производственной лрограшы АО "Ленэнерго".

Апробапия работы. Результаты работы обсуждалиоь на межреспубликан-сксм семинаре "Математическое и программное обеспечение задач многокритериальной оптимизации и их приложение" /Ереван, 1968/, нй всесоюзно! научно-првктическсм оеминаре "Интеллектуальное программное обеспечение 5БМ" /Ростов-на-jtony, 1990/. на III и ГУ всеооюзных школах-оемннарах "Комбинаторно-статистические метода анализа и обработки ин-формащи, экспертное оценивание" /Одесса, 1990. 1991/, на 1У всесоюзном семинаре по исследованию спераций и системному шализу /Батуми, 1983/, наХГУ международно!! конференши "Математическая оптимизация -теория я прялотение'УГЦР, 1989/, на IX международной конференши по многим критериям /США, 1990/, на международна* конгресов по компьютерным системам в прикладной математике /Санкт-Петербург, 1993/, на международной конференши по многокритериальным задачам при неопределенности /Орехово-Зуево, 1994/, в институте математики и механики УрО РАН, на Факультете прикладной матемагики-процессов управления СП61У, в Санкт-Петербургском зконсмико-математическсм институте РАН, на математически отделении института высокопроизводительных вычислительных систем РАН и в институте системного анализа РАН.

Публикации. Результаты диссертации опубликованы в .

CTOTiprvpa и объем работы. Диссертация'содержит развернутое введение, три главы, пять приложений с листингами программ, заключения и списка литературы, объем работы - 299 стр. Библиография насчитывает 110 названия, имеется в рисунков и II таблиц.

СОЕРУАНИЕ РАБОТУ

Во введении обосновывается актуальность темы диссертации, обсуждаются цели, структура и содержание работы.

Первая глава начинается фс^мршрованива исходной мате-матическсй модели, содержащей следующие объекты

где го. - число критериев, Е- - пространство значений \_-го критерия (индивидуальная шкала), Р^ С. - асишетдачное,

слабо связное бинарное (индивидуальное) отношение строгого предпоч-

- в -

тения, 13. : —- числовая функшя, с псмалью которой учитывается количественный характер информации о важности критериев, т. = Е = Р Е, - пространство оценок (коллективная шкала) , Р с: Е>- Е. - асимметричное бинарное (коллективное} отношение строгого предпочтения, а "У" с Е - множество допустимых (возможных) оценок, из которого осуществляется выоор.

Далее обычно считается, что - аддитивная группа с нулевым

элементен ^ , 1= . , а на Е: операция сложения опреде-

ляется при псмаян стандартного равенства

причем (0,,.. , Сц,4] = <0,^ -нулевой элемент

Наиболее простой способ задания Функши в случае 155. ,

= С > ") состоит в следующем:

Ол

U)

В основу предлагаемого подхода псшсжено следующее

Определение, пуст* С ] = ( 1 Дч. ..^тД , А fé ,

Вз jé у< , AnïS = ^ • Группа критериев А называется более

важной, чем группа критериев £S с наборами параметров "Ц*? О Vit А к

тдТ > О Vie . если истинна импликация à i

Vie

П ч

A

Vie A

; \

i

a

В определении двух равноценных критериев использована идея симмет-

рии.

Определение, пусть г, l G I

г ^ с положительными параметрами и

истинны

1 ¥■

. Будем говорить, что критерий г равноценен критерию I ] "•* - °

высказывания (г^ и

, если нижеследующие два

U4

I.U)

v ьс!\

г.- R ^ p. ->.

<1 I Ь ^w

uP,

a £V.

В петэвсй главы изучаются такие обше свойства введенных понятий важности » DSBHOiieHHccTi!, котошр имеют место при некоторых довольно слабых требованиях к участвуй™ в исходно!! модели объектам. В частноо-тп, иг:: определенных пведполпуениях ,

- в приведенных определениях маи?о считать",'что u =

Vs. 3 *

-t

- если кпитери:! t вагнее критерия i с параметрам ги: . Тл.\ и важнее

t t ® / . *

критерия к с параметрами , Пм^ , то критерий l будет важная

группы критериев с параметрами -+- , -utj* , ;

* *

- если KDirreprcJi ь важнее критерия j. с параметрами , а кслтегэиЯ i- важнее критерия j с пара'.ктрами Ы^ , 'их'- , то группа критериев будет важнее критерия i с параметрами из.* , "W^ ,

.. • -

■ если коптерда i важнее критерия j с параметрами Wc , "Uy , то

ramjco полсяеготе сохранится для любсА naps параметров "Mr', ги> ■ ,

таких, что > "USi* , OU; < tdj .

i «У

В §2 также вводятся активно используемые далее определения коэффициентов относительной важности. _ I Определение. Пусть А, Ь ^ 1 , А ^ , 2 V Ф / , Д Г\ & — .и группа критериев А важнее группы критериев &> с набораш параметров V* V <. е А и V | ь Г. . Положительное число *

©ч -

будем называть коэффициентом относительной важности, а

е = ^чгг* и А,

нормированным коэффициентом относительной важности для 1рупп критериев

А и Ь .

Очевидно,

О < < + ос ; I' сб^ < Г, = Л I- - 4/а .

Оказывается,возможна ситуашя, когда т.-й критерий важнее ]-го, а £ -й, в свою очередь, важнее г-го критерия. Доказано, что при определенных условиях необходимым условием подобной штуаиии является выполнение неравенства©^"©^ < ' . которое в термшах нормированных коэффициентов относительной важности принимает вид Оц - < .

В §3 напоминается, что конуоная многокритериальная задача содержит множество возможных решений X » -мерный векторный критерий ^ заданный по крайней мере на X и конус доминирования К<С. без начала координат. В случае К - \R4J_ конусную многокритериальную задачу предлагается именовать стандартной.

Ниже важную роль играет следующее

Определение. Лве конусные многокритериальные задачи (.X и (X, 0 , К^ , где , 0 =

с^ называются эквивалентными, есаш -4 и у

Из приведенного определения немедленно следует, что эквивалентные конусные многокритериальные задачи имеет одно и то же ынсиество недоминируемых оценок, которое для отношения строгого предпочтения Р

определяется равенством

1ГЬ0МРУ -

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

Прежде чем формулировать соответствующие результаты, заметим, что рассмотрение §§3-5 отраничено случаем асимметричного, транзитивного, инвариантного относительно положительного линейного преобразования отношения строгого предпочтения Р , которое удовлетворяет аксисме Парею. В терминах кснуса доминирования К это означает, что данный ксяус является острым, выпуклым, содержании не отришт ельный орт ант и не вгошчагашм начало координат. Крема того, будем считать, что вое функции определяются равенство» (IV

Теорема. Конусная многокритериальная задача, представляющая собой стандартную многокритериальную задачу (X Д , о дополни-

тельной информацией о тем, что критерий \ важнее критерия ^ с нормированным коэФФишентсм относительной важности , эквивалент-

на стандартно'.! многокритериальной задаче' СХ, ^, ^ ц.4) , в которой

^ = I/ \Гг>с]чЦ\.

Заметил, что в офсдаулярова.чнсй теореме относительно множества X и вектор-функши ^ никаких ггоедп сложений не делается; в этем проявляется ее универсальный хашктер. Косме того, новый критерий ^ сохраняет многие полезные свойства (например, выпуклость, вогаутооть, непрерывность и линейность) . В случае линейных критериев данный результат имеет наглядную гесметтжческуг иллюстрацию.

Следствие. Конусная многокритериальная задача, предотавляю-шя собой стандартную многокштетаальную задачу ОС Д, с дополнительной информацией о тал, что критерий равноценен коитерию ^ с нормированным коэффициентом относительной важности 0ц , эквивалентна стандартной многогоитешальной задаче , с^ ^ • гДе

Теорема. Конусная многокритерпальная_ задача, продетавлясная собой стандартную многокритериальную задачу (.Х.Д , о дополнительной информацией о тем, что критерий I важнее коитзрия ] с нормированным коэффициентом ^ и критерий I важнее критерия I с нормированным коэффициентом 6;1. , эквивалентна стандавтшй многокритериальна задаче (.К ъ ^«, в которой

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

Теорема. Конусная многокритериальная задача, представляющая собой стандартную многокритериальную задачу ОС с дополни-

тельной информацией о тал, что критерий ¡- важнее критерия к о нормированным коэффициентом и что критерий ] важнее критерия

с нормированным ксаЭДиивентсм , эквивалентна стандартней

многокритериальной задаче (.X, ^ , (5Г+ ^ » в котср0*1

НА.

I

В §4 первой гаавы доказан ал едущий общий результат.

Теорема. Пуоть А,Ь С I , А Ф 0 , (Ъ Ф / , А Л Ь — 0 . Конусная многокритериальная задача, представляв шая собой стандартную многокритериальную задачу (Х^ ^ р!4) с дополнительной информацией о тем, что группа критериев А важнее группы критериев В) о нормированными коэффициентами относительной важности , эквивалентна стандартной многокритериальной задаче (Х,, Ч 4 ^ , в которой ^ - ^-мерная вектор-функшя, соотавлвнн&я из тех компонент , для которых 1е 1Ч{Ь , а также компонент

вида о.. = 0 ^ д у Г, ¿6-А прячем р - м - слгД В + йо^А-'слг«!4^' а 4

Следствие.В условиях последней теоремы максимальное возыси-ное число критериев р доотитаетоя в случае, когда

слгс1 А = [.^^Чг1 % Ь = — I. 1

Например, щи по. = 1С, сог^! А = слгс! (Ь — , получаем ,

т.е. учет информации о том, что половина из десяти критериев важнее другой половины приводит к троекратному увеличению критериев.

Далее §4 посвящен изучению вопросов непротиворечивости и существенности конечного набора информации об относительней важности критериев.

Введем множество

Тот факт, что группа кттериев А важнее хрушш критериев Ь мсино записать в виде агу или и-\/ £ 1< , гае \< - конуо доминирования данного отношения предпочтения Р , причем вектор и —V € имеет положительные компонента, соответствующие ин-

дексам из множества , отрицательные - соответствующие индексам

из Ь , тогда как все остальные компоненты - нулевые.

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

3 и^-Ч •• ^ и АД,.. ^ . Сз)

Определение. Набор информации (3) будем называть непротиворечивым, если существует по крайней мере одно такое асимметричное, транзитивное и инвариантное относительно положительного линейного преобразования отношение Р , удовлетворяющее аксиоме Парето, для которого верво ц'-В'^ . ^ •

Цсшучены три варианта необходимых и достаточных условий непротиворечивости набора информации (3) - геометрический, алгебраический и вычислительный. Приведем формулировку последнего варианта, удобного для проверю! на компьютере.

Теорема. Для того, чтобы набор информации (3) был противоречивым, необходимо и достаточно, чтобы в задаче линейного программирования

« о, " (

К 7 С > ^ # с; ^

- о ^ ¿ = 4,1,.....с^ ,

оптимальное значение целевой функши было равно нулю..

В §5 л оказана сяедугавя теорема о полноте конви его набора инфор-иаши об относительной важности критериев.

Те о р е м а. Пусть С Р.т - произвольный острый выпуклый конус доминирования, не содержащий начало координат и такой, что К ^ Иэ , К • Для любого ^ > С существует такой конечный

набор пар векторов

^ е Г, и'^ч-в 1Гл К П\ДСи, „су,

что

ск пидси % ^е « • • -.^'-^Лисоо )< Е,

где \ГгСО^= Л^ц < , -

единичные срты пространства , а означает хауо-

дорфово расстояние между множествами А и . Более того, в формулировке теоремы можно считать, что компонента воех векторов ц'\ являютоя рациональными числами.

В соответствии с этой теоремой, не зная отношение предпочтения указанного класса, которым руководствуется ЛИР, на основе лишь конечного набора машияно-реализуемой информации об относительней важности критериев можно получить сколь угодно точное приближение неизвестного отношения предпочтения (точнее говоря, приближение конуса доминирования этого отношения),

Крема того, в §5 приводятся условия, когда конечный набор кнфорыазвд

- n -

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

В §6 после краткого изложения начальных понятий тар ии нечетких множеств, предложенной л.Заде, для исходной модели, в которой отношение строгого предпочтения Р является нечетким аешметричным отношением с функшей принадлежности (U (.•, О , формулщуотся определения относительной важности и равноиенности критериев. Прю едем первое

Определение. Пусть /\ ф ß ,

А Г\ [Ь . Будем говорить, что группа критериев А важнее

группы критериев Ь с заданными положительными парал атрами иЗ^ Vit А и iS^ и степенно уверенности , еоли

Оказывается, что все общие свойства понятий относительной важности ¡1 равноценности, установленные в §2, могут быть соотшт отвующим образом перенесены на случай нечеткого отношения предпочтения.

Последуютее рассмотрение §6 ограничивается случаем нечеткого асимметричного, инвариантного относительно положительного линейного преобразования отношения Р с функшей принадлежности ^ , удовлетворяющего нечеткой аксисме Парето:

е А с 1, fi

Vselx А

Вводится понятие многокритериальной задачи о нечетким кснуссы и устанавливается следующая

Теорема, нункшя принадлежности ¡Ц нечетгого отношения предпочтения указанного класса в нечеткой конусной мго гокритериальней

- 1,1 -

задаче, превставляппеЯ собс.Ч стандартную многокоатепиальну:о задачу с нечетко*'. ин^ошашеП о тш, что группа критериев А важнее труппы критериев Ь с нопмитюваншми коэффициентами относительней ва»ноо-ти G-- и степенью уверенности t {С, 1 ] ггседсгавит.'.а п вида

( 4 , если vj - y £ , = л если у-"J'* ^ ,

'J In ОЛОУ nWQTTliniV r^mrtjQtrv

-r

0 во всех остальных случаях

при всех ^ • Г.де f> = гч- u» cd £->■»• сд»И А • с о rc 1 Р, и ^

^-мерный вектор, первые г*-ьси4Ъ компонент которого суть и, и . u , а остальные компоненты вила У;;+ (Л-6-Л-

*"Ъ'.' '».а*-.?™1®« 4 «Jw * '

•ч; Vv-еЛ > Vi€- • 0(1Лалее, как и в четком случае, изучается непротиворечивость и существенность конечного набора нечеткой инФюрмации об относительной важности критериев; Формулируются соответствуйте результаты.

Креме того, в §6 обсуждается вопрос полноты конечного наоора нечеткой информации, который положительно решается для конечноэнвчных нечетких конусных отношений.

Прежде чем перейти к обсуждении результатов последующих гаав, отметим следующее. В работе В.В.Подиновского и О.Р.Меньшиковой (i.BM и М1?', 1988, т. 2Н, да) уже имеется определение относительной валкости для двух групп критериев, которое в случае Е;_-= 1Й. . Р = С>) яля l^c вида (I) и асимметричного инвариантного относительно положительного линейного преобразования отделения предпочтения эквивалентно общему определению из § I, хотя йтункшй U L , на Сазе которых б рамках развиваемого подхода вводятся коэффициенты относительной важности,у В.В. Подиновского нет. Предлагаемое здесь опредвяэяие двух равноценных критериев принципиально отличается сг соответствую!®го определения В. В.Подиновского. Лалее, хотя определения непротиворечивого набора информации о важности критериев у В.В.Подиновского вводится иным способом, в идейном плане оно близко к определении, данному автором диссертации. Близкими оказываются и критерии непротиворечивости (у В.В.Подиновского такой критерий был дан в форме решения определенной сиотемы неравенств, тогда как в данной диссертации алгебраический вариант критерия спирается на си от ему уравнений). в целом нельзя не опетить глубокое плодотворное влияние многочисленных работ В.В.Подиновокого на

- р,

прояснение многах вопросов и выработку у автора диссертации собственно.; позншк в области теории важности кр/теоиев.

Вторая глава посвяшена построение сиенок сверху и снизу для неизвеэ-тногс множества недешнируемнх решений (2) , когда относительно отношения строгого предпочтения ! известно лишь, что оно удовлетворяет некоторым разумным требованиям (асимметричности, инвариантности, транзитивности и парето-оптимальности) я, кроме того, имеется некоторый набор количественной информации об относительной важности критериев.

✓ ч

Определение, множество "V с. называется опенкей

сверху (снизу1) для мнстества (2) , если

В §1 втеюой главы обе опенки строятся для сшучая двух критериев при условии, что отношение строгого предпочтения Р удовлетворяет требования?,1 иррефлексивности, парето-сптямальности, слабой транзитивности '(.■зс.2; £"0 и инвариантности относительно поло-

жительного линейного преобразования, косме того, считается, что задан некоторый конечный набор интешаши об относительной важности критериев в форме (3^.

Для транзитивного отношения предпочтения установлено, что искомая опенка сверху мотет быть построена в виде множества парето-оптимальных решений относительно некоторой двумерной линейной вектор-Функши, кор-ффивденты которой определяются векторами и.\ V1" из (Л). Коли же указанное отнесение не является транзитивным, то опенка сверху предс-тавляетсобсй множество точек одновременного максимума некоторых двух линейных функций на множестве "V" •

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

^ ^ 2. не выполнено ни ^ Е* , ни а Р^

Доказано, что оценкой снизу является множество точек оптимальных по Слейтеру относительно некоторой двумерной линейной вектор-функции.

Приведет; иллюстративные примеры построения обеих оценок, а также получены необходимые и достаточные условия непротиворечивости исходной и отрицательной инФошаиии, используемые при построении одновременно

обеих указанных оиенок.

В Приложении I содержится написанная на языке СИ поогоамма построения указанных опенок вместе с проверкой на противоречивость исходных данных.

§2 посвящен построению опенки сверху для неизвестного множества не-дсминируемых опенок в обшем случае произвольного конечного числа критериев в классе отношений предпочтения, являющихся ирреФлексивными, па-рето-оптимальными, транзитивными и инвариантными относительно положительного линейного преобразования, креме того, считается заданным конечный набор количественной инФодааши об относительной важности критериев в вида (3).

Искомая опенка овеоху отооитоя как мнекеотво

м

на основе специального вида мажорантного отношения . В вотгоооах

вычисления указанной оценки оверху важную воль играет

Теорема. Пуоть К*-"", ^ ^ у • Соотношение 'Х V у имеет

место тогда и только тогда, когда вавно нулю оптимальное значение целевой функции в задаче линейного программирования

- - а* ^ ¿><4 - Ч ,

где

. > _ I А , еоли и Ъ С ,

Р л. а —; л '

д I - 1 , еали ц < о •

№сгомулш)аван алгоритм постооения оценки сверху в случае конечного множества

, который заключается в последовательном оешении задав линейного программирования специального вида.

В 5ч сохраняются предположения ггоедыдутего папагоаЯа относительно отношения строгого предпочтения и считается заданным конечный набор

отрицательной информации об относительной важности критериев в Фсшр-

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

где Ь^ - специального вида мияорантное отношение.

Локазана следующая ^

Теорема. Пусть эе, , "Х т^у . Соотношение "зс име-

ет место тогда и только тогда,когда для каждого I. = р в за-

даче линейного программирования

гпе а чл- г\¿ = цд.,..., р, оптимальное значение

целевой функции строго больше нуля.

Лалее в §3 в терминах решения задачи линейного программирования специального вида получены необходимые и достаточные условия того, чтобы набор исходной информации вместе о набором отрицательной информации не противоречили друг другу.

В Прилсиении 2 помещена написанная на языке ФОРТРАН программа построения как по отдельности оценки сверху или ониэу, так и одновременно обеих оданок в случае конечного множества

В §4 второй главы рассматривается класс нечетких отношений строгого предпочтения с функцией принадлежности р , обладающих свойствами иррефлексивности, транзитивности и инвариантности относительно положительного линейного преобразования. Заметим, что выполнение свойства паоето-сптимяльности (в нечетком варианте") , вообще говоря, не предпотв-гается. Считается заданной нечеткая ин^сюмашя в виде векторов иЛ ^ и чисел ^ , таких, что

•Г

ЭиЛ^е-. 5Г: и^-чЛ^-К, • (4)

Главным понятием рассмотрений 94 является нечеткое множество недоминируемых юешений, введенное С .Л. Орловским, ^Ункпия принадлежности которого определяется равенством

С - .^ти^Л . еслихеХ

* п, в противном случае.

Поскольку {унташ принадлежности ^ считается неизвестной, то таковой же будет и функция принадлежности (5) нечеткого множества недоминируемых решений. В этих услових для мндаеотва недоминируемых решений на основе дополнительной ин^кгомашта (-1) мскно лишь указать оган-1 ку сверху. формулируем соответствующее определение.

Определение. Нечеткое множество : I будем

называть оценкой сверху для нечеткого множества недсминируемых решений с Функцией принадлежности (5), если

Перейдем к списанию искомой опенки сверху и для удобства через

, ••• , ^_____\ЧЧ[

обозначим такую перестановку чисел , , .

•■■< - (Ч^ 4 А,

^ А - [^ ^ > < ^ НЕ 4 Ч

Через Л.^ , ( - -.-Д! , обозначим четкий полиэдральный вы-

пуклый конус, порожденный векторами ц1 -V1- , у которых соответствующие числа ^гО таковн> что ^ $ <11^ . очевидно,

с.. . ^ Л^ .

Введем нечеткий конуо со с суппоотсм при псмоши равенства

(-012СЛ в

. если С>ДД.У. а- -

мах \ А 1 1 . Е противном случае ;

и через ^ обозначим функщц принадлежности нечеткого конусного отношения с кснуссм ^ , не включающим начало координат в свсй суппорт. Таким обраэа.1, сО>Сл- для воех -.46^

Будем считать, что конус 51 е содешит ни один вектор ч'4 -Vе ,

такей, что ^I < . А,..., { Св противнем случае информация вида (.4} является противоречивой).

Имеет место следующая

Теорема. Нечеткое множество надсминируэмых решений для нечеткого отндаення с функцией принадлежности ^ является оценкой сверху для искомого множества недсминируемых решений (5).

}1алее в разбираются вычислительные аспекты построения указанной опенки сверху и Формулируется соответствующий алгоритм, который, в оо~ нознсм сводится к решению последовательности задач линейного программирования специального вида. Программа втого алгоритма для случая конечного мнсиества допустимых решений, написанная на языке ФОРТРАН, помешена в Прилскегош я.

Разобран иллюстративный пример построения оценки сверху для нечеткого множества недошнируемых решений в задаче с тремя критериями и четырьмя допустимыми решениями. Косые того, показано, каким образом оФорму-лированннй алгоритм мскет быть использован в более общем случае нечеткого допустимого множества.

§1 т р е т ь ей главы посвяшен изучению вопросов сложности (точнее, размерности) дискретных многокритериальных задач.

Задачу максимизации векторного критерия = (-то-п •• > на мншестве X С К^*- будем называть исходной задачей векторной максимизации (кратко: ЗШ4).

Определение. Пусть \ 5 ( г- совокупность всех эквивалентных вектеюных критериев (в смысле определения, данного в 'п пер-вей главы)в исходной ЭВМ, а "ы означает число компонент векгор-'Ьун-кши | . Натуральное число , определяемой равенством

йЬс — чи^лл. ио ,

назовем критериальной оазмеоностыо ЗВД и будем обозначать через ciuvv (А ) •

Оказывается, введенная критериальная размерность совпадает с размерностью частично упорядоченного отношением множества образов . Размерность частично упорядоченного мнсяества была введена в 194Я году Дувдиксм и Миллепсм и позднее иодаТишоована О.Оре.

Имеют место следующие утверждения.

Те о р е м а. Ксли ckw\(-( м. , то в множестве i(X) суш-

ствует такое конечное подмножество , что % t~Xc,)nw .

Теорема, Пусть множество образов -lOt) конечно. Если dlv^q-ç^x.^ — , то задача вычисления критериальной раэмернооти является полиномиально сложной, в случае > ¿L эта задача

|ГГ - полна.

Теорема. Пусть emc\ = • Тогда

ск^сСчУ) ^ , ы] . С6^

далее рассмотрение ограничивается случаем линейных $ункшй I, и конечного множества образов, показывается, что при числе переменных W= Я. критериальная пазмеонссть 33.' не превышает 2. Пои а> имеет место

Теорема. ДОя любого натушльного > Ъ существует множество 57е-соотояшее из ЗД. элементов, и линейны1.1, векторный критерий { , такие, что ^ •

Последняя теооема показывает, что даже в классе лияеиных векторных критериев, число переменных в которых больше двух, критериальная размерность мажет принимать сколь угодно большое значение. _

Нижеследующий результат устанавливает, что опенка durv^,!^4 ? имеющая место в силу неравенства (6 \ является точней в классе линейных векторных критериев, заданных на булевда кубе.

Т е о р е и а. пусть - булев куб. Существует линейная

вектор-Функпия $ , для котгобй выполнено равенство cUw^-^X^

Отметим, что доказательства дзух последних теорем являются ксиструть тивными.

В §1, креме того, офсюмулирсваны две нерешенные задачи, представлявшие интерес не только в рамках многокритериальна аггктазашп, но и для теории размерности частично упорядоченных множеств.

В 52 третье?. главы с различных точек зрения изучается внОор, основанный на введенном автгосм диссеоташи понятии г-оптимальной ТОЧКИ.

Определение. Рлемент называется г -сптималь-

ным, г € {4,2.,.., в ЗВД с вектооной Яункпией на множестве X. » если этот элемент является парето-оптимальным относительно каждой г -мерной векторм^ункши, составленной из компонент вектор-Функции

При г= гл Г- оптимальная тотка совпадает с парето-оптимальной. С уменнпением Г от гл. до \ получается конечная последовательность вложенных друг в друга множеств Г -оптимальных тсяек, каждое из кот одах является подмножеств см множества парето-оптимальных точек относительно исходной вектор-Лунгаш 4 • Иначе говоря, при уменьшении Г от гл. до 4 множество парето-сптимальных точек последовательно сужается, пока при Г= < не превратится в множество тсяек одновременного максимума по всем критериям. Так как точка одновременного максимума является подлинно идеальным решением ЗШ, то в случае, когда указанная последовательность вложенных множеств обрывается из-за пустоты очередного множества, представляется разумным в качестве подходящего решения ЗВМ использовать Г -сптимальнуго точку с наименншм возможным Г , пли кот ого см Г -оптимальные точки существует, описанный выбор условимся именовать Г"-сптималышм выбором.

При реализации г -оптимального выбора немалое теоретическое и практическое значение имеет в ото ос существования г-оптимальных тсяек при различных значениях параметра г . в общей постановке вопрос существования представляется чрезвычайно громоздким из-за специфического "комбинаторного" определения Г -оптимальной точки. В §2 приведены результаты численного исследования существования г -оптимальных тсяек, полученные с пагсшъю программы, написаннсй на языке Ф0РТРА.Н и пометенной в Приложении 4. Рассмотрен класс ЭВМ с конечным мясвествсм элементов, Ьодеожашм 2,1,^,^,6,7,8,9,10,1В,20,30,40,50 точек. При этом число кштериев взрыто овал ось от 3 до ТО. Элементы допустимого множества генерировались случайным образом по закону равномерного ваагоеделения. Выяснилось, что вероятность существования

Г -оптимальных точек (и их среднее число} резко уменьшается с увеличением разности между м. и г . Однако при числе критериев бо-

лее ^ вепоятность существования (»v,- ^ и См-а.) - оптимальных точек весьма высока даже для числа допустимых точек, близких к 50. Полученные результаты придают уверенность в целесообразности применения г -оптимального выбора на практике. __

Чосме того, в §2 установлена

Теорема. Г -оптимальный выбор является классически рациональным (парнодсминантным').

Предложена модификация г-оптимального выбора, связанная с предварительным учетсм количественной информации об относительной важности критериев (если такая информация имеется). Для этой цели мсошо использовать результаты §§2-3 первой плавы.

Наконец, в §2 введено понятие квази- г -оптимальней точки, мнежео-тво которых в случае конечного допустимого множества всегда непусто.

В описана об пая схема так называемого целевого программирования, родоначальниками которого считаются Чарнс и Купер. Предложено определенным образом развить этот метод и именовать его модифицированным алгоритмом целевого программирования, он включает следующие этапы:

- удаление из множества допустимых решений тех, которые не являютоя парет о-оптимальными;

- нормализация оставшихся решений;

- учет количественной информации об относительной важности критериев;

- применение метода целевого программирования.

Данный'алгоритм, программа которого, написанная на языке СИ, приведена в Приложении 5, был применен при решении задачи оптимизации голова! производственной программы энергетического объединения /на примере Ленэнерго/.

В разделе Заключение Фосмузшруотся основные полевения дисоертацеи, выносимые на защиту.

1. Предложены новые определения для количественного измерения относительной важности критериев. Изучено влияние и разработаны хетто реализуемые метода учета различного рода количественной информации об относительной важности критериев.

2. Получены необходимые и достаточные условия непротиворечивости прсозванного конечного набора количественной информации об относительной важности кштериев, а также ее существенности.

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

4. Предложенный количественный подход измерения относительно;! важности критериев распостпанен на случай нечеткого отношения строгого предпочтения.

Я. Разработаны алгоритмы построения оценок сверху п снизу для неизвестного множества недсмиотруемых решений на основе наличия конечного набора количественной информации об относительной важности критериев, реализованные на алгоритмическом языке *ГРТРАН.

В. Введено новое понятие кштепиальноК тзмерностп задачи векторной макшшзаши и изучены некоторые его свойства в случа:: линейного векторного критерия на конечном допустимом множестве.

7. предложена модификация известного метода целевого программирования, в которой прсизвсдаится учет конечного набора количественной информации об относительней важности критериев, эта модификация реализована на алгоритмическом языке СИ я апробирована при решении задачи составления гсшсасй производственной тгоогоакмы энергетического предприятия. Основные результаты диссертации опубликованы в работах I \ — 2 .

Литература

1. Ноган В.Л- Новый способ сужения области компромиссов.// Изв. АН СССР. Техническая кибернетика, 1976, Л 5.

2. Ногин В.Л. и др. Основы тесюии оптимизации.- м.: Высшая школа, 1986.

3. Коган В.Л. Опвнки для множества оптимальных решений в условиях отношения предпочтения, инвариантного относительно положительного линейного преобоазования.//лринятие решений в условиях неопределенности. Тезисы докл. ГТ Всесоюзн. семинара по исследованию операций и системному анализу.- М.-Ратуми, 1963, с. 37.

4. Нопш В.Л. Одна лшотеза в теории частично упорядоченных множеств. /Л1атеьштачвокое програшнов обеспечение задач многокритериальной оптимизации и их прилаяенне.- 'Ереван, 1988.

5. Нопш В.Л. Чош^ишраванный алгоритм целевого программирования.// Интеллектуальное програшное обеспечение ЯМ. Тезисы докл. Всесоюзн. научно-практич. оеыинара.-ростов-на-лону, 1990, с. 71.

6. Ноган В.Л. Многокритериальный выбор на основе г -оптимальных точек.//Ксмбинатоово-статистические метода анализа и обработки информации, экспертное оценивание. Тезиса докл. ТП Всессюзн. школы-семинара .-Одесоа, 1Р90, о. 91.

7. Ногин В.Л. Критериальная размерность задач векторной оптимизации и ее свойства.//Модели и метод» ептимизаши ,-М.,ВНИИ СИ, вып. 7, 1990,

с. 55-60.

8. Барыкин Е.Е., Вооспавва Е.А., Косматав Э.М., Ноган В.Л., Харитонова Н.Е. Сптнмизапия годовой производственной программы энергетического объединенид//Электрические станши, 1991, * 4, с. 9-13.

9. Ногин В.Д. Оценивание множества недоминируекых решений.//Ксмбина-тсрностатвстичеокие метода анализа и обработки информанта, экспертное оценивание. Тезисы докл. 1У Воесоюэн. школы-оеминара,-Сиесса, 1991, с. 142-144.

10. НогаяВ.Д. Перспективы и направления развития^количественной теории относительней важности критериев«// Иянавацвсвныэ наукоемкие технолопш. российская научно-техническая конференция, С.-Петербург, часть 5, 1995, с. 143.

41. JTOQWlk V-t>. 0«. ikt arderU\ oÇ vec-br ofck -

w^cxW ЬгоЫеы. // Mft^li. O^imgaW - TVeov/ <x*<i

кьЛЫюА.Travss,, W Xy\-W . СоЛ." , GЪЯ»

Ада» ьь. О.

kl IToûViLk E.S-VL»v\a-V.o* oHW ьс\ c viou4ow4lwaW

so\u\lows Fcwckowcx\ Avions av4

Vlovv, v. a, уь. SOi-SAS.

iTcqW М-Ъ. ^sV^aUcm OÎ \Ve W*/ «J ^ *vowAo«,.wA<d

o. Co^iw vw о a A

MWw^ics.-svtîvwwo f

4/, jToqWV/.Ъ. Oft^e VW/oÇ r«.\akve L^orWce <Ц СГСИ.У >àWvwC<mar^ он (WwVr A^UdUaVke-

j^oVvlsv v.t>. Ubber V о Wî/ «1 «A

•wi aoluko^.-^ Рч«^ Sek она ^sK.W^i v. 67,

^ ÏÊ-^VV^Veoi/ A rcUkvc ùw^or Vouer <4 etxWt-ia-. a Jo«AlfW«. 4-Worevn. // Мч1К»\е «-cWia uwaer Wer+aU4y, Ж Nrto.fcsVvo^ Or«V-Wo*c-

iiboU.x V.î>. Prob\evA t("biÄcreVe W^qU«,^^,

Зек. 135?. - 95.