Содержание к диссертации
Введение
1 Случай чёткого отношения предпочтения ЛПР 15
1.1 Основные определения 16
1.2 Задача многокритериального выбора 18
1.3 Известные результаты 20
1.4 Последовательный учёт набора «квантов» информации 21
1.6 Последовательный алгоритм учёта набора «квантов» информа
1.7 Нахождение образующих двойственного конуса 28
1.8 Исключение лишних критериев 31
Случай нечёткого отношения предпочтения ЛПР 34
2.1 Нечёткие множества 35
2.2 Нечёткие конические оболочки 35
2.3 Нечёткие двойственные конусы 39
2.4 Построение образующих нечёткого двойственного конуса 45
2.5 Задача сужения множества Парето 54
2.6 Учёт «квантов» нечёткой информации 56
3 Программная реализация: пакет ParSetRe 63
3.1 Решение задачи многокритериального выбора 63
3.2 Структура программы 66
4 Прикладная экономическая задача 72
4.1 Постановка задачи 72
4.2 Сужение множества Парето 73
Заключение
- Известные результаты
- Последовательный алгоритм учёта набора «квантов» информа
- Нечёткие двойственные конусы
- Структура программы
Известные результаты
Оказывается, что если задано более одного «кванта», можно выбрать любой из них, применить базовую теорему, определённым образом преобразовать оставшиеся кванты и получить задачу учёта «квантов», количество которых на единицу меньше. Так появляется последовательный алгоритм учёта информации об отношении предпочтения. В случае нескольких «квантов» возникает вопрос о непротиворечивости предоставляемой информации. Он также решается данным алгоритмом по ходу работы. Далее для наглядности приведён пример его использования. На этом же примере показано, что прямолинейное применение такого подхода может приводить к появлению избыточных критериев. Так возникает вопрос об их удалении. Для этого рассматривается взаимосвязь между задачей учёта информации об отношении предпочтения и задачей нахождения образующих двойственного конуса. Бла годаря ей удаётся получить необходимое и достаточное условие того, что критерий не является лишним, которое приведено в последнем параграфе.
Напомним определения основных понятий выпуклой геометрии, которыми в дальнейшем будем активно пользоваться.
Очевидно, что выпуклая коническая оболочка конечного числа векторов а1,..., ар Є Жт может быть представлена как в силу того, что векторы, не участвующие в сумме, гарантированной определением 1.3, можно добавить с нулевыми коэффициентами.
Модно доказать, что это множество действительно является конусом, и притом выпуклым. Определение 1.10. Бинарное отношение -С Ш.т х М.т называется конусным, если существует конус К С Мт: Ух, у Є Мт х - у х — J/GK. 1.2 Задача многокритериального выбора Пусть имеется множество вариантов произвольной природы X. ЛПР может оценить каждый вариант по нескольким числовым критериям /і,..., fm. Таким образом, можно считать, что задано отображение /:Хи Шт:
Будем предполагать, что отображение / инъективно, т. е. если для двух вариантов ж, у Є X верно f(x) = fiy), что означает, что у этих вариантов одинаковые оценки по всем критериям, то эти варианты равнозначны для лица, принимающего решение: х = у. Пусть, кроме того, ЛПР может непосредственно сравнивать пары вариантов. Для учёта этого введём отношение предпочтения ) ХС X х X: х -х у означает, что из этих двух вариантов ЛПР выбирает ж и не выбирает у. Таким образом, модель задачи принятия решения включает в себя три объекта (X, /, -х).
Сразу оговоримся, что отношение предпочтения известно лишь частично, т. к. зачастую сравнение всех пар вариантов не представляется возможным. Кроме того, возможна ситуация, когда не выполняется ни одно из соотношений х -х у и у -х ж, т. е. это отношение неполное.
Образ множества возможных вариантов Y = /(X) будем называть множеством возможных векторов. На нём индуцируется отношение предпочтения -: х -х х" = f(x ) - f(x").
Для удобства вводится обозначение P/(Y) = /(Р/(Х)). Задача принятия решения состоит в отыскании множества выбираемых вариантов С(Х) С X, включающего в себя все выбираемые ЛПР из X альтернативы, и только их. Формальное определение этому множеству не даётся, так как оно сразу определило бы поведение ЛПР в процессе выбора, и ЛПР, желая применить такую теорию, должен был бы познакомиться с определением, понять его и полностью согласиться. В случае несогласия теория оказалась бы неприменимой, и пришлось бы искать либо другое определение, либо другой подход.
В принятом в данной работе подходе ЛПР может осуществлять выбор в соответствии со своими индивидуальными вкусами и предпочтениями. Теория позволяет лишь сузить круг поиска выбираемых вариантов, т. е. построить оценку сверху на множество С(Х), в случае, если поведение ЛПР удовлетворяет четырём аксиомам «разумного выбора».
Аксиома продолжимости. Существует транзитивное иррефлексив-ное продолжение т отношения - на пространство Жт. Аксиома согласованности.
Аксиома инвариантности. У а 0, Vc, у , у" Є Pm: у У- у" = ау + с ау" + с. Отметим, что в силу транзитивности т аксиому согласованности можно заменить эквивалентным утверждением: Уу ,у" Є Pm: у у" = у У- у". Готовность ЛПР идти на компромисс, т. е. соглашаться на некоторые потери по одним критериям ради получения выгоды по другим, формализуется следующим понятием.
Определение 1.11. Вектор и Є Pm задаёт «квант» информации об отношении предпочтения ЛПР, если он имеет хотя бы одну положительную и хотя бы одну отрицательную компоненты ии)-0.
Отрицательные компоненты соответствуют тем критериям, по которым ЛПР готово пойти на уступки. Абсолютные величины этих компонент показывают наибольший приемлемый размер уступок. Положительные компоненты показывают наименьший прирост по тем критериям, ради повышения оценок по которым которых ЛПР идёт на компромисс.
ЛПР может предоставить информацию в виде нескольких «квантов». В таком случае необходимо убедиться, что этот набор не нарушает принятых аксиом.
Определение 1.12. Набор «квантов» и1}...}ир непротиворечив, если существует отношение -т, удовлетворяющее аксиомам разумного выбора, при котором верны соотношения и1 - 0, ..., ир - 0.
Первые три аксиомы позволяют доказать принцип Эджворта - Парето. Теорема 1.2 [27]. Каким бы ни было множество выбираемых вариантов С(Х), справедливо С(Х) С Ру(Х).
Он даёт исходную оценку сверху на множество выбираемых вариантов, которую в дальнейшем можно сужать с использованием «квантов» информации об отношении предпочтения. Для учёта одного кванта применяется следующий результат. Теорема 1.3 [27]. Пусть вектор и Є Ш171 является «квантом» информации об отношении предпочтения ЛПР. Тогда каким бы ни было множество выбираемых вариантов С(Х),
Последовательный алгоритм учёта набора «квантов» информа
Перейдём теперь к обобщению задачи учёта информации об отношении предпочтения на нечёткий случай. Это позволит моделировать ситуации, в которых ЛПР может быть не вполне убеждён в готовности к определённым компромиссам. С каждым «квантом» информации ассоциируется степень уверенности ЛПР в нём. Математически они представляют собой степени принадлежности нечёткому конусу, содержащемуся в конусе отношения предпочтения. Естественным образом оценка множества выбираемых вариантов также оказывается нечёткой.
В начале этой главы напоминаются основные определения теории нечётких множеств. Затем рассматриваются нечёткие конические оболочки и вводится понятие нечёткого двойственного конуса. Несколько утверждений посвящено описанию свойств этих объектов. Обобщается и алгоритм нахождения образующих двойственного конуса вместе с критерием их избыточности.
Следующий параграф содержит математическую постановку задачи учёта «квантов» нечёткой информации. Приведены обобщения аксиом на нечёткий случай. Завершает главу описание применения алгоритма нахождения образующих нечёткого двойственного конуса для учёта «квантов» и проверки их непротиворечивости
Напомним основные определения из теории нечётких множеств. Определение 2.1 [47]. Нечёткое множество А — множество объектов из некоторого универсального множества X с ассоциированной функцией принадлежности А{%) [0;1]. Для удобства в качестве обозначения нечёткого множества будем использовать и символ его функции принадлежности: ЛА. Определение 2.2 [47]. Нечёткое множество А является выпуклым, если Ух, у Є Mm, У а 0 = \&(ах + (1 — а)у) min {ЛА(Ж); ХА{У)} Определение 2.3 [41]. Замыканием нечёткого множества А называется нечёткое множество сі А с функцией принадлежности
Очевидно, всякое множество является подмножеством своего замыкания. Множество, совпадающее со своим замыканием, называется замкнутым.
Определение 2.4 [37]. Нечёткое множество А называется нечётким конусом, если его функция принадлежности удовлетворяет условию
Перейдём теперь к понятиям, определения которых ещё не часто встречаются в литературе. По аналогии с чётким случаем, нам будет удобно задавать нечёткие конусы с помощью образующих. Следовательно, необходимо обобщить определение конической оболочки.
Определение 2.5 [4]. Нечёткая коническая оболочка конечного числа векторов а1,..., aq Є М.т со степенями уверенности а1,..., aq Є [0; 1] — нечёт кое множество с функцией принадлежности
Максимум и минимум существуют, потому что различных ак конечное число. Минимум по пустому множеству считается равным 1; максимум по пустому множеству — 0. где (п) — ссылка на рассматриваемое представление вектора ж, которая будет опускаться, если понятно, о каком представлении идёт речь. Так, для і = l,q будем подразумевать представление аг = аг и писать gradeAa = а, а для нулевого вектора gradeA0 = 1. Из определения 2.5 следует, что Л(а ) gradeAa .
Введём также обозначение для множества представлений, на которых достигается максимум в определении 2.5: Покажем корректность этого определения. Утверждение 2.1. Нечёткая коническая оболочка конечного числа векторов является выпуклым нечётким конусом. Доказательство. В обозначениях определения 2.5 возьмём векторы ж, у и покажем, что для У а Є (0; 1) имеет место неравенство Х(ах + (1 — а)у) тіп{А(ж); А (у)}. Возьмём соответствующие представления векторов х и у из
Для доказательства того, что нечёткая коническая оболочка является конусом, рассмотрим произвольный вектор х и число а 0. Очевидно, gradeAa:r = gradeA:r для представлений этих векторов, отличающихся лишь множителем а. Но тогда и Х(ах) = Х(х). В некоторых случаях удобнее пользоваться следующим определением. Определение 2.6 [4]. Нечёткая коническая оболочка конечного числа векторов а1,... , aq Є М.т со степенями уверенности а1,..., aq: 1 = а0 а1 а2 ... aq 0 — нечёткое множество с функцией принадлежности
Максимум по пустому множеству считается равным 0, а коническая оболочка пустого множества векторов — {0}.
Доказательство. Рассмотрим векторы а1,..., aq со степенями уверенности а:1,..., aq: 1 а1 а2 ... aq 0. Пусть Х\(х) — функция принадлежности нечёткой конической оболочки этих векторов с соответствующими степенями принадлежности из определения 2.5, а \2{х) — из определения 2.6. Возьмём произвольный вектор х Є М.т. Если х cone {a1,..., а9}, то в обоих определениях максимум берётся по пустому множеству, и, следовательно, Xi(x) = \2{х) = 0.
Нечёткие двойственные конусы
Таким образом, алгоритм построения образующих нечёткого конуса, двойственного к нечёткой конической оболочке векторов е1,..., em, it1,... , ир со степенями принадлежности 1,..., 1, г/1,... , vv выглядит следующим образом. Алгоритм 2. Работа алгоритма начинается с образующих неотрицательного ортанта: Ь1 = е1, ..., Ьт = ет с единичными степенями принадлежности /З1 = = /Зт = 1.
На шаге s к исходному конусу добавляется образующая иа со степенью принадлежности Vs. В соответствии с утверждениями 2.10 и 2.11 образующие Ъг разбиваются на три группы: А = {i \usb% О}, В = jj \usV О}, С = \к \usbk = О}. Сначала добавляются новые образующие вида IP = (и3Ъг)Ъ — (и3Ъ )Ъг со степенями принадлежности min {/З ; /З-7} для V(i,j) Є А х В. Затем у всех образующих ty, j Є В степень принадлежности полагается равной min {/З-7; 1 — z/sj. Если vs = 1, то образующие этой группы просто удаляются. Построенные образующие переобозначаются за б1,... , brjs со степенями принадлежности /З1,..., /3qs. В завершение шага для каждой образующей Ьк строится множество T(bk) = {е \егЬк = 0} UJit \игЬк = 0, z/ + /Зк 1, г s}. По утверждению 2.13 те образующие Ьк, для которых 3/ ф к: /З1 /Зк, T(bl) 1Э T(bk), удаляются как несущественные.
В результате работы алгоритма получаются векторы Ь1,..., ЬЧр со степенями принадлежности /З1,... ,/3qp, нечёткая коническая оболочка которых двойственна к нечёткой конической оболочке векторов е1,... , em, it1,... , ир со степенями принадлежности 1,..., 1, г/1,..., vv. 2.5 Задача сужения множества Парето
Пусть X — множество возможных вариантов, т. е. объектов произвольной природы, из которых лицу, принимающему решение (ЛПР), необходимо выбрать один или несколько. Каждый вариант оценивается по нескольким числовым критериям /i,...,/m, которые можно объединить в векторный критерий / :1н Ш.т. Наконец, при выборе ЛПР может руководствоваться индивидуальными вкусами и предпочтениями, которые моделируются нечётким бинарным отношением предпочтения -х с функцией принадлежности /ІХ: считают, что /ix(V, х") = /І, если, выбирая из этих двух вариантов, ЛПР отдаёт предпочтение х со степенью уверенности /І. Тройка (X, /, -х) определяет задачу (нечёткого) многокритериального выбора. Множество выбираемых вариантов будем обозначать через С(Х), а его функция принадлежности через к{х). Удобно также ввести множество возможных векторов Y = f(X) С Шт. Отношение предпочтения -х индуцирует на нём нечёткое отношение - с функцией принадлежности /i: fix(x ,x") = fiY(f(xf) f(xff)) для всех х ,х" Є X. Сразу оговоримся, что мы будем считать варианты с одинаковыми оценками неразличимыми, так что х ф х" Ф f(x ) ф f{x").
Будем предполагать выполненые четырёх аксиом разумного выбора [26]. Аксиома 1. я(х") 1 — /ІХ(Ж , Х") для всех х , х" Є X. Другими словами, ЛПР не будет выбирать , если существует более предпочтительный вариант . Аксиома 2. Существует иррефлексивное транзитивное продолжение -на пространство Жт нечёткого отношения -. Функцию принадлежности отношения - в этом параграфе будем обозначать /І. Аксиома 3. Отношение - согласовано с каждым из критериев /і,..., /m, т. е. для каждого индекса і, для любых двух векторов у и у" пространства Мт, все компоненты которых одинаковы, за исключением г-ой, причём у[ у", имеет место равенство fi(yf,yff) = 1. Таким образом, без умаления общности предполагается, что ЛПР заинтересовано в максимизации всех критериев. Аксиома 4. Нечёткое отношение - инвариантно относительно положительного линейного преобразования, т. е. fj,(ay + с,ау" + с) = fi(yf,yff) для всех с, у , у" Є Mm, а 0. Следствием этой аксиомы является свойство конусности отношения -: существует такой нечёткий конус с функцией принадлежности ту, что /І(у , у") = г)(у — у") для \/т/, у" Є Ш171.
Выполнение приведённых аксиом гарантирует [26], что множество выбираемых вариантов содержится в множестве Парето Р/(Х), т. е. имеет место неравенство к{х) тг/(ж) для всех вариантов ж Є X, где функция принадлежности множества Парето 7Г/(ж) принимает значение 1 в точках самого множества Парето, а во всех остальных точках она равна 0. Напомним, что множество Парето — это чёткое множество где символ обозначает отношение Парето: у у" в том и только в том случае, если по каждой компоненте у[ у / и хотя бы одно такое неравенство строгое. Другими словами, ЛПР может с самого начала исключить из рассмотрения варианты, которые можно «улучшить» по одному или нескольким критериям, при этом не ухудшая оценки по остальным критериям.
Однако во многих случаях оценка множества выбираемых вариантов в виде множества Парето является достаточно широкой. Поэтому актуальной задача сужения множества Парето на основе дополнительной информации об отношении предпочтения ЛПР.
Определение 2.11 [8]. Пусть и Є Ш171 — вектор, имеющий хотя бы одну положительную и хотя бы одну отрицательную компоненты. Если имеет место равенство /І(ІІ, 0) = z/, то говорят, что задан «квант» (нечёткой) информации об отношении предпочтения ЛПР.
Например, в случае двух критериев наличие «кванта» /І(ІІ, 0) = 1 при щ = 1, U2 = — 1 означает, что ЛПР готово уступить одну единицу по второму критерию ради повышения на единицу оценки по первому критерию, другими словами, первый критерий более значим для ЛПР, нежели второй.
Предположим, что задан набор «квантов» информации ц(ик,0) = ик, к = 1,р. Наша цель — сузить исходное множество Парето, используя данный набор «квантов». 2.6 Учёт «квантов» нечёткой информации
По аналогии с чётким случаем введём коническую оболочку «квантов» и ортов критериального пространства и покажем, как с её помощью получается оценка на множество выбираемых решений.
Утверждение 2.14. Пусть для к = 1,р векторы ик У 0 со степенями уверенности vk 0. Пусть А (ж) — функция принадлежности нечёткой конической оболочки векторов е1,... , em, it1,... , ир со степенями уверенности 1,... , 1, г/1,... , vv; а к(х) — функция принадлежности множества выбираемых векторов. Обозначим за Y С Жт множество возможных векторов.
Структура программы
Следует отметить, что добавление и удаление критериев может привести к перестройке внутренних структур данных ассоциированных с этим набором критериев вариантов и квантов, поэтому рекомендуется составить список критериев до начала работы со списками вариантов и квантов.
Класс Choices хранит возможные варианты в виде векторов, размерность которых равна количеству критериев. Класс Quanta содержит список квантов информации, которые можно будет использовать для сужения списка вариантов. Каждый квант — вектор той же размерности, что и вариант. Поэтому методы добавления, изменения и удаления вариантов и квантов вынесены в общий базовый класс FuzzyVectorList. Добавление векторов производится с помощью метода public void addVector (final double [] components, final Certainty certainty); Размерность компонент вектора должна совпадать с количеством критериев, в противном случае возбуждается IllegalArgumentException. При добавлении варианта второй параметр роли не играет: исходное множество возможных вариантов считается чётким. При добавлении же квантов этот параметр характеризует степень уверенности ЛПР в готовности пойти на компромисс, описываемый данным квантом.
Класс Certainty также используется для описания степени желательности выбора того или иного варианта после сужения множества Парето. С математической точки зрения он хранит степень принадлежности вектора тому или иному нечёткому множеству. Объекты этого класса неизменяемы: любые операции с ними возвращают новый объект. В классе предусмотрен конструктор public Certainty (final double value);
Параметр value должен иметь значение в сегменте [0;1], иначе выбрасывается исключение IllegalArgumentException. Предопределены константы Certainty.MINIMUM и Certainty.MAXIMUM для соответственно наименьшей и наибольшей степеней уверенности. Для удаления вектора класс FuzzyVectorList предусматривает метод public void removeVector (final int vector); Параметром является индекс удаляемого вектора в этом списке. Для изменения векторов используются методы public void setComponent (final int vector , final int criterion , final double value); public void setCertainty (final int vector, final Certainty certainty); Здесь vector — индекс вектора в списке, criterion — номер критерия, компоненту по которому необходимо изменить, последний параметр — новое значение компоненты или степени уверенности. Упомянем, что предусмотрены методы и для чтения векторов: public double getComponent (final int vector, final int criterion); public Certainty getCertainty (final int vector);
Может возникнуть вопрос, почему степень уверенности хранится вместе с вектором несмотря на то, что она является характеристикой не вектора, а нечёткого множества. Такое решение было принято в связи с тем, что кванты по сути задают образующие нечёткого конуса, с которыми, если вспомнить определение 2.5, ассоциируются степени уверенности. Возможны ситуации, в которых один и тот же вектор используется в качестве образующей несколько раз, притом необязательно с одинаковыми степенями принадлежности. Если набор образующих считать конечным нечётким множеством, такие ситуации представить невозможно.
Рассмотрим теперь отличительные особенности классов Quanta и Choices. Так как учёт квантов приводит к перестройке векторного критерия, метод public FuzzyVectorList computeTransform (); возвращает список векторов, компоненты каждого из которых суть коэффициенты, с которыми надо суммировать исходные критерии, чтобы получить новый. При этом доминирование по такому критерию гарантирует варианту степень принадлежности не меньшую, чем степень уверенности, ассоциированную с этим новым критерием. С другой стороны, эти векторы являются образующими конуса, двойственного к нечёткой конической оболочке квантов и ортов критериального пространства. Если же набор квантов противоречив, метод возвращает null.
Так как расчёт образующих двойственного конуса — дорогая операция, её результаты кэшируются. Таким образом, реально этот метод производит рас чёт только в том случае, если набор квантов был изменён с момента предыдущего вызова. Полученный список векторов можно использовать для сужения набора вариантов с помощью метода класса Choice public void reduce (final FuzzyVectorList transform);
Он меняет степени принадлежности вариантов так, что они становятся оценками сверху на степени принадлежности множеству выбираемых вариантов. Все варианты, не входящие во множество Парето, получат нулевые степени принадлежности. Оценки остальных вариантов зависят от предоставленных квантов.
Графическая оболочка является простой надстройкой над описанным ядром, призванной предоставить пользователю удобный доступ ко всем возможностям ядра. Она выполнена в стиле MDI (Multiple Document Interface), т. е. пользователь имеет возможность работать одновременно с несколькими разными файлами.
Основное окно описывается классом FrameWindow. В нём могут располагаться фреймы ProblemWindow с отдельными задачами. Каждый такой фрейм содержит панель инструментов и четыре вкладки с информацией о задаче.
Первая вкладка — «Критерии» — отображает список критериев, хранящийся в классе Criteria. Вторая вкладка — «Кванты» — показывает список квантов информации из класса Quanta. Далее, третья вкладка — «Новые критерии» — отображает список векторов, возвращаемый методом computeTransform() класса Quanta, или сообщение о противоречивости квантов информации. Наконец, четвёртая вкладка — «Варианты» — отображает список вариантов из класса Chioces с оценками их степеней принадлежности множеству выбираемых решений.
Рассмотрим кнопки на панели инструментов окна задачи. Первые две отвечают за сохранение данных. Задачу можно сохранить в том файле, из которого она была открыта, а можно выбрать другой файл. Необходимость сохранения изменений показывается звёздочкой в заголовке окна задачи.
Следующие две кнопки позволяют добавлять варианты. Первая из них открывает диалог, в котором пользователю предлагается ввести оценки добавляемого варианта по всем имеющимся критериям. Вторая вставляет ва рианты из буфера обмена. Формат хранения данных в буфере совпадает с таковым для Excel, что позволяет легко переносить данные из электронной таблицы в ParSetRe и обратно.
Далее расположены кнопки для добавления квантов. Их поведение полностью аналогично таковому для кнопок, добавляющих варианты.
Затем следует кнопка сравнения пары критериев. Она открывает диалог, в котором пользователь может сравнить значимость двух критериев, ответив на вопрос, сколько он готов пожертвовать по одному критерию ради увеличения на единицу оценки по другому критерию. Это добавляет новый квант информации об отношении предпочтения.
Наконец, самая правая кнопка предназначена для сужения множества возможных вариантов. Она вычисляет оценки сверху на степени принадлежности вариантов множеству выбираемых решений.
