Рассмотрим пару <A,R>, где A - множество сравниваемых объектов (альтернатив); R - бинарное отношение на A. Задание бинарного отношения содержательно интерпретируется как введение некоторой системы предпочтений. Именно, если пара (a1, a2), где a1A, , принадлежит R, то подразумевается, что элемент a1 в определенном смысле “лучше” или “не хуже” элемента a2.
Пару <A, R> будем называть моделью выбора. Совершенно ясно, что если отношение R не является линейным (в смысле определения подраздела 1.1.1), то существуют несравнимые по данному отношению элементы.
Зададимся теперь вопросом о том, что же следует понимать под решением задачи выбора <A, R>. Для ответа на этот вопрос необходимо формализовать понятие “наилучшего” элемента (или элементов). Интуитивно наиболее естественный подход приводит к следующему определению.
Пусть задана модель <A, R>. Элемент a*А называется наилучшим по R в A, если a*Ra справедливо для всех aА\ a*.
(Иначе говоря, если a* “не хуже” или не менее предпочтителен или “лучше”, чем любой другой элемент из А, отличный от a*.)
ПРИМЕР 1.1.
А = {a, b, c}; R = {(a, b),(b, a),(a, c),(b, c),(b, b)}. Это же отношение задается графом (Рисунок 3). Наилучшими элементами являются элементы a и b (проверьте это).
ПРИМЕР 1.2.
А = {a,b,c}; R = {(a,a),(b,b),(c,c),(b,c)}. Граф отношения R представлен на рисунке4.
Наилучших элементов нет. Действительно, a не является наилучшим элементом, так как отношение R в этом случае обязано было бы содержать пары (a,b), (a,c). Точно так же показывается, что b и c не являются наилучшими элементами, так как отношение R в этом случае обязано было бы содержать пары (a,b), (a,c). Точно так же показывается, что b и c не являются наилучшими элементами.
На языке графов понятие наилучшего элемента соответствует наличию вершины, соединенной исходящими из нее стрелками со всеми остальными вершинами графа. При этом могут присутствовать и любые другие дополнительные соединения.
Пример 1.2 показывает, что наилучшие элементы могут отсутствовать, например, из-за наличия несравнимых по R элементов (в примере 1.2 элементы a и с не сравнимы по R). На рисунке 5 изображена ситуация, где все элементы сравнимы, но наилучшего элемента также нет (этот случай соответствует примеру 5 из введения).
Таким образом, понятие наилучшего элемента не является достаточно универсальным. И если в случае, представленном на рисунке 5, действительно трудно отметить наиболее предпочтительный элемент, то в примере 1.2 на рисунке 4 хотелось бы выделить элементы a и b , так как b , по крайней мере , “не хуже” чем с, и достаточно ограничиться рассмотрением только указанных двух элементов.
Введем вместо понятия наилучшего элемента более слабое понятие максимального элемента.
Элемент a0A называется максимальным по R в А (или максимальным в модели <A,R>), если aRa0 а0Ra (т.е. если aRa0 влечет a0Ra). Множество всех максимальных в <A, R> элементов обозначим через МахR А.
Очевидно, граф отношения, имеющего максимальные элементы, должен содержать вершины, в которых каждой входящей в нее стрелке соответствует “компенсирующая”, выходящая стрелка, направленная в вершину, из которой исходит указанная входящая стрелка (Рисунок 6).
В примерах 1.1 и 1.2 максимальными по R элементами будут элементы а, b (докажите это).
Упражнение.
Докажите, что наилучший по R в A элемент является и максимальным. (обратное утверждение в общем случае неверно, что доказывает пример 1.2)
Множество МахRA называется внешне устойчивым, если для любого элемента аА\МахR A найдется такой элемент а0МахR A, что справедливо а0Ra.
Понятие внешней устойчивости оказывается существенным для проблемы ПР. Действительно, если множество МахRA внешне устойчиво, то последующий выбор оптимального элемента (на основе, например, привлечения более детальной информации) может производиться только в пределах множества МахRA. В противном случае, когда устойчивости нет, такой вывод уже не будет иметь разумного обоснования.
Внешне устойчивое множество МахRA называется ядром отношения R в А. Однако, далее термин “ядро” применительно к множеству МахRA будет использоваться и без требования внешней устойчивости.
В примерах 1.1 и 1.2 ядро {a, b} будет устойчивым (проверьте это).
На рисунке 7 представлен случай, когда ядро {a, b} не является внешне устойчивым, так как для элемента d не существует такого элемента из ядра, который был бы “не хуже” по R - пары (a,d), (b,d) не принадлежат отношению R. Заметим, что свойство транзитивности aRc, cRdaRd здесь не выполняется; его может не быть и по смыслу (пример 5 из введения). Следовательно, в данном примере нельзя автоматически считать, что элемент а не хуже, чем d .
Далее под задачей ПР понимается задача выделения ядра - множества максимальных элементов из А по некоторому бинарному отношению R: . Специфика конкретных задач ПР находит отражение в задании соответствующего множества альтернатив А, а также в формировании бинарного отношения R, характеризующего вполне определенные цели принятия решений в той или иной практической ситуации.
0 коммент.:
Отправить комментарий