Диссертация (Алгоритмы сужения множества Парето на основе информации о предпочтениях ЛПР)

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙУНИВЕРСИТЕТНа правах рукописиБасков Олег ВладимировичАЛГОРИТМЫ СУЖЕНИЯ МНОЖЕСТВА ПАРЕТОНА ОСНОВЕ ИНФОРМАЦИИ О ПРЕДПОЧТЕНИЯХ ЛПР05.13.01 — системный анализ, управление и обработка информации(по прикладной математике и процессам управления)Диссертация на соискание учёной степеникандидата физико-математических наукНаучный руководительдоктор физико-математических наук,профессор В. Д. НогинСанкт-Петербург2014ОглавлениеВведение41 Случай чёткого отношения предпочтения ЛПР1.1 Основные определения .

. . . . . . . . . . . . . . . . . . . . . .1.2 Задача многокритериального выбора . . . . . . . . . . . . . .1.3 Известные результаты . . . . . . . . . . . . . . . . . . . . . . .1.4 Последовательный учёт набора «квантов» информации . . . .1.5 Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.6 Последовательный алгоритм учёта набора «квантов» информации . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.7 Нахождение образующих двойственного конуса . . . . . . . . .1.8 Исключение лишних критериев . . . . . . . . . . . . . . . . . .2 Случай нечёткого отношения предпочтения ЛПР2.1 Нечёткие множества . . . . . . . . .

. . . . . . . . . . . .2.2 Нечёткие конические оболочки . . . . . . . . . . . . . . .2.3 Нечёткие двойственные конусы . . . . . . . . . . . . . . .2.4 Построение образующих нечёткого двойственного конуса2.5 Задача сужения множества Парето . .

. . . . . . . . . . .2.6 Учёт «квантов» нечёткой информации . . . . . . . . . . ........................151618202126. 27. 28. 31......343535394554563 Программная реализация: пакет ParSetRe633.1 Решение задачи многокритериального выбора . . . . . . . . . . 633.2 Структура программы . . . . . . . . . . . . . . . . . .

. . . . . . 664 Прикладная экономическая задача724.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . 7224.2 Сужение множества Парето . . . . . . . . . . . . . . . . . . . . . 73Заключение773ВведениеЗадачи принятия решений встречаются гораздо чаще, чем мы о них задумываемся. В повседневной жизни при выборе из группы товаров, представленных в магазине, часто необходимо сравнить несколько характеристик, среди которых, к примеру, могут быть цена товара и его качество.

При ведениибизнеса нередко встречаются ситуации, в которых необходимо принятие важного стратегического решения, от которого зависит будущее предприятия, егосотрудников, но которое непременно сопряжено с определёнными рисками изатратами. Ситуаций, в которых требуется произвести выбор, неисчислимомного. И каждый выбор по своей природе многокритериален, поскольку человек склонен рассматривать и оценивать варианты с разных сторон.Многие авторы сходятся в том, что выбираемый вариант следует искатьво множестве Парето. Однако до сих пор нерешённой остаётся проблема собственно выбора варианта из этого множества. Зачастую непосредственныйвыбор из него затруднителен, поскольку множество Парето достаточно широкое. Существуют подходы, которые предлагают способ нахождения «наилучшего» парето-оптимального решения, однако в их основе лежат некоторые эвристики.

Поэтому актуальным представляется развитие аксиоматического подхода, в котором вместо навязывания лицу, принимающему решение(ЛПР), какого-либо варианта производится сужение множества Парето, т. е.сужение области поиска «наилучшего» решения.Выделяют три основных вида задач принятия решения [18]. Первый вид —задача упорядочивания альтернатив. В ней на множестве имеющихся вариантов следует ввести отношение порядка. Примером такой задачи являетсяопределение степени необходимости каких-либо покупок.

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

Именно этому виду задачпосвящена данная работа.Следует также упомянуть о теории группового многокритериального выбора, где рассматривается целая группа лиц, принимающих решение, каждый член которой может иметь свои собственные предпочтения и оценки вариантов. Основной проблемой здесь является агрегирование коллективныхпредпочтений для упорядочивания альтернатив или выделения наилучшегорешения [31].Модель задачи выбора может строиться по-разному. В общей постановкевводится множество всех допустимых вариантов X и изучаются свойства различных функций выбора C(X), определённых для всех подмножеств X множества X .

Значением функции выбора C(X) является множество вариантов,выбираемых из X, так что C(X) ⊆ X. В книге [1] выделяются и исследуются различные классы функций выбора, например, класс многокритериально-экстремизационных функций выбора, которые порождаются числовымивекторными критериями, заданными на множестве вариантов.В данной работе рассматривается более узкая постановка задачи принятия решения. А именно, исследуется задача многокритериального выбора,характеризуемая двумя центральными объектами: множеством возможныхвариантов X, содержащим все доступные альтернативы, и числовым векторным критерием f , описывающим цели ЛПР.

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

Впервые её исследовал английский экономист Ф. И. Эджворт [36] в случае двухкритериев. Он предложил определение кривой безразличия, обобщающее по5нятие экстремума скалярной функции. Позднее случай произвольного числакритериев был рассмотрен В. Парето [43]. Он ввёл понятие оптимальности,которое впоследствии стали называть его именем.

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

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

В то же время существуют методы, которые могут предложить решение за пределами множестваПарето.Впервые класс задач, в которых применим принцип Эджворта — Парето,был исследован в статье [24] В. Д. Ногиным. Им предложены три аксиомы, которые моделируют рациональное поведение ЛПР.

При их выполнении можнодоказать, что множество выбираемых решений действительно должно содержаться во множестве Парето. Однако если хотя бы одна аксиома нарушается,применение принципа Эджворта — Парето рискованно и недопустимо [24,25].К настоящему времени разработано и реализовано множество подходов крешению задачи принятия решения при многих критериях. Среди них можно выделить следующие группы: методы многокритериальной теории полезности (MAUT — Multiattribute Utility Theory) [14, 18, 21, 31, 38]; «outrankingapproaches» [18, 21, 31, 38, 45, 48]; методы вербального анализа решений [16–18, 31, 38]; итеративные процедуры принятия решений [18, 21, 31, 38]; аксиома6тический подход к сужению множества Парето [2–13, 15, 26–30], к которомуотносится и данная работа.Методы MAUT основаны на теории ожидаемой полезности Неймана иМоргенштерна [23].

Ключевым понятием здесь является лотерея, которуюсоставляют альтернативы со своими вероятностями наступления. Постулируется несколько аксиом, при выполнении которых поведение ЛПР называют«рациональным» и его предпочтения могут быть выражены в виде аддитивной функции полезности (теорема Неймана — Моргенштерна), т. е. каждомуварианту можно сопоставить число так, что варианты с большими значениями функции полезности предпочитаются вариантам с меньшими значениями.Таким образом можно проранжировать все варианты и выбрать наилучший,которому соответствует максимальная полезность.На многокритериальный случай эту теорию обобщили Кини и Райф [14].Они предложили сначала строить функцию полезности для каждого критерия по отдельности, а затем агрегировать их в общую функцию полезности.Добавив аксиомы независимости по полезности и по предпочтению, они доказали существование многомерной функции полезности, заданной на множестве возможных вариантов и имеющей либо мультипликативную, либо аддитивную форму.

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