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

г» - ¡1 г п

п о ^

САНКТ-ПЕТЕРБУРГСКИ". ГОСУЗИРСГВЕННЦЧ УНИВЕРСИТЕТ

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

НОГИН Владимир Ддштешгч г

ОТНОСИТЕЛЬНАЯ ЕЛУНОСГЬ КРИТЕРИЕВ 1' ЕЕ ПРИМЕШРТЗ В МНОГОКРИТЕРИАЛЬНОЙ СПШИЗ/ШИИ

01.01.11 - Системный анализ и автоматическое уппавленле

Автореферат

дпссеоташи на соискание учэясй степени доктора Аизико-математическизс наук

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

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

Техническом Университете.

ОШатпыше сгпоненги: ~ доктор технически* наук,

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

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

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

Велушя организация: институт системного анализа РАН.

Защита состоится " д^ра^чд IPP-^^r. в час.

на заседании диссертационного совета Я-ОбЧ.Я^ЛЧ по зашито диссертаций на соискание'ученей степени доктора фмзико-матема-ттгчеоких наук в Санкт-Петепбургсксм госудапственнсм университета по адресу: Санкт-Петербург, 10 линия B.C., дал 31, ауд.

С диссертацией могло ознакомиться в фундаментальней бислиотеке Санкт-Петербупгского государственного университета /Университетов наб., дсм 7/f/.

Автореферат разослан " Ю " _jçq ^Гр.

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

Набко А.П.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура и объем работы. Лиссеоташя' Содержит развернутое введение, три главы, пять приложений с листингам!? программ, заключения и списка литературы, объем работы - 299 стр. Ёибли о гравия насчитывает 110 названий. Имеется Р шсунков и II таблиц.

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

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

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

где «п. - число критериев, - ппостранство значений ]_-го

критерия (индивидуальная шкала), Р^ С Н-^*- - асимметричное, слабо связное бинарное (^индивидуальное) отношение строгого предпоч-

- в -

тения, 1¿- '. Р —>- - числовая функшя, с псмоиью которой учитывается количественный характер информации о важности критериев,-¡.= ^ у Е = п Е- - пространство опенок (коллективная акала) , Р> сС Еу- Е.1" - асимметричное оинарное (коллективное) отношение строгого предпочтения, a "Ye; Е - множество допустимых (возможных) ода-нок, из которого осуществляется выоор.

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

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

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

причем .., С .Л — О»« - нулевей элемент t.

Наиоолее простой способ задания функции в случае Я ,

_ состоит в следующем:

1Л

СП

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

Определение. Пусть" А>£> С I = , А 7* р ,

^Ь ^ г/ , Д р, = 0 . Труппа критериев А называется более

важной, чем группа критериев с набсоами параметров О А и

тд* > О VI 6 . если истинна ишишкапия 4 <1

А

Vj-.- ^

VieA

Л

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

Определение, пусть г,^ 6 I , 'г ^ , Е; = Е.- = , г . Будем говорить, что критерий г равноценен критерию с положительными параметрами и , если нижеследующие два

высказывания (гЛ и истинны

со

ио

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

- л приведенных агоеделениях ма?но считать';'что Чь~

- если критерий 1 важнее кпитешя ] с параметрами , и важнее критерия £ с параметрами , то критерий будет важнее группы критериев ^, с параметрами , иХ* , ;

• если критерий ь важнее критерия | с параметрами ъ^ , а ктатерий ^ важнее юзитеташ \ с папамгтрамп гии , тд' , то группа гоптеииевДс.Ъ) будет важнее критерия I с параметрами . » ■ы* + Ъ3>': ■

если коитешк V важнее критерия ^ с параметрами Тл1с , , то га;шсх: положение сохранится для любо* пары параметров , и •' , такпх. что > ЪЛ* , ы; < .

р.

- В -

В §2 также вводятся аетивно используемые далее определения коэффициентов относительной важности. _ I

Определение. Пусть А, fc> ^ 1 . А у , Ь -ф- / , А Г\ Р> , и группа критериев А важнее группы критериев 2>

с наборами параметров и* V L£ А и оо? V j fc Г> . Положительное число

- ^ ^ А % ¡< Р,

с

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

А и Ь .

Очевидно,

О < < + оо ; С' <. < А ; • = 4 I-j - V .

Оказывается, возможна ситуашя, когда г. -й критер!й важнее j -го, a j -й, в свои очередь, важнее 1-го критерия. Дасазано, что при определенных условиях необходимым условием подобной штуащи является выполнение неравенства < \ , которое в термшах нормировании!

коэффициентов относительной важнооти принимает вид Оц ■t'j,. < V^ •

В §3 напоминается, что конуоная многокритериальная задача содержит множество возможных решений X , ^ -мерный векторный критерий заданный по крайней мере на jv и конус дшинирования Сеа

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

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

Определение. Две конусные многокритериальные задачи (X И (X, о , Кн), rue 3 =

называются эквивалентными, золи jug

CV^c л'^Х] ^-'') е Кк)(fx)-К

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

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

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

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

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

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

на стандартно!! многокритериальной задаче (3\, С^, , в которой

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

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

Теорема. Конусная многокритерпальная_задача, представляющая собой стандартную многокритериальную задачу О4 -Л , с дополнительной информацией о тем, что критерий I важнее критерия ^ с нормированным коэффициентом Рц и критерий I важнее критерия I с нормированным коэффициент см , эквивалентна стандартной многокритериальна задаче СХ, ь которой

Б-6а- и + и-е^- + и- 0«ч\ и ,

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

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

-I- с нормированным коэффициентом , эквивалентна стандартней

многокритериальной задаче ^ 1 в которой

й, Л, \/й€:1ч НД .

I

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

Теорема. Пусть А^Ь С I , А ^ ^ , {Ь ^ ^ , АаЬ •= $ . Конусная многокритериальная задача, предотавдяв щая собой стандартную многокритериальную задачу (Х^ % р!4) о дополнительной информацией о тем, что груша критериев А важнее 1рушш критериев & о нормированными коаф&ишентами относительной важности , эквивалентна стандартной многокритериальной задаче (ЗС.^ с 4 ) . в которой ^ - ^-мерная вектор-функшя, составленная из тех компонент ' , Для которых 1е ХХЕЬ , а также компонент = ^И^^УЬ^^- причем +

сх^А-'согсГЬ' а 4

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

аа.гЛ А = 1 001 & ~ ^ ~ ^ '^^ЗГ 1

Например, при гч. 1С, cord Л -= слгс] &> 5", получаем = 'ЭаО , т.е. учет информации о том, что половика из десяти критериев важнее другой половины приводит к троекратному увеличении критериев.

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

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

^xtt^uC-CVio^] .

Тот факт, что группа кттеряев А важнее т^ушш критериев мсино записать в виде aPv или U.-V в к , где VC - конуо дсминирования данного отношения предпочтения Р , причем вектор

U — \J S имеет положительные компоненты, соответствушие ин-

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

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

3 for ul-v,4 jsT; ^ . СЗ)

Определение, набор информаши (3) будем называть непротиворечивым, если существует по крайней мере одно такое асимметричное, транзитивное и инвариантное относительно положительного линейного преобразования отношение Р , удовлетворяющее аксиэме Парето, для которого верно u^P . I— .., .

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

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

. + • • • + >" wv^Vv

— ^ ^= о, - ,

С ъ ъ с ^ А>3

^ ~ о , , с^ ,

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

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

Теорема, пусть ^ С! _ произвольный острый выпуклый ко-

нус доминирования, не содержащий начало координат и такой, что К ИЗ , К ^ . Для любого >-0 существует такой конечный набор пар векторов

и", чЛ е ЙГ> и1- V'1 в ГЬ К П\ГД 0^ , , = А Д , -•., ^ >

что

С К ПХГгСО^ ^ елже «.. ., ^-^ПиДО^) )< е,

»

\

• • • >

тле \ГгСО^= (»^(¡П < г} , -

единичные орты пространства , а «Цг/ЬСА^ВЛ означает хауо-

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

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

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

- п -

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

В §6 после краткого изложения начальных понятий теерии нечетких множеств, предложенной Л.Заде, для исходной модели, в которой отношение строгого предпочтения р* является нечетким асимметричным отношением с функцией принадлежности ^С'^ , формулщу пгся определения относительной важности и равноценности критериев. Прш едем первое

Определение. Пусть А, ЕЬ ^ X , !\ Ф ф , 9^ ф р , А ^ Сэ =■ р*. Будем говорить, что группа критериев А важнее группы критериев Ъ с заданными положительными парметрами -иЯ« V Се А и И степенью уверенности если

1\ САи&О

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

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

V & е 1 \ А

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

Т е о р е м а. Функция плинадлежности ^ нечетгого отношения предпочтения указанного класса в нечеткой конусной мнэгокритериальнсй

- м _

задаче, представляющей собс;1 стандартную многокритериальную) задачу с нечеткой ин+ошаше!» о таи, что группа критериев А важнее группы критериев Ь с нормированными коэффициентами относительной ва»ноо-ти и степенью уверенности ^ ^ ^с. 11 ггпедставима п вида

( 4 , если ^ ~ У)'' £ ,

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

при всех ^^ . где ^ =• го- сшс11Ъ-* илЛ А -сиМ Р, в у

р-мерный вектор, первые ксшшент которого суть

и. и - и .г, • а остальные ксмпоненты вида (Л-9'Л-

■ ч; \ЛеА , VIе £> • Удалее, как и в четком случае, изучается непротиворечивость и существенность конечного набора нечеткой информации об относительной важности критериев; Формулируются соответствующие результаты.

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

Прежде чем перейти к обсуждению результатов последующих гаев, отметим следующее. В работе В.В.Подиновского и О .Р .Меньшиковой (ГО.1 и МФ, 1988, т. 29, уже имеется определение относительной валкости для двух групп критериев, которое в случае Е- -=Й. , р1 = (_>) для вила (I) и асишетричного инвариантного относительно полсяительного линейного преобразования отношения предпочтения эквивалентно общему определению из §1, хотя АЬункшй , на Сазе которых в рамках раз-

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

[

- -

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

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

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

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

KD0MeY" су С N'b Э Y) ,

В втоосй гаавы обе опенки строятся для случая двух критериев при условии, что отношение строгого предпочтения Р удовлетворяет требованиям иррефлексивности, парето-сптимальности, слабой транзитивности '('а.г^Р'З "зсР^) и инвариантности относительно поло-

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

Для транзитивного отношения предпочтения установлено, что искомая опенка сверху монет быть построена в виде множества парето-оптимальных решений относительно некоторой двумерной линейной вектор-Функции, коэффициенты которсЯ определяются вектсгоами u.\ v1" из (Я). Если же указанное отнспение не является транзитивным, то оценка сверху предс-тавляетсобсй множество точек одновременного максимума некоторых двух линейных Функций на множестве

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

Р ?- , ни г Р^

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

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

=> не выполнено ни

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

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

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

Искомая опенка сверху огошгая как мнотеотво

.м

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

Теорема. Пусть ^ ^ у . Соотношение тс ч- ^ имеет

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

^ и. ^ .....

где

О.

\ , если и ^ О , - \ , если а < о •

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

линейного программирования специального вида.

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

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

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

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

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

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

ет место топш и только тогда,когда для каждого ¡. = А,!,...^ р в задаче линейного програширования

—аСГ--Г ц...^,

.....^ , ■>• - С',

где р, оптимальное значение

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

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

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

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

EU^^feST: uWfc/, -I,i..... (4)

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

( А - ОлЫ.эЛ , если-xeY, , 4 KVW = < yfY > (5)

* ^ П, в тгоотивнсм случае.

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

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

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

(К^гЛ ^ vn^C^O V=c е Р.**. Петзейдем к списанию искомой оценки сверху и для удобства через

f4«, • > , • , _____

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

■■■< -f^ 4 А,

V SAH't = t- * 1 ¿U , < Че 4

Через , обозначим четкий пояиэлтальннй вы-

пуклый конус, порожденный векторами -v1- , у катодах соответствующие числа таковы, что jU- $ . Очевидно,

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

. если (Яо1-> сКЗ 'Л: ^ -ма* и, \ ^А ь 1 > в противном случае;

и через обозначим функшю принадлежности нечеткого конусного

отношения с кснуссм ^ , не вкллчашим начало координат в свой сушорт. Таким образом, ^Дре^сг сОСЯ-'-^р для всех

Будем считать, что конус не содержит ни один вектор ц> ,

такой, что (Ч < (¡Чуц • ____в противнем случае информация

вида является противоречивей). Имеет место следующая

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

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

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

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

Задачу максимизаши векторного критерия 4 = .. ) на

множестве "К С (С^ будем называть исходной задачей векторной максимизаши (кратко: ЭВМ4). ^

Определение. Пусть \ I \ г, - совокупность всех экви-

валенткых векторных критериев (в смысле определения, данного в пер-вей главы)в исходной ЗШ, а Из означает число компонент векгоо-^ун-

_ С (.и) ' _

кши ^ . натуральное число , определяемой равенством

со о = Уил^. ио

назовем критериальной размерностью ЗВМ и будем обозначать через

Ai^iAJО .

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

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

Теорема. Ясли » то в множестве НХЛ суще-

ствует такое конечное подмножество -VCX^ . что \ "4>v •

Теорема. Пусть множеотво образов конечно. Если

cILvm.C-Ç^X) — 2L , то задача вычисления критериальной размерности является полиномиально слокнсй. В случае cALvh-C^-sIC^ 51 эта задача /Г - полна.

Теорема. Пусть cord ~ • Тогла

^ , tv.V

ралее рассмотрение огоагагчивается случаем линейных ^ушший -I L 4 \ - и конечного множества образов. Показывается, что при

числе переменных ^ X критериальная размерность ЯЗ.' но превышает 2. При n_> имеет место

Т е о р е м а. Для любого натурального t ^ Ъ существует мксжест-во ЗСс- соотояшее из 3.L элементов, и линейны!1, векторный

критерий X , такие, что ^ .

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

Нижесяедуюпий результат устанавливает, что опенка еА^л^^У.^} имевшая место в силу неравенства (6 \ является точной в классе линейных векторных критериев, заданных на булевда кубе.

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

вектор-пункция ^ , для которой выполнено равенство йГ""1.

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

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

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

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

ным, г е ( 4Д,,., О^Ъ в З&Л с векторной Яункцией на множестве X . если этот элемент является парето-оптимальным относительно каждой г -мерной вектор-Фунтоии, составленной из компонент вектор-Функции £

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

При реализации г -оптимального выбора немалое теоретическое и практическое значение имеет вопрос существования Г-оптимальных теяек при различных значениях параметра г .в общей постановке вопрос существования представляется чрезвычайно громоздким из-за специфического "комбинаторного" определения Г -оптимальной точки. В §2 приведены результаты численного исследования существования Г -оптимальных точек, получега&е с псы адью программы, написанной на языке ФОРТРАН и пометенной в Приложении 4. Рассмотрен класс ЗШ с конечным множеством элементов, Содержащим ?.,ч,<1,5,6,7,В,р, 10,15,20,40,40,50 точек. Пои этот число критериев варьировалось от 3 ло 10. элементы допустимого множества генерировались случайным образом по закону равномерного распределения. Выяснилось, что вероятность суиествоваяия

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

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

Кпше того, в §2 установлена

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные результаты диссертации опубликованы в работах £ \ — 3 .

J! ятература

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

2. Ноган В.Л. и дп. Основы теории оптимизацииU.: Высшая школа, 198Б. Я. Ноган В.JJ. Ошнки для мнеяеетва оптимальных решений в условиях

отношения предпочтения, инвариантного относительно положительного линейного преобразования.//Принятие решений в условиях неопределенности. Тезисы докл. ТТ Всессвзн. семинара по исследованию операций и системному анализу.- м.-Батуми, I5B3, с. 37.

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

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

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

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

с. 5F-60.

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

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

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

Jfoftkl* Vt>. Oiv -tke cxderuA d^e^ion. o{ vector ojsk-

problem. //Ma4\I. - tVory

/W\tcakoviS .Trovvs. XIV "Lvkrv\ . Сок-\. - watV > G-Ъ^,

ьь. W--VS0. iToqWl* \f\Vb. EsU^akcm c44V bd oX uoucb^uvo+ed SoWVcowS //J4ruwi€rLca\ Fuv«^Co*\a\ Апо\уь,ч awA OpUwliK*-W, v.U, -5-6, 5o*-SAS.

,, ЯооЧич V.-Ь. EsVtvaaW oi We W/ ^ vwwdo^mW

MWi«,- Ш^го Ш^ра-гь, 4/, iToqW-w V/.tv Cm-VW VWOу oV MaV'we Iv^orWce o-\ cr^i.V

ov, CWuW % W AtyUAUaVte-

(5- JWhlu Vbter ^UacxW V>r О W??y <A wowdowwM*-3o\uko^./7 Schawl ^'

4 6 kwWiw V,l>.TV\to»7 «Ц reWVwe O^orVawcr <4 erv^tCa: « lowfcWWsA VteorevA • f/ ct-cWa ^toUews.

и«Дег Ж OrcfcWc-

■г^емо, > 6S.

w.fos., A.

Зек. I33y. - 95.