книги / Математические методы в системах поддержки принятия решений
..pdfОтношение предпорядка монотонно, если |
x+z>-x, |
У х е X, У 1 е X, |
|
выпукло, если для УХ е [0,1] и всех х е X, |
y e X, z s |
X имеет |
мес |
то условие (у yx,z - < х) =>Ху+(1-Х,)г у х , |
и строго |
выпукло, |
если |
(у у х, у * х) =ф А.у+(1-Х,)х >- х или, что то же yRx =ф[Ху+(1 - Х)х]/Ьс.
|
Отношение |
R ациклично, |
если последовательность |
x ]Rx1, x2Rx3, ... |
..., |
xvRxv+l не |
приводит к |
х„+)Лс,. Такое отношение |
асимметрично, |
R n |
Rr' —0 , так как если x,Rxj выполняется, то XjR~'xt не выполняется, |
R~' = 0 .
Ацикличным является транзитивное, антирефлексивное отноше ние, так как оно асимметрично. Транзитивное и антирефлексивное бинарное отношение называют отношением строгого частичного по рядка.
Свойства ацикличности и транзитивности имеют существенное зна чение при обосновании утверждения о существовании функции полез ности на исходном множестве элементов X.
Функцией полезности называется действительная монотонная функ ция на упорядоченном X, т.е. функция, для которой и(х) > и(у) <=> х ч у, х, у е X. На классах безразличия такая функция постоянна. Функцию полезности называют также индикатором предпочтения на X. Линии
(поверхности) равных значений (уровней) функции полезности пред ставляют кривые безразличия, которые непрерывны и дважды диффе ренцируемы. При этом существует непрерывная кривая, пересекающая каждую поверхность безразличия ровно в одной точке и такая, что ее точки упорядочены по предпочтению. Если исходное бинарное предпочтение представляет собой выпуклый монотонный предпорядок, то такое отношение аппроксимируется вогнутыми функциями полез ности.
В теории и задачах принятия решений рассматривают следующие типы функций полезности. И н д и в и д у а л ь н а я ф у н к ц и я п о л е з н о с т и — это действительная функция, которая заменяет отношение предпочтения индивидуума — лица, принимающего решение в интере сах достижения своей единственной цели.
К о л л е к т и в н а я ф у н к ц и я п о л е з н о с т и (КФП) — это вектор-функция с действительными компонентами, каждая из которых заменяет отношение предпочтения отдельного суверенного индивида. При этом индивид является равноправным членом группы лиц, прини мающих решение на основе единогласия для достижения многих целей; КФП может заменять векторное отношение предпочтения и отдельного индивида в случае принятия им решения по многим целям. Одна из особенностей-трудностей при групповом принятии решения заключает ся в сравнении и агрегировании предпочтений индивидов. В связи с этим рассматривают эгалитарную и утилитарную КФП.
Э г а л и т а р н а я КФП строится на основе принципа справедливого отношения к равноправным суверенным участникам выбора решения. Однако этот принцип в общем случае не всегда согласуется с принци пом единогласия индивидов. Групповое решение может быть принято и на основе некоторой подсовокупности совокупности исходных отноше
21
ний предпочтения, т.е. КФП в этом случае не будет отражать в полном объеме интересы всех индивидов. Разновидностью эгалитарной КФП является, например, диктаторская к-го ранга; к — индекс индивида как
диктатора в составе группы или это индекс доминирующей компоненты векторной функции полезности индивида как лица, принимающего ре шение. Эгалитарной КФП является также сепарабельно аддитивная КФП.
У т и л и т а р н а я КФП представляется суммой ее компонент, т.е. суммой функций полезностей, соответствующих отношениям отдель ных индивидов из состава их группы. При построении такой функции могут быть выдвинуты дополнительные ограничения по выполнению требований индивидов; она согласуется с принципом единогласия (уни таризма), а любой максимизирующий ее элемент из X будет оптималь
ным по Парето.
Конкретные структуры КФП нами изложены в п. 1.8 и в главах 3 и 7.
1.3. Структура механизма для условий определенности
В условиях определенности ЛПР располагает единственной целью и множеством действий-решений Г с элементами у, которые он может
принять по отношению к неизвестному параметру ю как альтернативе из X. В связи с этим ЛПР должно определить, как, в какой последова тельности выбирать элементы х е X, когда окончить выбор и какое ре
шение принять: утвердить ли единственное <о’ как наиболее предпочти тельное в А" и считать, что со* = х \ либо остановиться на некотором £2 как подмножестве предпочтительных элементов из X; здесь х — резуль тат испытания (исход), X — множество исходов испытаний. Формально связь элементов х и со можно описывать числовой функцией связи Дх/со), определенной на произведении Х х {оо}, а действие ЛПР — ре шающей функцией ф(у/х), определенной на X и отображающей X в Г.
Каждая решающая функция однозначным образом должна разбивать множество X на два подмножества, в одном из которых будет содер
жаться £2 или («/.Очевидно, что подмножество, не содержащее £2 или со” следует исключать из дальнейшего процесса поиска £2 или со*. Для оцен ки последствий этого введем числовую функцию потерь (выигрыша) г (ш, у(х)), определенную на произведении множеств {со} х Г. Поскольку
здесь принятие решения рассматривается в условиях определенности, то естественно считать решающую функцию детерминированной, при нимающей значение, равное единице, если х € {со}, или нулю — в про
тивном случае. Функция связи принимает такие же значения: 1, если х ш о е {со}, и 0 — в противном случае, т.е. эта функция является харак теристической. При таких исходных данных множество X содержит хотя бы одну приемлемую альтернативу, а универсальное множество А не
прерывно по Хаусдорфу; выбор лучшей альтернативы согласуется со слабой аксиомой выявленного предпочтения: если элемент х, явно
22
предпочтительнее элемента хр то элемент х} не может быть предпочти тельнее элемента x h Тогда [12] имеет место утверждение о существова
нии функции выбора, реализуемой скалярным экстремальным механиз мом, т.е. можно записать для ЛПР функционал качества принятия решения; при конечном множестве X он имеет вид
Я(со,ф) = X X Ко>.7(ж)ЖУ/ * )/(* / «>).
уеГхеХ
а с учетом свойств введенных функций связи и решающей функции преобразуется к виду
Л(<0,ф) = ф>,у(х)).
Тогда искомое оптимальное решение есть результат реализации меха низма минимизации (максимизации) функции потерь (выигрыша) на множестве решений, т.е.
mmr{m,y(x))- » у* или minr(y(x))-» у*,
или, что то же, minr(x)-» х* =о>\ так как в рассматриваемых условиях
множество всех возможных решений Г =Х, а со, Я с X; X описывается
системой неравенств и равенств.
Заметим, что конкретный метод реализации этого механизма зави сит от свойств функции г(х) (непрерывности, гладкости, наличия ло кальных экстремумов), свойств множества X (выпуклости, связности, замкнутости) и свойств функций, описывающих его границу дХ. Для
примера рассмотрим следующую з а да ч у . Найти
шахЯ(х), х = {х,, х2, ..., х_}, (или minF(x,w)),
х>0 w>0
где Я(х) = ( p ,/’r (x ))-(w ,x r ), (F(x,w) = (\/p)[II{p,w) + (w7» ] ) ;
Т— обозначение транспонирования, Я(х) — суть г(х);
р— вектор, компоненты которого есть цены единиц соответствую щей выпускаемой продукции Y = (у,, у2, ..., у„);
F(x) — вектор выпускаемой продукции, Y = F(x), х — вектор затрат; w — вектор с компонентами цен единиц соответствующих затрат.
Это задача выбора решения по наилучшему поведению фирмы в стабильных условиях. Критериальная функция Я(х) выражает прибыль. Свойства этой функции определяются свойствами производственной функции F(x), компоненты которой могут быть степенными гладкими
функциями, функциями с постоянной эластичностью — ограниченны
ми функциями, производственными функциями с постоянными про порциями — непрерывными гладкими функциями, линейными произ водственными функциями и др.
23
1.4. Структура механизма для условий неопределенности в цели
Эти условия приводят к задачам принятия решений по векторному функционалу качества, каждый из компонентов которого однозначно отражает соответствующую частную цель ЛПР. Пусть, например, иссле дуется замкнутая экономическая система, состоящая из п производст венных фирм, т потребителей и ценообразующего органа-рынка.
Выпуск продукции описывается производственными функциями, а по требление — функциями полезности. Финансовые взаимоотношения между фирмами и потребителями описываются матрицей
Л = (а*), а„> 0, Y , a u =1>
]
где а9 — это доля прибыли у'-го производителя, которую он отдает /-му
потребителю.
Производственные фирмы стремятся извлечь максимальную при
быль шахр(у), потребители — получить максимальную полезность от
У]
приобретения товаров (продукции), т.е. шахи, (х), а рынок должен быть
в ситуации равновесия: весь спрос полностью удовлетворяется, а по ставленный товар сверх спроса имеет нулевую цену.
Состояние равновесия описывается следующими соотношениями, составляющими модель Эрроу-Дебре:
maxp(y;), ys е YJt у = |
1, 2,.... п, |
шахи,(х,), х, € Xh i = |
1, 2,.... т, |
||
Yj |
|
|
X/ |
|
|
|
п |
|
|
|
|
р (х ,)^ / |
> ( < |
» |
, j) V /€ |
1, 2,..., т, |
|
|
м |
|
|
|
|
(p,z) = 0, z = x - y - ( 0, х = 2 |
х „ |
у = ^ у . , |
со = £ с о ,, |
Х р (х,) = 1, |
|
|
|
( |
; |
i t |
|
где p(yj) — прибыль у-го производителя, Z — вектор избыточного спроса,
X, — множество товаров потребления, Yf — множество выпускаемых товаров,
р(уу) и и(х,) — векторные функции, их компоненты соответствуют
частным целям.
Достижение каждой частной цели в отдельности составляет задачу принятия решения в условиях определенности согласно скалярному экс тремальному механизму, но, как правило, сдерживает достижение других целей. Функция связи здесь векторная и обладает теми же свойствами, что и в условиях определенности, а любая из оптимальных по частным критериям решающая функция не является устойчивой, и требуется рас смотрение некоторого их семейства — семейства оптимальных недомини-
24
руемых (несравнимых между собой) решающих функций. В данном слу чае отыскание оптимального решения по векторному функционалу может быть выполнено с использованием паретовского механизма, опре деляющего для ЛПР на множестве его решений Г подмножество
Г = {у0: у0 е Г, Vy е Г [г,((0, у (х)) £ |
|
> п((о, у°(х)) => г,{(О, у(х)) = г,(<о, у°(х))], |
‘ = М>, |
где /•/(со, у(х)) — /-й компонент векторного функционала R(со, ф), |
|
Г = (J/XA), Г(К) = Aig min[max X ,г, (ю,у(х))], |
А, >0, Y А, = 1. |
В условиях приведенного примера у{х) ~ {ух, у г, ...,у„,хь хг, ...,хт,р), |
о — истинное состояние рынка, соответствующее конкурентному рав новесию,
П - ( p i y ^ M x , ) ) , Г х У ~ Х , Y = IJYj, X = I J X r
Теперь выбор лучшего решения из подмножества ДА) ЛПР может осуществить на основе дополнительной неформализуемой информации либо после сужения ДА,), например с использованием механизмов по иска среднеквадратичных или арбитражных решений [40].
Отметим, что принятие решений в рассматриваемых условиях мо жет выполняться при использовании и других механизмов, которые бу дут рассмотрены ниже.
1.5. Структура механизма для условий конфликта
Конфликт здесь понимается достаточно широко: статический и ди намический, антагонистический между двумя участниками или их коа лициями, неантагонистический между двумя и более участниками или их коалициями, конфликт в двух или более уровневых иерархических структурах. Каждый из участников может преследовать одну или не сколько целей и действовать в конфликте согласно своим собственным интересам либо интересам коалиции или уровня, в составе которого он находится. Естественно считать, что интересы каждого участника описываются соответствующим функционалом качества принятия им решения по стратегии поведения в конфликте и заключаются в дости жении как можно большего с позиции выигрыша его значения. В за висимости от информированности участника конфликта и порядка получения информации о возможных действиях других участников (коалиций, уровней) стратегии будут определяться как константы или функции; выбор оптимальной из них будет осуществляться согласно де терминированной решающей функции. Функция связи — векторная, компонент которой для ЛПР имеет вид
Az/y), z e Z, у е Y,
25
где Z — множество возможных априори сведений или исходов наблюде ний ЛПР за действиями противодействующих сторон; Y — множество
стратегий-действий противодействующих сторон — это декартово про изведение множеств их стратегий, устанавливается оно по априорным сведениям.
Если ЛПР не имеет возможности вести наблюдение за действиями из множества Y, то Z является элементом множества Y. Но тогда его функция связи становится характеристической функцией множества Y.
Будем считать, что стороны не обмениваются информацией о выбо ре ими действий из своих множеств, ЛПР располагает только априори решающей функцией у (у), определенной на множестве Y, и предполо жением, что выбор действия у е Y противодействующими сторонами
может быть детерминированным или случайным.
Последствия принятия ЛПР решений согласно своей решающей функции и с учетом решающих функций противодействующих сторон будем оценивать, как и в предыдущих случаях условий принятия реше ний, значениями функции потерь, определенной на произведении мно жеств Г х D x Y , где Г — множество решающих функций ЛПР, D — мно
жество решающих функций противодействующих сторон.
При изложенных исходных положениях можно записать выражение для функционала качества принятия решения ЛПР. Так, если налицо статический антагонистический конфликт двух сторон, множества их стратегий X, Y конечны и создаются только условия стратегической не
определенности, то функционал качества принятия ЛПР решения запи сывается в виде
Д(ф,ф) = X ' E ^ U y r t z M y / z W z / y W y ) ) ,
где L(y, y(z)) — функция потерь,
Az/y) — функция связи, ' £ f ( z / y ) = 1
Z
<р(y/z) — решающая функция ЛПР, ]£ф(у/г) = 1
г
ф(у) — априорная для ЛПР решающая функция противодействую щей стороны, ^ ф (у ) = 1.
г
Порядок суммирования в выражении для Л(ф,у) можно менять мес тами, так как ряд в его правой части абсолютно сходящийся.
Когда решающие функции — детерминированные, ЛПР не распола гает возможностью получения информации в виде Z о действиях проти водействующей стороны, тогда Z представляется каким-то у е Y, функ ция связи принимает вид характеристической на множестве Y и
функционал /?(ф,ф) преобразуется к виду
Я(<р,ф) = L(y,y(z)) или /?(ф,ф) = Цх,у),
26
так как у(г) есть отображение результатов наблюдений z в действия ЛПР х е X, т.е. y(z) = х и в рассматриваемом случае z =y. При этом каждый
из участников конфликта вводит на своем множестве стратегий систему бинарных отношений предпочтения (нестрогого или строгого, или эк вивалентность), которые в совокупности удовлетворяют принципу максимина [40]; последний означает, что ЛПР не может рассчитывать на благоприятные стратегии по отношению к нему со стороны противо действующих сил и обязано при выборе решения проявлять осторож ность. Тогда механизм принятия ЛПР решения записывается в виде
у 0 в x°Arg max minЦу,х),
хеХ yeY
У<>)€Г
где операция min разрешает стратегическую неопределенность относительно выбора действий противодействующей стороны.
Отыскание решения у# е Г (х° е А), как правило, осуществляется с
использованием условно-экстремальных методов недифференцируемой оптимизации. При этом предполагается сведение максиминной задачи с ограничениями к задаче математического программирования. Послед няя формулируется с бесконечным числом ограничений при непрерыв ной по своим аргументам функции Цх,у) на компакте X x Y либо с ко нечным — при дискретной по своим аргументам функции L(x,y).
Заметим, что в случае, когда одна из сторон или обе выдвигают не сколько целей в конфликте, очевидным образом возникают еще и усло вия целевой неопределенности — задача принятия решения становится многокритериальной при конфликте. Отыскание оптимального реше ния в этом случае можно выполнить с использованием паретовского механизма с учетом угроз первой стороне (в ее составе ЛПР) от второй и контругроз второй стороне от первой. Для этого по каждому частному критерию предварительно определяется наилучший гарантированный результат соответственно для условий получения ЛПР и невозможности получения им информации о возможных действиях противодействую щей стороны. В развитие этого положения отметим также, что ЛПР мо жет воспользоваться паретовским механизмом и в конфликте несколь ких сторон, когда каждая из них имеет свою цель и не входит в какиелибо коалиции с другими сторонами.
1.6. Структура механизма для условий риска
Эти условия представляются следующими исходными данными:
— Пространством выборок — тройкой
У= (Z,YAz/y)),
где Z — множество возможных результатов наблюдений за состоянием
условий принятия решений, которые создаются Природой или проти водействующими сторонами (ПиПС);
27
Z € Z, z будем интерпретировать повторной выборкой из распреде ления fiz/y) с неизвестным для ЛПР значением фактора — параметра y e Y;
Y — множество неконтролируемых ЛПР факторов-параметров как
чистых стратегий ПиПС;
Az/y) — функция связи, или в рассматриваемых условиях, это обоб
щенная вероятностная функция (распределение, плотность), или это так называемая функция правдоподобия — функция от у € У при фик сированных результатах наблюдений z е Z;
— Априорной для ЛПР решающей функцией ф(у) — плотностью функции распределения вероятностей на множестве У как чистых стра тегий ПиПС; ф(у) задает смешанную стратегию ПиПС до проведения наблюдения над Z стороной, в составе которой находится ЛПР;
— Множеством решающих функций для ЛПРд.е. ф(уД), определен
ных на |
Г х Z, где Г — множество альтернативных решений-действий |
ЛПР у е |
Г; если наблюдения над Z не проводятся, т.е. Z e 0 , то |
<р(у/г) = <р(у(х», Г=Х, X — множество действий ЛПР, ф(у(х) = ф(х) зада |
|
ет смешанные стратегии ЛПР; |
— |
Функцией потерь L(y,y(z)) или НууХ), определенной на Г х У или |
на Х х |
У когда наблюдения над Z выполняются или не проводятся соот |
ветственно.
При таких исходных данных формулируется функционал качества принятия решения, он записывается в виде среднего вальдовского рис
ка /?(ф,ф). Так, если множества |
У Z, А X конечны, то |
||
Л(ф,ф) = |
X |
X |
v (y )/( V yM y/г) Uy,y(z)) |
Y |
Z |
Г |
|
ИЛИ |
|
|
|
Л(ф,ф) = ^ ^ фООф^ Ш у.*). |
|||
|
|
Y |
X |
если наблюдения над Z не проводятся. Очевидно при этом
]Г ф(у/г) = 1 ]>>(*) = 1 ]Г V(Y) = 1
ГX г
Механизм принятия ЛПР решения записывается в виде
ф* е Arg min тахЛ(ш,ф)
(V)(у)
или для заданного ф в виде ф’ € Arg min /?(ф,ф), где ф* — оптимальное
решение ЛПР. Методы реализации этого механизма зависят от полноты наличия перечисленных выше исходных данных и характеристик близо-
28
ста и сложности условий. Задача отыскания решения ф\ как правило, осуществляется с использованием условно-экстремальных методов.
Раскроем здесь сущность механизма, реализация которого основы вается на методе последовательного анализа. Для этого будем рассмат ривать последовательно выполняемые наблюдения-измерения, состав ляющие конечную выборку fo, z2, z„} объема п.
Пусть измерения одинаково распределены и взаимно независимы. Обозначим через (ф,ф) риск принятия окончательного решения без
проведения наблюдения z„ и предположим, что на выполнение каждого наблюдения z„ / = 0, 1,2,... требуется C(z,) единиц затрат. При этом значение среднего общего риска от наблюдения z„ и последующего вы бора решения будет равно C(z„) + Л*(ф, <p(y/zt, z2, ..., z„)).
Целесообразность проведения наблюдения z„ перед принятием
окончательного решения или его выбора без проведения такого наблю дения можно установить на основе сравнения двух рисков
Kn-i (Ф.Ф) и c (zi) + #(V> <р(т/z„ z2, .... z„)).
Так, если C(z,) + Л*(у, <р(у/г„ z2, ..., О ) < К »-■<¥.ф). то необходи
мо получить; в противном случае — наблюдение z„ не целесообразно.
Отсюда, очевидно, что значение риска, как количественной основы принятия решения относительно проведения наблюдения г„, должно удовлетворять соотношению вида
К (ф,ф) = min{/?*n_, (\у,ф), Л’(ф.ф(уД, ,Z 2 ,...,z„))+C(z„)}.
Если были выполнены измерения г,, z2, ..., z„-2, то после наблюдения z„-2 ЛПР должно решить, выбирать ли окончательное решение из допус тимого множества без очередного наблюдения z„-\ или предварительно выполнить эксперимент по получению z„_l.
Обозначим через Л2”(ф,ф) оптимальное значение среднего общего
риска принятия решения относительно проведения или не проведения наблюдения ,. Тогда по аналогии с предыдущим рассуждением значе
ние /?2*(ф,ф) должно удовлетворять соотношению |
|
|
К (Ф.Ф) = |
(ф,ф), Л'(\|/,ф(у/г, ,г2 |
))+C(z„.{)}• |
Здесь затраты на выполненные наблюдения не учитываются, так как они не оказывают влияния на решение продолжать или не продолжать наблюдение и они не компенсируемы.
Пусть были выполнены наблюдения Z\, Z2, ..., z,-. Тогда целесообраз ность выполнения наблюдения Z/+i перед принятием окончательного ре
шения можно установить согласно принципу оптимальности Веллмана по рекуррентному соотношению
K i (WP) = |
(Ф.Ф). л ‘ (Ф ,ф (уЛ , ,Z 2 ..... z, ))+C(z/+l)}, |
|
* = 0,1,2.....п - 1. |
29
Здесь затраты на выполненные наблюдения также не учитываются. Итак, сущность механизма последовательного выбора окончатель
ного решения заключается в проверке неравенства
(¥>ф) - (¥>ф)>
если оно выполняется, то окончательное решение принимается без дальнейших наблюдений, иначе необходимо выполнить наблюдение Z\.
Далее окончательное решение выбирается без дальнейших наблюдений, если 7^((\|/,ф)< Л’+| (у,ф), в противном случае требуется выполнение
очередного наблюдения, но при этом объем выборки {г,, z2 .... Z»J не должен превысить п.
1.7. Структура механизма для условий нечеткости исходной информации
Кратко изложим одну структуру механизмов принятия решения при нечетко определенной цели и нечетком множестве возможных альтер нативных действий ЛПР [3;4;5] . Здесь нечеткой цели будет соответст вовать какое-то нечеткое подмножество С исходного универсального множества X. Достижение цели, как правило, может быть осуществлено
с какой-то степенью цс (х)-степенью принадлежности при какой-то цс А)-степени выполнения ограничения. Степень принадлежности оп ределяется значением функции принадлежности элемента х е X к С (к G). Функцией принадлежности называют отображение X —> [0,1]. Не
четкое подмножество С, например, универсального множества действи тельных чисел от 15 до 35, ^={15,16,17,...,35} можно представить в виде
С = {(Цс(15) = 1/х= 15),(цс (16) = 0 ,9 Д = 16),(Цс(17) = 0,7/х= 17),
(М18) = 0,3/х = 18),(М19) = 0,1А = 19),<Цс(20) = 0 Д = 20),
(Мс(21) = О Д = 21),...,(|ХС(35) = О Д = 35)}.
Один из методов восстановления рс(х) (|Д.0(х)) изложен в 1.8 п.З. Тогда степень отождествления альтернативы х с оптимальной может
быть определена согласно принципу наилучшего гарантированного ре зультата [6], т.е. при использовании выражения
М*) = min{pc(x),pc(x)} = Цс(х) а ЦСА),
где ц0А), ЦсА) — функции принадлежности, Г = G n C .
Под решением в рассматриваемых условиях понимается нечеткое подмножество нечеткого множества Т с X с функцией принадлежности
ЦуА)- Такое подмножество представляется пересечением нечеткого множества цели и нечетко ограниченного множества исходных альтер натив на множестве X. Выбор же конкретной наилучшей альтернати-
зо