Формальная модель задачи принятия решениЙ

Рассмотрим пару <A,R>, где A - множество сравниваемых объектов (альтернатив); R - бинарное отношение на A. Задание бинарного отношения содержательно интерпретируется как введение некоторой системы предпочтений. Именно, если пара (a₁, a₂), где a₁A, , принадлежит R, то подразумевается, что элемент a₁ в определенном смысле “лучше” или “не хуже” элемента a₂.

Пару <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 , по крайней мере , “не хуже” чем с, и достаточно ограничиться рассмотрением только указанных двух элементов.

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

Элемент a⁰A называется максимальным по R в А (или максимальным в модели <A,R>), если aRa⁰ а^0Ra (т.е. если aRa⁰ влечет a⁰Ra). Множество всех максимальных в <A, R> элементов обозначим через Мах_R А.

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

В примерах 1.1 и 1.2 максимальными по R элементами будут элементы а, b (докажите это).

Упражнение.

Докажите, что наилучший по R в A элемент является и максимальным. (обратное утверждение в общем случае неверно, что доказывает пример 1.2)

Множество Мах_RA называется внешне устойчивым, если для любого элемента аА\Мах_R A найдется такой элемент а⁰Мах_R A, что справедливо а⁰Ra.

Понятие внешней устойчивости оказывается существенным для проблемы ПР. Действительно, если множество Мах_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, характеризующего вполне определенные цели принятия решений в той или иной практической ситуации.

Предлагаю ознакомиться с аналогичными статьями: