pora.zavantag.com Описание выбора на языке бинарных отношений. Формальные модели принятия
страница 1

Описание выбора на языке бинарных отношений. Формальные модели принятия решений.

Язык бинарных отношений – второй, более общий, чем критериальный, язык описания системы предпочтений ЛПР.

Предполагается, что:

Отдельный исход сам по себе не оценивается и критериальные функ­ции не вводятся;

Каждая пара исходов уi, уj может находиться в одном из следующих отношений:


Будем далее предполагать, что свои предпочтения пользователь устанав­ливает в некотором множестве А. В стандартном случае — это множест­во исходов: А=Y. Однако при детерминистской связи X с Y возможно А=X, или при многокритериальной оценке исходов А =f(Y),f=f1,…,fm. В последнем случае предполагается, что система предпочтений ЛПР за­дается непосредственно в пространстве векторных оценок исходов. При необходимости можно полагать, что это пространство и есть простран­ство исходов. В рассматриваемом случае система предпочтений пользо­вателя задается с помощью соответствующего бинарного отношения R на А. Напомним, что бинарным отношением на множестве А называется произвольное подмножество R множества А2, где А2 - множество всех упорядоченных пар вида i, аj), где аi, аj А. Имеем, следовательно, RА2, в том числе А2А2. Основные свойства бинарных отношений (рефлексивность, симметричность, транзитивность, антирефлексивность и т. д.) предполагаются известными.

Существует наглядный способ задания бинарных отношений на конеч­ных множествах. Изобразим элементы конечного множества А точками на плоскости. Если задано отношение RА2 и i, аj) R, где аi, аj А, то проведем стрелку от аi, к аj. Если i, аi) R, то у точки аi нарисуем петлю-стрелку, выходящую из аi, и входящую в ту же точку. Получившаяся фигура называется ориенти­рованным графом, а сами точки — вершинами графа. Заметим здесь же, что вместо i, аj) R можно писать аiRаj.

Основной вопрос заключается в следующем. Пусть на множестве А зада­на система предпочтений ЛПР в виде бинарного отношения R (часто это отношение строгого доминирования). Что тогда следует понимать под решением задачи выбора? Этот основной вопрос в разных случаях (системах оптимизации и принятия решений, пакетах прикладных про­грамм) решается неоднозначно, и пользователям необходимо ясно осоз­навать, что же конкретно имеется в виду в каждом отдельном случае. Перейдем к точным формулировкам.

Пусть А - заданное множество и R — произвольное бинарное отноше­ние на А. Тогда пара <А, R> называется моделью выбора.



Определение 1.1

Пусть задана модель <А, R>. Элемент а*А называется наилучшим по R в А, если (а*, а) R для .

На рис. 1.6, а наилучшими элементами являются а1, а2. На графе рис. 1.6, б наилучших элементов нет.

Рис. 1.6. Понятие наилучшего элемента

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

Если предположить, что бинарное отношение, представленное на рис. 1.6, б, является отношением предпочтения, и стрелки означают не­который вариант доминирования, то, по-видимому, целесообразно как-то исключить a1 из дальнейшего рассмотрения, ибо этот элемент “доминируется” элементом а3. С помощью понятия наилучшего элемента это сделать невозможно, хотя в случае, представленном на рис. 1.6, а, мы ис­ключили элемент а3, как не являющийся наилучшим.


Введем вместо наилучшего элемента более слабое понятие максимально­го элемента.

Определение 1.2

Элемент а0А называется максимальным в модели <А,R> или макси­мальным по R в А, если .

Множество всех максимальных в <А, R> элементов обозначим через МахRA.

Очевидно, граф отношения, имеющего максимальные элементы, должен содержать вершины, в которых каждой входящей в нее стрелке (если тако­вые имеются) соответствует "компенсирующая", выходящая стрелка, на­правленная в вершину, из которой исходит указанная входящая стрелка.

В примерах, приведенных на рис. 1.6, максимальными по R элементами будут:

а) а1, а2;б) а2, а3

Легко доказать, что наилучший по R в А элемент является и максималь­ным. Обратное верно только, если отношение R обладает специальным свойством слабой связности:

На рис. 1.6, б отношение R не является слабо связным. Иногда используется понятие R-оптимального элемента.



Определение 1.3

Элемент а0 А называется R-оптимальным на А, если .

Иначе говоря, здесь требуется существование вершины, в которую не входит ни одна стрелка.

На рис. 1.6, а R-оптимальных элементов нет, на рис. 1.6, б элемент а3 бу­дет R-оптимальным.

Основным понятием для нас далее будет понятие максимального элемента.

Определение 1.4

Множество МахRA называется внешне устойчивым, если для любого эле­мента аА\МахRA найдется такой a0МахRA, что справедливо (а0, а) R.

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

Внешне устойчивое множество МахRA называется ядром отношения R в А. Иногда термин "ядро" применительно к множеству МахRA использу­ется и без требования внешней устойчивости.

В примерах на рис. 1.6 множества МахRA являются внешне устойчивы­ми. На рис. 1.7 представлен случай, когда множество

МахRA = {a1,a2} не является внешне устойчивым.





Рис. 1.7. Отсутствие внешней устойчивости

Далее под задачей ПР, сформулированной на языке бинарных отноше­ний, понимается задача выделения ядра— множества максимальных элементов из А по некоторому бинарному отношению R: А* = МахRA. Специфика конкретных задач ПР находит отражение в задании соответ­ствующего множества вариантов А, а также в формировании бинарного отношения R, характеризующего вполне определенные цели принятия решений в той или иной практической ситуации. Весьма важным с прак­тической точки зрения являются следующие специальные виды бинарных отношений:




1.3. Связь различных способов описания выбора. Однокритериальный и многокритериальный выбор

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



Однокритериальный выбор. Пусть


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

Отношение R1, является, очевидно, рефлексивным и транзитивным и, сле­довательно, определяет квазипорядок на Y. Отношение R2 обладает свойством антирефлексивности (у неверно, что f(у)>f(у)) и транзи­тивности, являясь строгим порядком. В обоих случаях справедливо ра­венство:



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



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

которые требуется максимизировать.

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

Здесь . Отношение доминирования Rр называется отноше­нием Парето, Rs - отношением Слейтера. Употребляется также запись





Определение 1.5

Если для некоторой точки у°Y не существует более предпочтительной по Парето точки, т. е. такой точки у, что (у, у°) Rp, то тогда точка у° на­зывается эффективным или Парето-оптималъным решением многокритери­альной задачи fk(у) —> mах, k: = 1 , 2, ..., т; у Y.

Множество, включающее в себя все эффективные элементы множества Y, обозначается Рf(Y) или просто Р(Y) (если ясно, о каком векторном кри­терии f идет речь) и называется множеством Парето для векторного от­ношения

Очевидно, . Образ множества Р(Y) в пространстве критериев Rm обозначается Р(f). Множество Р(f) =f(Р(Y)) называется множеством эффективных оценок. Множество эффективных оценок называется также множеством Парето в пространстве критериев.

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

Ясно, что бинарное отношение Rр является антирефлексивным, т. к.. Кроме того, легко установить, что



Таким образом, отношение Rp транзитивно. Отсюда следует, что Rр — частичный строгий порядок на Y.

Обычно цель решения многокритериальной задачи

состоит в выделении множества Парето Р(Y). При отсутствии дополни­тельной информации о системе предпочтений пользователя большего сделать нельзя.

Обратимся теперь к отношению RS.

Определение 1.6

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

Иначе говоря, исход "у" называется слабо эффективным, если он не мо­жет быть улучшен сразу по всем от критериям, задаваемым с помощью частных целевых функций fi(у), i =1, 2, ..., m. Множество слабо эффек­тивных элементов обозначается через Sf(Y) или просто S(Y). Очевидно,. Аналогично предыдущему случаю вводим обозна­чение S(f)=f(S(Y)).

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

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

с выполнением свойства внешней устойчивости множества Парето.

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

Пример 1.1. Пусть задана векторная целевая функция f= (f1, f2) на множе­стве Y=1, ..., у5}, причем частные целевые функции fi требуется макси­мизировать. Образы точек уi в пространстве критериев (f1,f2) обозначим соответствующими числами (рис. 1.8).

Используя определение доминирования по Парето, можно для этой за­дачи построить само отношение Rр и его граф (рис. 1.9).

Используя определение ядра, с помощью непосредственного рассмотре­ния графа получаем:





Рис. 1.8. Двухкритериальная задача


Рис. 1.9. Отношение Парето и его граф

На рис. 1.9 ядро выделено штриховкой. Можно заметить, что наилучшие элементы (см. определение 1.1) в данном случае отсутствуют, а понятие максимального элемента позволяет в полной мере формализовать мно­гокритериальную задачу выбора как задачу построения множества не­доминируемых по Парето элементов.

С помощью аналогичных рассмотрений устанавливаем, что отношение Слейтера RS (так же, как и отношение Rр) является строгим порядком и может быть представлено графически (рис. 1.10). Ядро выделено штри­ховкой.



Рис. 1.10. Отношение Слейтера
Видно, что, во-первых, , а во-вторых,

Эти включения выполняются и в общем случае.



Замечание 1.1

Отношение Парето Rр порождает соответствующее отношение несравни­мости Rн:



Для последнего примера имеем, в частности, Rн = {(у4, у2), (у2, у3), (у1, у4), (y4 , y1),…}

Важно отметить, что, например но .

Таким образом, отношение несравнимости в многокритериальных зада­чах, являясь симметричным () не является тран­зитивным.


1.4. Функции выбора

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

Перейдем к более точным определениям.

Пусть X — множество (может быть и бесконечное) всех возможных аль­тернатив. Тогда через 2Л обозначается множество всех подмножеств X. Среди всех подмножеств X выделяется класс X^ допустимых предъявле­ний [4]:



ХО с 2х. Введем следующее определение.

Определение 1. 7

Функцией выбора на классе допустимых предъявлений X^ называется функция

С: ХО -> 2х

такая, что для любого множества а€ ХО

С(Л)сЛ.

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



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

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

/,(о)->тах, А с К".

а€А

'

Такая функция выбора может быть задана следующим образом: СР(А)±{а е А \ \/у е А, у * а : 3/, у, < а,}.



Здесь точка а из А выбирается тогда и только тогда, когда любая другая точка из А будет "хуже" (в данном случае — меньше) хотя бы по одному из частных критериев /А..

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



О Наследование (Н-свойство). Это свойство подразумевает, что вари­ант, выбираемый из некоторого множества, будет также выбран, ес­ли предъявить для выбора любое подмножество, содержащее этот вариант:

УУ с У е УО -> С(У) о У' с С(У').

Смысл этой записи состоит в следующем. С(У) — это выбранные эле­менты из У. Если какие-то из них будут предъявлены в составе под­множества У, т.е. пересечение С(У)пУ' не пусто, то они также должны войти в выбор С(У).

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



П Отбрасывание (О-свойство). Это свойство называется также условием независимости от отвергнутых альтернатив. Оно означает, что если удалить из предъявляемого множества какие-то (вообще говоря, не все) невыбранные альтернативы, то выбор на оставшемся множестве не изменится:

УУ' с 7 е УД С(У) с У -> С(У") = С(У).

Иначе говоря, если подмножество У включает в себя все выбранные из 7 варианты: С(У) с У', то выбор на У совпадает с выбором на У.
П Согласованность (С-свойство). Данное требование означает, что если вариант выбирается в каждом из двух множеств (предъявлений), то он будет выбран и в объединении этих множеств:

Упражнение 1.1. Докажите, что "паретовская" функция Ср обладает всеми тремя свойствами.

В теории функций выбора рассматриваются и другие аксиомы [1 , 4, 26].

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

Упражнение 1.2. Докажите, что:

О если Сь С2 обладают //-свойством, то это же свойство есть у функции

С,иС2;

О если С|, С2 имеют С-свойство, то оно же имеется у функции С, пС2, а для функции С, иС2 это неверно.

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

В заключение рассмотрения функций выбора отметим, что введение ме­ханизма предъявления множеств является принципиальным для практи­ческих применений [1, 4]. Часто полагают, что класс допустимых предъ­явлений совпадает с множеством всех подмножеств 2Л, где X — исходное множество альтернатив. Однако простейшие примеры показывают, что в действительности нам оказывается доступным лишь некоторое подмно-



жество ХО с 2х. Например, пусть множество X означает множество всех возможных видов данного товара. Мы должны выбрать один или не­сколько видов товара. Обычно мы ограничены в своем выборе теми ма­газинами, которые мы в состоянии посетить. Реально мы будем иметь дело с некоторым множеством ХО, определяемым фактом наличия раз­личных видов товара в каждом из доступных магазинов.
страница 1
скачать файл

Смотрите также:
Описание выбора на языке бинарных отношений. Формальные модели принятия решений
135.43kb. 1 стр.

Методические указания по дисциплине «Менеджмент» содержат описание двух практических занятий, необходимых для обучения студентов современным методам принятия управленческих решений в области управления персоналом
1102.67kb. 4 стр.

Основная задача направления: объяснение выбора при принятии решений, распределении риска и вознаграждения
10.03kb. 1 стр.

© pora.zavantag.com, 2018