Бінарні відношення та їх використання для прийняття рішень

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Реферат

Бінарні відношення та їх використання для прийняття рішень



Вступ

бінарний еквівалентність відношення

Усі задачі характеризуються тим, що прийняття рішень у них являє собою свідомий вибір однієї з можливих альтернатив (залежно від конкретного змісту їх називають стратегіями, планами, варіантами) на основі певного принципу (критерію) оптимальності.

Цей вибір робить особа, яка приймає рішення (ОПР). У ролі такої особи виступають окремі люди або групи людей, що мають право вибору і несуть відповідальність за його наслідки. Це може бути майстер, диспетчер, начальник зміни, керівник підприємства або рада директорів. Беручи за основу наявні дані (у тому числі й математичні розрахунки та дослідження), ОПР вибирає остаточний варіант рішення в межах своєї компетенції.

Отже, будь-який процес прийняття рішень можна охарактеризувати такими елементами:

1. Особа, що приймає рішення.

2. Множина змінних, значення яких вибирає ОПР (варіанти, стратегії, плани, керуючі дії).

3. Множина змінних, значення яких залежать від прийнятого рішення (результати, вихідні змінні ситуації прийняття рішень).

4. Множина змінних, значення яких ОПР не регулює (параметри і зовнішнє середовище).

5. Інтервал часу, протягом якого приймаються рішення.

6. Математична модель задачі прийняття рішення, що являє собою множину співвідношень між параметрами, керуючими діями і вихідними змінними.

7. Обмеження, що описують вимоги, викликані ситуацією прийняття рішення по відношенню до вихідних змінних задачі та керуючих дій.

8. Цільова функція або критерій оптимальності, за допомогою якого оцінюють якість вибраного рішення.

Кожен з цих елементів може характеризуватися різним ступенем невизначеності і залежно від цього будуть отримані різні класи задач прийняття рішень.

Якщо параметри й зовнішні збурення (середовище) залишаються незмінними в часі, то математична модель буде статичною. В іншому випадку модель ситуації прийняття рішень буде динамічною. Опис статичної моделі, можна подати у вигляді графіка, таблиці, функціональної залежності або алгоритму обчислення вихідних змінних. Динамічні моделі описують за допомогою різних класів диференціальних або різницевих рівнянь.

Якщо зовнішні збурення носять невипадковий характер, то маємо детерміновану модель прийняття рішення. Коли ж вони мають випадковий характер, то отримуємо стохастичну модель. У цьому випадку вихідні змінні також будуть випадковими, а їхній розподіл визначатиметься розподілом зовнішніх збурень.

У тому разі, коли множина можливих альтернатив і критерій оптимальності цілком визначені, проблема прийняття рішень зводиться до задачі оптимізації.

Коли ситуація потребує врахування кількох критеріїв - її описують за допомогою задачі багатокритерійної оптимізації.



1. Поняття про бінарні відношення

Найпростіша ситуація, в якій можна зробити обґрунтований вибір з кількох об'єктів, виникає, коли подано один «критерій якості», що дозволяє порівнювати будь-які два об'єкти, точно вказати, який з них кращий, і вибрати той (або ті), для якого цей критерій досягає максимального значення. Однак в більшості реальних ситуацій визначити один такий критерій доволі складно, а інколи взагалі не можливо. Але розглядаючи деякі пари об'єктів, можна назвати кращий з них. У таких випадках кажуть, що ці два об'єкти перебувають у бінарному відношенні. Це поняття дозволяє формалізувати операції попарного порівняння альтернатив, і тому воно широко використовується у теорії прийняття рішень.

Розглянемо деякі вислови, які виражають взаємозв'язки між об'єктами.

1. Тетяна старша за Ігора.

2. Фірми А та В збиткові.

3. Київ розташований південніше від Москви.

Як бачимо, ці вислови описують відношення різного типу:

Наприклад, другий й четвертий означають, що два об'єкти віднесені до одного й того самого класу; перший, третій й п'ятий - відображають порядок об'єктів у системі. Крім того, у всіх п'яти прикладах чітко виділено назви об'єктів і назви відношень. Легко помітити, що коли замість однієї назви об'єкта поставити іншу, можливі такі ситуації:

1) відношення знову буде виконано (Київ розташований південніше від Мурманська);

2) відношення не буде виконуватися (Київ розташований південніше від Одеси);

3) відношення не буде мати сенсу (залізо розташоване південніше від води).

Отже, говорити про відношення ми можемо тільки тоді, коли вміємо виділяти множину об'єктів, на якій воно визначене.

Математично визначення відношення можна сформулювати таким чином:

В и з н а ч е н н я 1. Відношенням R на множині Щ називається підмножина декартового добутку Щ Ч Щ, тобто R ? Щ ².

Задання підмножини R у множині Щ Ч Щ визначає, які саме пари елементів перебувають у відношенні R.

Відношення R, задане на множині Щ, позначимо як: (R, ?). Тут і далі записи типу x R y: або (y, x) ? R, означають, що елементи x та y множини Щ перебувають у відношенні R.

2. Способи задання відношень

Для того, щоб задати відношення (R, ?), необхідно задати всі пари елементів (x, y) ? Щ Ч Щ, які включено в множину R. Крім повного переліку всіх пар, існують три способи задання відношень: за допомогою матриці, графа й розрізів. Перші два способи застосовують, щоб задати відношення на скінченних множинах, задання відношення розрізами може бути застосовано й до нескінченних множин.

Опишемо названі способи задання відношень.

Задання відношення за допомогою матриці. Нехай множина Щ складається з n елементів, R - подане на цій множині бінарне відношення. Пронумеруємо елементи множини Щ цілими числами від 1 до n. Для того, щоб задати відношення, побудуємо квадратну таблицю розміром n Ч n. Її i-й рядок відповідає елементу x _i множини Щ, j-й стовпчик - елементу x _j з множини Щ. На перетині i-го рядка та j-го стовпчика ставимо 1, якщо елемент x_i перебуває у відношенні R з елементом x _j, і нуль в інших випадках, а саме:



П р и к л а д: Нехай X= {1, 2,…, 5,}, R - відношення «більше» на множині Х. Тоді його можна описати у вигляді матриці таким чином:

Задання відношення за допомогою графа. Для того, щоб задати відношення за допомогою графа, поставимо у взаємно однозначну відповідність елементам скінченної множини Щ, на якій визначено відношення, вершини графа x₁,… x_n, (за будь-якою нумерацією).

Провести дугу від вершини x_i до x_j, можна тоді й тільки тоді, коли елемент x_i перебуває у відношенні R з елементом x_j, коли ж i = j, то дуга (x_i, x _j) перетворюється на петлю при вершині x_i.

П р и к л а д: Задамо відношення з прикладу 1 за допомогою графа.

Рис. 1. Задання відношення «більше» на множинi: Х= {1, 2, 3, 4, 5}, за допомогою графа



Отже, коли задано будь-який орієнтований граф G, що має n вершин, і вибрано нумерацію на множині Щ, яка складається з n елементів, то тим самим на цій множині задано деяке відношення: R = R (G), а саме, твердження x_i R x_j буде справедливим тоді і тільки тоді, коли в графі G наявна дуга (x_i, x_j). Отже, граф виступає як геометричне зображення відношення.

Задання відношень за допомогою розрізів. Розглянемо відношення R на множині Щ.

В и з н а ч е н н я 2. Верхнім розрізом відношення (R, Щ) в елементі x, позначене через R⁺ (x), називається множина елементів y ? Щ, для яких виконано умову: (y, x) ? R, тобто:

В и з н а ч е н н я 3. Нижнім розрізом R^? (x) відношення (R, Щ) в елементі х називається множина елементів y ? Щ, для яких (x, y) ? R, а саме:

Отже, верхній розріз (множина R⁺) являє собою множину всіх таких елементів y, що перебувають у відношенні R з фіксованим елементом х (y R x). Нижній розріз (множина R^?) - це множина всіх таких елементiв у, з якими фіксований елемент х перебуває у відношенні R (x R y).

Таким чином, для того, щоб задати відношення за допомогою розрізів, необхідно описати всі верхні або всі нижні його розрізи. Тобто відношення R буде задано, якщо для кожного елемента x ? Щ задано множину R⁺ (x) або для кожного елемента x ? Щ задано множину R^?(x).

П р и к л а д: Нехай задано множину: Щ = {1, 2, 3,…, 10}. Відношення R означає «бути дільником», тобто x R y, якщо х - дільник y. Задати це відношення можна в такий спосіб:

за допомогою верхніх розрізів:

або за допомогою нижніх розрізів:

Розглянемо відношення спеціального вигляду та описані вище способи їх задання. Відношення називається порожнім (позначається ?), якщо воно не виконується для жодної пари (x, y) ? ЩЧЩ.

Для порожнього відношення справедливі такі твердження:

1. У матриці А (?) величини a_i,j (?) = 0 для всіх значень i, j.

2. Граф G(?) не має дуг.

3. R⁺ (х) = R^? (х) = ? для всякого елемента x ? Щ.

Відношення називається повним (позначається U), якщо воно виконується для всіх пар (x, y) ? ЩЧЩ. Для повного відношення правильні такі ознаки:

1. У матриці А(U) величини a_i,j (U) = 1 для всіх значень i, j.

2. У графі G(U) дуги з'єднують будь-яку пару вершин.

3. Розрізи R⁺ (х) = R^? (х) = Щ для всіх елементів x ? Щ.

Відношення називається діагональним або відношенням рівності (позначається E), коли воно виконується для всіх пар (x, y) ? ЩЧЩ, які складаються із збіжних елементів. Тобто x E y, якщо x та y - це один і той самий елемент множини Щ. Для діагонального відношення Е мають місце такі твердження:

1. У матриці А (Е)

2. У графі G(Е) наявні тільки петлі при вершинах, інші дуги відсутні.

3. Розрізи R⁺ (х) = R^? (х) = x для всіх елементів x ? Щ.

Відношення називається антидіагональним (позначається Е), коли воно виконується для всіх пар (x, y) ? ЩЧЩ, які складаються із незбіжних елементів. Для відношення Е справедливі такі ознаки:

1. У матриці А (Е)

2. У графі G(Е) наявні всі дуги (x_i, x_j), якщо i ? j (відсутні тільки петлі при вершинах).

3. Розрізи R⁺ (х) = R^?(x)= Щ \{x} для всіх елементів x ? Щ.

3. Операції над відношеннями

В и з н а ч е н н я 4. Відношення R ₁ включено у відношення R₂ (записується як R ₁?R₂), коли множину пар, для яких виконується відношення R₁, включено в множину пар, для яких виконується R₂.

Будемо говорити, що відношення R ₁ строго включено в R₂ (R ₁<R₂), якщо R ₁?R₂ й R₁?R₂. Рівність відношень реалізується так само, як і рівність множин.

Для матричного задання відношень буде діяти таке правило: якщо R ₁?R₂, то a _ij (R ₁) ? a _ij(R₂), j i, = 1, n.

П р и к л а д: R₁ - відношення «?» на множині дійсних чисел, R₂ - відношення «<» на тій самій множині. Тоді R₂? R₁.

Визначення 5. Відношення R називається доповненням відношення R, тоді і тільки тоді, коли воно пов'язує тільки ті пари елементів, для яких не виконується відношення R.

Очевидно, що

Тому в матричному записі a_ij (R) = 1? a_ij (R), i, j= 1, n.

У графі G (R) наявні ті і тільки ті дуги, що відсутні у графі G (R).

Для розрізів відношення R справедливі такі твердження:

Приклад: Нехай R - відношення «?», задане на множині дійсних чисел, тоді R - відношення «<», задане на тій самій множині.

В и з н а ч е н н я 6. Перетином відношеннь R₁ та R₂ (записується R₁ ? R₂) називається відношення, визначене перетином відповідних підмножин множини Щ².

У матричному записі це означає, що



Визначення 7. Об'єднанням відношень R₁ та R₂ (позначається R₁ ? R₂) називається відношення, отримане шляхом об'єднання відповідних підмножин множини Щ².

В матричному записі це можна подати таким чином:

В и з н а ч е н н я 8. Оберненим до відношення R називається відношення R^?1, яке задовольняє таку умову:

Для матриць відношень R та R^?1 буде мати місце така формула:

Приклад: Нехай R - відношення «?» на множині дійсних чисел. Тоді оберненим до нього відношенням R^?1 буде відношення «?» на множині дійсних чисел.

Приклад: Нехай відношення R на множині: Х ={x₁, x₂, x₃, x₄, x₅}, задано матрицею:

Побудувати відповідні йому обернене відношення та доповнення.

Розв'язування

Згідно з визначенням 5 доповнення відношення R можна задати такою матрицею:

Обернене відношення будуємо за визначенням 8, отже,

Визначення 9. Добутком (або композицією) відношень R₁ та R₂ (позначається як R₁ЕR₂) називається відношення, яке будується за таким правилом: x (R₁Е R₂) y, коли існує елемент z ? Щ, який задовольняє умови x R₁ z та z R₂ y.

Приклад: Розглянемо відношення R₁ та R₂, подані на множині дійсних чисел. Причому, R₁ - відношення «менше», R₂ - відношення «більше». Пара чисел (x, y) ? R₁ Е R₂, коли існує число z, для якого виконано такі вимоги:

x < z та z > y. Вочевидь, ця умова виконується для всіх чисел x, y, а тому R₁ Е R₂ - це повне відношення (тобто таке, яким пов'язані всі елементи даної множини).

Приклад: Нехай множина Х ={x₁, x₂, x₃, x₄, x₅}, на ній подано два відношення R₁ та R₂, а саме:

Визначити їх композицію.

Розв'язування

Згідно із визначенням 9 x (R₁ ? R₂) y, коли існує елемент z ? Щ, який задовольняє умови x R₁ z та z R₂ y. У матричному записі це означає, що

де n - порядок матриці.

Інакше кажучи, композиція відношень обчислюється як максимінний добуток відповідних їм матриць.

Тоді отримуємо, що

Визначення 10. Відношення (R₁,Щ₁) називається звуженням відношення (R, Щ) на множину Щ₁, якщо Щ₁ ? Щ та R₁ = R ? Щ₁ Ч Щ₁. Звуження відношення (R, Щ) на множину Щ₁ називають також відношенням R на множині Щ₁.

Приклад 2.9. Відношення «>» на множині натуральних чисел є звуженням відношення «>» на множині дійсних чисел.

4. Властивості відношень

Визначення 11. Відношення R називається рефлексивним, якщо x R x для будь-якого елемента x ? Щ.

Наприклад, відношення «бути схожими», «бути не старшим», «менше або дорівнює» - рефлексивні; «бути братом», «бути старшим», «більше» - не рефлексивні.

У матриці рефлексивного відношення на головній діагоналі розміщуються одиниці, тобто елемент матриці a_ij = 1, якщо i = j.

Граф рефлексивного відношення обов'язково має петлі при вершинах. Стосовно верхнього й нижнього розрізів справедливі твердження: x ? R⁺ (x), x ? R^? (x) для всіх елементів x ? Щ.

Визначення 12. Відношення R називається антирефлексивним, коли твердження x R y означає, що x ? y для ?x ? Щ.

У матриці антирефлексивного відношення елементи головної діагоналі дорівнюють нулю, тобто a_ij = 0, якщо i = j.

Граф антирефлексивного відношення не має петель при вершинах, а верхні та нижні розрізи задовольняють такі умови: x ?R⁺(x), x ?R^?(x) для всіх елементів x ? Щ.

Антирефлексивними будуть відношення «більше», «менше», «бути старшим».

Визначення 13. Відношення R називається симетричним, якщо R= R^?1 (x R y ? y R x).

Матриця симетричного відношення симетрична, тобто a_ij = a_ji для всіх значень i, j. У графі такого відношення всі дуги парні, а верхні й нижні розрізи збігаються для всіх елементів x ? Щ, тобто R⁺ (x) = R^? (x) для всіх x ? Щ.

Симетричними є відношення рівності, «бути схожим», «вчитися в одній групі».

Визначення 14. Відношення R називається асиметричним, якщо R ? R^?1= ­ (тобто з двох виразів x R y та y R x хоча б один не відповідає дійсності).

У матриці симетричного відношення a_ji ? a_ij = 0 для всіх значень i, j. Тобто з двох симетричних елементів a_ij і a_ji хоча б один обов'язково дорівнює 0.

Асиметричними, наприклад, є відношення «більше» та «менше».

Зауважимо, що антирефлексивність - це обов'язкова умова асиметричності.

Визначення 15. Відношення R називається антисиметричним, якщо твердження x R y та y R x можуть бути правильними одночасно тоді і тільки тоді, коли x = y.

У матриці антисиметричного відношення a_ij ? a_ji = 0, коли i ? j.

Прикладами антисиметричних будуть відношення «більше або дорівнює», «не більше», «не гірше».

Визначення 16. Відношення R називається транзитивним, якщо R² ? R (тобто, коли з тверджень x R z та z R y випливає, що x R y).

Транзитивними є відношення «більше або дорівнює», «менше», «бути старшим», «вчитися в одній групі».

Умова: R² ? R, дає зручний спосіб перевірки транзитивності відношення в разі, коли відношення задано за допомогою матриці. Для цього необхідно обчислити матрицю відношення R² (тобто піднести в квадрат матрицю вихідного відношення) і перевірити умову. Якщо a_ij (R²) ? a_ij (R) для всіх значень i, j, то відношення транзитивне. Коли ж цю умову порушено хоча б для однієї пари індексів i, j, то відношення не буде транзитивним.

Визначення 17. Відношення R називається ациклічним, якщо R^k?R^?1 = ?, тобто з умов, x R z₁, z₁ R z₂…, z_{k ?1} R y випливає, що x ? y.

Це означає, що граф такого відношення не містить циклів.

Визначення 18. Відношення R називається від'ємно транзитивним, якщо його доповнення R транзитивне.

Визначення 19. Відношення R називається сильно транзитивним, якщо воно одночасно транзитивне і від'ємно транзитивне.

Властивості ациклічності й транзитивності відіграють особливу роль у теорії прийняття рішень, оскільки вони виражають природні взаємозв'язки між об'єктами. Дійсно, якщо об'єкт х у деякому сенсі не гірший за об'єкт y, а об'єкт y в тому самому сенсі не гірший за об'єкт z, то природно чекати, що об'єкт x буде не гіршим від об'єкта z (транзитивність), і в будь-якому разі об'єкт z не кращий за об'єкт x (ациклічність).

Приклад: Визначити властивості такого відношення:

Розв'язування

Дане відношення є рефлексивним (оскільки його матриця містить на головній діагоналі тільки одиниці), воно не буде симетричним (тому що серед симетричних елементів є такі, що не дорівнюють один одному, наприклад елементи a₁₂ та a₂₁). Оскільки елемент a₁₃ = a₃₁, то відношення не буде також асиметричним й антисиметричним.

Для перевірки його транзитивності обчислимо добуток даного відношення на себе, тобто

R² R, отже, вихідне відношення не є транзитивним.

5. Відношення еквівалентності, порядку, домінування й переваги

Визначення 20. Відношення R є відношенням еквівалентності (еквівалентністю), якщо воно рефлексивне, симетричне й транзитивне. Позначимо його R_е, або символом ~.

Прикладами відношеннями еквівалентності будуть такі:

? «учитися на одному курсі», «учитися в одній групі», задані на множині студентів факультету;

? «мати однакову остачу при діленні на 3» на множині натуральних чисел;

? відношення подібності на множині трикутників та інші.

Характерним для еквівалентності є те, що вона розподіляє елементи на класи. У першому прикладі - це курси або групи студентів факультету, у другому - множини чисел, що мають однакову остачу при діленні на 3, у третьому - множини подібних трикутників. Отже, задання еквівалентності на множині тісно пов'язане з її розбиттям на неперетинні підмножини. Розглянемо цю властивість еквівалентності докладніше.

Нехай задано деяке розбиття множини ?. Тобто задано підмножини ?₁, ?₂,… ?_N множини ?, які задовольняють умову: Щ =?^N_i=1 Щ_i, причому Щ_i ? Щ_j = ?, коли i ? j, i, j, = 1,2, …, N. Уведемо на множині ? відношення R таким чином: x R y тоді і тільки тоді, коли існує множина ?_i, така, що x ? Щ_i і y ?Щ_i.

З а в д а н н я. Доведіть, що уведене таким чином відношення являє собою еквівалентність.

Як бачимо, задання еквівалентності на деякій множині Щ рівносильне розбиттю цієї множини на класи еквівалентних між собою елементів. І навпаки, будь-яке розбиття множини Щ визначає на ній відповідну йому еквівалентність.

Визначення 21. Відношенням нестрогого порядку «?» (нестрогим порядком) називається відношення, що має властивості рефлексивності, антисиметричності й транзитивності.

Визначення 22. Відношенням строгого порядку «<» (строгим порядком) називається відношення, яке має властивості антирефлексивності, асиметричності й транзитивності.

Якщо на множині Щ задано відношення «?», тобто деякий нестрогий порядок, то йому можна поставити у відповідність строгий порядок «<», що визначається за таким правилом: x < y тоді і тільки тоді, коли x ? y та x ? y. І навпаки, якщо «<» - відношення строгого порядку, задане на множині Щ, то йому можна поставити у відповідність відношення «?» таким чином: x ? y тоді і тільки тоді, коли x < y або x = y. Тобто за нестрогим порядком ми можемо визначити відповідний йому строгий порядок і навпаки.

Припустимо, що на деякій множині задано відношення порядку (для всіх, або деяких пар її елементів), тоді кажуть, що на цій множині задано частковий порядок.

Частковий порядок на множині Щ називається лінійним порядком, якщо для будь яких елементів x, y? Щ справедливе одне з трьох тверджень: x < y, x = y або x > y (тобто ми можемо порівняти будь-які два елементи множини Щ).

Визначення 23. Відношенням домінування називається відношення, що має властивості антирефлексивності й асиметричності.

Будемо говорити, що елемент x домінує над елементом y, якщо x в якому-небудь сенсі кращий за y.

Таким чином, відношення строгого порядку являє собою окремий випадок відношення домінування, для якого характерна ще й транзитивність. У загальному ж сенсі при домінуванні як транзитивність так і ациклічність можуть не мати місця.

Визначення 24. Два елементи можна порівняти за відношенням R, коли x R y або y R x. В інших випадках елементи непорівнянні.

Якщо R - повне відношення на множині Щ, то будь-які два елементи цієї множини можна порівняти.

Розглянемо, які порядки можна задати на m-вимірному просторі Е_m:

1. a ? b тоді і тільки тоді, коли a_i ? b_i, i = 1, 2, …, m;

2. a ? b тоді і тільки тоді, коли a_i ? b_i, i = 1, 2, …, m; та a ? b;

3. a > b тоді і тільки тоді, коли i I b a >, m i…, 2, 1 =;

4. a b тоді і тільки тоді, коли a = b або a_i > b_i хоча б для одного значення m i ? {1, 2, …, m};

5. a = b тоді і тільки тоді, коли a_i = b_i, i = 1, 2, …, m.

Відношення 1 являє собою частковий порядок, воно рефлексивне, антисиметричне й транзитивне).

Відношення 2 і 3 - це строгі часткові порядки. Вони антирефлексивні, асиметричні й транзитивні.

Відношення 4 є рефлексивним, але воно не буде ні симетричним ні транзитивним.

Зв'язок між цими відношеннями схематично зображено на рис. 2.2.

Рис. 2. Схема взаємозв'язку між відношеннями у просторі Е_m

Для опису переваги зазвичай використовують такі бінарні відношення, задані на множині альтернатив Щ: строгої переваги, байдужості та нестрогої переваги.

Відношення строгої переваги R^S означає, що один об'єкт (строго) переважає над іншим (тобто один об'єкт кращий від іншого).

Відношення байдужості R^I означає, що об'єкти однакові за перевагами, і коли обмежити вибір цими двома об'єктами, не важливо, який з них буде вибрано.

Відношення нестрогої переваги означає, що один об'єкт не менш переважний, ніж інший (тобто один об'єкт не гірший від іншого).

Припустимо, що за допомогою ОПР або експертів було визначено відношення нестрогої переваги R на множині допустимих альтернатив Х.

Це означає, що відносно будь-якої пари альтернатив (x, y) ? XЧX можлива одна із таких ситуацій:

1) об'єкт х не гірший від об'єкта y, тобто, x > y інакше кажучи (x, y) ? R;

2) об'єкт y не гірший за об'єкт х, тобто y ? x, або (y, x) ? R;

3) об'єкти х та y не порівнянні між собою, тобто (x, y) ? R та (y, x) ? R.

Ця інформація дозволяє звузити клас варіантів раціонального вибору, включивши в нього лише ті альтернативи, над якими не домінує жодна інша альтернатива множини Х.

Щоб пояснити це поняття, визначимо відповідні відношенню переваги R відношення строгої переваги R^S і відношення однаковості (байдужості) I.

Будемо говорити, що альтернатива х строго краща від альтернативи y (має строгу перевагу над альтернативою y), якщо одночасно x ? y та y ? x, тобто

Сукупність усіх таких пар назвемо відношенням строгої переваги R^S на множині Х.

Легко переконатись, що це відношення має задовольняти такі властивості:

1) антирефлексивність,

2) асиметричність.

Для більш компактного запису відношення R^S використаємо визначення відношення R^?1, оберненого до R, а саме, врахуємо, що (x, y) ? R^?1 ? (y, x) ? R.

Тоді відношення строгої переваги може бути записано в такому виглядi:

Відношення однаковості, що відповідає відношенню переваги R, можна визначити таким чином: (x, y) ? R^I тоді і тільки тоді, коли або не виконується жодна з умов: x ? y і y ? x, або одночасно мають місце обидві: x ? y та y ? x. Інакше кажучи, (x, y) ? R^I, коли інформація, яку ми маємо, недостатня для обґрунтованого вибору між альтернативами х та у.

Математично відношення R^I можна записати такою формулою:



Легко побачити, що чим більше інформації про реальну ситуацію або процес, тим вужчим виявляється відношення однаковості.

Приклад: Нехай множина X ={x₁, x₂, x₃, x₄,} на ній подано відношення нестрогої переваги R:

Побудувати відповідні йому відношення еквівалентності, строгої переваги, однаковості.

Розв'язування

Згідно з визначенням, R^e = R ? R^?1. Побудуємо спочатку відношення R^?1:

Тепер знайдемо відношення еквівалентності, а саме:

Як видно з цієї матриці, елементи x₁, x₄ еквівалентні.

Тепер відповідно до визначення знайдемо відношення R^S таким чином:

Це означає, що елемент x₁ строго переважає елемент x₂, елемент x₂ в свою чергу переважніший за x₄, елемент x₃ переважає x₂, а x₄ кращий від x₃ відповідно.

Відношення байдужості знаходимо за такою формулою:



Матриця цього відношення набуває такого вигляду:

Це відношення означає, що серед елементів {x₁, x₃}, {x₁, x₄}, {x₃, x₄} можна вибирати будь-який, тобто інформації для того, щоб здійснити обгрунтований вибір між елементами кожної пари, недостатньо.

Коли (x, y) ? R^S, то будемо говорити, що альтернатива х домінує над альтернативою у (x > y).

Визначення 25. Альтернативу x ? X назвемо недомінованою на множині Х за відношенням R, якщо (y, x) ? R^S, ?y ? X. Тобто якщо альтернатива х - недомінована, то в множині Х не має жодної альтернативи, яка домінувала б над альтернативою х.

У наведеному вище прикладі недомінованою виявилась альтернатива x₁.

Якщо деякі альтернативи у певному сенсі недоміновані, то їх вибір у задачах прийняття рішень доречно вважати раціональним у межах наявної інформації.

Таким чином, інформація у формі відношення переваги дозволяє звузити клас раціональних рішень на множині Х до множини недомінованих альтернатив, яка має такий вигляд:



6. Поняття R-оптимальності, найкращого, найгіршого, максимального й мінімального елементів

Розгянутий вище матеріал мав на меті дати формальний опис попарного порівняння альтернатив, що є необхідною умовою для виділення найкращого елемента (або кількох кращих) з всієї множини альтернатив Х. Тепер формалізуємо саме поняття «кращий», використавши для цього апарат бінарних відношень.

Елемент x* множини Х будемо називати найкращим за відношенням R, якщо x* R x справедливе для всякого елемента x ? X.

Елемент x_* ? X будемо називати найгіршим за відношенням R, якщо x R x_* для всіх x ? X.

Легко впевнитись, що найкращий і найгірший елементи існують не завжди. Зокрема, їх не буде, коли відношення не є повним, як у наведеному нижче прикладі.

П р и к л а д: Розглянемо множину: B = {a, b, c}, і відношення R на ній, яке подано таким чином: R ={(a, a,) (a, b,) (b, b), (c, b)}. Визначити найкращі та найгірші за даним відношенням елементи множини В, якщо такі існують.

Зобразимо описане відношення за допомогою графа (див. рис. 3)

Рис. 3. Граф відношення R

Як бачимо, це відношення не має найкращих і найгірших елементів, бо елементи а та с непорівнянні.

Уведемо поняття максимального елемента.

Елемент x_max називається максимальним за відношенням R^S на множині Х, якщо для абиякого елемента x ? X має місце твердження x_max R^S x, або x_max непорівняний з x.

Іншими словами, не існує елемента (альтернативи) x ? X, який був би кращим за альтернативу x_max.

Множина максимальних за відношенням R елементів множини Х позначається max_R X.

Елемент x_min називається мінімальним відносно R^S на множині Х, якщо для всіх x ? X або x R^S x_min, або х непорівняний з x_min. Отже не існує елемента x ? X який був би гіршим за x_min; немає жодного елемента х, над яким би домінував елемент x_min.

У наведеному вище прикладі максимальним буде елемент а, мінімальним - елемент с.

Множина мінімальних за відношенням R елементів множини Х позначається як min _R X.

Зауважимо, що коли найкращі елементи існують, то вони будуть і максимальними, протилежна ситуація не буде справедливою.

Отже, якщо треба обрати найкращу в деякому сенсі альтернативу, то природним буде її вибір із множини максимальних (недомінованих) альтернатив.

П р и к л а д: Нехай відношення R подано у вигляді графа G (рис. 4). Знайти найкращі, найгірші, максимальні та мінімальні за відношенням R^S елементи.

Найкращих елементів не існує, оскільки елемент e не порівнянний з іншими; найгірших елементів також немає. Максимальними за відношенням R^S є елементи а, d, e. Мінімальними - с, d, e.

Зверніть увагу, що елементи d, e - максимальні й мінімальні одночасно. Це пояснюється тим, що вони непорівнянні з іншими, тобто у нас не має інформації про переваги цих елементів.



Рис. 4. Граф відношення R

Розв'язування

Множина max_R X максимальних за відношенням R об'єктів множини X є внутрішньо стійкою в тому сенсі, що коли a, b ? max_R X, то не може виконуватись жодне з тверджень: a R b та b R a.

Множина називається зовнішньо стійкою, якщо для кожного немаксимального елемента a ? X знайдеться більш переважний від нього елемент серед максимальних. Тобто буде справедливим твердження: a⁰ R a для деякого елемента a⁰? max_R X.

Внутрішньо та зовнішньо стійка множина max_R X називається ядром відношення R у множині X.

Поняття стійкості має велике значення, бо якщо множина max_R X зовнішньо стійка, то оптимальний елемент має бути вибраний саме з цієї множини. Якщо ж вона не є зовнішньо стійкою, то для обмеження нею вибору немає підстав.

Якщо виникає потреба вибрати не один, а кілька кращих елементів, або впорядкувати всі об'єкти за перевагами, то поняття максимального елемента і ядра відношення втрачають своє значення.

П р и к л а д: Припустимо, що множина B = {a, b, c}, і на ній задане відношення: R ={(a, c)}. Тут множина максимальних елементів max _R B = {a, b}. Однак при виборі двох кращих елементів не можна не брати до уваги наявність елемента c, оскільки коли з'явиться інформація, що він переважніший, ніж b, то шуканими будуть елементи a та c.

Числова функція ?, визначена на множині Х називається зростаючою (неспадною) за відношенням R, коли з умови a R b випливає, що ? (a) > ?(b) [відповідно ? (a) ? ?(b)] для всіх елементів a, b ? X.

Має місце таке твердження.

Нехай B ? A і a⁰? B надає неспадній за відношенням R на множині В функції Ш найбільшого на ній значення. Для того, щоб об'єкт a⁰ був максимальним за відношенням R на множині В, достатньо виконання однієї з таких умов:

1. Ш зростає за відношенням R на множині В.

2. a⁰? B - єдина точка максимуму функції Ш на множині В.

Доведення

Припустимо, що елемент a⁰ не є максимальним за відношенням R. Тоді в множині В знайдеться елемент a, який переважає a⁰ за відношенням R, тобто a R a⁰. Але тоді має виконуватись нерівність: Ш (a) ? Ш(a⁰), причому ця нерівність строга, якщо функція Ш зростає за відношенням R на множині В. Але строга нерівність суперечить тому, що елемент a⁰ - точка максимуму функції Ш, а нестрога нерівність - тому що a⁰ являє собою єдину точку максимуму Ш на множині В. Доведення закінчено.

При моделюванні реальних систем можуть мати місце такі ситуації, коли в ОПР або в експертів немає чіткого уявлення про переваги між альтернативами, але їм конче необхідно подати конкретні висновки про те, які з альтернатив є кращими. У цьому випадку експерти змушені певним чином «огрубляти» свої знання та уявлення, і відповідна математична модель буде менш адекватною реальній ситуації.

Більш гнучким способом формалізації таких уявлень є можливість для експертів визначити міру свого переконання в перевазі альтернативи використовуючи числа з інтервалу [0; 1], тобто описати свої думки за допомогою нечіткого відношення переваги, коли кожній парі альтернатив (x, y) відповідає число з інтервалу [0,1], яке відображає міру правильності переваги: x ? y.

Зауважимо, що характерна особливість «мови» бінарних відношень - це припущення про те, що результат порівняння за перевагами двох елементів не залежить від складу всієї множини. Однак у деяких випадках така залежність має місце, і для її врахування необхідна більш багата «мова» опису переваг, основана на використанні функцій вибору.

7. Поняття функції вибору. Класи функцій вибору

У реальних ситуаціях вибору на множині альтернатив ? особа, що приймає рішення, вибирає деяку альтернативу керуючись своєю особистою думкою про кращі альтернативи. У різних людей уявлення про одну й ту саму ситуацію може істотно відрізнятися, але логічно припустити, що в схожих ситуаціях одна й та сама людина буде діяти однаково, і тому є можливість сформулювати правило, за яким буде здійснено вибір.

Розглянемо таку ситуацію: нехай ? - множина альтернатив, серед яких проводиться вибір, а множини альтернатив Х являють собою її підмножини.

Позначимо через () X C множину альтернатив, яку виділяє ОПР, з множини Х.

Наприклад, ? - множина всіх груп у вищому навчальному закладі, Х - довільна підмножина ? (це може бути множина груп ІІІ курсу, множина груп факультету і под.). Вважатимемо, що C (X) - найкраща група з множини груп Х. Незалежно від того, хто приймає рішення (вибирає найкращу групу) природно вважати, що найкраща група закладу буде найкращою групою свого курсу, свого факультету тощо.

Математично це можна записати так: якщо X?? X і x ? C (X) ? X?, то x ? C (X?).

Тобто всілякий вибір у конкретній ситуації можна вважати логічно обґрунтованим, якщо відомі рішення в інших ситуаціях, пов'язаних із даною. Це означає, що множини C (X) виявляються залежними при різних множинах Х, якщо вибір здійснює одна й та сама ОПР. Для формалізації цієї залежності використовують поняття функції вибору.

Функцією вибору C (X) називається відображення, яке ставить у відповідність кожній множині X?Щ її підмножину C (X) ? X.

C (X) будемо інтерпретувати як найбільш переважні альтернативи з множини Х.

Зауважимо, що в цьому визначенні немає ніяких апріорних обмежень на функції вибору, зокрема не виключена можливість пустого вибору, тобто ситуації, коли C (X).

Ця ситуація називається відмовою від вибору.

Її прикладом може бути випадок, коли покупець йде з магазину, нічого не купивши.

В окремому випадку, зокрема, коли відоме відношення строгої переваги R на множині альтернатив, функцію вибору можна визначити такою рівністю:

П р и к л а д: Нехай на множині: X ={x₁, x₂, x₃, x₄,} матрицею задано відношення переваги R, а саме:

Побудувати відповідну цьому відношенню функцію вибору.

Розв'язування

Побудуємо відношення строгої переваги: R^S= R \ R^?1, яке відповідає даному відношенню:

Тепер задамо функцію вибору за таким правилом: C (X) = max_R X. Для цього розглянемо всі можливі підмножини даної множини {x₁, x₂, x₃, x₄,} і визначимо максимальні елементи за звуженням відношення R на відповідні підмножини.

Розглянемо спочатку одноелементні підмножини. Вибір із одного елемента буде тим самим елементом, тому

Далі розглянемо двоелементні підмножини. Звуження даного відношення на множину {x₁, x₂} дає можливість зробити висновок, що елемент x₁ більш переважний, ніж x₂, тому максимальним елементом для цієї множини буде x₁, і тоді



Аналогічно для інших двоелементних множин

і так само

Отже, функцію вибору задано.

Зауважимо, що існують також інші способи задання функцій вибору. Таким чином, за відношенням переваги ми можемо побудувати функцію вибору, але не для всякої функції вибору існує відповідне їй відношення переваги.

П р и к л а д: Функцію вибору задано таким чином:



Як бачимо, дві останні умови суперечать одна одній, тому відношення побудувати неможливо.

П р и к л а д: Функцію вибору задано таким чином:

Відповідним даній функції буде таке відношення строгої переваги:

Функції вибору зручно класифікувати відповідно до тих умов, які зазвичай використовують при їх вивченні.

Приклади таких умов наведено в таблиці 1.

Таблиця 1. Класифікація функцій вибору

1. Умова наслідування
Якщо X? ? X, то C (X?)? C (X) ? X?. Сенс цієї умови такий: якщо розглянути вибір з довільної множини і вибір з деякої її підмножини, то всі альтернативи, які були вибрані з вихідної множини і ввійшли до підмножини, що розглядається, будуть також вибрані з цієї підмножини. Наприклад, якщо проводився міжнародний конкурс і переможцем став проект з Болгарії, то він повинен бути і серед переможців болгарського конкурсу
2. Умова згоди
Ця умова означає, що альтернативи, які були вибрані з кожної множини Xi, будуть вибрані також і з їх об'єднання
3. Умова незалежності від нехтуваних альтернатив
Якщо C (X) ? X? ? X, то C (X) = C (X?) Зміст цієї умови такий: коли розглянути довільну множину X ?, яка містить усі альтернативи, вибрані з множини Х, то вибір з X ? буде такий самий, як і вибір з множини Х Наприклад, коли під час конкурсу проект x не був включений до кращих, то в іншому конкурсі, де беруть участь усі ті проекти, що й у попередньому, за винятком x, склад переможців не зміниться
4. Умова Плотта (незалежність від вибору шляху)
Умова Плотта передбачає, що вибір альтернатив із об'єднання виборів, які в свою чергу зроблені з кожної множини, точно відповідає вибору із об'єднання виборів, які зроблені з кожної множини окремо Наприклад, для проведення міжнародного конкурсу можна спочатку відібрати переможців національних конкурсів, а потім уже влаштовувати змагання серед них
5. Умова суматорності
Ця умова означає, що вибір з об'єднання множин дорівнює об'єднанню виборів з кожної множини окремо Наприклад, на районній дошці пошани відзначено людей, обраних у різних організаціях
6. Умова мультиплікаторності
За цієї умови вибір із перетину двох множин буде дорівнювати перетину виборів
7. Умови монотонності
Якщо X? ? X, то C (X?) ? C (X), тобто вибір з більш широкої множини буде ширшим



8. Функції корисності

Для порівняння різних альтернатив і вибору найкращої з них також можна використовувати деяку кількісну міру їхніх властивостей, за значеннями якої можна порівняти альтернативи між собою та вибрати найкращу. Правила (процедури) прийняття рішень на основі цієї міри використовують теорію корисності, розроблену Дж. фон Нейманом і О. Моргенштерном [5]. Математичною основою даної теорії виступає система аксіом, у яких стверджується існування деякої міри цінності, що дозволяє впорядкувати альтернативи (результати рішень). Така міра називається функцією корисності, або корисністю результатів.

Практичне застосування теорії корисності ґрунтується на таких аксіомах:

1. Результат (альтернатива) х_і є кращою за альтернативу х_j (записується x_i > x_j), тоді і тільки тоді, коли u(x_i) = f(x_i) > u(x_j), де u(x_i) і u(x_j) - значення корисності альтернатив x_i і x_j відповідно.

2. Якщо x_i > x_j, а x_j > x_k, то x_i > x_k, і u(x_i) > u(x_k) (транзитивність).

3. Якщо х₁, х₂ - деякі альтернативи, то u(x₁, x₂) = u(x₁) + u(x₂) (адитивність).

Аналогічно, коли є n результатів x₁, x₂, … x_n, які досягаються одночасно, то

Іншими словами, корисність кількох результатів, які досягаються одночасно дорівнює сумі значень їхніх корисностей.

Визначимо із застосуванням понять функції корисності (цільової функції) f(x) такі відношення на множині альтернатив Х:

- відношення слабкої (нестрогої) переваги «не гірше», яке позначається символом ?,

- відношення рівноцінності, що позначається символом ~,

- відношення строгої переваги, що позначається символом >.

Визначення. Для двох альтернатив х₁, х₂ можна стверджувати, що

х₁ ? х₂, тоді і тільки тоді, коли f(x₁) ? f(x₂);

x₁ ~ x₂, тоді і тільки тоді, коли f(x₁) = f(x₂);

x₁ > x₂, тоді і тільки тоді, коли f(x₁) > f(x₂).

Символи ? і < при порівнянні значень цільових функцій для різних альтернатив беруться залежно від того, чи вважається кращою альтернатива при більшому або меншому значенні цільової функції.

Розглянемо кілька варіантів застосування цієї методики в різних ситуаціях.

I. Наявні тільки два результати.

У цьому разі методика обчислення корисності така:

1. Встановлюємо, який результат є кращим для особи, що приймає рішення. Припустимо, що x₁ > x₂, тобто альтернатива х₁ краща, ніж альтернатива х₂.

2. Потім визначаємо таку ймовірність б, при якій досягнення результату х₁ буде еквівалентне результату х₂, отриманому з імовірністю 1.

3. Оцінюємо співвідношення між значеннями корисності результатів х₁ і х₂.

Для цього приймемо, що корисність u(x₂) = 1,

тоді бu(x₁) = u(x₂); u(x₁) = 1/б.

II. Існує n можливих альтернатив х₁, х₂, … x_n, між якими встановлено переваги: x₁ > x₂ > … > x_n.

У цьому випадку методика визначення корисності така:

1. Визначаємо величину б₁ із умови, що б₁u(x₁) = u(x₂).

2. Аналогічно обчислюємо, що

3. Вважаючи, що корисність найменш переважного результату дорівнює 1, знаходимо значення корисності для інших результатів, а саме:

III. Наявні якісні критерії. За таких умов маємо інформацію про переваги між окремими альтернативами та їхніми групами. Тоді може застосовуватися методика, побудована на алгоритмі, який запропонували Р. Акоф і Р. Черчмен [1].

Припустимо, що існує n альтернатив: х₁, х₂, … x_n. Методика визначення корисності передбачає такі етапи:

1. Упорядковують усі альтернативи за зменшенням переваги. Нехай х₁ - альтернатива, що має найбільшу перевагу, а х_n - альтернатива, перевага якої найменша.

2. Складають таблицю можливих комбінацій результатів, що досягаються одночасно, і тоді встановлюють їхню перевагу над окремими результатами х₁, х₂, … x_n (табл. 2).



Таблиця 2

Інформацію про переваги результатів зазвичай отримують від експертів.

3. Приписують початкові оцінки корисності окремим результам u₀(x₁), u₀(x₂),…, u₀(x_n). Потім початкові оцінки підставляють в останнє співвідношення табл. 2. Якщо воно задовольняється, то оцінки не змінюють.

У протилежному випадку проводять корекцію корисності так, щоб дане співвідношення задовольнялось.

Після цього переходять до наступного співвідношення. Процес корекції триває до тих пір, поки не утвориться система оцінок u*(x₁), u*(x₂), … u*(x_n), яка задовольнятиме всі перелічені в таблиці співвідношення. Корекцію належить проводити таким чином, щоб було необхідно змінювати мінімальну кількість оцінок результатів.

П р и к л а д: Нехай експерт упорядковує п'ять результатів х₁, х₂, … х₅, приписавши їм такі оцінки: u₀(x₁) = 7; u₀(x₂) = 4; u₀(x₃) = 2; u₀(x₄) = 1,5; u₀(x₅) = 1.

Розглянувши можливі варіанти вибору, він висловив такі думки про цінність тих чи інших комбінацій варіантів:

1) x₁ < x₂ + x₃ +x₄ + x₅;

2) x₁ < x₂ + x₃ +x₄;

3) x₁ > x₂ + x₃ + x₅;

4) x₁ > x₂ + x₃;

5) x₂ > x₃ + x₄ + x₅;

6) x₂ > x₃ + x₄;

7) x₃ > x₄ + x₅.

Потрібно оцінити корисність результатів так, щоб задовольнити всі нерівності.

Для розв'язування цієї задачі підставляємо початкові оцінки в нерівність 7, тобто

Отже, нерівність 7 не задовольняється.

Змінимо корисність результату х₃: u₁(x₃) = 3, і перевіримо нерівність 6. Отже,

Ця нерівність також не задовольняється.

Приймемо, що u₁(x₂) = 5. Тоді нерівність 5 задовольняється.

Звертаємося до нерівності 4:

Вона не виконується.

Тому приймемо, що u₁(x₁) = 8,5. Тепер нерівності 3, 2, 1 задовольняються.

Перевіряємо ще раз нерівності 6 і 7 при змінених значеннях корисності альтернатив:

5 > 3 + 1,5,

3 > 1,5 + 1.

Таким чином, обидві нерівності виконуються.

Отже, випишемо остаточні оцінки корисності результатів:

u₁(x₁) = 8,5; u₁(x₂) = 5; u₁(x₃) = 3; u₁(x₄) = 1,5; u₁(x₅) = 1.

Зауважимо, що описану методику визначення корисності можна застосовувати, коли кількість результатів обмежена, а саме n < 6 або 7.

Множину альтернатив розбивають на підмножини, що складаються з 5 - 7 альтернатив і мають один спільний результат, наприклад х₁. Потім приписують початкові значення корисності всім альтернативам, причому корисність спільного результату х₁ має бути однаковою у всіх підмножинах. Далі застосовують спосіб корекції оцінок корисності окремо до кожної з підмножин, враховуючи обмеження: u(x₁) = const. Унаслідок цього отримують систему корисності з єдиною мірою для всіх підмножин u(x1).

Після того, як відповідно до описаної методики функцію корисності всіх альтернатив визначено, вирішальне правило вибору найкращої з них в умовах визначеності записується таким чином: знайти таку альтернативу х₀, щоб f(x₀) = max f(x)

Очевидно, що цільова функція, на підставі якої проводиться вибір шуканої альтернативи, може бути побудована різними способами.

Визначення. Цільові функції f₁(x) і f₂(x), що характеризують одну й ту саму властивість рішення, яке вибирається, і визначені на одній множині допустимих альтернатив, називатимемо еквівалентними, якщо вони задають на ній одне й те саме відношення слабкої переваги, тобто, коли для будь-яких двох альтернатив х₁ і х₂ з твердження: , випливає, що і, навпаки, коли з твердження: , виходить, що . Тут індекс fi над знаком слабкої переваги вказує на функцію, за допомогою якої це відношення задано.