- •3.8.3. Метод послідовних поступок
- •2.1. Поняття бінарного відношення
- •2.2. Способи задавання відношень
- •2.3. Операції над відношеннями
- •2.4. Властивості відношень
- •2.5. Відношення еквівалентності, порядку, домінування та переваги
- •2.6. Поняття r-оптимальності, найкращого, найгіршого, максимального та мінімального елементів
- •2.7. Поняття функції вибору. Класи функцій вибору
- •2.8. Функції корисності
- •Багатокритеріальні задачі оптимізації
- •3.1. Загальна постановка багатокритеріальної задачі оптимізації
- •3.2. Поняття ефективної альтернативи
- •3.3. Теоретичне і практичне значення ефективного рішення.
- •3.4. Властивості ефективних альтернатив і способи їх знаходження.
- •3.5. Загальна проблема пошуку компромісних рішень
- •3.5.1. Принципи рівномірності
- •3.5.2. Принципи справедливої поступки
- •3.5.3. Інші принципи оптимальності
- •3.6. Методи нормалізації критеріїв
- •3.7. Способи урахування пріоритету критеріїв
- •3.7.1. Методи урахування жорсткого пріоритету
- •3.7.2. Методи урахування гнучкого пріоритету
- •3.8. Методи розв’язання багатокритеріальних задач оптимізації
- •3.8.1. Методи зведення до узагальненого критерію (методи згортки)
- •3.8.2. Метод головного критерію
- •3.8.3. Метод послідовних поступок
2.4. Властивості відношень
О з н а ч е н н я 2.11. Відношення R називається рефлексивним, якщо для будь-якого .
Відношення «бути схожими», «бути не старшим» є рефлексивними, «бути братом», «бути старшим» – не рефлексивні.
В матриці рефлексивного відношення на головній діагоналі знаходяться одиниці, тобто матриця така, що якщо. Граф рефлексивного відношення обов’язково має петлі у вершинах. Для верхнього й нижнього розрізів справедливо , для всіх x .
О з н а ч е н н я 2.12. Відношення R називається антирефлексивним, якщо означає , для .
В матриці антирефлексивного відношення на головній діагоналі знаходяться нулі, тобто якщо. Граф рефлексивного відношення не має петель у вершинах, і верхні та нижні розрізи задовольняють умові , для всіх x .
Прикладами антирефлексивних відношень будуть відношення «більше», «менше», «бути старшим».
О з н а ч е н н я 2.13. Відношення R називається симетричним, якщо .
Матриця симетричного відношення симетрична, тобто для всіх i, j. У графі всі дуги парні. Для розрізів має місце рівність для всіх x .
Симетричними є відношення рівності, «бути схожим», «вчитися в одній групі».
О з н а ч е н н я 2.14. Відношення R називається асиметричним, якщо (тобто з двох виразів x R y та y R x хоча б один не вірний).
У матриці симетричного відношення для всіх i, j. Тобто з двох симетричних елементів і хоча б один обов’язково дорівнює 0.
Асиметричними, наприклад, є відношення «більше» та «менше».
Зауважимо, що антирефлексивність є обов’язковою умовою асиметричності.
О з н а ч е н н я 2.15. Відношення R називається антисиметричним, якщо x R y та y R x можуть бути вірні одночасно тоді і тільки тоді, коли x = y.
Для матриці антисиметричного відношення справедливо , якщо.
Прикладами антисиметричних відношень будуть відношення «більше або дорівнює», «не більше», «не гірше».
О з н а ч е н н я 2.16. Відношення R називається транзитивним, якщо ( якщо з та випливає ).
Прикладами транзитивних відношень є відношення «більше або дорівнює», «менше», «бути старшим», «вчитися в одній групі».
Умова дає зручний спосіб перевірки транзитивності відношення. Якщо відношення задано матрицею для цього необхідно обчислити матрицю відношення (тобто піднести в квадрат матрицю вихідного відношення) і перевірити умову. Якщо для всіх i, j – відношення транзитивне. Якщо ж умову порушено хоча б для однієї пари індексів i, j – відношення не буде транзитивним.
О з н а ч е н н я 2.17. Відношення R називається ациклічним, якщо , тобто з ... , випливає, що .
Це означає, що граф такого відношення не містить циклів.
О з н а ч е н н я 2.18. Відношення R називається від’ємно транзитивним, якщо його доповнення транзитивне.
О з н а ч е н н я 2.19. Відношення R називається сильно транзитивним, якщо воно водночас транзитивне та від’ємно транзитивне.
Властивості ациклічності та транзитивності особливо важливі у теорії прийняття рішень, тому що вони виражають природні взаємозв’язки між об’єктами. Дійсно, якщо об’єкт х в деякому сенсі не гірше за об’єкт y, а об’єкт y в тому ж сенсі не гірше за об’єкт z, то природно чекати, що об’єкт x буде не гіршим за об’єкт z (транзитивність), і у всякому разі z не краще за x (ациклічність).
П р и к л а д 2.10. Визначити властивості даного відношення
Розв’язування
Дане відношення є рефлексивним, воно не є симетричним, асиметричним та антисиметричним.
Для перевірки транзитивності даного відношення знайдемо добуток даного відношення на себе.
Оскільки , дане відношення не є транзитивним.