Наилучшие решения

Пусть на множестве А задано отношение нестрого предпочтения R и пусть В – подмножество А.

Тогда объект (элемент) а^*В называется наилучшим (оптимальным) по отношению R, если он не менее предпочтителен, чем любой другой объект из В.

а^*Rа – для любого а В

Наилучший объект единственен с точностью до эквивалентности I, т.е. если в^* тоже является наилучшим на множестве В, то а^*Iв^*.

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

Если отношение R не является связанным квазипорядком, то наилучших элементов может не оказаться даже в конечном множестве В.

Пример: если мн-во В={a,b,c}, и отношение R={(a,a),(b,b),(c,c),(b,c)}

То в В наилучшего элемента нет, т.к. нет информации об отношениях между а и с (или а и b).

В таких случаях используется понятие максимальный объект.

Объект а⁰А называется max-м по отношению Р относительно В, если в В не существует объекта а строго более предпочтительного, чем а⁰,

Т.е. если аРа⁰не имеет место ни при каком, аВ.

Иногда это решение называют недоминируемым.

Множество максимальных из множества В по отношению Р: max_pB

Характеристики max-ых объектов

Множество максимальных объектов max_pB внутренне устойчиво в том смысле, что если объекты а,b max_pB ,то не может быть ни аРВ, ни bPa.

(нет доминирующих альтернатив над а,b).

Множество max_pB называется внешне устойчивым, если для любого объекта а,b B, который не является максимальным, найдется более предпочтительный максимальный объект, т.е. будет а⁰Ра для некоторого а⁰  max_pB.

Внешне и внутренне устойчивое множество max_pB называется ядром отношений Р в В.