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

вы — решения х* целесообразно осуществить согласно максимальному значению функции цг(х). При этом структура механизма выбора реше­ ния записывается в виде [7;8]

х* € Ага max X,

Х<йс(х),

Х^цс(х),

хеХ.

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

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

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

1.8. Структуры механизмов выбора решений коллективом экспертов

Под г р у п п о в ы м в ы б о р о м р е ш е н и я понимают выработку со­ гласованного коллективного упорядочения альтернатив на основе систем предпочтения экспертов или, что то же, тройку (X , {> }, / е [1,я]), где X —

конечное множество альтернатив, >„ — система предпочтения /-го экс­ перта (СП,), [1,я] = N — количество экспертов.

Введем обозначение R, для СП,. Очевидно, что в случае, когда СП/ V/ е N, может быть заменена функциями полезности соответствующих

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

По результатам упорядочения N экспертов должна быть выделена наилучшая альтернатива. Далее будем исходить из того, что СП, V/ е N,

31

определяет полное транзитивное асимметричное бинарное отношение предпочтений на множестве X, и каждый эксперт ранжирует альтерна­

тивы самостоятельно.

Результаты ранжирования составляют так называемый профиль по­ рядков предпочтений (Д,, Zf2, R„), и структура механизма группового

выбора решения представляется правилом

F : (Л,, Л2, ..., R„) —>R,

где R — профиль порядка предпочтений коллектива.

Здесь отметим важное обстоятельство: единственного правила F не

существует, оно строится согласно принятой экспертами системе акси­ ом, охватывающей все возможное множество профилей предпочтений экспертов. Соответствующая исходная система включает следующие ак­ сиомы Эрроу:

Аксиома универсальности. Правило F определено для всех возможных профилей предпочтений экспертов.

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

Аксиома независимости от посторонних альтернатив. Если профиль предпочтений изменен так, что в попарных сравнениях альтернатив неко­ торого подмножества Х ] и исходного множества альтернатив X пред­ почтения экспертов остаются без изменений, то порядки коллективной системы предпочтений для альтернатив из Х х, обусловленные первоначаль­ ными и измененными профилями предпочтений экспертов, должны быть одинаковыми, т.е. эксперты располагают и руководствуются информаци­ ей только об альтернативах из Х х.

Заметим, что эта аксиома не всегда выполнима. Сущность аксиомы заключается в сведении построения порядка на множестве X к парным

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

Аксиома суверенности экспертов. Для каждой пары альтернативхиу найдется такой профиль предпочтений экспертов, что по системе пред­ почтений коллектива экспертов х будет предпочтительнее у.

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

графическим; при отсутствии диктатора возможно игровое взаимодей­ ствие между экспертами без информирования друг друга).

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

32

Теорема Эрроу. Если число экспертов не меньше двух, а количество альтернатив не меньше трех, то не существует правила группового выбо­ ра решения, удовлетворяющего перечисленным аксиомам. (Об условии и

требовании по преодолению утверждения теоремы см., например, [131]).

Эта теорема допускает различные модификации системы аксиом. Они изложены в [40;50;71], и по ним построены соответствующие пра­ вила — механизмы группового выбора решений. При этом правила удовлетворяют требованию согласования индивидуальных бинарных от­ ношений предпочтения в одно коллективное и требованию существова­ ния недоминируемых альтернатив по коллективному бинарному отно­ шению предпочтения на всем множестве X; иначе говоря, правила

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

А. Правило простого большинства. Принимается коллективное реше­ ние в пользу выбора альтернативы х е X, если большинство экспертов отдает предпочтение этой альтернативе. Иначе, пусть 1(х,у) — число экспертов, строго предпочитающих альтернативу х альтернативе у. То­

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

х> у& 1 (х,у)> 1 (у,х),

х ~ у< ^1(у,х) = 1(х,у).

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

Видно, что по большинству предпочтений следует принять решение в пользу альтернативы х (/ = 10), так как в пользу альтернативы у I = 8, а в пользу z 1 = 7. Но при этом из профиля предпочтений также видно,

что 15 экспертов альтернативу считают наихудшей.

Рассмотрим применение правила большинства в з а д а ч е обнару­ жения ошибок при мажоритарном декодировании линейных кодов [115].

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

п — длина кодовой комбинации сообщения, к — число информационных разрядов,

аи аъ ..., ак, Ьь Ь2, ..., Ьг — кодовый вектор (кодовая комбинация), аь а2, ..., ак — информационные разряды кодового вектора, Ьь Ьъ ..., Ьг — проверочные разряды.

Проверочные разряды формируем из информационных символов па выражению

bj = спщ + спа2 + ... + Cjiflk, j = l, г,

где коэффициенты cJb cj 2 > cjk принимают значения, равные нулю или

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

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

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

дающей матрицы

С каждой кодовой комбинацией на приемном пункте канала свя­ зи связывают систему проверок по числу проверочных разрядов. Так, например, для принятой без ошибок кодовой комбинации а, а2 ... ак Ь{ Ь2 ... Ь, соответствующая система такова:

с„а, + с12а2 + ... + с1как = Ьх,

С11а\ с22а2 Cljflk ~ *2>

Сг\а \ + СЛ°2 + ••• + Criflk = Ьк,

что обычно записывают в виде проверочной матрицы

34

т.е., если ошибки при приеме нет, то

vtf£ =0,

где v = а, а2 ... ак bt b2 ... Ь„ и система является ортогональной (разделен­

ной). Однако в реальных условиях передачи кодов по каналу связи на приемном пункте могут быть ошибки; всего их может быть 2' - 1 .

Если теперь выполнить не менее г проверок, то путем простого го­ лосования можно исправить любые t < (к + 1)/2 ошибок, так как ошиб­

ка в одном разряде (символе) влияет согласно ортогональности не более чем на одну проверку. Отсюда следует, что среди значений символа Ьр

представимого соотношениями

bj = сиа, + спа2 + ... + cikqk

bj = с2,а, + сг2а2 + ... + с2как

bj = сг,а, + сла2+ ... + с^ к,

неправильными могут оказаться не более t < (к + 1)/2. В результате по большинству голосов — значений Ь2 определяется правильное значение

этого символа.

Б. Правило a -большинства. Это правило записывается в виде:

0,5 < а ^ (/ + 1)/2/.

В. Правило суммы мест альтернатив— правило Гудмана — Марковица. Это правило заключается в следующем. Каждый эксперт объявляет свои предпочтения на множестве альтернатив и ранжирует альтернативы в порядке от лучшей к худшей. Система предпочтений СП, каждого /-го эксперта, / = 1 ,..., п, заменяется функцией полезности альтернатив м,(х) х б X. В частном случае такой функцией может быть выбрана функция,

значение которой для самой наихудшей по СП, альтернативы (и эквива­ лентных ей) принимается нулевым, т.е. и,(х) = 0, а для находящихся пе­

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

Если в этом правиле исключить этап восстановления функции по­ лезности и заменить его учетом рангов альтернатив по результатам под­

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

Г. Структура правила Борда. Каждый эксперт согласно своей СП, = 1 , 2, ... п, ранжирует альтернативы в порядке их ухудшения (без­

различие запрещается, но это не принципиально); СП, обладает свойст­ вами рефлексивности, полноты и ацикличности. Наихудшей альтерна­ тиве приписывают ноль очков, предпоследней — одно очко и т.д. Альтернатива, самая лучшая по СП„ получает количество очков, равное числу альтернатив без единицы. Затем для каждой альтернативы вычис­ ляется сумма очков, и наилучшей считается альтернатива с наибольшей суммой очков. Иначе, восстанавливается функция группового выбо­ ра—функция выбора Борда

g(X ,C IIt,/ = Х -,п ) = {х.Ь{х) = тглЬ(у)),

где / — число экспертов, которые высказали предпочтение в пользу аль­ тернативы х, т.е. х у у.

Д. Правило Кондорсе. Оно основано на подсчете очков альтернатив, установленных по результатам их упорядочения каждым экспертом, и на правиле большинства. Сущность правила: строится профиль пред­ почтений на X каждым экспертом и согласно ранжированию альтерна­

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

Этому правилу свойствен недостаток: парные сравнения по правилу большинства могут привести к циклу и, как следствие, к невозможно­ сти выбора наилучшей альтернативы (к парадоксу Кондорсе ). Вероят­ ность проявления парадокса Кондорсе растет достаточно быстро при большом количестве альтернатив.

Состоятельными правилами по Кондорсе являются также правила Копленда и Симпсона [50]. П о п р а в и л у К о п л е н д а сравниваются попарно альтернативы и лучшей альтернативе по правилу большинства приписывается 1 , худшей - 1 и ноль при равенстве; суммируются очки

по всем альтернативам. Альтернатива с наибольшим количеством очков признается лучшей. П о п р а в и л у С и м п с о н а : сравниваются попар­ но альтернативы; определяется число экспертов, для которых одна аль­ тернатива лучше другой. Альтернатива, признанная большим числом экспертов, становится наилучшей из всех.

Е. Правило Дельфи — метод с обратной связью. Согласно этому пра­ вилу, каждый эксперт анонимно выдает ответы на заранее подготовлен­ ную анкету, по сути альтернатив. Ответы экспертов обобщает другая группа экспертов, которая свои результаты обобщения с безличными аргументами передает вновь первоначальным экспертам. Последние на анонимной основе могут уточнить или изменить свои первоначальные

36

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

Ж. Правило упорядочения альтернатив, основанное на применении ло­ гического определителя А[ r-го ранга — на попарном параллельно­

последовательном сравнении альтернатив.

Определение. Логический определитель А[ r-го ранга, г =1, 2,..., к,

есть функция от элементов множества X, равная r-му в порядке неубыва­ ния по СП коллектива экспертов элементу Xм. Это — функция выбора, она является функцией бесконечнозначной логики и выражается в различ­ ных логически эквивалентных формах [113,131]; простейшая из них запи­ сывается в виде дизъюнктивной нормальной формы (ДНФ)

A'k = v х, ..х , ,

где к — количество альтернатив в X.

Из принятого вида А'к вытекает следующая структура алгоритма

упорядочения альтернатив.

5. По результатам оп. 4 выписать упорядоченные в порядке неухудшения элементы

Проиллюстрируем работу алгоритма на примере. Пусть Х = { х ь х2 х3}. Тогда согласно ДНФ для A[, r= 1 , 2, 3, имеем соотношения

х (,) = А \ = х,х 2х3,

которые реализуются алгоритмом со структурой, представленной на схеме (рис. 1 ).

Эта структура трехступенчатая, в ее составе 8 двухвходовых экспер­

тов.

Эксперты на основе попарного сравнения элементов согласно опе­ рациям V, д выделяют лучший или худший элемент.

3. Метод Саати [114]. Пусть имеется п альтернатив {х,, х2, ...,хи} и

каждый эксперт согласно своей СП„ упорядочивает их. В результате восстанавливается профиль порядков предпочтений. По этому профи-

37

Рис. 1. Структура алгоритма

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

п х п А = (а„) i,j= 1, 2,..., л,

где а9 = w,/wj, w„ w, — веса альтернатив х„ хр вычисленные как суммы их рангов в профиле предпочтений; w, > 0, wy > 0; а„ = 1/ал, ай = aflp V /,/, /.

Матрицу А называют согласованной, она обратно-симметричная, ее диагональ состоит из единиц, значит,

X х ' =п>

где X, — собственные значения матрицы А, / = 1 , 2 , п, Х ^ — наи­

большее собственное значение, равное л, а остальные — нулевые; при этом отклонение А.тах от л является мерой близости полученной шкалы

к основной шкале отношений (см. av). Показатель близости у или, ина-

А -™ ~ п че, показатель согласованности вычисляется по выражению у = —2s -----.

л - 1

Если у = 0, то суждения экспертов полностью согласованы. Собствен­ ным значениям соответствуют собственные векторы w, они вычисляют­ ся из основного уравнения относительно собственных значений и векторов

Aw = X w ,w = (w„ w2, ..., w„).

Теперь для решения задачи упорядочения альтернатив, пользуясь матрицей А, достаточно найти вектор w из основного уравнения

38

и тогда по компоненте w( = max{w, ,w2,...,w„} определить наилучшую

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

£ w, = 1, » = 1 , 2 , п, w, > О

достаточно заметить, что оно совпадает с оптимальным решением в виде седловой точки в смешанной стратегии (w,, w2, ..., wh ..., w„); мак­

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

На практике профиль порядков предпочтений может изменяться во времени; в связи с этим уравнение (*) преобразуется к виду

A(t)w(t) = Xmaxw(0 ,

где Хмп также зависит от времени.

На основе решения задачи (*) восстанавливают также функцию

принадлежности Цс(х,), Цс(*2)» —>Мс(*я) альтернатив х2, ..., х„ к не­

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

ляются по выражению ц с (х,) = — — , из которого видно, что значения

2 > ,

/>1

оказываются измеренными в шкале отношений. Восстановленная та­ ким образом функция принадлежности имеет субъективный характер; она может рассматриваться с точки зрения понятия субъективной веро­ ятности, т.е. РсС*/) принимается как вероятность принадлежности х, к множеству С, определяемая ЛПР, а Рс(*/)> / = 1, 2,..., л, как смешанная

стратегия ЛПР.

Изложенная идея упорядочения альтернатив используется и в мето­ дах отбора наиболее информативных признаков в статистических зада­ чах и механизмах выбора решений, например, по методу главных ком­ понент, методу дивергенции, энтропии и др. [73; 101—103].

И. Изложим еще один прием упорядочения N объектов (близкий к

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

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

39

для упорядочения объектов исходные данные будут сосредоточены в матрице переходных вероятностей Р. Последние оцениваются по коли­

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

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

азначит, становится обоснованным применение эргодической теоремы

[84]для определения порядка на множестве объектов независимо от на­ чального состояния графа. Согласно этой теореме, устанавливается су­ ществование неподвижного (собственного вектора для собственного

значения X = 1 ) вероятностного стационарного вектора матрицы пере­ ходных вероятностей Р. Обозначим через q = {q \,q \,-,q 'N) неподвиж­

ный вектор. Стационарный вектор q вычисляется из однородного мат­ ричного уравнения q = Pq или, что то же, из решения линейной

системы алгебраических уравнений

ij* °>

1=1 м

где Р0 — элементы матрицы переходных вероятностей i,j= 1,2,..., N,

X = 1, Е — единичная матрица такого же размера, что и матрица Р.

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

1.9. Принцип организации выбора решения

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

1.Задача принятия решения заключается в выборе из заданного ис­ ходного множества элементов наилучшего элемента или некоторого подмножества наилучших элементов, при которых обеспечивается дос­ тижение экстремального значения критерия качества при удовлетворе­ нии требований-ограничений, обусловленных заданными (или текущи­ ми) условиями: определенности, неопределенности, конфликта, или риска.

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

40