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

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

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

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

Если удается построить более слабые отношения порядка – частичного порядка или строгого порядка, то это приводит к диаграммам с некоторым множеством максимальных элементов (рис. 5.7).

Рис. 5.6. Диаграмма совершенного строгого порядка для классов эквивалентных элементов

Рис. 5.7. Диаграмма с множеством максимальных элементов

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

Первый этап. Применяется принцип недоминируемости.

Принцип недоминируемости: лучшее решение или лучший элемент в упорядоченном множестве (B, b), где b – отношение частичного порядка или отношение строгого порядка, необходимо искать среди недоминируемых (или максимальных) элементов.

В результате применения принципа недоминируемости выделяется множество B1 максимальных элементов.

В случае диаграммы рис. 5.7 это приводит к множеству из шести элементов: A, B, C, F, H, N – которые несравнимы между собой.

Второй этап. В множество элементов B1 вносится дополнительная информация в форме отношения порядка: информация о доминировании и информация о безразличии.

Информация о доминировании вносится в форме бинарного отношения b1 на множестве B1.

Информация о безразличии может задаваться разбиением множества B1 на попарно непересекающиеся классы эквивалентных элементов либо заданием одного или нескольких классов неразличимых (эквивалентных) элементов.

В случае рассматриваемого примера с диаграммой рис. 5.7 дополнительная информация о доминировании может быть следующей:

1. b1 = {A > F, C > H, B > H, H > N, F > N}.

2. Дополнительная информация о безразличии пусть будет такой:

– элементы A, B, C неразличимы, образуют класс эквивалентности Кл. 1;

– элементы F, H неразличимы, образуют класс эквивалентности Кл. 2.

Третий этап. Строят диаграмму отношения порядка для упорядоченного множества B1. Если она линейна, то определяют наибольший элемент и тем самым находят решение рассматриваемой задачи. Если диаграмма имеет несколько максимальных элементов, то повторно выполняются все этапы метода. Циклическое повторение этапов метода продолжается до тех пор, пока не будет получена линейная диаграмма.

Для рассматриваемого примера получаем линейную диаграмму (рис. 5.8).

Рис. 5.8. Преобразованная диаграмма рис. 5.7 после применения принципа недоминируемости и внесения дополнительной информации

Очевидно, что в качестве лучшего элемента может быть взят любой их трех элементов: A, B или C.

< Предыдущая		Следующая >