Пусть на множестве А задано отношение нестрого предпочтения R и пусть В – подмножество А. Тогда объект (элемент) а*ÎВ называется наилучшим (оптимальным) по отношению R, если он не менее предпочтителен, чем любой другой объект из В.
а*Rа – для любого а ÎВ
Наилучший объект единственен с точностью до эквивалентности I, т.е. если в* тоже является наилучшим на множестве В, то а*Iв*.
Если нужно провести выбор одного объекта из В, то можно взять любой из наилучших.
Если отношение R не является связанным квазипорядком, то наилучших элементов может не оказаться даже в конечном множестве В.
Пример: если мн-во В={a,b,c}, и отношение R={(a,a),(b,b),(c,c),(b,c)}, то в В наилучшего элемента нет, т.к. нет информации об отношениях между а и с (или а и b).
В таких случаях используется понятие максимальный объект.
ТЛекция №15
Объект а0ÎА называется max-м по отношению Р относительно В, если в В не существует объекта а строго более предпочтительного, чем а0, т.е. если аРа0не имеет место ни при каком, аÎВ. Иногда это решение называют недоминируемым. Множество максимальных из множества В по отношению Р: maxpB
Характеристикиmax-ых объектов
Множество максимальных объектов maxpBвнутренне устойчиво в том смысле, что если объекты а,bÎ maxpB ,то не может быть ни аРВ, ни bPa. (нет доминирующих альтернатив над а,b).
Множество maxpB называется внешне устойчивым, если для любого объекта а,bÎ B, который не является максимальным, найдется более предпочтительный максимальный объект, т.е. будет а0Ра для некоторого а0 Î maxpB.
Внешне и внутренне устойчивое множество maxpB называется ядром отношений Р в В.
Если множество maxpB не является внешне устойчивым, то для утверждения о том, что выбор следует ограничить рамками этого множества, нет основания (т.е. наилучший объект может Ï этому множеству)
В тех случаях, когда требуется выбрать не один наилучший, а несколько лучших объектов или упорядочить объекты по предпочтительности, понятие максимального объекта и ядра, теряют свое значение.
Пример:если требуется выбрать два объекта, то нельзя утверждать, что все они должны быть максимальными по Р: Пусть В={a,b,c} и P={(a,c)}, тогда maxpB ={a,b}. Т.к. ничего не знаем о b, то он попадает в maxpB.
Однако если требуется выбрать два лучших объекта, то отбрасывать с нельзя, если принимающий решение дополнительно сообщит, что с предпочтительнее чем b, то искомыми окажутся объекты а и с.
P={(a,c),(c,b)}, сначала находим наилучший первый элемент – а, и убираем его из множества В; затем из (c,b) выбираем наилучший – с.
Объект а* ÎВ называется наихудшим на множестве В, если для любого а ÎB верно соотношение аRa*. Объект а0 называется минимальным по отношению Р относительно В, если ни для одного а ÎB не выполняется соотношение а0Ра.
Множество min-х по Р объектов из В – minpB.
Характерной особенностью языка бинарных отношений является допущение о том, что результат сопоставления по предпочтению двух объектов не зависит от состава всего множества выбора А.
В ряде случаев такая зависимость имеет место и для её учета приходится использовать другой язык описания предпочтений, основанный на использовании функции выбора.
Для многокритериальных задач максимизации на множестве допустимых оценок критериев введем отношения:
· Нестрого предпочтения:
a_³b – а нестрого предпочтительнее, чем b если аi³bi , i=1…n, по всем локальным критериям оценка аi не хуже оценки bi
· Два отношения строго предпочтения:
a>b - а строго предпочтительнее, чем b, если аi>bi , - нет лучше аi для всех i=1…n,
а ³b - а строго предпочтительнее, чем b, если аi>bi , для всех I и хотя бы для одного аj>bj
В соответствии с данными выше определениями оценка y*ÎY называется наилучшей по отношению нестрого предпочтения вида _³, если для любого yÎY, выполняется y*³_y.
Т.к. отношение ³ является порядком, то может существовать только одна такая оценка (решение) y*. Но оценка y* не всегда присутствует во множестве допустимых оценок из-за того, что порядок _³ не является полным.
Поэтому в зависимости от существа задачи приходится использовать оценки максимальные по ³ или по >.
Оценка y0ÎY (Y- множество оценок), называется максимальной по отношению строгопредпочтения (³, >), относительно Y, если не существует оценки yÎY, такой что y³y0, y>y0.
Оценка максимальная по отношению ³ называется эффективной или оптимальной по Парето. Множество всех таких оценок из Y – P(Y) – эффективное множество.
Оценка максимальная по отношению > называется слабоэффективной или слабо оптимальной поПарето или оптимальной по Слейтору. Множество всех таких оценок из Y – S(Y) – слабо эффективное множество.
Т.к. из отношения, а>b следует, что верно отношение, а ³b, то всякая эффективная относительно Y векторная оценка является и слабо эффективной:
Найти множества S и Р:
P(Y): y’³y.y’ по всем не хуже, а по одному лучше. Если y’ нет, то yÎP(Y).S(Y): y’>yy’ по всем лучше. Если y’ нет, то yÎS(Y).
P(Y)ÍS(Y)