Отношений и операторов

На прошлом занятии мы познакомились с предметом задачи выбора. Альтернативы, среди которых осуществляется выбор, мы описали при помощи набора критериев. В такой постановке задачи принятие решения осуществляется выбором альтернативы, максимизирующей значения критериев. В случае однокритериальной задачи выбора сложностей не возникает. Однако на практике качество той или иной альтернативы редко выражается значением единственного критерия. А принятие решений в многомерных задачах оказывается непростым. Мы изучили основные методами принятия решений для многокритериальной задачи выбора: 1. Сведение многокритериальной задачи к однокритериальной. Введение суперкритерия, являющегося функционалом всех критериев задачи 2. Условная максимизация Нахождение условного экстремума основного критерия при заданных ограничениях на второстепенные критерии. 3. Поиск альтернативы с заданными свойствами. Значения для критериев задаются точно или в виде верхних и нижних границ – уровней притязаний. Точку пересечения уровней притязаний называют целью или опорной точкой. Принятие решения состоит в приближении к цели по некоторой траектории в пространстве. Понятие «близости» определяется введением на пространстве значений критериев некоторой меры расстояния. 4. Нахождение паретовского множества альтернатив. Из множества всех альтернатив исключаются те альтернативы, для которых существует альтернатива лучшая хотя бы по одному из критериев. Оставшееся множество называют паретовским множеством. Этот метод не приводит к выбору единственной альтернативы, но обычно существенно сужает задачу выбора. Бинарные отношения Примерами бинарных отношений являются известнее отношения порядка (<), равенства (=), неравенства. Давайте дадим строгое математическое определение понятия бинарное отношение. Определение. Бинарное отношение R на множестве Х определяется как некоторое подмножество упорядоченных пар (х, у), таких, что х находится в отношении R с у, записывается xRy. Если х и у не находятся в бинарном отношении R, то мы пишем xRy. Очевидно, что R – это подмножество ХхХ. Способы задания бинарных отношений: 1. Непосредственное перечисление пар элементов множества Х, находящихся в бинарном отношении R, определенном на множестве Х. 2. Матричное задание бинарного отношения. Если множество X конечно, все элементы этого множества нумеруются: X={x1…xn}. Затем, определяется матрица А размера nxn, такая что aij={1: xiRxj; 0: xiRxj } для всех индексов i и j. 3. Графовое представление бинарного отношения. Пусть множество X конечно. Для бинарного отношения R, заданного на множестве Х, определим ориентированный граф G(R) следующим образом. Все элементы множества Х представлены вершинами графа G. Между двумя вершинами x и y существует ребро (x,y) тогда, и только тогда, когда xRy. 4. Сечения. Этот способ задания бинарных отношений используется тогда, когда множество Х бесконечно. Пусть бинарное отношение R определено на множестве Х. Определим два множества: • R+(X)={yŒX| (y,x)ŒR}- верхнее сечение отношения R; • R-(X)={yŒX| (x,y)ŒR}- нижнее сечение отношения R; Бинарное отношение однозначно определяется одним из его сечений. Свойства бинарных отношений Пусть бинарное отношение R задано на множестве Х. Бинарное отношение R называется: • рефлексивным, если xRx для всех xŒX; • антирефлексивным, если xRx для всех xŒX (отношение может выполняться только для несовпадающих элементов); • симметричным, если xRy fi yRx для всех xŒX; • асимметричным если xRy fi yRx для всех x,yŒX; • антисимметричным, если для всех x,yŒX (xRy & yRx) fi x=y; • транзитивным, если для всех x,y,z Œ X (xRy & yRz)fixRz; • отрицательно транзитивным, если отношение R является транзитивным; • сильно транзитивным, если отношение R одновременно транзитивно и отрицательно транзитивно; Мы будем определять типы бинарных отношений через наборы свойств, которые для этих бинарных отношений выполняются. Отношения эквивалентности, порядка и доминирования. Определение. Рефлексивное, симметричное и транзитивное бинарное отношение называется отношением эквивалентности. Отношение эквивалентности принято обозначать символом ~. Примеры: 1. Математическое отношение равенства, определенное на множестве комплексных чисел; 2. Отношение принадлежности к одной студенческой группе, определенное на множестве студентов университета; 3. Отношение «иметь одинаковый остаток от деления на 3», определенное на множестве целых чисел. 4. Отношение «быть ровесниками», определенное на множестве людей. 5. Отношение подобия, определенное на множестве треугольников. Задание на некотором множестве отношения эквивалентности приводит к разбиению этого множества на непересекающиеся подмножества. В каждом из подмножеств содержатся только эквивалентные между собой элементы, а сами подмножества называются классами эквивалентности. X=X1» X2» …» Xn, Xi«Xj = ∅ ¤ i≠j Любые два элемента x, y множества Х эквивалентны (x~y) тогда, и только тогда когда они принадлежат одному классу эквивалентности. Отношение эквивалентности позволяет описать равнозначность двух и более альтернатив. Что же делать, если нам нужно описать предпочтение одной альтернативы перед другой? При описании задачи выбора на критериальном языке, мы всегда делали выбор в пользу альтернативы с максимальным значением критерия. В наших примерах все критерии принимали численные значения. На множестве действительных чисел определено бинарное отношение «меньше или равно» Ј. Мы делали выбор х, если "yŒX q(y)Ј q(x). Является ли это бинарное отношение отношением эквивалентности? Нет! Не выполняется свойство симметричности. Контрпример: 3Ј5, но не верно, что 5Ј3 – не выполняется свойство симметричности.

Определение. Рефлексивное, антсимметричное, транзитивное бинарное отношение называется отношением нестрогого порядка. Отношение нестрогого порядка принято обозначать символом Ј, так же, как и отношение «меньше или равно». Примеры:

1. Уже знакомое нам бинарное отношение «больше или равно», определенное на множестве действительных чисел;

2. Бинарное отношение «не позже чем» определенное на множестве моментов времени;

3. Бинарное отношение «меньше или равно», определенное на множестве действительных чисел;

4. Бинарное отношение «является несобственным подмножеством» некоторого множества, определенное на множестве всех подмножеств этого множества. Это бинарное отношение обозначают символом Х;

5. Бинарное отношение порядка следования лекций определенное на множестве всех лекций, читаемых в некотором университете.

Отношение нестрогого порядка допускает равнозначные элементы. Однако, бывают ситуации, когда нам требуется описать строгое предпочтение, исключить равнозначность, как в случае определения чемпиона. Примером такого бинарного отношения является «строго больше», определенное на множестве действительных чисел (>). Является ли это отношение отношением нестрогого порядка? Нет! Контрпример: Не верно, что 3>3 – не выполняется свойство рефлексивности. Определение. Антирефлексивное, асимметричное, транзитивное отношение называется отношением строгого порядка. Отношение строгого порядка принято обозначать символом <, так же, как и математическое отношение «строго меньше». Примеры: 1. Уже знакомое нам бинарное отношение «строго больше», определенное на множестве действительных чисел; 2. Бинарное отношение «раньше», определенное на множестве моментов жизни одного конкретного дерева; 3. Бинарное отношение «строго меньше», определенное на множестве действительных чисел; 4. Бинарное отношение «является собственным подмножеством» некоторого множества, определенное на множестве всех подмножеств этого множества. Это бинарное отношение обозначают символом Г. 5. Бинарное отношение очередности, определенное на множестве людей, стоящих в очереди. Бинарное отношение строгого порядка обобщается бинарным отношением доминирования. Определение. Антирефлексивное, асимметричное бинарное отношение называется отношением доминирования. Отношение доминирования не так привычно, как отношения эквивалентности и отношения порядка. Тем не менее, именно в таком отношении нередко находятся предметы окружающего нас мира. Например: Ваша собака выполняет ваши команды, а вы выполняете команды своего начальника. Отсюда никак не следует, что ваша собака будет слушаться вашего начальника. Налицо пример нетранзитивного, антирефлексивного и асимметричного отношения доминирования. Следует отметить, что отношения порядка и доминирования могут быть определены, как для всех пар элементов множества Х, так и быть для некоторых пар элементов неопределенными. Например: В приведенном выше примере отношение «выполняет команды» не определено для прохожего и незнакомой ему дворняги. Никто из них не будет выполнять команды другого. Определение. Бинарное отношение порядка, определенное на множестве Х, называется отношением линейного порядка, а множество Х называют линейно упорядоченным. Если это отношение определено для всех пар элементов (x,y)ŒXҐX. В противном случае, это отношение называется отношением частичного порядка, а множество Х называют частично упорядоченным. В природе значительно больше частично-упорядоченных множеств, чем линейно- упорядоченных. Предложите примеры!