Метод наискорейшего спуска (метод градиента)
Выбирают
,
где все производные вычисляются при
,
и уменьшают длину шага
по
мере приближения к минимуму функции
.
Для аналитических функций
и
малых значений
тейлоровское
разложение
позволяет
выбрать оптимальную величину шага
(5)
где все производные вычисляются при . Параболическая интерполяция функции может оказаться более удобной.
42 Методи з використанням бінарних відношень
Бинарным отношением в множестве E
называется всякое подмножество B
из произведения
.
Бинарное отношение
называется
отношением эквивалентности в
множестве E, если подмножество
:
a)
рефлексивно:
;
б)
симметрично:
;
в)
транзитивно:
.
Вместо
часто
пишут a ~ b или a = b.
Бинарное отношение
называется
отношением порядка в множестве E,
если оно:
a)
рефлексивно:
;
б)
транзитивно:
;
в)
антисимметрично:
.
При этом говорят, что отношение
упорядочивает
E. Вместо
часто
пишут
или
.
Если
всегда
или
,
то говорят, что множество E вполне
упорядочено.
Любое бинарные отношение представляется множеством упорядоченных пар элементов.
43 Методи electre (I, II, III). Загальна характеристика.
В кінці 60-х років група французьких учених на чолі з професором Б.Руа запропонувала підхід до попарному порівнянні багатокритеріальних альтернатив, не заснований на теорії корисності. Оцінка кожної альтернативи є відносною (у порівнянні з іншою альтернативою). Так виник метод ELECTRE (ліквідації Et Choix Traduisant ла Realite - виключення і вибір, що відображають реальність). В даний час розроблений ряд методів сімейства ELECTRE. Методи ELECTRE спрямовані на вирішення завдань з уже заданими багатокритеріальним альтернативами. В цих методах не визначається кількісно показник якості кожної з альтернатив, а встановлюється лише умова переваги однієї альтернативи над іншою. Постановка завдання зазвичай має такий вигляд. Дано: N критеріїв зі шкалами оцінок (зазвичай кількісні), ваги критеріїв (зазвичай цілі числа), альтернативи з оцінками за критеріями. Потрібно: виділити групу найкращих альтернатив. Основні етапи методів ELECTRE 1) на підставі заданих оцінок двох альтернатив підраховуються значення двох індексів: згоди і незгоди. Ці індекси визначають згоду і незгоду з гіпотезою, що альтернатива А перевершує альтернативу В; 2) задаються рівні згоди і незгоди, з якими порівнюються підраховані індекси для кожної пари альтернатив. Якщо індекс згоди вище заданого рівня, а індекс незгоди - нижче, то одна з альтернатив перевершує іншу. В іншому випадку альтернативи непорівнянні; 3) з безлічі альтернатив видаляються домінованих. Решта утворюють перше ядро. Альтернативи, що входять в ядро, можуть бути або еквівалентними або непорівнянні; 4) вводяться більш «слабкі» значення рівнів згоди і незгоди (менший за значенням рівень згоди і більший рівень незгоди), при яких виділяються ядра з меншою кількістю альтернатив; 5) останнім ядро входять найкращі альтернативи. Послідовність ядер визначає впорядкованість альтернатив за якістю. У різних методах сімейства ELECTRE індекси згоди і незгоди будуються по-різному. Основні ідеї побудови цих індексів показані на прикладі методу ELECTRE1. Кожному з N критеріїв ставиться у відповідність ціле число р, що характеризує важливість критерію. Б.Руа запропонував розглядати р як «число голосів» членів журі, які голосують за важливість даного критерію. Висувається гіпотеза про перевагу альтернативи А над альтернативою В. Безліч I, що складається з N критеріїв, розбивається на три підмножини - Підмножина критеріїв, за якими А краще В; - Підмножина критеріїв, за якими А рівноцінно В; - Підмножина критеріїв, за якими У переважніше А. Далі формулюється індекс згоди з гіпотезою про перевагу А над В. (В інших методах сімейства ELECTRE використовуються індекси сильної і слабкої переваги). Індекс згоди підраховується на основі ваг критеріїв. Так, в методі ELECTRE1 цей індекс визначається як відношення суми ваг критеріїв підмножин і до загальної суми ваг А в методі ELECTRE II індекс згоди визначається як відношення суми ваг критеріїв підмножин до суми ваг критеріїв підмножин Індекс незгоди з гіпотезою про перевагу А над В визначається на основі самого «суперечливого» критерію - критерію, за яким В найбільшою мірою перевершує А. Розрахунок його однаковий як в методі ELECTRE I, так і в методі ELECTRE II
методе ELECTRE III используются псевдокритерии и числовые бинарные отношения. Задано N псевдокритериев и уро вень вето g j ( xj )>0.
Индексы согласия и несогласия вычисляются следующим способом:
Для каждой пары альтернатив А i , А к строится «числовое» бинарное отношение в следующем виздесь I * - множество критериев, для которых d k ( A i , A j )> C ( A i , A j ).
Величину d ( A i , Aj ) можно интерпретировать как меру уверенности в справедливости гипотезы о том, что Ai предпочти тельнее A j .
Этап исследования альтернатив .На этом этапе определяется сначала . Устанавливается достаточно близкий к l max уровень, при кото ром принимается гипотеза о превосходстве A i над A j .
Далее для каждой альтернативы A i подсчитываются два индекса:
• индекс «силы» — число альтернатив, доминируемых A i ; индекс «слабости» - число альтернатив, доминирующих А i .
Альтернативе А i присваивается характеризующее ее число, равное разности индексов «силы» и «слабости». Затем строится сверху вниз первый полный порядок альтернатив аналогично тому, как это делается в методе ELECTRE II . Альтернативы с наибольшим значением А. удаляются, для оставшихся опять выделяется ядро на основе подсчета тех же чисел, и т.д. Другой порядок определяется при подходе снизу вверх. На основе полных двух порядков строится средний, аналогично тому, как это делается в методе ELECTRE II . Отметим, что метод ELECTRE IV близок по идеям к методу ELECTRE III . Наиболее существенное отличие состоит в том, что в ELECTRE IV не используются веса критериев [3].