Пошук навчальних матеріалів по назві і опису в нашій базі:

Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень»




113.91 Kb.
НазваМетодичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень»
Дата конвертації23.03.2013
Розмір113.91 Kb.
ТипМетодичні вказівки
Зміст
Оптимізація по бінарному відношенню.
МІНІСТЕРСТВО ВИЩОЇ ОСВІТИ УКРАЇНИ

КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ

Методичні вказівки
до розрахунково-графічної роботи по курсу

« ТЕОРІЯ ПРИЙНЯТТЯ РІШЕНЬ»
для студентів спеціальності

« АВТОМАТИЗОВАНІ СИСТЕМИ ОБРОБКИ ІНФОРМАЦІЇ ТА УПРАВЛІННЯ»

денної форми навчання

Київ КПІ 1992

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

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

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

Методичні вказівки містять варіанти завдань по розрахунково-графічній роботі.

ОПТИМІЗАЦІЯ ПО БІНАРНОМУ ВІДНОШЕННЮ.
Використання в ТПР відношення переваги з точки зору системного підходу полягає в декомпозиції задачі вибору альтернативи з на послідовне вирішення задач попарного порівняння альтернатив. При цьому, якщо відношення переваги задано на , то задача про порівняння ( чи непорівняння ) по будь-яких фактично розв’язана. Але для розв’язання задачі вибору із цього недостатньо. Необхідно задати принцип вибору кращої альтернативи по результатам парних порівнянь.

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

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

Визначення 1. Елемент називається найбільшим по на , якщо , виконується .

Визначення 2. Елемент називається максимальним по на , якщо , виконується .

Визначення 3. Елемент називається найбільшим по на , якщо , виконується .

Визначення 4. Елемент називається строго найбільшим по на , якщо , виконується , до того ж з слідує .

Визначення 5. Елемент називається максимальним по на , якщо , з слідує .

Визначення 6. Елемент називається строго максимальним по на , якщо , з слідує.

Позначимо через ,, множину елементів максимальних по на , максимальних по на , строго максимальних по на , і через , , – множину елементів, найбільших по на , найбільших по на , строго найбільших по на відповідно. Порівнюючи принципи домінування і блокування з визначеннями 1-6, легко встановити, що визначення ,, відповідають принципу блокування, а визначення , , – принципу домінування.

Аналізуючи визначення 1-6 з врахуванням властивостей відношень переваги, приходимо до наступних відношень:

,

,

,

,

,

.

Позначимо через асиметричну, через – симетричну частину відношення переваги . Справедливі наступні співвідношення :

,

,

де .

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

, (1)

. (2)

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

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

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

Із властивостей нестрогого порядку легко виводяться наступні умови: якщо – відношення зв’язного нестрогого порядку на скінченному , то завжди існує максимальний по на елемент; якщо – відношення нестрогого порядку на скінченному , то завжди існує максимальний по елемент; якщо – відношення зв’язного квазіпорядку на скінченному , то завжди існує найбільший по на елемент; якщо – відношення квазіпорядку на скінченному , то завжди існує максимальний по на елемент.

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

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

В [3] наведено представничий набір таких умов. Наведемо деякі з них.

Твердження 2. Відношення володіє максимальним елементом на скінченному у тому і тільки у тому випадку, коли транзитивне замикання є строгим порядком.

Твердження 3. Відношення володіє максимальним елементом на скінченному у тому і тільки у тому випадку, коли транзитивне замикання його асиметричної частини - строгий порядок.

Твердження 4. Відношення має найбільший на скінченному елемент тоді і тільки тоді, коли воно зв’язне на , а транзитивне замикання його асиметричної частини - строгий порядок.

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

Розглянемо інші підходи до оптимізації по бінарному відношенню.

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

.

Очевидно, що множина елементів максимальних по на , що визначається

(3)

і множіна элементов строго максимальних по на , що визначається

(4)

є внутрішньо стійкими.

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

.

Визначення 9. Множину ,яка на має властивості внутрішньої та зовнішньої стійкості будемо називати розв’язком Неймана-Моргенштерна, а елемент – елементом оптимальним по Нейману-Моргенштерну [6].

Цей принцип має наступне інтуїтивне обгрунтування : множина «гарних» альтернатив повинна включати тільки непорівняльні елементи по переважності альтернативи / якщо має перевагу над , то не може бути признана «гарною» /; якщо деяка альтернатива не належить множині «гарних» альтернатив, то серед «гарних» альтернатив обов’язково повинна знайтись альтернатива , котра переважна за .

Зауважимо, що виділення множини максимальних елементів може бути проведено на основі властивостей окремого елементу / співвідношення (3), (4) / Виділення множини потребує обліку властивостей деякої сукупності елементів. Іншими словами, прийнявши цей принцип, не можна визначити, чи є окремий елемент «гарним» / чи не є / , але можна сказати про множину елементів , що вона є / чи не є / підмножиною гарних елементів [7].

Якщо потрібно вибрати «кращий» на альтернативний розв’язок, то його потрібно шукати на зовнішньо стійкій підмножині . Якщо не володіє властивістю зовнішньої стійкості, то таке звуження області вибору не обгрунтовано.

Твердження 5. Якщо відношення нестрогої переваги транзитивне, то внутрішньо і зовнішньо стійка на будь-якому скінченному .

Взагалі, для будь-якого даже на скінченному множина може бути порожньою, або не єдиною на . З умовами непорожності, одиничності , різними умовами внутрішньої та зовнішньої стійкості множини максимальних елементів можна ознайомитися в [7,8,9]. Наведемо наступну умову [7]: у випадку ациклічного на скінченному існує одиничне .

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

Розглянемо спосіб находження множини для ациклічних відношень. З допомогою відношень :

,

,

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

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

Розглянемо послідовність підмножин , побудовану з допомогою співвідношень .

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

Розглянемо ще один принцип оптимізації по бінарному відношенню, котрий є більш ефективний при неациклічному або нетранзитивному відношенні переваги, ніж оптимізація по блокуванню або оптимізація по домінуванню. Нехай – відношення нестрогої переваги. Позначимо : – його асиметричну частину , – симетричну частину , – відношення непорівняльності по //. Будь-яка точка може характеризуватися в термінах верхніх та нижніх перерізів цих відношень :

,

,

,

,

,

.

Очевидно, що , так як – асиметрично; , так як – рефлексивно; так як – антирефлексивно //.

Визначення 1-6 можна переформулювати в термінах верхніх та нижніх перерізів відношень ,,. Наприклад, найбільший по на елемент – такий елемент, що .

Сформуємо наступні множини :

,

,

,

.

Означення 10. називається – максимальним елементом по на , якщо є максимальним по включенню елементом сімейства , тобто, якщо .

Порівнюючи означення 10 з означеннями 1-6, можемо сформулювати наступні твердження :

Твердження 5. Максимальний по елемент є 2-максимальним елементом.

Твердження 6. Найбільший по елемент є 4-максимальним елементом.

Твердження 7. Максимальний по елемент є 1-максимальним елементом.

Твердження 8.Строго максимальний по елемент є 2-максимальним елементом.

Твердження 9. Найбільший по елемент є 3-максимальним елементом.

Твердження 10.Строго найбільший по елемент є 2-максимальним елементом.

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


Варіанти завдань.

Відношення R задане булевой матрицею відношень. Представити відношення графом.

Необхідно:

1) знайти множину найбільших елементів;

2) знайти множину максимальних елементів;

3) знайти множину k оптимальних елементів;

4) знайти множину елементів оптимальних по Нейману-Моргенштерну.
Варіанти завдань дивись файл Variantu.doc

Схожі:

Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень» iconМетодичні вказівки до виконання розрахунково-графічної роботи з курсу дм та птм
Розрахунково–графічна робота(ргр) є комплексною, відповідає розділу “Механічні передачі” І являє собою етап проектування передач...
Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень» iconМетодичні вказівки до виконання лабораторних та розрахунково-графічної робіт на тему „комбінаційні схеми та цифрові
Методичні вказівки до виконання лабораторних та розрахунково-графічної робіт на тему „Комбінаційні схеми та цифрові апарати з пам'яттю”...
Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень» iconМетодичні вказівки до виконання розрахунково-графічної роботи з основ ґрунтознавства та охорони ґрунтів
Прикладна літоекологія та радіологія” (для студентів 3 курсу денної та 4 курсу заочної форм навчання спец. 070800 „Екологія та охорона...
Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень» iconВ. Б. Юскаєв 3145 методичні вказівки та Завдання
Методичні вказівки та завдання до виконання розрахунково-графічної роботи «Моделювання і дослідження електронних пристроїв» з дисципліни...
Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень» iconМетодичні вказівки до виконання розрахунково-графічної роботи для студентів 4 курсу денної та заочної форм навчання
Електричні системи і комплекси транспортних засобів”; 092202 “Електричний транспорт”; 092203 “ Електромеханічні системи автоматизації...
Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень» iconМетодичні вказівки до виконання розрахунково-графічної роботи з курсу дм та птм
Дм та птм "Кінематичний розрахунок привода І розрахунок зубчастої передачі редуктора"/укладач В. Б. Курочкін. – Суми: Сумський державний...
Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень» iconПояснювальна записка до розрахунково-графічної роботи з учбової дисципліни " Теорія електричних кіл" на тему:" Розрахунок лінійних електричних кіл основними методами аналізу "
Мета розрахунково-графічної роботи: оволодіти навичками розрахунку електромагнітних процесів у складних електричних колах за допомогою...
Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень» iconПояснювальна записка до розрахунково-графічної роботи з учбової дисципліни " Теорія електричних кіл" на тему:" Розрахунок лінійних електричних кіл основними методами аналізу "
Мета розрахунково-графічної роботи: оволодіти навичками розрахунку електромагнітних процесів у складних електричних колах за допомогою...
Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень» iconМетодичні вказівки до виконання розрахунково-графічної роботи "Розрахунок параметрів хвостосховища" з курсу "Основи утилізації відходів"
Розрахунок параметрів хвостосховища” з курсу “ Основи утилізації відходів” (для студентів 4 курсу денної І 5 курсу заочної форм навчання...
Методичні вказівки до розрахунково-графічної роботи по курсу «теорія прийняття рішень» iconМетодичні вказівки до розрахунково-графічної роботи з дисципліни " гідравліка, сільськогосподарське водопостачання, гідро- та пневмоприводи"
Розробка принципіальної схеми гідропривода і описання принципу його роботи
Додайте кнопку на своєму сайті:
ua.convdocs.org


База даних захищена авторським правом ©ua.convdocs.org 2014
звернутися до адміністрації
ua.convdocs.org
Реферати
Автореферати
Методички
Документи
Випадковий документ
Головна сторінка