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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Захаров Алексей Олегович

ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ ЗАМКНУТОЙ ИНФОРМАЦИИ ОВ ОТНОШЕНИИ ПРЕДПОЧТЕНИЯ ЛПР

05.13.01 — Системный анализ, управление и обработка информации (по прикладной математике и процессам управления)

АВТОРЕФЕРАТ диссертации па соискание ученой степени кандидата физико-математических паук

1 - СКТ 2013

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

005535306

Работа выполнена па кафедре теории управления факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета.

доктор физико-математических наук, профессор Ногин Владимир Дмитриевич

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор технических паук, профессор Петровский Алексей Борисович (Институт системного анализа РАН, заведующий лабораторией методов и систем поддержки принятия решений)

кандидат физико-математических паук, доцеит Зенкевич Николай Анатольевич ("Санкт-Петербургский государственный университет, доцент кафедры математической теории игр и статистических решений)

Санкт-Петербургский институт информатики и автоматизации РАН (СПИИРАН)

Защита состоится 30 октября 2013 г. в 14 часов па заседании диссертационного совета Д.212.232.50 но защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский проспект, 35, ауд. 327.

С диссертацией можно ознакомиться в Научной библиотеке имени М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9. Автореферат размещен на сайте www.spbu.ru.

Автореферат разослан «2Ь 3 г.

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

Курбатова Г. И.

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

Актуальность темы исследования. Задачи многокритериального выбора встречаются в различных областях экономики, науки и техники, поскольку любой выбор многоаспектен по своей природе и человек (лицо, принимающее решение — ЛПР) рассматривает объекты с различных сторон. Однако, в силу данных обстоятельств такой выбор ещё и сложен, и без проведения дополнительных исследований обойтись практически невозможно.

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

В настоящее время существует достаточно большое число различных подходов и алгоритмов решения задачи многокритериального выбора в зависимости от имеющейся в распоряжении исследователя дополнительной информации о предпочтениях ЛПР. Большой вклад в эту область внесли отечественные и зарубежные исследователи: Ю. Б. Гермейер, О. И. Ларичев, А. В. Лотов, В. Д. Ногин, А. Б. Петровский, В. В. Подиновский, F. Y. Edgeworth, Р. С. Fishburn, R. L. Keeney, V. Pareto, Н. Raiffa, В. Roy, Т. L. Saaty, R. E. Steuer, P. L. Yu и многие другие. Существующие подходы можно классифицировать по следующим группам: методы многокритериальной теории полезности (Multiattribute Utility Theory), так называемые «outranking approach» (дословно «подход внешнего ранжирования»), методы вербального анализа решений, различные итеративные и диалоговые процедуры, а также аксиоматический подход к сужению множества Парето.

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

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

в модель «рационального» поведения ЛПР.

Предметом исследования являются задача многокритериального выбора, разработка методов её решения.

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

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

2. Определить условия на параметры замкнутой информации, при которых возможно её применение.

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

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

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

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

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

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

Апробация работы. Результаты, представленные в диссертации, докладывались на ХЬ, Х1Л, ХЫ1, ХЫУ международных научных конференциях аспирантов и студентов «Процессы управления и устойчивость» факультета ПМ-ПУ СПбГУ (Санкт-Петербург, 2009-2011, 2013), V Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск,

2012). Работа выполнена при поддержке Российского фонда фундаментальных исследований (проекты №№ 08-01-00301-а, 11-07-00449-а, 12-01-16034-моб_з _рос).

Публикации. Материалы диссертации опубликованы в 8-ми работах [1— 8], из которых 3 [1—3] являются статьями в журналах, входящих в Перечень ведущих рецензируемых научных журналов и изданий ВАК.

Структура и объём работы. Диссертация состоит из введения, шести глав, заключения и списка литературы, включающего 63 наименования. Работа содержит 8 рисунков. Объём составляет 122 страницы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приводятся основные термины и постановка задачи многокритериального выбора в соответствии с монографией Ногина В. Д. «Принятие решений в многокритериальной среде: количественный подход» (Изд. 2, испр. и доп. М.: Физматлит, 2005). В терминах решений задача многокритериального выбора < X, /, содержит три объекта:

• множество возможных решений X, X С Кп, из которого ЛПР необходимо

сделать выбор;

• числовой векторный критерий /: X —► К"1;

• асимметричное бинарное отношение строгого предпочтения >-х, заданное

па множестве X.

Возможна постановка задачи многокритериального выбора в терминах векторов < У, Она представлена множеством возможных векторов

(векторных оценок) У = /(X) и бинарным отношением предпочтения >-у, заданным па У.

Множество выбираемых решений обозначается С(Х) (множество выбираемых векторов — С (У)). Предполагаются выполненными четыре аксиомы «разумного» выбора (см. вышеуказанную монографию В. Д. Ногина).

Через I обозначается множество всех номеров критериев, т. е. I = {1,.. • ,т}. Пусть А,В С I, АП В = 0, назовём множества А к В

группами критериев.

Говорят, что задан «квант информации» об отношении предпочтения ЛПР с группами А и В и с положительными параметрами для всех г £ А, ш,- для всех ] 6 В} если для вектора у е Кт, такого что

Уг = щ, У] = -щ, Ув = 0 УгеА, У? € в, Уз € / \ (А и В),

справедливо соотношение у >- 0т. При этом группу критериев А называют более значимой, а группу В — менее значимой.

Во второй главе в качестве дополнительной информации об отношении предпочтения ЛПР вводится так называемая «замкнутая информация». Рассматривается подмножество множества номеров критериев С I, Ь = {ц, 12, ■■ ■, и}, к ^ 2, все элементы которого попарно различны.

Определение 1. ► Задание замкнутой информации об отношении предпочтения ЛПР с критериями ги ..., гк и с положительными параметрами и)Ц\ ..ии\кк~1], означает, что для векторов у(1>, у(2\ ... 2/М е Ет с компонентами

= уР = 0 У^ЛКг,};

(1)

= = 2/^ = 0 УзеТМг^}

справедливы соотношения у(1> >- 0т, у(2) >- 0т, ..., у№ >- 0т.

Другими словами, в соответствии с приведённым определением критерий ¿1 является более значимым, чем критерий ¿2 с положительными параметрами

^¡2 ^ критерий г2 — более значимым, чем критерий г3 с положительными (2) (2)

параметрами г^', ю\з' и т. д.; критерий гк — более значимым, чем критерий ¿1 с положительными параметрами ю^К

Введённая информация является взаимозависимой (см. вышеуказанную монографию В. Д. Ногина), поэтому может оказаться ситуация, когда она будет противоречивой. Пусть = Мт и(-К") и {0т}), т. е. Nm есть множество векторов пространства Ет, имеющих по крайней мере одну положительную компоненту и по крайней мере одну отрицательную. Очевидно, что вектор, фигурирующий в определении «кванта информации», принадлежит множеству Ыт.

Набор «квантов информации», заданный при помощи векторову^ е И™, г = 1, к, называется непротиворечивым (совместным), если существует хотя бы одно бинарное отношение >-', подчинённое аксиомам «разумного» выбора и такое, что выполняются соотношения у® у' 0т, г = 1, к. Пусть квадратная матрица ]¥ порядка к:

Ш =

/ Ч1} 0 . 0

(2) ад,- . 0

>2

0 0 .. (к-1) . и)) ' (к-1)

1 0 0 ..

0

(2)

В диссертации получен следующий критерий непротиворечивости замкнутой информации, введённой в определении 1.

Теорема 1 (критерий непротиворечивости). ► Пусть имеется замкнутая информация об отношении предпочтения с критериями гь ..., г'ь

Для того чтобы эта информация была непротиворечивой, необходимо и

достаточно, чтобы \\У\ > 0. -4 _ _

Введём семейство матриц з = 1,к, р = 1, к, в которых на месте в-го столбца 1V3 матрицы У/ стоит единичный вектор ер пространства Шк.

В работе доказана теорема о сужении множества Парето, показывающая каким образом строится верхняя оценка для множества выбираемых векторов на основе замкнутой информации, введённой в определении 1.

Теорема 2. ► Пусть выполнены аксиомы «разумного» выбора и имеется непротиворечивая замкнут,ая информация об отношении предпочтения ЛПР с критериями ц, ..., и с соответствующими положительными параметрами. Тогда для любого множества выбираемых векторов С(У) справедливы включения

С(У) с Р(У) С Р{У),

где Р{У) — образ множества парето-оптпималъных решений в задаче многокритериального выбора с множеством, возможных реикний X и векторным критерием д при отображении /, т. е. Р(У) = }{Рц{Х)), а компоненты «нового» т-м,ерного век торного критерия д определяются равенствами

к _

Д. = £ |И",р1/<р. 5 = 0г = п VI е 1\1ь < (з)

Р=1

При к = 3 (¿1 = г, г2 = Ч = I) формулы (3) примут следующий вид:

gi = + \Ww\f, + \Wu\fi = Ц'Ч^Л + «>,(2Ч(3)£ + Ц2)Ч!3)/ь

9! = \W2.i\fi + \Wta\fj + |^2,з|/, = Ц'Ч(3)Л + ч^Ч^Л + ч^Ч^Л.

91 = + IW3.iI/i + 1^3, з|Л = и£Ч(2)Л + ^Ч^/,' +

= Л V3е1\{ьЗ,1}.

Числовые примеры, приведённые в работе, демонстрируют, что в общем случае нельзя ответить на вопрос, насколько «новая» оценка Р(У) точнее исходной, т. е. множества Парето Р(У). Всё зависит от конкретного множества У и значений параметров замкнутой информации.

Третья глава посвящена обобщению результатов второй главы. Рассматривается замкнутая информация, в которой вместо критериев 1ъ...,гк используются группы критериев Ль ..., Ак.

Определение 2. ► Задание замкнут,ой информации об отношении предпочтения ЛПР с группами критериев АъА2,...,Ак и с набором по-

г (1) (1) (к-1) (*-1) (к) (к) _ I

ложителъных параметров ,..., и)^ , , ,и>и е К |

¿! е Аи---Ак € означает, что для векторов у(2),..., у(к) 6 Кт

вида

(i) = wa)

Vii

„,(2)

t, > Уг2 ' „

h

(1) = -t^, »ÍD = O Vil e AuVi2 6 4Vs€/\ (Al U A2);

(2) (2)

- 2/»2) = O V¿2 G A2, Vt3 € A3, Vs £ I \ (A2 U Аз);

(*) (i) v) — w- ', tk '

(*)

W¡, =

справедливы соотношения у 0т,у(2) >- 0т,... >- О, Матрица (2) обобщена на случай групп критериев:

= 0 Vi* е Л*, Vii € Ai, Ve € / \ (Лх U А»)

'm- ^

Ж(гь г2,.. -, г'*;) =

\

о

J2>

о о

(k-1) "Li ,л*-1)

со

где гр е Ар, р = 1, /с. Здесь И^, г2,..., г*) уже зависит от номеров критериев, т. е. образует целое семейство матриц.

Найдено необходимое и достаточное условие непротиворечивости замкнутой информации с группами критериев.

Теорема 3 (критерий непротиворечивости). ► Пусть имеется замкнутая информация с заданными группами критериев Аь А2,..., Ак. Для того чтобы данная информация была непротиворечивой, необходимо и достаточно, чтобы существовали такие номера гр е Ар, р = 1, к, при которых выполнено |И^(г1, г2,..., 4)1 > 0. -4

Рассматривается замкнутая информация с тремя группами критериев А, В, С, т. е. для векторов у(2), еГс компонентами

(5)

yt(1) = »í1» = у!

V? у,(2) =

= И(Ч = у]

= -Ч У?] = 0 V? € 5, W е С, Vs 6 / \ (S и С);

<3) =0 V/ € С, Vi € A, Vs G I \ (A U С)

справедливы соотношения >- 0т,у(2) >- 0т,у(3) >- 0т. Пусть

D = A U В U С, PQT = {(i,j, г) 6 А х 5 х С I |W(t,¿, 01 > 0}, Рц = {ieA | 0| > 0} для всех j еВ,1еС,

Qu = {j€B \ | W(i, j, 0| > 0} для всех г e Aje С, Tij = {lec I \W{i,j, 01 > 0} для всех ieA,jeB, fi = {(»,i, 0 6 PQT I Pji = {¿}, = {¿},Tij = {i}}-

Получен следующий результат.

Теорема 4. ► Пусть выполнены аксиомы «разумного» выбора и имеется непротиворечивая замкнутая информация об отношении предпочтения ЛПР с тремя заданными группами критериев А, В, С, причём множество Г2 не пусто. Тогда для любого непустого множества выбираемых векторов С(У) справедливы включения

С(У) С Р(У) С Р{У),

где Р{У) = /(Рд(Х)); а т-мерный векторный критерий д имеет компоненты, указанные в диссертации.

В данной теореме формулы «нового» векторного критерия д содержат величины а, /3, 7, где (а, /3,7) € Г2. Однако, в работе доказано, что построенная верхняя оценка Р(У) не зависит от выбора совокупности (а, /3,7) из П.

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

Пх = ш,0 е в х С I \Рц\ ф 0, \Р„\ > 1, = {¿},Ту = {/} Уг е Ря).

Если множество П пусто, а не является таковым, то это означает, что найдётся такая совокупность (а,/3,7) € РЦТ, что для любых ] В, 3 ф Р и любых I £ С, I ф 7 совокупности (а, 3, 7) и (а,р,1) не удовлетворяют условиям ^(а,.7,7)| > 0 и \\У{а,Р,1)\ > 0 соответственно, в то время как существуют такие г € А, г ф а, что для (г, /3,7) условие > О

выполнено.

Доказана теорема, показывающая каким образом производится учёт замкнутой информации, когда П пустое, а непустое. Её формулировка аналогична теореме 4, отличие состоит в следующем: «новый» критерийд является в-мерным, я = т + + \В\ + |С| - |Р^7|)(|Р/(7| - 1), формулы для расчёта компонент имеют другой вид и содержат (/3,7) £ Пх. Показано, что верхняя оценка Р(У) не зависит от выбора совокупности (/3,7) из Пь

п2 = {(-¿,0 е А X с I \<2и\ ф 0, > 1, Рп = {¿},Ту = {/} V? е <?«}.

Пз = {(м) еАхВ I |Гу| ф 0, |Гу| > 1, Рц = = {Л V/ е Ту}.

Также получены следствия об учёте замкнутой информации в случаях: 1) пусто, Пг не пусто; 2) П пусто, П3 не пусто.

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

Следуя монографии Кофмана А. «Введение в теорию нечётких множеств» (М.: Радио и связь, 1982), напомним основные понятия теории нечётких множеств. Нечёткое множество представляет собой обобщение традиционного понятия множества, где каждому элементу ставится в соответствие степень его принадлежности в интервале [О, 1]. Таким образом, нечёткое множество А в V (II — некоторое множество, называемое универсальным) задаётся своей функцией принадлежности А л: С —> [0,1]. Величина А л (и) есть степень

принадлежности элемента и множеству А. Если функция принадлежности принимает значения только 0 и 1, то имеет место случай традиционного (чёткого) множества. Нечётким бинарным отношением на II называется нечёткое подмножество декартова произведения [/ х [/. Далее в роли универсального множества выступает множество возможных решений X.

Рассматривается нечёткая многокритериальная задача (Х,/,Цх), которая содержит: 1) непустое множество (чёткое) возможных решений X, X С С К71; 2) числовой векторный критерий /: X -> Ет; 3) нечёткое асимметричное бинарное отношение строгого предпочтения ЛПР с функцией принадлежности цх- X х X -> (0,1]. Равенство х{2)) = ц* означает выбор ЛПР решения хт вместо ж(2) со степенью уверенности ц*. Бинарное отношение дх асимметрично, если из выполнения х^) > 0 следует

= о.

Множества выбираемых решений С(Х) и векторов С{У) также являются нечёткими. Они обладают функциями принадлежности Хх: X —>• [0,1] и Ау : У —>• [0,1] соответственно.

Допустимо рассмотрение задачи и в терминах векторов (векторных оценок) {У, цу).

Ранее В. Д. Ногиным были переформулированы аксиомы «разумного» выбора и принцип Эджворта — Парето па многокритеральнуго задачу с нечётким отношением предпочтения. Они предполагаются выполненными.

Рассматривается функция принадлежности \у множества Парето (четкого) Р{У), причём Ау(у) = 1 для всех у € Р{У), А£(у) = 0 для всех у еУ\ Р(У).

Вводится следующее определение, обобщающее определение 1 на нечёткий случай.

Определение 3. ► Задание замкнутой информации о нечётком отношении предпочтения ЛПР (нечёткой замкнутой информации) с критериями и.....гь со степенями уверенности ш,..., € (0,1] и с положительны-

(1) (1) (2) (2) (к-1) (*-1) (*) (к) ми скалярными параметрами ии^', ги>2, , и>{к ,и>{к

означает, что для векторов ... е Кт с компонентами (1) (см. определение 1) справедливы равенства ц{ут, 0т) = ц\,... 0т) = <

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

Набор нечётких «квантов информации», заданный с помощью векторов у(') е дгт1 г = хД, в совокупности с набором чисел /¿1,...,/^ € (0,1] называется непротиворечивым (совместным), если найдётся нечёткое бинарное отношение предпочтения с функцией принадлежности /х(-,-)> удовлетворяющее аксиомам «нечёткого разумного» выбора и такое, что/х(у(1), 0т) = г = 1, к.

Доказано, что критерий непротиворечивости для случая нечёткого отношения предпочтения повторят соответствующий критерий для случая чёткого отношения. В результате получено, что для замкнутой информации степени уверенности /ц,... не влияют на непротиворечивость и её необходимое

и достаточное условие заключается в проверке справедливости неравенства >0.

Рассматривается нечёткая замкнутая информация с критериями г, I с заданными степенями уверенности € (0,1].

В зависимости от соотношений между степенями уверенности реализуется либо ситуация (I): ^ ^ ц2 ^ /л3, ц3 > VI > Мг, И2 ^ Мз > А«ь либо (II):

> Из > М2> № > АН > /¿з, ¿¿з > /и2 > /¿1. В рамках каждой из них переименованием критериев можно перейти от одного двойного неравенства к другому.

Получены теоремы о сужении множества Парето в случаях (I) и (II), которые приводятся далее.

Рассматривается функция принадлежности

А ^ (у) = 1

' sup ф, у) Уу е У,

zeY

(6)

где

<(z,y) = <

1, если 2 - у е R™, щ, если z - у £ R+, z-yi R™, Н2, если z - у е R![', z - у <£ R™, My,z е У, уф z, если z-y е R™, z-y <£ R"', в остальных случаях,

0,

а векторы а, а, а <Е Rm, a G {y,z}, а е {y,z}, а Е {у, £}, выглядят так е' — единичные векторы пространства Rm):

а — а + (wj^a; + (wf ^ - l)a,j)e?,

а = а+ {wf}ai + (и;'1' - 1 )aj)ej + (w^w^m + w^w^aj + {wf^ - l)a,)e', a = a+ ((wf Ц(3) - l)aj + w^w^aj + wfw^a^ + {w^w^cn +

+ К(3Ч(1) - 1Ц- + Ц'Ч'ЧУ + «Ц^ + г^ЧЧ' + (^Ч^ -

Доказан следующий результат.

Теорема 5. ► Пусть выполнены аксиомы «нечёткого разумного» выбора и задана непротиворечивая нечёткая замкнутая информация с критериями г, I со степенями уверенности (11, Ц2, /хз С (0,1], и [г 1 ^ ^ /¿з- Тогда для любой функции принадлежности Лу(-) нечёткого множества выбираемых векторов С(У) справедливы неравенства Ху(у) ^ Л у (у) ^ Л у(у) для всех у € У, где функция Ху (•) определяется равенством (6). <

Показано, что построение «нечёткой» верхней оценки множества выбираемых векторов (т. е. функции принадлежности А у на У) в теореме 5 заключается в решении четырёх многокритериальных задач с чётким отношением предпочтения, которые отличаются друг от друга векторным критерием.

(1) (з)

м 'ч/Л '

Первая многокритериальная задача имеет множество возможных решений X и векторный критерий /. На данном этапе Ау (у) = 1 Для всех векторов у € Р(У), Ху (у) = 0 для всех векторов у е У \ Р(У).

На втором шаге решается многокритериальная задача с векторным критерием /, полученным из критерия / заменой компоненты па ш^Л + ^Г'Л-р(У) = ДР/рО), (У) = 1-/^1 Для всех векторов у е Р(У) \ Р(У) (т. е. для векторов, принадлежащих множеству Парето первой задачи, но не принадлежащих множеству Парето на данном шаге).

У третьей многокритериальной задачи векторный критерий / образован компонентами векторного критерия /, где j-й критерий заменён на Ц1'/¿4-

а I-й - на ш^Л + + «\(1Ч2)/<- ¿(П = Д^/РО)-

Ау (у) = 1 - М2 для всех у € Р(У) \ Р(У).

На четвёртом шаге решается многокритериальная задача с векторным критерием /, полученным из критерия / заменой г-й, и I-й компонент на + + „<3Ч2)/ь Ц'Ч3'/, + у>?4% + -ГЦ1'/*и

+ + соответственно. Р(У) = ДР/РО), =

= 1-^3 для всех векторов у е Р(У) \ Р(У). Кроме того, Ау (у) = 1 для всех векторов у е Р(У), Ау (у) = 0 для всех векторов у £ У \ Р(У).

Сужающаяся последовательность множеств Парето Р(У) С Р(У) С С Р(У) С Р(У), на которых значения функции принадлежности А^ определяются по описанному выше алгоритму, задаёт «нечеткую» оценку сверху множества выбираемых векторов.

Определим нечёткое отношение £(■, •) следующим образом:

1, если г — у 6 ™т

С(*,!/) =

+ >

Ни если г - у € К!?, г — у ф ,

/у,3, если г — у € г — у ^ К™, Уу, г е У, у ф г, (7)

если г - у 6 Е+, г - у <£ . О, в остальных случаях,

>

причём векторы Ь, Ь, Ъ € Кт, где Ь £ {у, г}, Ь 6 {у, г}, 6 6 {у,г}, таковы, что Ь = а, Ь = а и

6 = 6+чз>б, + чз) - ту++ч%(3) - +^Ч'31^-.

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

Теорема 6. ► Пусть выполнены условия теоремы 5, но > Цз > Тогда для любой функции принадлежности Ау(-) нечёткого множества выбираемых векторов С(У) справедливы неравенства Ау(у) ^ А^(у) ^ Ау(у)

для всех у £ У, где функция А у (•) определяется равенством (6), а нечёткое отношение £(-, •) —равенством (7).

Также доказана теорема об учёте нечёткой замкнутой информации, в которой участвует произвольное число «квантов».

В пятой главе обобщаются некоторые результаты четвёртой главы. Рассматривается нечёткая замкнутая информация, в которой вместо критериев используются группы критериев.

Определение 4. ► Задание замкнутой информации о нечётком отношении предпочтения ЛПР с группами критериев А\,... ,Ак со степенями уверенности Цх,..., /х* € (0,1] и с набором положительных параметров {ЧХ)> Ч4' • • • > г"и-11)>гиг\~1)>и'^)>гиЦ:) е К I ¿1 е Аи... ,1к е Ак} означает, что для векторов ... 6 Кт с компонентами (4) (см. определение 2) справедливы равенства ц(у^,От) = ци ... ,р.(у{к\От) = -4

Аналогично предыдущей главе показано, что необходимое и достаточное условие непротиворечивости совпадает с соответствующим условием для чёткой замкнутой информации и заключается в существовании таких номеров ip е Ар, р = 1, к, для которых выполнено | И^гь..., >0.

Рассматривается нечёткая замкнутая информация с тремя группами критериев А, В, С со степенями уверенности//1,/¿2,/¿з € (0,1]. Согласно определению 4 она задаётся векторами у(2\ уе Ет с компонентами (5), что справедливы равенства р(у(1), 0т) = дь /¿(у(2), 0т) = ц2, ц{у{3), 0т) = ц3.

Как и в предыдущей главе, возможна либо ситуация (I), либо (II), для каждой из которых аналогично теоремам 5 и С доказаны теоремы о сужении множества Парето, где также решаются четыре многокритериальные задачи с чётким отношением предпочтения. Таким образом сделано обобщение на нечёткий случай теоремы 4 (когда множество Г2 не пусто).

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

Основные положения и результаты, выносимые на защиту.

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

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

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

4. Разработаны правила использования непротиворечивой замкнутой информации в случае нечёткого отношения предпочтения.

Тематика диссертации соответствует пункту 4 паспорта специальности 05.13.01 — системный анализ, управление и обработка информации (по прикладной математике и процессам управления).

Публикации автора по теме диссертации

Статьи в журналах, рекомендованных ВАК

1. Захаров А.О. Сужение множества Парето на основе замкнутой информации об отношении предпочтения ЛПР // Вестник С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2009. Вып. 4. С. 69—83.

2. Захаров А.О. Сужение множества Парето па основе взаимозависимой информации замкнутого типа // Искусственный интеллект и принятие решений. 2011. № 1. С. 67-81.

3. Захаров А.О. Сужение множества Парето па основе замкнутой информации о нечётком отношении предпочтения лица, принимающего решение // Вестник С.-Петерб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2012. Вып. 3. С. 33—47.

Другие публикации

4. Захаров А.О. Сужение множества Парето па основе циклической информации об отношении предпочтения ЛПР // Процессы управления и устойчивость: Труды 40-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2009. С. 602-607.

5. Захаров А.О. Сужение множества Парето на основе замкнутой информации о группах критериев // Процессы управления и устойчивость: Труды 41-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Г. Ш. Тамасяна. СПб.: Издат. Дом С.-Петерб. гос. унта, 2010. С. 587-592.

6. Захаров А.О. Сужение множества Парето на основе нечёткой замкнутой информации // Процессы управления и устойчивость: Труды 42-й международной научной конференции аспирантов и студентов / Под ред. А. С. Ерёмина, Н. В. Смирнова. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2011. С. 467-472.

7. Захаров А.О. Сужение множества Парето на основе нечёткой информации замкнутого типа // Проблемы оптимизации и экономические приложения: материалы V Всероссийской конференции (Омск, 2—6 июля 2012 г.). Омск: Изд-во Ом. гос. ун-та, 2012. С. 191.

8. Захаров А.О. Учёт информации об отношении предпочтения в одной экономической задаче // Процессы управления и устойчивость: Труды 44-й международной научной конференции аспирантов и студентов / Под ред. Н. В. Смирнова, Т. Е. Смирновой. СПб.: Издат. Дом С.-Петерб. гос. ун-та, 2013. С. 582-587.

Подписано к печати 12.09.13. Формат 60x84 'Лб. Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 1,00. _Тираж 100 экз. Заказ 5855._

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043, 428-6919

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

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

04201363680

Захаров Алексей Олегович

ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ ЗАМКНУТОЙ ИНФОРМАЦИИ ОБ ОТНОШЕНИИ ПРЕДПОЧТЕНИЯ ЛПР

05.13.01 — системный анализ, управление и обработка информации (по прикладной математике и процессам управления)

Диссертация на соискание ученой степени кандидата физико-математических наук

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

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

Оглавление

Введение 4

1 Основные положения аксиоматического подхода 20

2 Информация замкнутого типа. Критерии 27

2.1 Определение ............................................................27

2.2 Непротиворечивость....................................................28

2.3 Учет замкнутой информации..........................................33

2.4 Прикладной пример....................................................46

3 Информация замкнутого типа. Группы критериев 50

3.1 Определение и критерий непротиворечивости........................50

3.2 Учет замкнутой информации..........................................54

3.2.1 Случай 1 ........................................................54

3.2.2 Случай 2 ........................................................65

4 Нечеткая информация замкнутого типа. Критерии 73

4.1 Основные понятия нечетких множеств и нечетких отношений . . 73

4.2 Задача «нечеткого» многокритериального

выбора....................................................................75

4.3 Понятие нечеткой замкнутой информации и ее непротиворечивость 77

4.4 Учет нечеткой замкнутой информации. Случай трех критериев . 83

4.5 Учет нечеткой замкнутой информации.

Случай к критериев.......................... 91

5 Нечеткая информация замкнутого типа. Группы критериев 100

5.1 Определение и критерий непротиворечивости............100

5.2 Учет нечеткой замкнутой информации ...............101

6 Учет замкнутой информации в одной экономической задаче 105 Заключение 112 Литература 114

Введение

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

Проблемы принятия решений лежат на стыке нескольких наук (математика, экономика, психология и т. д.), каждая из которых рассматривает их со своей стороны. Один из разделов психологии — когнитивная психология — занимается выявлением структуры переработки информации человеком, механизмов «работы» мозга при принятии решений. Выработаны стратегии поведения человека при многокритериальном выборе [16, 17, 19]: компенсации и исключения. Первые основаны на сравнении оценок каждой альтернативы, во вторых происходит удаление альтернатив, не удовлетворяющих определенным требованиям по одному или нескольким критериям. Были сформированы психологические теории многокритериального выбора: теория поиска доминантной структуры (Н. Montgomery, О. Svenson), теория конструирования стратегий (J.

W. Payne). В первой из них ЛПР, охватывая все альтернативы, по первому впечатлению выделяет доминирующую и попарно сравнивает ее с остальными. Если некоторая альтернатива будет превосходить данную, то тогда она будет являться претендентом на доминирующую, в противном случае доминантную структуру составит исходная выбранная альтернатива. Согласно второй теории в процессе принятия решений используется не одна, а несколько стратегий: сначала человек может определенным образом сопоставить оценки альтернатив между собой, затем исключить из рассмотрения альтернативы, неприемлемые по некоторым критериям, и т. д. Данные теории нашли свое подтверждение при проведении различных схем психологических экспериментов [19].

Работа посвящена разработкам новых подходов и решений задачи многокритериального выбора. Изложение начнем с понятия задачи многокритериальной оптимизации, которая характеризуется следующими объектами: непустое множество возможных решений (альтернатив, вариантов) X и числовой векторный критерий /, заданный на X и отражающий стремления, намерения, цели и вкусы лица, принимающего решение (ЛПР). В качестве первого объекта могут выступать: ассортимент товаров в магазине, экономические планы развития предприятия, объекты инвестирования, политические стратегии; в качестве второго — стоимость и качество покупки; прибыль, затраты и экологический ущерб предприятия и т. д. Как правило, достижение определенной цели выражается в максимизации или минимизации компонентов векторного критерия на множестве возможных решений. Однако в реальных задачах достижение экстремальных значений одновременно по всем критериям в одной точке практически невозможно. Данный факт является существенным отличием от одно-критериальной экстремальной задачи. Поэтому использование привычного понятия максимума числовой функции не представляется допустимым. Впервые понятие оптимума для двух критериев (кривая безразличия) ввел английский экономист F. Y. Edgeworth [46], позднее данное определение обобщил итальянский социолог и экономист V. Pareto на случай произвольного числа крите-

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

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

Выделяют [19, 39, 48, 59] основные типы многокритериальных задач принятия решений: задача выбора, задача ранжирования (упорядочивания), задача классификации. Первой из них посвящена данная работа, вторая заключается в упорядочивании имеющихся альтернатив от худшей к лучшей в силу предпочтений ЛПР (назначение ранга каждой альтернативе), под третьей понимается задача отнесения каждой альтернативы к конкретному классу, обладающему определенными свойствами (например, распределение товаров по трем группам — высокого качества, среднего и низкого).

Также существует теория группового многокритериального выбора, где рассматривается целая группа ЛПР, каждый член которой имеет собственные предпочтения и критериальные оценки альтернатив. Здесь разработаны различные методологии (А. Б. Петровский, Т. L. Saaty и J. М. Alexander, С. L. Hwang и С. Yoon) по агрегированию коллективных предпочтений и нахожде-

^В некоторой литературе используется терминология «множество Эждворта — Парето»

нию «наилучшей» альтернативы или составлению результирующего упорядочивания альтернатив [39].

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

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

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

Впервые аксиоматическое обоснование принципа Эждворта — Парето было приведено в статье [29] и монографии [34] В. Д. Ногина, где показано для какого класса задач возможно его применение. Предложенная аксиоматика представляет собой модель рационального поведения ЛПР. Более того, при нарушении хотя бы одной из этих аксиом применение принципа Эджворта — Парето является рискованным и недопустимым [29, 32], что как раз упускают из виду не только большинство авторов методологий по принятию решений при многих критериях, но и множество экономистов.

Разработано множество подходов по решению многокритериальных задач выбора (а также ранжирования и классификации) [10, 19, 23, 24, 34, 36, 39, 45, 47, 48, 53, 59, 60, 61, 63]. Их можно выделить в следующие группы: методы многокритериальной теории полезности (Multiattribute Utility Theory) [10,19, 23, 39, 48]; так называемые «outranking approach»1) [19, 23, 39, 48, 49, 58, 59, 63]; методы вербального анализа решений [15, 17, 18, 19, 39, 48]; различные итеративные процедуры [19, 23, 39, 45, 48]; аксиоматический подход сужения множества Парето [1—9, 11, 12, 27—38, 55, 56] (исследования в настоящей работе проводятся в рамках данного метода).

Теория полезности основана на теории экономического поведения J. von Neumann и О. Morgenstern [26] и является по сути теоретико-игровым подходом к принятию решений. В качестве ключевого понятия здесь фигурирует лотерея, которую составляют альтернативы со своими вероятностями наступления. Постулируется ряд аксиом, при выполнении которых существует аддитивная функция полезности, заданная на множестве альтернатив (теорема Неймана — Моргенштерна). Таким образом, каждой альтернативе ставится в соответствие

Единый перевод понятия «outranking approach» в русской литературе так и не прижился. Каждый автор предлагает свой вариант: у Петровского — пороговый метод [39], у Ларичева — подход, направленный на разработку индексов парного сравнения альтернатив (РИПСА) [18], у Лотова — метод классификации альтернатив [23], у Ногина — метод с «искусственным» отношением предпочтения [36].

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

На многокритериальный случай теорию полезности обобщили И,. Ь. Кеепеу, Н. 11а1А:а, Р. С. Р1зЫшгп [10], где функция полезности строится для каждого критерия, а потом все они агрегируются в одну общую функцию полезности. Аксиоматика одномерного случая дополняется аксиомами независимости по полезности и по предпочтению, при выполнении которых утверждается [10] существование многомерной функции полезности, заданной на множестве альтернатив и имеющей в зависимости от ряда факторов либо аддитивную, либо мультипликативную форму. И уже на ее основании делается окончательный выбор (или ранжирование) по аналогии с одномерным случаем.

Однако данные методы имеют ряд недостатков. Во-первых, возникают большие трудности с построением функции полезности для каждого критерия, поскольку такая процедура связана со сравнением лотерей и отдельных альтернатив. К примеру, ЛПР может быть задан такой вопрос: определить эквивалент (гипотетическую альтернативу с конкретной прибылью) лотерее, имеющей с вероятностью 0,6 исход с прибылью в 100 тыс. р. и с вероятностью 0,4 исход с прибылью в 200 тыс. р. Такого рода действия очень сложны для человека. Во-вторых, вид функции полезности справедлив при выполнении всех аксиом. Однако, как правило, данная проверка выполняется лишь частично.

К многокритериальной теории полезности также можно отнести метод анализа иерархий [44] (МАИ), разработанный Т. Ь. 8аа1у. Здесь в качестве функции полезности используется линейная свертка компонент векторного критерия, коэффициенты которой суть «веса» каждого критерия. Наилучшим признается тот вариант, который максимизирует свертку. Подразумевается, что «вес» отражает важность соответствующего критерия, однако четкого опре-

деления не дается. Ключевым моментом является построение матриц парных сравнений альтернатив и компонент векторного критерия. На их основе вычисляются «вес» каждого критерия и оценка альтернативы по каждому критерию. Это самый простой вариант метода, в общем случае строится иерархическая структура (дерево), каждый уровень которой есть подцели ЛПР, вершиной дерева является общая агрегированная цель.

Максимизация линейной сверки на самом деле является только достаточным условием парето-оптимальности. Необходимое условие справедливо, когда множество возможных решений выпукло, а векторный критерий покомпонентно вогнут (лемма Карлина, см. [43]). В данном случае множество альтернатив конечно (т. е. не выпукло), значит при максимизации линейной свертки (даже используя все допустимые значения «весов») могут быть упущены некоторые парето-оптимальные решения. Кроме того, в методе существует определенная эвристика по определению согласованности суждений в виде индекса согласованности. В [31] предложена модификация МАИ, где проблема несогласованности решается без использования данного индекса. И, как было уже сказано, этот подход используется только для задач с конечным множеством возможных альтернатив.

Группой французских математиков во главе с В. Roy было заложено другое направление в принятии решений при многих критериях, методы в рамках которого в иностранной литературе именуют «outranking approach» (дословно «подход внешнего ранжирования»). Первым здесь является ELECTRE [49, 58, 59], разработанный В. Roy в 1968 году. Высказывается разумное предположение, что одна альтернатива может доминировать другую или быть ей эквивалентной в рамках некоторых пороговых значений. Например, варианты А и В считаются эквивалентными по данному критерию, если разность их критериальных оценок не превосходит некоторого значения (порог безразличия), которое, вообще говоря, для каждого критерия свое. Для каждой пары альтернатив А и В рассчитываются индексы согласия с(Д В) и разногласия

d(A,B), которые отражают степень (от 0 до 1) доминирования и недоминирования первой альтернативы над второй. Моделируется отношение предпочтения «одна альтернатива по крайней мере такая же хорошая, как другая» (outranking relation), которое справедливо для А и В, если значения индексов согласия и разногласия не меньше и не больше соответственно своих предельных значений: уровня согласия с\ и уровня разногласия d\, задаваемых ЛПР (с(А, В) ^ ci, d(A, В) ^ d\). Таким образом, использование данных индексов отражает принципы согласия (concordance) и несущественного разногласия (non-discordance). Уменьшая значение С\ и увеличивая значение d\, можно построить сужающуюся последовательность ядер данного отношения, которая будет задавать ранжирование вариантов. В случае задачи выбора «оптимальным» решением может являться наименьшее из них. Необходимо отметить, что ядро построенного бинарного отношения может включать доминируемые варианты [23], которые, по идее, не должны входить в окончательный выбор.

У методов типа «outranking approach» отсутствует аксиоматическая обоснованность в отличии от теории поле�