Составители: А.И. Бобков, О.А. Тюрликова Рецензенты: кафедра вычислительных систем ЛИАП;

Составители: А.И. Бобков, О.А. Тюрликова
Рецензенты: кафедра вычислительных систем ЛИАП;

кандидат технических наук доцент Г.С. Евсеев

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

Лабораторные работы выполняются студентами интенсивной целевой подготовки специальности "Автоматизированные системы управления" при изучении дисциплины "Системный анализ"

Подготовлены к публикации кафедрой автоматизированных систем управления по рекомендации методической комиссии факультета систем управления и электрооборудования летательных аппаратов Ленинградского института авиационного приборостроения.

(С) Ленинградский институт

авиационного приборостроения

Редактор Е.И.Набоко (ЛИАП), 1987

Подписано к печати 11,08,78 Формат 60x84 I/l6

Объем 2 п.л. Уч.-изд..л. 2 Тираж 100 зкз

Зак. №461 Бесплатно

Ротапринт ЛИАП I90000,Ленинград,Герцена,67

Методические указания.

Содержанием задачи принятия решений является выбор одного из

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

Действующим элементом, производящим выбор, является лицо принимающее решение (ЛПР) (в качестве ЛПР) может выступать группа лиц), что определяет субъективизм решения задачи.

Допустим, что ЛПР имеет обобщенное представление об альтернативах, достаточное для выбора наиболее предпочтительной. Такая простая задача не является предметом рассмотрения теории принятия решений. В теории рассматривается такая проблемная ситуация, которая требует анализа альтернатив с разных точек зрения. При этом оценка качества альтернатив требует определения набора характеристик, способа их оценки, методов сведения показателей в единое целое. Основным источником информации для оценки альтернатив являются экспер-ты-специалисты в данной области. В отличии от ЛПР эксперты не несут ответственность за принимаемое решение.

Разнообразие методов принятия решений, использование вычисли-тельных средств часто делает необходимым привлечение еще одного специалиста, который выступает в роли консультанта по методам принятия решений и их программной поддержке. Таким образом, в общем случае, определяются функциональные обязанности для трех лиц, участвующих в процессе решения задачи: ЛПР, эксперта и консультанта.

Относительно любой пары альтернатив (х,y) может быть справедливо одно из следующих утверждений:

• x и y несравнимы;
• x предпочтительнее y ();
• у предпочтительнее х ();
• x и y эквимлентны ( ~ ).

Попарное сравнение, выполненное для всех элементов множества

альтернатив X, формально может быть описано с помощью бинарного
отношения.

Бинарным отношением R на множестве Х называется множество

упорядоченных пар (x,y), где (R является подмножеством декартового произведения X × Х). Если , то будем пи-

писать х R у и говорить, что х находится в отношении R с y

Для описания бинарного отношения можно использовать следующие
способы выделения некоторой совокупности пар R из множества

всех возможных пар X × Х:

- перечисление всех пар, входящих в R;

- матрица отношения А(R), элемент которой a_ij = 1, если
пара (х_i , x_j)Î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 = { х₁, х₂, х₃, х₄, x₅ }и R = {(х₁, х₁),(х₁, х₃),
(х₁, х₄),(х₂, х₃),(х₂, х₅),(x₃, х₁),(х₃, x₂),(x₄, х₃),(х₄, х₅),(х₅, х₃),(х₅, x₅)}.

Матрица отношении А(R), в которой i - той строке соответству-
ет элемент x_i, а j - му столбцу - j, имеет вид:

x₁ x₂ x₃ x₄ x₅

Граф отношения G(R) представлен на рис.I.

Верхние и нижние сечения для отношения R
R ⁺(x ₁) = { x ₁, x ₃};
R ⁺(x ₂) = { x ₃};
R ⁺(x ₃) = { х ₁, х ₂, х ₄, х ₅};
R ⁺(x ₄) = { x ₁};
R ⁺(x ₅) = { х ₂, х ₄, x ₅};

R ^-(x ₁) = { x ₁, х ₃, х ₄};
R ^-(х ₂) = { х ₃, х ₅}

R ^-(x ₃) = { х ₁, х ₂};
R ^-(x ₄) = { x ₃, x ₅};
R ^-(x ₅) = { x ₃, x ₅};

Легко заметить, что множество R ⁺(x_i) включает те элементы множества Х, которым соответствует I в i - ом столбце матрицы А(R) (они же являются вершинами, которые непосредственно предшествуют вершине x_i, в графе G(R)).
Множество R (х_i) образовано элементами множества Х, которым соответствует Х в i - той строке матрицы А(R) (они не являются вершинами, которые непосредственно следуют за вершиной в графе G(R)).
Матрица отношения A(R) представляет собой матрицу смежности графа G(R), а верхние сечения R⁺ (х) – списки смежности.
Свойства бинарных отношений приведены в табл.1

Свойство		Способ задания отношения
Перечисление пар	Матрица A(R)	Граф G(R)	Сечения R ^+(х)
Рефлексивность	(х,х) Î 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 ₁) = Æ;
R ⁺(x ₂) ={ x ₁, x ₂};

R ⁺(x ₃) ={ x ₁};

R ⁺(x ₄) ={ x ₃, x ₄, x ₅};

R ⁺(x ₅) =Æ.

Мажоранты – { x ₁, x ₅}.

В качестве критериального пространства будем использовать ев­клидово пространство E_m, а альтернативу рассматривать как точку в E_m. Для двух векторов x = (x ₁,..., x_m) и у = (y ₁..., y_m) из Е_m определим отношение Парето и отношение лексикографии

Отношение Парето Р

х Р y Û x_i ³ y_i, и $ i ₀, x_{i 0} > y_{i 0}

На рис.3 изображены верхнее и нижнее сеченая отношения Р в точке х Î E ₂

рис3 рис4

Множеством Парето на X Í E_m называется множество недоминируемых по Р элементов из X. Из определения следует, что множест­во Парето X ^P содержит те и только те элементы х, для которых Р⁺(x)=Æ.

Пример 3. Пусть Х= {х¹,х²,х³,х⁴,х⁵};

х¹ = (2,4); х² = (2,2); х³ = (3,3); х⁴=(5,3); х⁵=(4,1).

Множества Х и Х ^P изображены на рис.4

Р⁺(х¹) = Æ; P⁺(х²) ={ х¹,х³,х⁴ }, Р⁺(х³) = {х⁴};

P⁺(х⁴) = Æ ; P⁺(х⁵) = {х⁴}; X ^P = { х¹,х⁴ }.

Отношение лексикографии (L).

Пусть на осях координат задан линейный порядок

k₁ > k₂ >... > k_m, тогда

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} ]...

Отметим, что множество Х состоит из единственного элемента, а множество X^P может содержать как единственный элемент, так и всё исходное множество Х (X - дискретное конечное множество).

Верхнее и нижнее сечения отношения L в точке х ÎЕ₂ изобра­жены на рис.5. Здесь k₁ - первая координата, k₂ - вторая. На рис.6 показаны сечения для отношения L в случае, если в качестве k₁, ис­пользуется вторая координата, а в качестве k₂- первая.

Контрольные вопросы и задания

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 ₃, x ₄, x ₅ и x ₉, x ₁₀ будут равными

r ₃= r ₄ = r ₅ = (3 + 4 + 5) / 3 = 4;

r ₉ = r ₁₀ = (9 + 10) / 2 = 9,5.

Ранги объектов определяют только порядок расположения объектов по показателям сравнения. Ранги как числа не дают возможности сде­лать вывод о том, на сколько или во сколько раз предпочтительнее один объект по сравнению с другим.

Недостатком ранжирования является практическая невозможность упорядочения большого числа объектов (> 15-20). Это объясняется тем, что в процессе ранжирования эксперт должен установить взаимо­связь между всеми объектами, рассматривая их как единую совокупность. Поэтому при ранжирования большого числа объектов эксперты могут до­пускать существенные ошибки. В этом случае имеет смысл перейти к процедуре сравнения всех возможных пар объектов (парное сравнение) При сравнении пары объектов возможно либо отношение строгого по­рядка, либо отношение эквивалентности.

Результат попарных сравнений может быть представлен в виде матрицы

Недостаток метода парного сравнения - возможное нарушение транзитивности отношения.

Непосредственная оценка - представляет собой процедуру при­писывания объектам числовых значений в выбранной количественной шкале.

Методы обработки экспертной информации. При привлечении к

экспертизе нескольких специалистов необходимо обработать получен­ную информацию с целью получить результирующую оценку Группа эк­спертов может быть однородной или включать экспертов с разной сте­пенью компетентности. В последнем случае выравнивание оценок произ­водится с помощью коэффициентов, учитывающих вклад оценок отдельных экспертов в результирующую оценку.

При обработке результатов экспертизы возникают следующие ос­новные задачи:

- определение согласованности мнений экспертов;

- построение обобщенной оценки;

- определение зависимости между суждениями экспертов;

- оценка надежности результатов экспертизы. Различают методы определения согласованности для количествен­ных и качественных шкал измерения.

В случае количественных шкал измерений рассматривают оценку эксперта как реализацию случайной величины. Оценивают математичес­кое ожидание и дисперсию . Оценка математического ожида­ния принимается за центр группирования, а оценка дисперсии служит количественной мерой разброса относительно центра. В качестве ме­ры согласованности принимают отношение .

В случае ранжирования объектов в качестве меры согласованнос­ти экспертных оценок используется коэффициент конкордации (коэффи­циент согласия).

Пусть результаты упорядочивания m объектов группой из nэкспертов представлены в виде табл.4, где r_ij - ранг, присваиваемый i -м экспертом j -му объекту; r_j - сумма рангов для

j -го объекта. Будем рассматривать r_i, как реализацию случайной величины 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 определяется как отношение полу­ченной оценки дисперсии к максимально возможной дисперсии которая равна . Тогда, .

Эта формула используется в случае строгого ранжирования (от­сутствуют эквивалентные объекты).

В случае нестрогого ранжирования (имеются одинаковые ранги) коэффициент конкордации вычисляется по формуле , где ,

t_s - показатель связанных рангов в S - й ранжировке,

Н_S - число групп равных рангов в S - й ранжировке,

h _k - число равных рангов в k - й группе связанных рангов

при ранжировке S - м экспертом.

Если совпадающих рангов нет, то H_S =0, h _k = 0 и следовательно, Т_S = 0.

Коэффициент конкордации W Î [0,1], причем W = 1 в слу­чае одинаковых ранжировок, a W = 0, когда все ранжировки различны.

Построение обобщённой оценки. Пусть измерение производится в порядковой шкале методом ранжирования. Представим ранжировку, выполненную S - ым экспертом в виде матрицы парных сравнений , где r_is, r_ks - ранги, приписываемые S -ым экспертом i, k -му объекту соответственно.

Определим расстояние между матрицами парных сравнений , т.е. расстояние равно числу несовпадающих соответствующих элемен­тов матриц.

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

Результирующая матрица a^*, называемая медианой, это такая матрица, что сумма расстояний от нее до всех заданных матриц мини-

мальна

.

Легко показать, что построение матрицы парных сравнений, соот­ветствующей медиане, осуществляется по принципу простого большинст­ва голосов экспертов для каждого элемента матрицы. ,где - количество голосов, поданных экспертами за предпочтение i -го объекта k -му объекту.

Численные оценки. Опишем метод Дельфи для построения результирующей оценки. Экспертам предоставляется медиана, диапазон кван­тилей и обоснование оценок, выходящие за этот диапазон.

весь интервал допустимых значений оцениваемой величины разбивается на k интервалов

t ₁, t ₂,..., t_к. Эксперт оцени­вает вероятность попадания оце­ниваемой величины в каждый из интервалов. По результатам их оценок составляется табл.5, где p_ij - оценка вероятности попадания оцениваемой величи­ны в j -й интервал, данная

Таблица 5.

Эксперты	Интервалы
	t1	t2	• • •	tk
Э1	P11	Р12	...	Р1k
Э2	P21	Р22	...	Р2k
Эn	Рn1	Рn2	...	Pnk

i -м экспертом. На основании этой таблицы определяется мнение экспертов о попадании оцениваемой величины в каждый из интервалов t_j: ,

где a _i. - веса экспертов. При отсутствии информации о компетентнос­ти экспертов можно положить a _i =1.

Результирующей оценкой является медиана построенного распре­деления q ₂, определяемая из условия

Р (T £ q₂) = 0,5

Помимо q ₂ вычисляется диапазон квантилей D q = q ₃- q ₁,

где Р (Т £ q ₃) = 0.75; Р (Т £ q ₁) = 0,25.

Эмпирически установлено, что процедуру можно прекращать, ког­да диапазон квантилей уменьшился в 1,6 раза по сравнению с первона­чальным.

Задача многомерного метрического шкалирования состоит в сле­дующем. Задана симметричная матрица различий D = { d_ij } между n объектами А ₁,..., A_n. Нужно найти координаты точек a_i ÎE _r, сопос­тавленных объектам A_i так, чтобы матрица X = { x_ij } расстояний меж­ду этими точками в Е _r была возможно более близка к исходной матри­це различий D в смысле некоторого заранее выбранного критерия. Приведем алгоритм неметрического многомерного шкалирования. Упоря­дочим по возрастанию n ² чисел, являющихся элементами матрицы D, и обозначим полученный порядок через r (A). Отобразим объекты A_i в пространство E _r и упорядочим по возрастанию n ² чисел, являющихся элементами матрицы расстояний между точками a_i, полученный порядок обозначим через r (a).

Задача неметрического многомерного шкалирования состоит в том, чтобы построить отображение q в пространство минимальной размер­ности так, чтобы r(a) = r (А) - Для этого выполняют следующие опе­рации:

1. Определяют ранжировку r (А)и нормируют элементы матрицы D так, что минимальный равен нулю, а максимальный - единце

2. Помещают n точек в n вершин правильного (n -1) - мерного симплекса, центр которого находится в начале координат, а ребра имеют двину 1. Координаты n точек a ¹, a ²,..., aⁿ в ( n -1)- мерном пространстве вычисляют по формулам

, для четного n проекция на (n -1)-ю ось .

3. Для построенных точек вычисляют ранжировку и сравнивают ее с r (A). Если r (a) = r (A), то вычисления прекращают. В противном случае нормируют матрицу расстояний Х между точками aⁱ так же, как матрицу D. Элементы пронормированных матриц обозначают через и соответственно.

4. Находят новые значения координат точек a_i по формулам .

где ; ; ; ; a=0,2; b=0,05. Полагают , вычисляют ранжировку r (a) и повторяют приведенные операции.

Методы принятия решений

Доминирование Пусть X = { x ₁,..., x_n } множество допустимых альтернатив. Каждой альтернативе х Î Х поставлено в соответствие числовых показателей - критерии оценки ка­чества альтернатив. Каждая альтернатива представляется как точке в критериальном пространстве Е _m. Точка находится в отно­шении Парето c точкой , если для которого . Если критерии j _i возрастают по предпочтительности, то из двух точек , таких, что находится в отношении Парето с следует выбрать и соответственно альтернативу x ₄. Множество недоминируемых по Парето альтернатив, образует аффективное множество (оптимальное по Парето). Поскольку не все точки сравнимы по Парето, то эффективное множество может содержать от одной до n точек, т.е. все множество исходных альтернатив.

Использование глобального критерия. Пусть сформулирован ряд гипотез о проблемной ситуации и несколько вариантов решений (альтернатив). Для каждой гипотезы определены вероятности их осуществления. Результаты представлены в виде таблицы 6

Таблица 6

Гипотезы Альтернативы	S 1	S 2	...	S n
A1	f11	f12	...	f1n
A2	f21	f22	...	f2n
Am	fm1	fm2	...	fmn
Вероятности гипотез	P1	Р2	...	Рn

Различают три вида стратегий: осторожная (пессимистическая), оптимистическая и рациональная (рассчитанная на средние условия). Применение критерия пессимизма не требует знания вероятностей ситуаций, и в этом его преимущество, поскольку часто эти вероятности неизменны.

В случае измерения в порядковой шкале . Эта стратеги известна как принцип гарантированного результата или максиминный критерий Вальда. Критерий оптимизма . Если предпочтения в рангах, то . Критерий максимума среднего выигрыша .

Критерий Гурвица .

Метод ограничений, метод уступок. Пусть j₁,j₂,...,j_m - множество целевых функций (критериев) X ₀ - ограничения на множестве альтернатив.

Допустим, что ЛПР считает возможным выбрать любую альтернативу x Î X ₀, для которой выполняются условия j _i (x) ³a _i, , где a₁,...,a_m - установленная ЛПР нижняя граница по каждому критерию. Если такая точка не найдётся, то ЛПР снижает уровни своих притязаний a₁,...,a_m, и действует таким образом, пока такая точка не найдется.

Модификация этого подхода, представляет собой процедуру, в которой устанавливается нижняя граница для всех критериев, кроме одного свободного критерия. Для свободного критерия j_k решается однокритериальная задача

Если ЛПР не удовлетворено полученным результатом, то процедура повторяется при другом свободном критерии и ограничениях.

В методе уступок предполагается, что критерии можно упорядо-

чнть но важности j₁,j₂,...,j_m. В начале решается задача

Пусть -решение этой задачи.

Далее ЛПР задает величину D₁ - уступку по критерию j₁. Решается задача На последнем шаге

Метод целевой функции свертка критериев. ЛПР описывает структуру предпочтения критериев в виде скалярной целевой функции F (j (x),l), где l - вектор параметров. Часто F - линейная функция. Задавая начальные параметры l₀, решается одноэкстремальная задача

Если ЛПР не удовлетворено полученными значениями критериев, то вектор l₀ меняется. Метод идеальной точки. Предполагается, что в пространстве критериев задана точка "идеала" "точка утопии" j^* и в этом же пространстве введена метрика r(j, j^*). Решается следующая задача Как правило используется обобщенная евклидова метрика .

Решается следующая задача

При р = 2, получаем обычное евклидово расстояние.

При р = 1 имеем .

При получим равномерную метрику .

Естественный способ задания идеальной точки следующий . Функция расстояния до идеальной точки позволяет упорядочить все альтернативы и выбрать наилучшую. Однако необходимо иметь в виду, что упорядочение с помощью метрики не отвечает аксиоме независимости, которая требует чтобы результат сравнения двух альтернатив не зависел от наличия третьей альтернативы. Этот эффект обязан смещением идеальной точки, за счет добавления некоторой альтернативы. Этот эффект продемонстрирован на рис.7 и рис.8.

При выборе метода принятия решений важной его характеристикой

является мощность множества выбранных альтернатив и соотношение

этого множества с множеством Парето.

Утверждение 1. Обозначим через X^ид множество альтернатив.

выбранных с помощью метода идеальной точки.

Если множество векторных оценок допустимых альтернатив выпукло то для любого р, кроме р = 1,¥ справедливо | X^ид |=1.

Утверждение 2. Для любого р, кроме р=¥ выполняется условие , где X^P - множество Парето.

Нарушение утверждения 1 при иллюстрируется на рис.9, а нарушение утверждения 2 при на рис.10

Градиентный метод. Пусть векторной оценке каждой из альтерна­тив поставлено в соответствие действительное число, т.е. на множест­ве векторных оценок определена скалярная функция v, прячём спра­ведливы следующие соотношения, которые определяют структуру предпоч­тения ЛПР:

Будем называть определенную функцию v функцией ценности. На рис.11 показан пример функции ценности, представленной кри­выми безразличия линиями равного уровня в случае двух критериев

Восстановление функции ценности позволяет упорядочить все альтерна­тивы. Трудности, связанные с восста­новлением функции ценности, а также отсутствие необходимости в упорядо­чении всех альтернатив, привели к следующей человеко-машинной проце­дура поиска наиболее предпочтитель­ной альтернативы.

Основу градиентного метода составляет подходящий формальный алгоритм оптимизации (например, Франка - Вульфа). Предполагается, что предпочтении ЛПР могут быть описаны некоторой априори неиз­вестной скалярной функцией. Фиксируются свойства таких функций, которые используются для определения ее градиента и для выбора ве­личины шага при одномерной оптимизации.

Предлагается вычислять градиент с помощью определения предель­ных норы замещения одного из критериев всеми остальными. Эта опе­рация выполняется в режиме диалога ЛПР с ЭВМ. Для определения ве­личины шага ЛПР представляется график изменения всех критериев вдоль выбранного направления и ЛПР должен указать на нем оптималь­ную точку.

Методы принятия решений в условиях риска. Задача формулиру­ется следующим образом. ЛПР должен выбрать одну из нескольких аль­тернатив, каждая из которых в конечном итоге будет иметь своим ре­зультатом некоторый исход. Принимающий решение точно не знает, к какому именно исходу приведет любая из выбранных альтернатив, но для каждого способа действий он в состоянии установить вероятности получения различных исходов. Схема такой ситуации для двух альтер­натив (действий) и двух исходов представлена на рис. 12.

Пусть L= (p₁, x ₁; p₂, x ₂) - лотерея, где P i - вероятность выигрыша x_i. Выбор действия a ₁ или a ₂ можно рассматривать как выбор из лотерей

L₁ = (p₁₁, x ₁; p₁₂, x ₂); L₂ = (p₂₁, x ₁; p₂₂, x ₂). Как установить отношение предпочтения на множестве лотерей?

Обозначим через u (х) функцию полезности на множестве исходов. Ожидаемая полезность лотереи и является показателем, который следует использовать при выборе лотереи. Следует выбирать ту лотерею, для которой максимальна ожидаемая полезность. Пусть в результате исследования структурных условий независимости критериев выявлено, что m - мерная функция полезности быть декомпозирована может следующим образом

где - некоторая строго монотонная аддитивная, мультипликативная, полилинейная функция;

u_j (r_j) - одномерная функция полезности, отражающая предпочтения ЛПР на множестве значений критерия R _j и его отношение к риску.

В таком случае построение u (r) заключается в восстановлении u_j (r_j) для и определении параметров функции .

Независимо от типа шкалы критериев R _j и метода восстановления u_j (r_j) вся работа по её построению может быть условно разбита на пять этапов:

· подготовка к построению функции полезности;

· выявление существенных качественных характеристик;

· определение количественных характеристик;

· выбор аппроксимирующей функции;

· проверка согласованности ответов ЛПР.

Включение подготовительного этапа преследует две цели:

· ЛПР должно понять, что консультанта интересует предпочтение именно

ЛПР (нет и не может быть объективно правильных предпочтений);

· определить область изменений значений критерия R _j. На этапе выявления

качественных характеристик определяется отношение ЛПР к риску и проверяется, является функция полезности

u_j (r_j) монотонное. Для проверки монотонности выясняют, предпочита­ет ли ЛПР точку S точке Q (рис. 13) или наоборот. Пусть , тогда предлагается сравнить точки 0 и Р и т.д. В заключении можно задать обобщающий вопрос: если r_j ¹ > r_j ^*, всег­да ли имеет место ? Если предыдущие ответы ЛПР давали ос­нование ожидать утвердительный ответ, а получен отрицательный, то следует заново (c целью обучения) проверить и исследовать его предпочтения на множестве значений [ r_j ⁰, r_j ^*].

Для определения отношения ЛПР к риску необходимо выяснить, предпочитает ли ЛПР лотерею < (r_j + h_j);(r_j - h_j) > или же гарантированное значение r_j для произвольно выбранного значения r_j и h_j. Если предпочитает лотерею, то считать расположенным к риску, в про­тивном случае - осторожным. Такого рода сравнение производится многократно для разных значений r_j и h_j, покрывающих весь интервал [ r_j ⁰, r_j^k ]. Если ЛПР постоянно предпочитает r_j, то с уверен­ностью можно сделать заключение, что оно осторожно и наоборот.

На третьем этапе определяется и фиксируется значение функции полезности для некоторых точек r_j Î[ r_j ⁰, r_j ^*]. Чаще всего это сво­дится к выявлению эквивалентов определенности нескольких лотерей вида 50-50.

1. Определяется такое значение r_j ^0,5, что r_j^0,5 ~ <r_j^*; r_j⁰> или в терминах функция полезности u_j (r_j ^0,5)= 0,5 u_j (r_j ⁰) + 0,5 u_j (r_j ^*).

Поскольку функция полезности является уникальной с точностью до положительных линейных преобразований, то можно принять u_j (r_j)=0; u_j (r_j ^*)= 1. Тогда u_j (r_j ^0,5) = 0,5

2. Определяются значения r_j ^0,25 и r_j ^0,75, такие, что

r_j ^0,5 ~ < r_j ^0,5; r_j ⁰ > Þ u_j (r_j ^0,25) = 0,25

r_j ^0,75 ~ < r^*_j; r^0,5_j > Þ u_j (r_j ^0,75) = 0,75

3. Для проверки согласованности суждений ЛПР определяется

такое значение , что ~ < r_j ^0,75; r _j^0,25 >.

Должно иметь место равенство r_j ^0,5 = .

4. Определяется (если необходимо) значения r_j ^0,125 r_j ^0,375 r_j ^0,625 r_j ^0,875

и производится проверка значений r_j ^0,25 r_j ^0,75.

Пример графического представления u_j (r_j) после определения точек

r_j ⁰_, r_j ^0,25_, r_j ^0,5_, r_j ^0,75_, r_j ^* для осторожного (не склонного к риску) ЛПР дается на рис.14

Основным преимуществом такой процедуры является использование легко интерпретируемых ЛПР лотерей типа 50—50, однако сфера ее применимости ограничена критериями отношений.

Рассмотрим метод построения функций полезности на значениях критериев с порядковой шкалой. Пусть критерий имеет R_j имеет M отдельных значений и индексы

K = 1,2,…, M этим значениям присвоены так, что

r_j ^M r_j ^M-1 … r_j ¹_.

Тогда, исхода из свойств функций полезности, можно положить u_j (r_j ¹) = 0 и

u_j (r_j ^M) = 1 предложить для ЛПР совокупность вопросов следующего вида:

определить такое значение вероятности p^k Î [0,1], что лотерея < r_j ^M, p^k, r_j ¹, (1- p^k) > будет равно предпочтительной, сточки зрения ЛПР, определенному результату r_j ^k.

r_j ^k ~ < r_j ^M, p^k, r_j ¹, (1 - p^k) >

и положить u_j(r^k_j) = p^k .

Процедура проверки согласованности полученных оценок аналогична

/* далее ничего непонятно примерно 3 строчки */ (?процедуре, что позволяет определить такие значения вероятности /*какая-то формула*/, что

/* r_j ^k ~ < r_j ^M-1, q ^k,??? r_j^k,(1-qk) > */

После этого определяют новые значения функции полезности w_j(r^k_j) исходя из отношения /* которое тоже не совсем понятное /*

w _j (r_j ^k) = q ^k u_j (r_j ^M+1) + (1 - q^k) u_j (r_j ²).

Если затем, для всех kÎ3, M-2 имеет место w _j (r_j ^k) = u_j (r_j ^k) ± ε,

т.е основание считать оценки ЛПР согласованными.

Определение шкалируемых констант. Если строго монотонная функция ψ может быть представлена аддитивной, мультипликативной или полилинейной формой, то после восстановления u_j (r_j ^k), следует определить шкалируемые константы.

Сложность данного этапа работы заключается в том, что ЛПР сравнивать многомерные исходы и лотереи на них.

Введем обозначения:

r ^* = (r ₁ ^*, …, r_j^*,…_, r_m ^*) – исход, все компоненты которого принимают наиболее предпочтительные значения соответствующих критериев;

r ⁰ = (r ₁⁰, …, r_j ⁰,…, r_j ⁰) – исход, значение компонент которого зафиксированы на наименее предпочтительном уровне;

(r_j ^*_, r_j ⁰) = (r ₁⁰…, r_{j -1}⁰, r_j ⁰, r ⁰ _{j +1},…, r_m ⁰) – исход, все компоненты которого зафиксированы на наименее предпочтительном уровне, за исключением j -той компоненты, которая принимает значение r_j ^*.

Тогда, если u (r ⁰) = 0 и u (r ^*) = 1, а также

u_j (r_j ⁰) = 0, u_j (r_j ^*) = 1, (),

то k _j = p _j, , где p _j Î [0,1] – такое значение вероятности, что равноценными для ЛПР является определенный исход (r_j ^*_, r_j ⁰) и лотерея, производящая исход r ^* с вероятностью p _j и исход r ⁰ с вероятностью 1- p_j т.е.

/*стертая формула*/ (r_j ^*_, r_j- ⁰) ~ < r ^*, p_j^m; r ⁰,(1 - p _j)>

Далее следует провести контроль определенных констант.

Под задачей выбор а понимают выделение некоторого подмножества альтернатив из заданного множества при неопределенном принципе оптимальности. В практической ситуации выбора при некотором множестве альтернатив лицо, принимающее решение, выбирал некоторую альтернативу, руководствуется своим личным представлениём о лучших альтернативах. У разных лиц в одной и той же ситуации представление о лучших альтернативах может различаться, а, следовательно, они могут выбирать разные альтернативы. При этом каждый из них может привести вполне рациональное обоснование сделанного выбора. Даже при выборе одних и тех же альтернатив разными лицами обоснования могут различаться. Таким образом, по известному выбору в конкретной ситуации вряд ля можно сказать что-либо определенное о тех причинах, которые побудили сделать именно данный выбор, а не другой, т.е. восстановить логику выбора. Для формализации взаимной зависимости выборов при взаимосвязанных ситуациях пользуются понятием функции выбора.

Дата добавления: 2015-08-29