Турунтаев Л.П. Теория принятия решений. Учебное пособие томск 2007 Томский межвузовский центр
![]()
|
1 v 1 k 3 0 0,25 0,5 0,75 1 0 10 15 20 25 30 40 v 3 если процент творческой работы составляет 15 %, а работа должна быть эквивалентна по степени удовлетворения работе, заработная плата которой 100 $, но процент творческой работы составляет 50 %. Если ЛПР называет, допустим, 1 k =155 $, то 1 2 3 1 2 3 ( , , ) ( , , ) U k k k U k k k ∗ = o o , 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 ( ) ( ) ( ) ( ) ( ) ( ), v k v k v k v k v k v k ∗ λ + λ + λ = λ + λ + λ o o т.е. 2 1 1 1 ( ). v k λ = λ По графику функции полезности 1 1 ( ) v k опре- деляем для 1 k =155. 2 1 1 155 150 (155) [0,75 0,5] 0,5 0,625 160 150 v λ − = − + = = − λ 76 Аналогично у ЛПР определяем эквивалентность альтерна- тив: 2 (100, , 40) k 1 2 ( ?, , 0). k k − Пусть ЛПР называет 1 k =140. Тогда после подстановок в функцию полезности 3 1 1 (140). v λ = λ 1 140 130 (140) [0,5 0,25] 0,25 0,375. 150 130 v − = − + = − Решаем 1 2 3 1 2 1 3 1; 0,625 0; 0,375 0. λ + λ + λ = λ − λ = λ − λ = Получаем 1 2 3 0,5; 0,3125; 0,1875. λ = λ = λ = Определяем значения функции полезности для вышеприве- денных альтернатив 1 20-15 : (100, 50, 20) 0,5 0 0,3125 1 0,25 0,25 0,1875 25-15 0,3828; x U = ⋅ + ⋅ + ⋅ + ⋅ = = 2 : (140, 30, 0) 0,3047; x U = 3 : (170, 25, 5) 0,6093; x U = 4 : (130, 15, 40) 0,3125; x U = 5 : (140, 40, 10) 0,4139. x U = Итак, наиболее благоприятное место работы — это третье предприятие. 4.3 Задачи принятия решений на основе бинарных отношений предпочтений Важным предположением в языке бинарных отношений яв- ляется независимость предпочтения двух альтернатив от любой третьей [3]. Бинарные отношения могут быть установлены на множестве альтернатив и множестве критериев. И в том и в дру- гом случае для каждой пары сравниваемых объектов , x y X ∈ некоторым образом можно установить, что один из них пред- почтительнее другого либо они равноценны или несравнимы. В общем виде для задания бинарного отношения R на мно- жестве Х необходимо тем или иным способом указать все пары (x, y) множества Х, для которых выполнено отношение R. Существует четыре способа задания отношений: 1) непосредственное перечисление пар, 77 2) матричный, 3) графовый, 4) сечением. Рассмотрим пример отношений в студенческой группе, со- стоящей из трех человек. На множестве 1 2 3 ( , , ) X x x x = студен- тов зададим отношение R — «учится лучше». Пусть первым спо- собом задано отношение R следующим образом: 1 2 1 3 ; x Rx x Rx Тогда можно составить матрицу А отношений R, состоящую из нулей и единиц, в которой åñëè â ï ðî òèâí î ì ñëó÷àå 1, ( ) 0, ( ). i j ij i j x Rx a R x Rx = 1 x 2 x 3 x 1 x 0 1 1 2 x 0 0 0 3 x 0 0 0 Граф отношений, в котором стрелки направлены в сторону менее предпочтительного студента, показан на рис. 4.5. Рис. 4.5 — Графовый способ задания отношений 2 x 3 x 1 x Сечения задаются по каждому элементу множества Х. Раз- личают верхнее сечение ( ) R x + и нижнее — ( ). R x − Верхним сечением для х называется множество элементов из Х, предпоч- тительных относительно рассматриваемого х. Нижним сечением для х называется множество элементов из Х менее предпочти- тельных х. 78 1 ( ) R x + = {Ø — пустое множество}; 2 1 3 1 ( ) { }; ( ) { }; R x x R x x + + = = 1 2 3 2 ( ) { , }, ( ) R x x x R x − − = = {Ø}; 3 ( ) R x − = {Ø}. В приведенном примере отношения R заданы не на всем множестве Х. Если не все элементы сравнимы по отношению R, то оно называется неполным (несовершенным, нелинейным, частичным). На всем множестве объектов Х могут быть уста- новлены отношения эквивалентности, строгого порядка и нестрогого порядка. В [3, 4, 6] даны определения данных от- ношений. Напомним, что отношение эквивалентности содержа- тельно интерпретируется как взаимозаменяемость, одинако- вость объектов. Часто отождествляют понятия эквивалентности, равноценности и несравнимости. Отношение эквивалентности порождает разбиение множества объектов на классы, объеди- няющие неразличимые объекты по одному либо группе крите- риев. В приведенном примере 2 x и 3 x находятся в отношении эквивалентности 2 x 3 x . Отношение строгого порядка может интерпретироваться как предпочтительность одного объекта по сравнению с другим, например «лучше», «важнее», «старше» и т.д. В приведенном примере 1 x учится лучше 2 x и 3 x , 1 x f 2 x и 1 x f 3 x . Отноше- ние строгого порядка порождает строгое упорядочение по пред- почтительности. Если бы добавили, например, отношение 3 x f 2 x , то получили бы строгий порядок 1 x f 3 x f 2 x . В случае строгого упорядочения объектов по предпочти- тельности П. Фишберном [22] доказана теорема, что можно по- строить функцию полезности ( ) U x , такую, что для ( ) ( ). i j i j x x U x U x ⇒ > f Определение функции ( ) U x позволяет перейти от языка бинарных отношений к критериальному язы- ку, взяв ( ) U x в качестве критериальной функции. Отношение нестрогого порядка есть объединение отноше- ний строгого порядка и эквивалентности, оно интерпретируется как предпочтительность либо эквивалентность i j x x ≥ объектов 79 ( i x не хуже j x ). Отношение полного нестрогого порядка поро- ждает строгое упорядочение классов эквивалентности объектов. Если добавим отношения 2 3 x x ≥ и 3 2 , x x ≥ получим порядок 1 2 ( x x f ∼ 3 x ). Альтернатива в ЗПР может быть представлена описанием в критериальном пространстве. Через критериальное пространст- во на множестве альтернатив можно установить бинарные от- ношения. Обозначим: 1 2 ( , , ..., ) m x x x x = — вектор оценок альтернативы х; 1 2 ( , , ..., ) m y y y y = — вектор оценок альтернативы y. Введем на альтернативах x и y отношения строгого пред- почтения (отношение Парето), равноценности и несравнимости для равнозначных критериев. Отношение Парето Р Объекты х и y находятся в отношении Парето Р (строгого предпочтения), если для всех критериев оценки , 1, ≥ = i i x y i m и хотя бы по одному критерию j оценка , 1, . j j x y j m > = { } P ( , 1, ) ( , , 1, ) i i j j x y x y i m j x y j m ⇒ ≥ = ∧ ∃ > = Пример Установить отношения Парето для x, y, z, если х = (5,5,5,5); у = (5,4,5,5); z = (5,5,5,4). Сравнивая попарно критерии для всех альтернатив, получим P ; P ; P ; P . x y x z y z z y Отношение равноценности I Объекты х и у находятся в отношении равноценности I, ес- ли для всех критериев оценки , 1, . i i x y i m = = I { , 1, }. i i x y x y i m ⇒ = = 80 Отношение несравнимости N Объекты х и y находятся в отношении несравнимости N, ес- ли хотя бы по одному критерию i оценка i i x y > и найдется дру- гой критерий j, для которого оценка j j x y < { } N ( , , 1, ) ( , , 1, ) i i j j x y i x y i m j x y j m ⇒ ∃ > = ∧ ∃ < = Отношение Парето на всем множестве альтернатив позво- ляет установить множество предпочтительных (недоминируе- мых) альтернатив, верхнее сечение которых пусто. Данное мно- жество называют множеством Парето, внутри него выполня- ются отношения несравнимости. При необходимости же выбора из множества Парето более предпочтительных следует привле- кать дополнительные соображения: вводить новые отношения (например, мажоритарное, лексиграфическое и др. [42]), новые критерии и ограничения, привлекать экспертов либо бросать жребий. Выбор альтернатив в целом целесообразно производить в два этапа: определение множества Парето, затем определение подмножества более предпочтительных альтернатив из множе- ства Парето. Ниже рассмотрим некоторые из отношений, которые позво- ляют «сузить» множество Парето. Мажоритарное отношение ì P Идейная основа мажоритарного отношения — это принцип выбора лучшего решения на основе голосования. Предполагает- ся, что критерии равнозначны и утверждение «x предпочтитель- ней y» выполняется тогда и только тогда, когда x превосходит y по большему числу оценок, чем y превосходит x. Формально ì P определяется: ì 1 0, m xy y i i xP = ⇒ σ > ∑ где åñëè åñëè åñëè 1, 0; 0, 0; 1, 0. i i xy i i i i i x y x y x y − > σ = − = − − < 81 Пример Пусть (5, 8, 6, 5, 3, 3, 3); y (3, 3, 3, 4, 9, 9, 9). x = = Очевид- но, что имеет место 7 ì 1 1 0 xy i i x P y = σ = > ⇒ ∑ Отношение лексикографии L P Предполагается, что критерии упорядочены по важности значимости. Пусть критерий первый важнее второго, второй — третьего и т.д. Отношение лексикографии определяется: [ ] [ ] [ ] ì 1 1 1 1 2 2 1 1 2 2 m m x P y x y x y x y x y x y x y ⇒ > ∨ = ∧ > ∨ ∨ = ∧ = ∧ ∧ > Отношения Подиновского ï ï , : P I а) для равноважных критериев имеет место отношения предпочтения P и эквивалентности I по Подиновскому: ï 1 1 , m m i i i i x P y x y = = ⇒ > ∑ ∑ ï 1 1 ; m m i i i i x I y x y = = ⇒ = ∑ ∑ б) для разноважных критериев (пусть упорядочены по убы- ванию важности) имеет место отношения: ï 1 1 i 1 1 , 1, , , n n K K i i i i i i i x P y x y n m K x y = = = = ⇒ ≥ = ∧ ∃ > ∑ ∑ ∑ ∑ ï 1 1 , 1, . n n i i i i x I y x y n m = = ⇒ = = ∑ ∑ Пример Пусть (4, 5, 3, 2); (4, 3, 5, 5) x y = = а) для равноважных — ï ï ; ; x P y y P x б) для разноважных — ï ï ; . x P y y P x 82 4.4 Принятие решений на основе функций выбора 4.4.1 Постановка задачи Пусть задано множество альтернатив Х и имеется возмож- ность наблюдать, какие альтернативы выбираются ЛПР. Необ- ходимо по наблюдаемым оптимальным решениям и согласно некоторым принципам рационального поведения ЛПР постро- ить функцию выбора ( ). C X В общем виде { } ( ) , C X x X x x = ∈ o f где x o — база сравнения. Функция ( ) C x описывает выбор как операцию над произвольным множеством альтернатив Х, которая учитывает особенности получаемой от ЛПР информации (качест- венной или количественной) о предпочтениях на множестве крите- риев альтернатив и ставит этому множеству в соответствие неко- торое его подмножество. Накладывая на функцию выбора опреде- ленные требования, можно через нее описывать и варианты выбо- ра, которые отражаются в критериальном языке и языке бинарных отношений. Рассмотрим ниже некоторые функции выбора [38]. 4.4.2 Выбор с учетом числа доминирующих критериев Пусть X — множество альтернатив измеряется через крите- риальное множество К, критерии будем считать равнозначными. Рассмотрим , x y X ∈ , и пусть для каждой альтернативы x X ∈ определено значение ( , ), q x y характеризующее число критери- ев, по которым альтернатива x превосходит альтернативу y X ∈ ( , ) , xy k k q x y = δ ∑ где åñëè åñëè 1, 0; 0, 0; k k xy k k k x y x y − > δ = − ≤ k x — оценка альтернативы х по критерию k . Определим ( ) x Q y как доминирующий показатель над аль- тернативой , y X ∈ равной максимальному числу критериев, по которым другие альтернативы предпочтительнее альтернативы y 83 ( ) max ( , ). x x Q y q x y = Значением функции выбора в критериальном пространстве ( ) k C X является подмножество всех вариантов x X ∈ с макси- мальным доминирующим показателем ( ) ( ) min ( ) . k X X y C X x X Q x Q y = ∈ = Пример Пусть 1 2 3 4 5 ( , , , , ), X x x x x x = 1 2 3 4 5 (1, 1, 5); (3, 2, 4); (4, 3, 2); (7, 0, 1); (2, 8, 0). x x x x x = = = = = Найти ( ) k C X подмножество альтернатив, не уступающих другим по совокупности критериев. Построим матрицу А размерности (5 5) × с элементами ( , ) : i j ij a q x x = 1 2 3 4 5 0 1 1 2 1 2 0 1 2 2 2 2 0 2 2 1 1 1 0 2 2 1 1 1 0 x x A x x x = Для каждого столбца матрицы А определим доминирующие показатели ( ) max j X ij i Q x a = 1 2 3 4 ( ) 2; ( ) 2; ( ) 1; ( ) 2; X X X X Q x Q x Q x Q x = = = = 5 ( ) 2. X Q x = Показатель 3 ( ) 1 X Q x = говорит о том, что над аль- тернативой 3 x доминируют другие альтернативы максимум по одному критерию. Значит альтернатива 3 x является наилучшей, 2 2 1 2 2 84 т.е. 3 ( ) { }. k C X x = Все рассмотренные альтернативы i x X ∈ со- ставляют множество Парето. Из примера видно, что функция выбора ( ) k C X «сужает» это множество. 4.4.3 Метод идеальной точки Пусть Х — множество альтернатив, измеряемое через кри- териальное множество. Рассмотрим 1 2 , ( , , ..., , ..., ), i m x X x x x x x ∈ = где i x — оценка альтернативы х по критерию i. Пусть дана идеальная точка (альтернатива) 1 2 ( , , ..., , ..., ), i m a a a a a = где i a — максимально возможное значение по i-му критерию max . i i x X a x ∈ = Зададим для всех альтернатив x X ∈ функцию, являющуюся взвешенным евклидовым расстоянием между точками è : a x 1/ 2 2 1 ( , ) ( ) , m i i i i x a a x = ρ = α − ∑ где i α — весовой коэффициент критерия i. Введенные понятия позволяют задать функцию выбора ( ) ( , ) min ( , ) . I y C X x X x a y a = ∈ ρ = ρ Если оценки альтернатив по критериям получены в поряд- ковой (ранговой) шкале измерений, то евклидовое расстояние между точками è a x будет иметь вид 1/ 2 2 1 ( , ) (1 ) , m i i i x a r = ρ = α − ∑ где i r — ранг альтернативы по критерию i . |