Графы предпочтений

В случае конечных множеств альтернатив, очень удобно находить решения, используя так называемые графы предпочтений. Определение. Пусть Х – это множество альтернатив, на котором задано некоторое бинарное отношение предпочтения R (отношение порядка или доминирования). Запись xRy означает, что x – это более предпочтительная альтернатива, чем y. Граф, описывающий это отношение R на множестве X, называется графом предпочтений. Решение задачи выбора состоит в нахождении таких вершин графа предпочтения, которые не имеют более предпочтительной альтернативы, то есть не имеют входящих ребер. Определение. Вершины графа предпочтений, не имеющие входящих ребер называются недоминируемыми альтернативами. Пример: Пусть множество Х состоит из 1. Холодильник 2. Микроволновка 3. Телевизор Пусть нам требуется определить первоочередную покупку. Пусть отношение предпочтения – это «приобрести раньше, чем». Для следующего набора предпочтений построим граф. 1. Холодильник приобрести раньше, чем Микроволновку 2. Холодильник приобрести раньше, чем Телевизор 3. Телевизор приобрести раньше, чем Микроволновку

Решение задачи выбора состоит в нахождении таких вершин графа предпочтения, которые не имеют более предпочтительной альтернативы, то есть не имеют входящих ребер. Определение. Вершины графа предпочтений, не имеющие входящих ребер называются недоминируемыми альтернативами. Пример: Пусть множество Х состоит из 1. Холодильник 2. Микроволновка 3. Телевизор Пусть нам требуется определить первоочередную покупку. Пусть отношение предпочтения – это «приобрести раньше, чем». Для следующего набора предпочтений построим граф. 1. Холодильник приобрести раньше, чем Микроволновку 2. Холодильник приобрести раньше, чем Телевизор 3. Телевизор приобрести раньше, чем Микроволновку Решение задачи выбора сводится к нахождению недоминируемых альтернатив. Таковой в нашем примере является Холодильник. Таким образом, именно холодильник и следует покупать в первую очередь. Существует теорема, которая определяет, в каких случаях нахождение решения по недоминируемым вершинам графа предпочтений сводится к решению однокритериальной задачи выбора. А мы знаем, что такие задачи решаются тривиально.

Теорема. Если для некоторого множества альтернатив Х, и бинарного отношения предпочтения R, определенного на множестве Х, граф предпочтений сильно транзитивен и антирефлексивен, то задача принятия решения сводится к однокритериальной задаче выбора. Эту теорему можно использовать при построении автоматизированных систем принятия решений. Удобство описания задачи выбора на языке бинарных отношений состоит в том, что требуется задать предпочтения только попарно. Это оказывается часто намного проще, чем задать конкретные значения критериев для всех альтернатив. Кроме того, для разных пар альтернатив предпочтения могут задаваться на основании различных наборов критериев!

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