|
Составители: А.И. Бобков, О.А. Тюрликова
Рецензенты: кафедра вычислительных систем ЛИАП;
кандидат технических наук доцент Г.С. Евсеев
Даются методические указания к выполнению лабораторных работ, связанных с изучением методов принятия решений и алгоритмов выбора вариантов систем пни многих критериях.
Лабораторные работы выполняются студентами интенсивной целевой подготовки специальности "Автоматизированные системы управления" при изучении дисциплины "Системный анализ"
Подготовлены к публикации кафедрой автоматизированных систем управления по рекомендации методической комиссии факультета систем управления и электрооборудования летательных аппаратов Ленинградского института авиационного приборостроения.
(С) Ленинградский институт
авиационного приборостроения
Редактор Е.И.Набоко (ЛИАП), 1987
Подписано к печати 11,08,78 Формат 60x84 I/l6
Объем 2 п.л. Уч.-изд..л. 2 Тираж 100 зкз
Зак. №461 Бесплатно
Ротапринт ЛИАП I90000,Ленинград,Герцена,67
Методические указания.
Содержанием задачи принятия решений является выбор одного из
множества допустимых и взаимоисключающих способов действий (альтернатив), который признается наилучшим для достижения одной или
нескольких целей. Множество допустимых альтернатив представляет
собой совокупность тех решений, которые удовлетворяют ограничениям и рассматриваются как средство достижения желаемого результата (цели).
Действующим элементом, производящим выбор, является лицо принимающее решение (ЛПР) (в качестве ЛПР) может выступать группа лиц), что определяет субъективизм решения задачи.
Допустим, что ЛПР имеет обобщенное представление об альтернативах, достаточное для выбора наиболее предпочтительной. Такая простая задача не является предметом рассмотрения теории принятия решений. В теории рассматривается такая проблемная ситуация, которая требует анализа альтернатив с разных точек зрения. При этом оценка качества альтернатив требует определения набора характеристик, способа их оценки, методов сведения показателей в единое целое. Основным источником информации для оценки альтернатив являются экспер-ты-специалисты в данной области. В отличии от ЛПР эксперты не несут ответственность за принимаемое решение.
Разнообразие методов принятия решений, использование вычисли-тельных средств часто делает необходимым привлечение еще одного специалиста, который выступает в роли консультанта по методам принятия решений и их программной поддержке. Таким образом, в общем случае, определяются функциональные обязанности для трех лиц, участвующих в процессе решения задачи: ЛПР, эксперта и консультанта.
Относительно любой пары альтернатив (х,y) может быть справедливо одно из следующих утверждений:
Попарное сравнение, выполненное для всех элементов множества
альтернатив X, формально может быть описано с помощью бинарного
отношения.
Бинарным отношением R на множестве Х называется множество
упорядоченных пар (x,y), где (R является подмножеством декартового произведения X × Х). Если , то будем пи-
писать х R у и говорить, что х находится в отношении R с y
Для описания бинарного отношения можно использовать следующие
способы выделения некоторой совокупности пар R из множества
всех возможных пар X × Х:
- перечисление всех пар, входящих в R;
- матрица отношения А(R), элемент которой aij = 1, если
пара (хi , xj)ÎR и равен 0 в противном случае;
- граф отношения G (R) = (X, U), вершинам которого поставлены во взаимно однозначное соответствие элементы множества X, а
дуга (х, y)Î U тогда и только тогда, когда (x, y)Î R;
- верхнее R +(x) и нижнее R -(х) сечение, которые определяются следующим образом:
R+(x) =
{ y Î X: y R x };
R - (x) = { yÎ X: x R y }.
В верхнее сечение R+(x) входят только те элементы из X,
которые находятся в отношении R с x,а в R-(х) - c которы-
ми x находится в отношении R. Для описания отношения R зада-
ются верхние или нижние сечения для всех x Î X.
Пример1. Пусть X = { х1, х2, х3, х4, x5 }и R = {(х1, х1),(х1, х3),
(х1, х4),(х2, х3),(х2, х5),(x3, х1),(х3, x2),(x4, х3),(х4, х5),(х5, х3),(х5, x5)}.
Матрица отношении А(R), в которой i - той строке соответству-
ет элемент xi, а j - му столбцу - j, имеет вид:
x1 x2 x3 x4 x5
Граф отношения G(R) представлен на рис.I.
Верхние и нижние сечения для отношения R
R +(x 1) = { x 1, x 3};
R +(x 2) = { x 3};
R +(x 3) = { х 1, х 2, х 4, х 5};
R +(x 4) = { x 1};
R +(x 5) = { х 2, х 4, x 5};
R -(x 1) = { x 1, х 3, х 4};
R -(х 2) = { х 3, х 5}
R -(x 3) = { х 1, х 2};
R -(x 4) = { x 3, x 5};
R -(x 5) = { x 3, x 5};
Легко заметить, что множество R +(xi) включает те элементы множества Х, которым соответствует I в i - ом столбце матрицы А(R) (они же являются вершинами, которые непосредственно предшествуют вершине xi, в графе G(R)).
Множество R (хi) образовано элементами множества Х, которым соответствует Х в i - той строке матрицы А(R) (они не являются вершинами, которые непосредственно следуют за вершиной в графе G(R)).
Матрица отношения A(R) представляет собой матрицу смежности графа G(R), а верхние сечения R+ (х) – списки смежности.
Свойства бинарных отношений приведены в табл.1
Свойство |
| Способ задания отношения | ||
Перечисление | Матрица | Граф | Сечения | |
Рефлексивность | (х,х) Î R, " x Î X | aii =1, ; aij Î{0,1}, i≠j. | При каждой вершине имеется петля | x Î R +(x)для " x Î X |
Антирефлексивность | (х,х) R, " x Î X | aii =0, ; aij Î{0,1}, i≠j. | Петли отсутствуют | x Î R +(x)для " x Î X |
Симметричность | (x, y)Î R Û (y, x)Î R | aij =1Û aji =1 | (x,y) Î U Û (y,x) Î U | x Î R +(y) Û y Î R +(x) |
Асимметричность
| Þ ; ;" x Î X | aij =1 Þ aji =0; aii =0, | петли отсутствуют (x,y)Î U Þ (у,х) U;
| x R +(x); xÎ R +(y) => |
Антисимметричность
| Þ ; | aij =1 Þ aji =0; $ i, a ii =1; | имеется хотя бы одна петля (x,y)Î U Þ (у,х) U; | $ х, x Î R +(x); x ÎR+(y) Þ |
Транзитивность
| (x,y),(y,z)Î R Þ (x,z)Î R | aik =1, akj =1 Þ aij =1; | (x,y)Î U, (y,z)Î U => (x,z)Î U; | x Î R +(y), y Î R +(z)Þ x Î R +(z); |
Свойства бинарных отношений используются для описания классов отношений. В задачах принятия решений наиболее часто используются отношения эквивалентности, порядка и доминирования. Свойства, присущие этим классам отношений, приведены в табл.2
Таблица 2
Свойство
Класс
| Рефлек- сивность | Антиреф- лексвность | симметричность | Асиммет-ричность | Анти-симмет-ричность | Тран-зитив-ность |
Эквивалентности | + |
| + |
|
| + |
Порядка |
|
|
|
|
|
|
а)нестрогое | +
|
|
|
| + | + |
б)строгое |
| + |
| + |
| + |
Доминирования |
| + |
| + |
|
|
Пусть на Х задано бинарное отношение R. Элемент х Î Х называется мажорантой по отношению R, если не существует элемента находящегося в отношении R с элементом x.
Мажоранта в графе отношения соответствует вершине без входящих дуг, в матрице - нулевому столбцу, а верхнее сечение мажоранты является пустым множеством.
Множество мажорант или множество недоминируемых поR элементов составляет множество предпочтительных элементов при выборе.
В зависимости от бинарного отношения множество недоминируемых элементов может быть как пустым множеством, так и составлять исходное множество Х.
Пример 2. Рассмотрим отношение, заданное графом на рис.2
Рис.2
R +(x 1) = Æ;
R +(x 2) ={ x 1, x 2};
R +(x 3) ={ x 1};
R +(x 4) ={ x 3, x 4, x 5};
R +(x 5) =Æ.
Мажоранты – { x 1, x 5}.
В качестве критериального пространства будем использовать евклидово пространство Em, а альтернативу рассматривать как точку в Em. Для двух векторов x = (x 1,..., xm) и у = (y 1..., ym) из Еm определим отношение Парето и отношение лексикографии
Отношение Парето Р
х Р y Û xi ³ yi, и $ i 0, xi 0 > yi 0
На рис.3 изображены верхнее и нижнее сеченая отношения Р в точке х Î E 2
рис3 рис4
Множеством Парето на X Í Em называется множество недоминируемых по Р элементов из X. Из определения следует, что множество Парето X P содержит те и только те элементы х, для которых Р+(x)=Æ.
Пример 3. Пусть Х= {х1,х2,х3,х4,х5};
х1 = (2,4); х2 = (2,2); х3 = (3,3); х4=(5,3); х5=(4,1).
Множества Х и Х P изображены на рис.4
Р+(х1) = Æ; P+(х2) ={ х1,х3,х4 }, Р+(х3) = {х4};
P+(х4) = Æ ; P+(х5) = {х4}; X P = { х1,х4 }.
Отношение лексикографии (L).
Пусть на осях координат задан линейный порядок
k1 > k2 >... > km, тогда
x L y Û [ х k1 > y k1], или [ х k1???= y k1, х k2 > y k2], или
[ х k i = y k i, , x k j+1 > y k j+1 ]...
Отметим, что множество Х состоит из единственного элемента, а множество XP может содержать как единственный элемент, так и всё исходное множество Х (X - дискретное конечное множество).
Верхнее и нижнее сечения отношения L в точке х ÎЕ2 изображены на рис.5. Здесь k1 - первая координата, k2 - вторая. На рис.6 показаны сечения для отношения L в случае, если в качестве k1, используется вторая координата, а в качестве k2- первая.
Контрольные вопросы и задания
1. Сформулируйте правило построения нижнего сечения R -(х)через верхние сечения { R +(x)}.
2. Предложите алгоритмы машинных процедур для проверки свойств отношения:
а) рефлексивности;
б) антирефлексивности;
в) симметричности;
г) асимметричности;
д) антисимметричности;
е) транзитивности
заданного матрицей.
3. Какими свойствами из перечисленных в п.2 обладают отношения Парето и лексикографии?
4. Докажите, что Р-(х)ÌL-(х) для " x ÎE m.
5. Какими свойствами обладают отношения: "быть братом", "быть родителем", "учиться на одном курсе"?
Выбор критериев и шкал. Для сравнения альтернатив используются числа, которые рассматриваются как результат измерения (оценка) по некоторой шкале. Все виды шкал можно разделить на два типа: качественные и количественные. Качественные шкалы делятся на шкалы наименований и шкалы порядка. Количественные шкалы подразделяются на шкалы интервалов, отношений, разностей и абсолютные шкалы.
В шкале наименований описывается различие или эквивалентность объектов, а в шкале порядка - качественное превосходство, отличие объектов. В этих шкалах нет понятия начала отсчета и масштаба измерения. Использование шкалы наименований позволяет относительно любой пары объектов утверждать, что сравниваемые объекты одинаковые (тождественные, эквивалентные) или различные. Шкалы наименований используются для распознавания различных объектов, разбиения множества объектов на классы, включающие эквивалентные объекты. Отношение эквивалентности является рефлексивным, симметричным и транзитивным. В случае шкалы наименований, каждому объекту ставится в соответствие число, причем эквивалентным объектам должно соответствовать одинаковое число, а не эквивалентным - разные числа. Тогда для представления отношения эквивалентности на множестве объектов можно пользоваться отношением тождества на множестве на-
туральных чисел. Симметричность отношения эквивалентности не позволяет в результате сравнения выделить среди объектов более предпочтительный.
Шкалы интервалов, отношений, разностей и абсолютная шкала являются количественными шкалами. В этих шкалах существуют понятия начала отсчета и масштаба, которые выбираются произвольно. Количественные шкалы позволяют измерить, на сколько (шкалы интервалов и разностей) или во сколько (шкалы отношений и абсолютная) раз один объект отличается от другого по выбранному показателю.
Допустимые преобразование для различных шкал приведены в табл.3
Таблица 3
Типы шкал
| допустимые преобразования
|
наименований (классификации)
порядковая интервалов отношений разностей абсолютная
| любое взаимно однозначное преобразование
любое монотонное преобразование линейное преобразование j(х)= ax + b преобразование подобия j(х)= ax. преобразование сдвига j(х) = х + b тождественное преобразование j(x)= х
|
Опишем методы субъективных измерений с помощью приведенных выше шкал.
Ранжирование - процедура упорядочения объектов, выполняемая ЛПР или экспертом. В зависимости от вида отношений между объектами возможны различные варианты упорядочения объектов.
I. Среди объектов нет эквивалентных - существует только отношение строгого порядка.
В результате сравнения составляется упорядоченная последовательность ,
где объект с первым номером является наиболее предпочтительным.
2. Пусть теперь, кроме отношения строгого порядка, между объектами имеется отношение эквивалентности, например, Тогда упорядочение имеет нестрогий порядок.
В этом случае наиболее предпочтительному объекту приписывается ранг, равный единице, второму по предпочтительности - ранг, равный двум и т.д.
Для эквивалентных объектов, с точки зрения Обработки экспертных оценок, удобно назначить одинаковые ранги, равные среднему арифметическому значению рангов, присваиваемых одинаковым объектам. Такие ранги называются связанными рангами.
Например, пусть объекты упорядочены следующим образом . Тогда ранги объектов x 3, x 4, x 5 и x 9, x 10 будут равными
r 3= r 4 = r 5 = (3 + 4 + 5) / 3 = 4;
r 9 = r 10 = (9 + 10) / 2 = 9,5.
Ранги объектов определяют только порядок расположения объектов по показателям сравнения. Ранги как числа не дают возможности сделать вывод о том, на сколько или во сколько раз предпочтительнее один объект по сравнению с другим.
Недостатком ранжирования является практическая невозможность упорядочения большого числа объектов (> 15-20). Это объясняется тем, что в процессе ранжирования эксперт должен установить взаимосвязь между всеми объектами, рассматривая их как единую совокупность. Поэтому при ранжирования большого числа объектов эксперты могут допускать существенные ошибки. В этом случае имеет смысл перейти к процедуре сравнения всех возможных пар объектов (парное сравнение) При сравнении пары объектов возможно либо отношение строгого порядка, либо отношение эквивалентности.
Результат попарных сравнений может быть представлен в виде матрицы
Недостаток метода парного сравнения - возможное нарушение транзитивности отношения.
Непосредственная оценка - представляет собой процедуру приписывания объектам числовых значений в выбранной количественной шкале.
Методы обработки экспертной информации. При привлечении к
экспертизе нескольких специалистов необходимо обработать полученную информацию с целью получить результирующую оценку Группа экспертов может быть однородной или включать экспертов с разной степенью компетентности. В последнем случае выравнивание оценок производится с помощью коэффициентов, учитывающих вклад оценок отдельных экспертов в результирующую оценку.
При обработке результатов экспертизы возникают следующие основные задачи:
- определение согласованности мнений экспертов;
- построение обобщенной оценки;
- определение зависимости между суждениями экспертов;
- оценка надежности результатов экспертизы. Различают методы определения согласованности для количественных и качественных шкал измерения.
В случае количественных шкал измерений рассматривают оценку эксперта как реализацию случайной величины. Оценивают математическое ожидание и дисперсию . Оценка математического ожидания принимается за центр группирования, а оценка дисперсии служит количественной мерой разброса относительно центра. В качестве меры согласованности принимают отношение .
В случае ранжирования объектов в качестве меры согласованности экспертных оценок используется коэффициент конкордации (коэффициент согласия).
Пусть результаты упорядочивания m объектов группой из nэкспертов представлены в виде табл.4, где rij - ранг, присваиваемый i -м экспертом j -му объекту; rj - сумма рангов для
j -го объекта. Будем рассматривать ri, как реализацию случайной величины r, для распределения которой вычислим оценкуматематического ожидания
и дисперсии .
A i Э j | A1 | A2 | … | Am |
Э1 | r 11 | r 12 | … | r 1m |
Э2 | r 21 | r 22 | … | r 2m |
… | … | … | … | … |
Эn | r n1 | r n2 | … | r nm |
r 1 | r 2 | … | r m |
Коэффициент конкордации W определяется как отношение полученной оценки дисперсии к максимально возможной дисперсии которая равна . Тогда, .
Эта формула используется в случае строгого ранжирования (отсутствуют эквивалентные объекты).
В случае нестрогого ранжирования (имеются одинаковые ранги) коэффициент конкордации вычисляется по формуле , где ,
ts - показатель связанных рангов в S - й ранжировке,
НS - число групп равных рангов в S - й ранжировке,
h k - число равных рангов в k - й группе связанных рангов
при ранжировке S - м экспертом.
Если совпадающих рангов нет, то HS =0, h k = 0 и следовательно, ТS = 0.
Коэффициент конкордации W Î [0,1], причем W = 1 в случае одинаковых ранжировок, a W = 0, когда все ранжировки различны.
Построение обобщённой оценки. Пусть измерение производится в порядковой шкале методом ранжирования. Представим ранжировку, выполненную S - ым экспертом в виде матрицы парных сравнений , где ris, rks - ранги, приписываемые S -ым экспертом i, k -му объекту соответственно.
Определим расстояние между матрицами парных сравнений , т.е. расстояние равно числу несовпадающих соответствующих элементов матриц.
С помощью введенной метрики определяют матрицу, соответствующую обобщенной результирующей ранжировке.
Результирующая матрица a*, называемая медианой, это такая матрица, что сумма расстояний от нее до всех заданных матриц мини-
мальна
.
Легко показать, что построение матрицы парных сравнений, соответствующей медиане, осуществляется по принципу простого большинства голосов экспертов для каждого элемента матрицы. ,где - количество голосов, поданных экспертами за предпочтение i -го объекта k -му объекту.
Численные оценки. Опишем метод Дельфи для построения результирующей оценки. Экспертам предоставляется медиана, диапазон квантилей и обоснование оценок, выходящие за этот диапазон.
весь интервал допустимых значений оцениваемой величины разбивается на k интервалов
t 1, t 2,..., tк. Эксперт оценивает вероятность попадания оцениваемой величины в каждый из интервалов. По результатам их оценок составляется табл.5, где pij - оценка вероятности попадания оцениваемой величины в j -й интервал, данная
Таблица 5.
Эксперты
| Интервалы
| |||
|
|
|
| |
| t1
| t2
| • • •
| tk
|
Э1
| P11
| Р12
| ...
| Р1k
|
Э2
| P21
| Р22
| ...
| Р2k
|
Эn
| Рn1
| Рn2
| ...
| Pnk
|
i -м экспертом. На основании этой таблицы определяется мнение экспертов о попадании оцениваемой величины в каждый из интервалов tj: ,
где a i. - веса экспертов. При отсутствии информации о компетентности экспертов можно положить a i =1.
Результирующей оценкой является медиана построенного распределения q 2, определяемая из условия
Р (T £ q2) = 0,5
Помимо q 2 вычисляется диапазон квантилей D q = q 3- q 1,
где Р (Т £ q 3) = 0.75; Р (Т £ q 1) = 0,25.
Эмпирически установлено, что процедуру можно прекращать, когда диапазон квантилей уменьшился в 1,6 раза по сравнению с первоначальным.
Задача многомерного метрического шкалирования состоит в следующем. Задана симметричная матрица различий D = { dij } между n объектами А 1,..., An. Нужно найти координаты точек ai ÎE r, сопоставленных объектам Ai так, чтобы матрица X = { xij } расстояний между этими точками в Е r была возможно более близка к исходной матрице различий D в смысле некоторого заранее выбранного критерия. Приведем алгоритм неметрического многомерного шкалирования. Упорядочим по возрастанию n 2 чисел, являющихся элементами матрицы D, и обозначим полученный порядок через r (A). Отобразим объекты Ai в пространство E r и упорядочим по возрастанию n 2 чисел, являющихся элементами матрицы расстояний между точками ai, полученный порядок обозначим через r (a).
Задача неметрического многомерного шкалирования состоит в том, чтобы построить отображение q в пространство минимальной размерности так, чтобы r(a) = r (А) - Для этого выполняют следующие операции:
1. Определяют ранжировку r (А)и нормируют элементы матрицы D так, что минимальный равен нулю, а максимальный - единце
2. Помещают n точек в n вершин правильного (n -1) - мерного симплекса, центр которого находится в начале координат, а ребра имеют двину 1. Координаты n точек a 1, a 2,..., an в ( n -1)- мерном пространстве вычисляют по формулам
, для четного n проекция на (n -1)-ю ось .
3. Для построенных точек вычисляют ранжировку и сравнивают ее с r (A). Если r (a) = r (A), то вычисления прекращают. В противном случае нормируют матрицу расстояний Х между точками ai так же, как матрицу D. Элементы пронормированных матриц обозначают через и соответственно.
4. Находят новые значения координат точек ai по формулам .
где ; ; ; ; a=0,2; b=0,05. Полагают , вычисляют ранжировку r (a) и повторяют приведенные операции.
Методы принятия решений
Доминирование Пусть X = { x 1,..., xn } множество допустимых альтернатив. Каждой альтернативе х Î Х поставлено в соответствие числовых показателей - критерии оценки качества альтернатив. Каждая альтернатива представляется как точке в критериальном пространстве Е m. Точка находится в отношении Парето c точкой , если для которого . Если критерии j i возрастают по предпочтительности, то из двух точек , таких, что находится в отношении Парето с следует выбрать и соответственно альтернативу x 4. Множество недоминируемых по Парето альтернатив, образует аффективное множество (оптимальное по Парето). Поскольку не все точки сравнимы по Парето, то эффективное множество может содержать от одной до n точек, т.е. все множество исходных альтернатив.
Использование глобального критерия. Пусть сформулирован ряд гипотез о проблемной ситуации и несколько вариантов решений (альтернатив). Для каждой гипотезы определены вероятности их осуществления. Результаты представлены в виде таблицы 6
Таблица 6
Гипотезы
Альтернативы |
S 1
|
S 2
| ...
|
S n
|
A1
| f11
| f12
| ...
| f1n
|
A2
| f21
| f22
| ...
| f2n
|
Am
| fm1
| fm2
| ...
| fmn
|
Вероятности гипотез
| P1
| Р2
| ...
| Рn
|
Различают три вида стратегий: осторожная (пессимистическая), оптимистическая и рациональная (рассчитанная на средние условия). Применение критерия пессимизма не требует знания вероятностей ситуаций, и в этом его преимущество, поскольку часто эти вероятности неизменны.
В случае измерения в порядковой шкале . Эта стратеги известна как принцип гарантированного результата или максиминный критерий Вальда. Критерий оптимизма . Если предпочтения в рангах, то . Критерий максимума среднего выигрыша .
Критерий Гурвица .
Метод ограничений, метод уступок. Пусть j1,j2,...,jm - множество целевых функций (критериев) X 0 - ограничения на множестве альтернатив.
Допустим, что ЛПР считает возможным выбрать любую альтернативу x Î X 0, для которой выполняются условия j i (x) ³a i, , где a1,...,am - установленная ЛПР нижняя граница по каждому критерию. Если такая точка не найдётся, то ЛПР снижает уровни своих притязаний a1,...,am, и действует таким образом, пока такая точка не найдется.
Модификация этого подхода, представляет собой процедуру, в которой устанавливается нижняя граница для всех критериев, кроме одного свободного критерия. Для свободного критерия jk решается однокритериальная задача
Если ЛПР не удовлетворено полученным результатом, то процедура повторяется при другом свободном критерии и ограничениях.
В методе уступок предполагается, что критерии можно упорядо-
чнть но важности j1,j2,...,jm. В начале решается задача
Пусть -решение этой задачи.
Далее ЛПР задает величину D1 - уступку по критерию j1. Решается задача На последнем шаге
Метод целевой функции свертка критериев. ЛПР описывает структуру предпочтения критериев в виде скалярной целевой функции F (j (x),l), где l - вектор параметров. Часто F - линейная функция. Задавая начальные параметры l0, решается одноэкстремальная задача
Если ЛПР не удовлетворено полученными значениями критериев, то вектор l0 меняется. Метод идеальной точки. Предполагается, что в пространстве критериев задана точка "идеала" "точка утопии" j* и в этом же пространстве введена метрика r(j, j*). Решается следующая задача Как правило используется обобщенная евклидова метрика .
Решается следующая задача
При р = 2, получаем обычное евклидово расстояние.
При р = 1 имеем .
При получим равномерную метрику .
Естественный способ задания идеальной точки следующий . Функция расстояния до идеальной точки позволяет упорядочить все альтернативы и выбрать наилучшую. Однако необходимо иметь в виду, что упорядочение с помощью метрики не отвечает аксиоме независимости, которая требует чтобы результат сравнения двух альтернатив не зависел от наличия третьей альтернативы. Этот эффект обязан смещением идеальной точки, за счет добавления некоторой альтернативы. Этот эффект продемонстрирован на рис.7 и рис.8.
При выборе метода принятия решений важной его характеристикой
является мощность множества выбранных альтернатив и соотношение
этого множества с множеством Парето.
Утверждение 1. Обозначим через Xид множество альтернатив.
выбранных с помощью метода идеальной точки.
Если множество векторных оценок допустимых альтернатив выпукло то для любого р, кроме р = 1,¥ справедливо | Xид |=1.
Утверждение 2. Для любого р, кроме р=¥ выполняется условие , где XP - множество Парето.
Нарушение утверждения 1 при иллюстрируется на рис.9, а нарушение утверждения 2 при на рис.10
Градиентный метод. Пусть векторной оценке каждой из альтернатив поставлено в соответствие действительное число, т.е. на множестве векторных оценок определена скалярная функция v, прячём справедливы следующие соотношения, которые определяют структуру предпочтения ЛПР:
Будем называть определенную функцию v функцией ценности. На рис.11 показан пример функции ценности, представленной кривыми безразличия линиями равного уровня в случае двух критериев
Восстановление функции ценности позволяет упорядочить все альтернативы. Трудности, связанные с восстановлением функции ценности, а также отсутствие необходимости в упорядочении всех альтернатив, привели к следующей человеко-машинной процедура поиска наиболее предпочтительной альтернативы.
Основу градиентного метода составляет подходящий формальный алгоритм оптимизации (например, Франка - Вульфа). Предполагается, что предпочтении ЛПР могут быть описаны некоторой априори неизвестной скалярной функцией. Фиксируются свойства таких функций, которые используются для определения ее градиента и для выбора величины шага при одномерной оптимизации.
Предлагается вычислять градиент с помощью определения предельных норы замещения одного из критериев всеми остальными. Эта операция выполняется в режиме диалога ЛПР с ЭВМ. Для определения величины шага ЛПР представляется график изменения всех критериев вдоль выбранного направления и ЛПР должен указать на нем оптимальную точку.
Методы принятия решений в условиях риска. Задача формулируется следующим образом. ЛПР должен выбрать одну из нескольких альтернатив, каждая из которых в конечном итоге будет иметь своим результатом некоторый исход. Принимающий решение точно не знает, к какому именно исходу приведет любая из выбранных альтернатив, но для каждого способа действий он в состоянии установить вероятности получения различных исходов. Схема такой ситуации для двух альтернатив (действий) и двух исходов представлена на рис. 12.
Пусть L= (p1, x 1; p2, x 2) - лотерея, где P i - вероятность выигрыша xi. Выбор действия a 1 или a 2 можно рассматривать как выбор из лотерей
L1 = (p11, x 1; p12, x 2); L2 = (p21, x 1; p22, x 2). Как установить отношение предпочтения на множестве лотерей?
Обозначим через u (х) функцию полезности на множестве исходов. Ожидаемая полезность лотереи и является показателем, который следует использовать при выборе лотереи. Следует выбирать ту лотерею, для которой максимальна ожидаемая полезность. Пусть в результате исследования структурных условий независимости критериев выявлено, что m - мерная функция полезности быть декомпозирована может следующим образом
где - некоторая строго монотонная аддитивная, мультипликативная, полилинейная функция;
uj (rj) - одномерная функция полезности, отражающая предпочтения ЛПР на множестве значений критерия R j и его отношение к риску.
В таком случае построение u (r) заключается в восстановлении uj (rj) для и определении параметров функции .
Независимо от типа шкалы критериев R j и метода восстановления uj (rj) вся работа по её построению может быть условно разбита на пять этапов:
· подготовка к построению функции полезности;
· выявление существенных качественных характеристик;
· определение количественных характеристик;
· выбор аппроксимирующей функции;
· проверка согласованности ответов ЛПР.
Включение подготовительного этапа преследует две цели:
· ЛПР должно понять, что консультанта интересует предпочтение именно
ЛПР (нет и не может быть объективно правильных предпочтений);
· определить область изменений значений критерия R j. На этапе выявления
качественных характеристик определяется отношение ЛПР к риску и проверяется, является функция полезности
uj (rj) монотонное. Для проверки монотонности выясняют, предпочитает ли ЛПР точку S точке Q (рис. 13) или наоборот. Пусть , тогда предлагается сравнить точки 0 и Р и т.д. В заключении можно задать обобщающий вопрос: если rj 1 > rj *, всегда ли имеет место ? Если предыдущие ответы ЛПР давали основание ожидать утвердительный ответ, а получен отрицательный, то следует заново (c целью обучения) проверить и исследовать его предпочтения на множестве значений [ rj 0, rj *].
Для определения отношения ЛПР к риску необходимо выяснить, предпочитает ли ЛПР лотерею < (rj + hj);(rj - hj) > или же гарантированное значение rj для произвольно выбранного значения rj и hj. Если предпочитает лотерею, то считать расположенным к риску, в противном случае - осторожным. Такого рода сравнение производится многократно для разных значений rj и hj, покрывающих весь интервал [ rj 0, rjk ]. Если ЛПР постоянно предпочитает rj, то с уверенностью можно сделать заключение, что оно осторожно и наоборот.
На третьем этапе определяется и фиксируется значение функции полезности для некоторых точек rj Î[ rj 0, rj *]. Чаще всего это сводится к выявлению эквивалентов определенности нескольких лотерей вида 50-50.
1. Определяется такое значение rj 0,5, что rj0,5 ~ <rj*; rj0> или в терминах функция полезности uj (rj 0,5)= 0,5 uj (rj 0) + 0,5 uj (rj *).
Поскольку функция полезности является уникальной с точностью до положительных линейных преобразований, то можно принять uj (rj)=0; uj (rj *)= 1. Тогда uj (rj 0,5) = 0,5
2. Определяются значения rj 0,25 и rj 0,75, такие, что
rj 0,5 ~ < rj 0,5; rj 0 > Þ uj (rj 0,25) = 0,25
rj 0,75 ~ < r*j; r0,5j > Þ uj (rj 0,75) = 0,75
3. Для проверки согласованности суждений ЛПР определяется
такое значение , что ~ < rj 0,75; r j0,25 >.
Должно иметь место равенство rj 0,5 = .
4. Определяется (если необходимо) значения rj 0,125 rj 0,375 rj 0,625 rj 0,875
и производится проверка значений rj 0,25 rj 0,75.
Пример графического представления uj (rj) после определения точек
rj 0, rj 0,25, rj 0,5, rj 0,75, rj * для осторожного (не склонного к риску) ЛПР дается на рис.14
Основным преимуществом такой процедуры является использование легко интерпретируемых ЛПР лотерей типа 50—50, однако сфера ее применимости ограничена критериями отношений.
Рассмотрим метод построения функций полезности на значениях критериев с порядковой шкалой. Пусть критерий имеет Rj имеет M отдельных значений и индексы
K = 1,2,…, M этим значениям присвоены так, что
rj M rj M-1 … rj 1.
Тогда, исхода из свойств функций полезности, можно положить uj (rj 1) = 0 и
uj (rj M) = 1 предложить для ЛПР совокупность вопросов следующего вида:
определить такое значение вероятности pk Î [0,1], что лотерея < rj M, pk, rj 1, (1- pk) > будет равно предпочтительной, сточки зрения ЛПР, определенному результату rj k.
rj k ~ < rj M, pk, rj 1, (1 - pk) >
и положить uj(rkj) = pk .
Процедура проверки согласованности полученных оценок аналогична
/* далее ничего непонятно примерно 3 строчки */ (?процедуре, что позволяет определить такие значения вероятности /*какая-то формула*/, что
/* rj k ~ < rj M-1, q k,??? rjk,(1-qk) > */
После этого определяют новые значения функции полезности wj(rkj) исходя из отношения /* которое тоже не совсем понятное /*
w j (rj k) = q k uj (rj M+1) + (1 - qk) uj (rj 2).
Если затем, для всех kÎ3, M-2 имеет место w j (rj k) = uj (rj k) ± ε,
т.е основание считать оценки ЛПР согласованными.
Определение шкалируемых констант. Если строго монотонная функция ψ может быть представлена аддитивной, мультипликативной или полилинейной формой, то после восстановления uj (rj k), следует определить шкалируемые константы.
Сложность данного этапа работы заключается в том, что ЛПР сравнивать многомерные исходы и лотереи на них.
Введем обозначения:
r * = (r 1 *, …, rj*,…, rm *) – исход, все компоненты которого принимают наиболее предпочтительные значения соответствующих критериев;
r 0 = (r 10, …, rj 0,…, rj 0) – исход, значение компонент которого зафиксированы на наименее предпочтительном уровне;
(rj *, rj 0) = (r 10…, rj -10, rj 0, r 0 j +1,…, rm 0) – исход, все компоненты которого зафиксированы на наименее предпочтительном уровне, за исключением j -той компоненты, которая принимает значение rj *.
Тогда, если u (r 0) = 0 и u (r *) = 1, а также
uj (rj 0) = 0, uj (rj *) = 1, (),
то k j = p j, , где p j Î [0,1] – такое значение вероятности, что равноценными для ЛПР является определенный исход (rj *, rj 0) и лотерея, производящая исход r * с вероятностью p j и исход r 0 с вероятностью 1- pj т.е.
/*стертая формула*/ (rj *, rj- 0) ~ < r *, pjm; r 0,(1 - p j)>
Далее следует провести контроль определенных констант.
Под задачей выбор а понимают выделение некоторого подмножества альтернатив из заданного множества при неопределенном принципе оптимальности. В практической ситуации выбора при некотором множестве альтернатив лицо, принимающее решение, выбирал некоторую альтернативу, руководствуется своим личным представлениём о лучших альтернативах. У разных лиц в одной и той же ситуации представление о лучших альтернативах может различаться, а, следовательно, они могут выбирать разные альтернативы. При этом каждый из них может привести вполне рациональное обоснование сделанного выбора. Даже при выборе одних и тех же альтернатив разными лицами обоснования могут различаться. Таким образом, по известному выбору в конкретной ситуации вряд ля можно сказать что-либо определенное о тех причинах, которые побудили сделать именно данный выбор, а не другой, т.е. восстановить логику выбора. Для формализации взаимной зависимости выборов при взаимосвязанных ситуациях пользуются понятием функции выбора.
Дата добавления: 2015-08-29; просмотров: 25 | Нарушение авторских прав
<== предыдущая лекция | | | следующая лекция ==> |
Министерство образования Российской Федерации | | | Методические указания по выполнению лабораторных работ по курсу Конструкция тракторов и автомобилей составлены в соответствии с программой для высших сельскохозяйственных учебных |