численные методы. Задача принятия решений общая постановка, примеры

• Название: Задача принятия решений общая постановка, примеры
• Анкор: численные методы
• Дата: 17.11.2021
• Размер: 1.64 Mb.
• Имя файла: Chast_1 (1).doc
• Тип: Задача; #274613
• страница: 4 из 7

3. Если , , то .

4. Для и из примера 3: .

5. 1.Если , то .

2. Если , то .
6. 1.Если , то .

2. Если , то .

7. Пусть , , где Z – множество целых чисел. Пара , если существует такое, что , . В качестве такого z можно выбрать . Таким образом, = .

8.Отношение является сужением отношения на множество целых чисел Z.
2.3. Свойства отношений

1. 
   Отношение R называется рефлексивным, если . Другими словами, если для любого выполнено: .
   

Для рефлексивного отношения R справедливо: ; в графе G(R) в каждой вершине имеется петля; , , .

2. 
   Отношение R называется антирефлексивным, если  (или ). Другими словами, если , .
   

Для антирефлексивного отношения R справедливо: ; в графе G(R) петли отсутствуют; , , .

3. 
   Отношение R называется симметричным, если , т.е. если , то , .
   

Для симметричного отношения R справедливо: ; в граф G(R) вместе с дугой входит дуга ; .

4. 
   Отношение R называется асимметричным, если , т.е. если , то , .
   

Для асимметричного отношения R справедливо: ; в граф G(R) дуги и одновременно входить не могут; для любых и сечение не содержит x.

5. 
   Отношение R называется антисимметричным, если , т.е. , только тогда, когда .
   

Для антисимметричного отношения R справедливо: , если ; в граф G(R) дуги и при одновременно входить не могут; для любых и ( ) сечение не содержит x.

6. 
   Отношение R называется транзитивным, если , т.е. если , , то .
   

В матрице транзитивного отношения Rдлялюбых i, k: ; в графе существует дуга (x, y), если существует путь от x к y; для любых и справедливо .

7. 
   Отношение R называется отрицательно транзитивным, если транзитивно.
   
8. 
   Отношение R называется сильно транзитивным, если оно одновременно транзитивно и отрицательно транзитивно.
   
9. 
   Отношение R называется ацикличным, если , , то есть из , , …, следует .
   
10. 
    Отношение R называется связным (полным), если для любых элементов выполнено или .
    

Связи между свойствами бинарных отношений

1. 
   Если отношение рефлексивно (симметрично, антисимметрично, асимметрично, транзитивно), то – рефлексивно (симметрично, антисимметрично, асимметрично, транзитивно).
   
2. 
   Если отношение рефлексивно, то – антирефлексивно и если антирефлексивно, то – рефлексивно.
   
3. 
   Отношение асимметрично тогда и только тогда, когда связно.
   
4. 
   Если отношение асимметрично, то оно антирефлексивно.
   
5. 
   Оъединение и пересечение произвольного числа рефлексивных (антирефлексивных, симметричных) есть отношение рефлексивное (антирефлексивное, симметричное).
   
6. 
   Отношение отрицательно транзитивно тогда и только тогда, когда транзитивно.
   
7. 
   Если бинарное отношение антирефлексивно и транзитивно, то оно асимметрично.
   
8. 
   Если отношение асимметрично и отрицательно транзитивно, то оно транзитивно.
   

Примеры_1.'>Примеры

1. Отношения «быть не старше», «быть похожим», являются рефлексивными.

2. Антирефлексивными являются следующие отношения: «быть моложе», «быть родителем», .

3. Отношения: «быть родственником», симметричные.

4. Отношение асимметрично.

5. Отношение антисимметрично.

6. Отношения: , , являются транзитивными.

Отношение «выиграть футбольный матч» транзитивным не является.

7. Отношение , заданное графом:

1 2

3. 
   ,
   

является ацикличным.

Отношение , заданное графом

2

1. 
   3 ,
   

ацикличным не является, так как , , .


2.4. Специальные типы бинарных отношений

Для определения вышеперечисленных отношений воспользуемся таблицей.

Свойства Отношения	Реф-лексив-ность	Анти-рефлек-сивность	Симмет-ричность	Асим-метрич-ность	Антисим-метрич-ность	Тран-зитив-ность	Связность
Толерантность	+		+
Эквивалентность ()	+		+			+
Доминирование (<<)		+		+
Строгий порядок (<)		+		+		+
Нестрогий порядок ( )	+				+	+
Линейный порядок	+				+	+	+
Квазипорядок	+					+

Примеры

1. Отношение «быть похожим» является отношением толерантности.

2. Отношения «учиться на одном курсе», «иметь одинаковый остаток при делении на 3», отношение подобия являются отношениями эквивалентности.

3.Отношения «быть не ниже ростом», являются отношениями нестрогого порядка.

4.Отношения «быть старше», являются отношениями строгого порядка.

5. Отношение «выиграть матч» является отношением доминирования.

6. Отношение «быть не хуже» и отношение предпочтения являются отношениями квазипорядка.
2.5. Понятие R-оптимальности

Важное место в теории выбора и принятия решений занимает понятие «лучшего элемента». Для формализации этого понятия введем в рассмотрение следующие определения.

Элемент x называется максимумом по отношению R, заданному на множестве X, если для всех выполнено: .

Элемент x называется минимумом по отношению R, заданному на множестве X, если для всех выполнено: .

Элемент называется мажорантой (минорантой) по отношению R, заданному на множестве X, если для всех выполнено: ( ).

Множество мажорант обозначается или и называется множеством недоминируемых по R элементов или множеством R-оптимальных элементов. Множество минорант обозначается ; множество минимумов обозначается , а множество максимумов или .
Примеры

1. Отношение не имеет ни максимумов, ни минимумов; отношение имеет минимум x=0 (так как , ), но не имеет максимума.
2.6. Метризованные бинарные отношения

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

Метризованным отношением называется пара , где – бинарное отношение на множестве ; – множество чисел, характеризующих степень предпочтительности альтернативы относительно альтернативы , либо степень эквивалентности альтернатив и .

Граф метризованного бинарного отношения отличается от графа бинарного отношения R наличием числа над каждой дугой, соединяющей вершины i и j.

Матрицей смежности бинарного отношения является квадратная матрица , с элементами


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

Метризованное отношение называется аддитивным, если для любой тройки индексов i, j, l таких, что , справедливо: и .

Метризованное отношение называется мультипликативным, если для любой тройки индексов i, j, l таких, что , справедливо: и .

Для метризованного аддитивного бинарного отношения числа показывают, на сколько элемент превосходит элемент , а для мультипликативного - во сколько раз.

называется метризованным отношением квазипорядка (толерантности, эквивалентности, строго порядка, нестрогого порядка, доминирования), если R является отношением квазипорядка (толерантности, эквивалентности, строго порядка, нестрогого порядка, доминирования).

Матрицу аддитивного метризованного отношения квазипорядка записывают также в следующем виде:


а матрицу мультипликативного отношения квазипорядка в виде:


Примеры

1. 
   Аддитивным метризованным отношением квазипорядка является отношение, заданное следующим графом:
   

3 0




0

5 2 4
3 2

0 0 0



Матрица данного отношения имеет вид:
.
2. Мультипликативным метризованным отношением квазипорядка является отношение, заданное следующим графом:




1

6 4

1 1

12

2 3


1



Матрица данного отношения имеет вид:
.

Упражнения к § 2

1. 
   Основные упражнения
   

1. Пусть . Отношение . Задать отношение R:

1) матрицей; 2) сечениями.

2. Пусть . Доказать, что:

1. 
   , ;
   

2) ; .

3. Доказать, что ; .

4. Доказать, что .

5. Доказать, что для любых отношений , справедливо:

1. 
   = ;
   
2. 
   = .
   

6. Доказать, что ; .

7. Доказать, что .

8. Рассмотрим матрицу произведения отношений. Доказать, что , где произведение матриц , определяется по следующей формуле:

. (*)

9. Бинарные отношения , заданы матрицами:

, .

Построить матрицу отношения .

10. 
    Доказать, что отношение R симметрично тогда и только тогда, когда .
    

11. Доказать, что если отношение R асимметрично, то оно антирефлексивно.

12. Найти максимум, минимум, миноранты, мажоранты бинарных отношений, заданных графами:

1) : а




;

b c

2 ) : a
;

b c

3. 
   :
   

a

b c .

13. Доказать, что максимум по частичному порядку единственен. Верно ли это утверждение для произвольного R?

14. Могут ли одновременно существовать : 1) максимумы и мажоранты; 2) минимумы и миноранты.

15. 
    15. Доказать, что: 1) ; 2) .
    
16. 
    16. Бинарные отношения, заданными графами, дополнить до аддитивных и мультипликативных метризованных отношений квазипорядка:
    

1)

4

2

2 3


2)






5

2 4 4


II. Дополнительные упражнения

1. 
   Пусть . Бинарные отношения:
   

1. 
   ;
   
2. 
   задать
   

а) матрицей смежности; b) графом; c) сечениями.

2. 
   Изобразить на плоскости следующие бинарные отношения:
   

1. 
   ;
   
2. 
   ;
   
3. 
   ;
   
4. 
   ;
   
5. 
   ;
   
6. 
   ;
   
7. 
   ;
   
8. 
   ;
   
9. 
   ;
   

10) ;

11) ;

12) .

Выписать верхние и нижние сечения бинарных отношений из пп. 1), 2), 4), 6), 7), 11).

3. 
   Вывести формулу, выражающую нижнее сечение через верхние сечения .
   
4. 
   Какими особенностями обладают матрица, граф, сечения антидиагонального отношения?
   
5. 
   Сколько можно выписать матриц смежности для бинарного отношения, заданного на множестве n элементов? Показать, что отношение R, для которого матрица A(R) не зависит от нумерации элементов множества , либо пустое, либо полное, либо диагональное, либо антидиагональное.
   
6. 
   Для отношений из №2 указать полные, пустые, диагональные, антидиагональные отношения.
   
7. 
   Для бинарных отношений из № 2 выписать все пары вложенных отношений. Указать все пары взаимодополнительных отношений. Для пп. 1) – 5) выписать дополнительные, обратные и двойственные отношения.
   
8. 
   Для бинарных отношений из №1 найти: дополнение, пересечение, объединение, обратные, двойственные отношения, произведение отношений. Для каждого бинарного отношения найти матрицу смежности, граф, сечения.
   
9. 
   Доказать, что для любых и : ;
   

.

10. 
    Доказать, что .
    
11. 
    Отношения R и связаны соотношением двойственности. Доказать, что:
    

1. 
   1) ; 2) ; 3) .
   

12. 
    Какой вид имеет отношение , когда R – отношение "меньше" на множестве действительных чисел? Когда R – произвольное отношение?
    
13. 
    Для отношений и , заданных матрицами: ; , найти .
    
14. 
    Доказать, что если R рефлексивно, то – антирефлексивно; если R – антирефлексивно, то рефлексивно.
    
15. 
    Доказать, что для рефлексивного отношения R транзитивность эквивалентна равенству .
    
16. 
    Какие из отношений №2 являются транзитивными?
    
17. 
    Привести пример антисимметричного отношения, которое при этом не симметрично и не асимметрично.
    
18. 
    Описать отношение, являющееся одновременно симметричным и антисимметричным.
    
19. 
    Привести пример отношений, обладающих в точности одним, двумя, тремя и четырьмя свойствами из числа следующих: рефлексивность, симметричность, транзитивность, антисимметричность.
    
20. 
    Показать, что всякое ацикличное отношение асимметрично.
    
21. 
    Сформулировать условия на матрицу, граф и сечения отрицательно транзитивного отношения.
    
22. 
    Пусть R – отношение эквивалентности на множестве . Доказать, что:
    

1. 
   ; 2) если , то ; 3) если , то .
   

23.Для бинарных отношений, заданных на множестве графами или матрицами, проверить выполнение всех свойств:

1. 
   ; 2) ; 3) ; 4) ;
   

5) :








6) :
1 3

2. 
   4 .
   

Являются ли перечисленные отношения отношениями эквивалентности, строгим порядком, нестрогим порядком, квазипорядком, доминированием?

24.Пусть R – произвольное отношение на множестве . Доказать:

1. 
   ; ; 2) ; .
   

25. Найти максимумы, минимумы, мажоранты, миноранты для следующих бинарных отношений:

1) a d



;

f

c

b g

b

2) c

;

a d

3)




a b .