книги / Математические методы в системах поддержки принятия решений
..pdfнезависимо одна от другой, так и в составе независимых коалиций и конфликт может быть либо антагонистическим, либо с непротивопо ложными интересами. В последнем случае стороны, участвующие в конфликте, могут принимать решения в зависимости от схемы обмена информацией о их возможных действиях. Задачи выбора решения в ус ловиях конфликта формулируются как задачи теории классических и динамических игр.
Условия |
принятия решений при н е ч е т к о й и с х о д н о й и н |
ф о р м а ц и и |
возникают: |
—из-за недостаточной информированности ЛПР;
—неоднозначности определения критериев;
—задания нечетких множеств альтернативных действий ЛПР, факторов-параметров;
—неполноты описания связи результатов наблюдения за состояни ем условий с факторами-параметрами, их определяющими;
—неполноты и недостаточности математических моделей описания
иисследования возможной динамики факторов-параметров и т.д. Задачи выбора решения при возникновении таких обстоятельств по
существу представляют непростые модернизации и переформулировки задач теории полезности и хорошо структуризованных задач выбора ре шений в условиях определенности, неопределенности, риска и кон фликта.
Здесь и далее предполагается, что цель или конечное множество це лей формулирует ЛПР; ЛПР определяет также и множество допустимых альтернативных действий (решений).
Одной из характерных и принципиальных особенностей процесса выбора решения является использование информации о состоянии ус ловий. Для этого вводится решающая функция, определенная на мно жестве возможных значений факторов или результатов наблюдений за состоянием условий и отображающая это множество в множество воз можных решений ЛПР, т.е. решающая функция — это правило, по кото
рому на основании полученных наблюдений делают выбор решения. Такие функции могут быть получены различными способами. Они со ставляют соответствующие множества. Решающая функция может быть случайной, детерминированной, логической.
Очевидно, информация о состоянии условий должна быть связана с параметрами условий. Такая связь описывается вещественной функцией,
определенной на прямом произведении множеств априорных сведений или возможных результатов наблюдений за состоянием условий и мно жества возможных истинных параметров условий, иначе говоря, связь описывается параметрической вещественной функцией. Эта функция может быть плотностью распределения вероятностей полученных ре зультатов наблюдений при существовании условий с фиксированными значениями факторов-параметров или условной индикаторной характе ристической функцией на множестве значений факторов-параметров, когда по ним имеются только априорные сведения и они учитываются без ошибок и воздействия помех.
и
Выбор решающей функции должен быть оптимизирован согласно принципу оптимальности. В связи с этим вводится функционал качест ва — критерий эффективности принятия решения или система пред почтений ЛПР.
Критерий эффективности решений должен строго соответствовать целям ЛПР, структуре системы, которую представляет ЛПР, и опреде ляться на полных множествах существенных исходных данных как средств ЛПР для реализации решения и внешних неконтролируемых факторах. Структура системы может быть различной: централизован ной, децентрализованной, иерархической многоуровневой и др. Для ц е н т р а л и з о в а н н о й системы характерно доминирование ее це лей над целями отдельных подсистем и наличие полного информаци онного взаимодействия между ними; вырабатываемые в системе реше ния оптимальны по Парето. В д е ц е н т р а л и з о в а н н о й системе входящие в ее состав подсистемы руководствуются только своими це лями, информационное взаимодействие между ними по существу от сутствует, и вырабатываемые решения будут оптимальными в смысле равновесия по Нэшу. В и е р а р х и ч е с к о й системе имеет место дерево-граф частных критериев, согласно которому организуется об мен информацией между уровнями подсистем и вырабатываемые решения становятся оптимальными в форме равновесия по Штакельбергу или, в общем случае, в форме принципа наилучшего гарантиро ванного результата. В таких системах отсутствует возможность полной централизации выработки решения и предусматривается распределе ние функций по обработке информации; цели подсистем непротиво положны.
Отмеченные обстоятельства обусловливают множество различных ситуаций, задач и методов выбора решения. В методологическом плане в зависимости от возможностей и полноты их количественного описа ния задачи выбора решений можно распределить на такие группы:
—задачи с полным математическим описанием исходных данных, условий, критериев и принципов оптимальности решений;
—задачи с полным математическим описанием исходных данных, условий и качественным описанием критериев и принципов оптималь ности;
—задачи с математическим описанием основных ресурсных исход ных данных и качественным описанием условий, критериев и принци пов оптимальности решений.
Последние две группы задач обусловили актуальную необходимость разработки СППР (систем поддержки принятия решений) человекомашинных систем, позволяющих ЛПР в реальном времени использо вать данные, знания, объективные и субъективные модели при выборе окончательного наилучшего решения [1]; СППР создаются для опреде ленных задач, в своем составе они содержат блок принятия (выбора) ре шений, в котором реализуются формализованные механизмы выбора решений и предъявления соответствующих результатов ЛПР. В нашем случае под такими механизмами достаточно понимать алгоритмы, обес-
12
печивающие решение задачи выбора искомого наилучшего решения или их некоторого множества
где А — множество всех мыслимых альтернатив или это универсальное
множество;
X — конкретное исходное множество допустимых альтернатив, это
множество предъявлений; С(Х) — множество наиболее предпочтительных — наилучших реше
ний или это, так называемая, функция выбора.
Отметим, что функция выбора является математическим выражени ем принципа оптимальности, как основы формирования необходимых и достаточных условий оптимальности принятия решений, и что для выбора решения должны быть установлены ее существование и структу ра, реализуемая соответствующим алгоритмом. Так, если существует скалярная функция
f a(x), х е Х с Е " , такая, что С(Х) = Aig min/ 0(х),
хеХ
то функция выбора С(Х) называется скалярной, она реализуется ска
лярным экстремальным механизмом и имеет место тогда, когда на мно жестве X введено сильно транзитивное антирефлексивное бинарное
отношение предпочтения. По такой функции можно восстановить би нарное отношение, т.е. она, по определению, является рационализируе мой.
Имеют место задачи выбора решений, когда исходы множества X случайны: на множестве X заданы вероятностные меры Р„ i = 1,2,..., п, и
каждая альтернатива появляется согласно этим мерам. Иначе говоря, альтернативами являются вероятностные меры Ph i - 1,2,..., п. Тогда
скалярная функция выбора устанавливается на основе тех же, что и в детерминированном варианте, свойств бинарных отношений R, но вве
денных на множестве вероятностных мер, для которых выполняются также следующие два условия:
(Р} < Pk, а е [0,1]) =» аР, + (1 - |
а )Pk < аР} + (1 - а )Рк, |
||
(Р> < Pj, Pj < Рк) => aP, + |
(1 - а Pk < |
/>,) и Pk < p/>, + (1 - p)i>„ |
|
|
a, pe |
[0,1], |
|
при любых Ph Pj, Pk, i,j, к = |
1,2,..., |
n, i * j * k . |
При этом отношения R относятся к конкретному моменту времени.
Нередко возникает необходимость в рассмотрении нескольких ска лярных функций на X, тогда их объединение называют совокупно
экстремальной функцией выбора. Согласно такой функции, из множе ства X отбираются максимальные элементы, каждый из которых опти
мален по «своему» критерию, например, какой-то (пусть первый) мак симальный элемент оптимален по первому критерию, другой — по
13
второму и т.д. В случае, когда критерии упорядочены по важности, со ответствующая функция выбора определяет лексикографический поря док выбора. Лексикографическое упорядочение обладает важным свой ством: оно позволяет выбрать решение, когда альтернативы слабо различаются. Соответствующая ситуация согласуется с тем фактом, что для ЛПР при равенстве значений каких-то параметров альтернатив ста новится необходимым осуществлять выбор решения на основе сравне ния значений других дополнительных параметров.
Если же на множестве X существует вектор-функция
fix ) = (fi(x), / 2(х),..., /„(*)), х е X,
такая, что |
|
С(Х) = {х е Х р у е Х , у |
(у) £ f (х), i = \,т), |
то функция выбора называется паретовской, она реализуется механиз
мами построения множества Парето и имеет место тогда и только тогда, когда на множестве введено транзитивное антирефлексивное бинарное отношение предпочтения, или, что то же самое, для существования век торной функции выбора необходимо и достаточно, чтобы бинарное от ношение на X было асимметрично и транзитивно.
При введенных системах предпочтения имеют место частичные по рядки [11], это является необходимым и достаточным для существова ния числовых функций-критериев f 0(x) и f{x), / = 1,т; их восстановление
может быть выполнено по алгоритмам [13], в том числе и в зависимости от времени.
Из физических соображений также ясно, что выбор решения объек тивно связан с каким-то выигрышем или затратами. Их характеризуют соответственно ограниченными числовыми функциями выигрыша, по терь, определенными на произведении множеств факторов — парамет
ров условий и альтернативных действий — решений ЛПР. Такие функ ции восстанавливают, как правило, с учетом практических соображений ЛПР. При этом функционал качества принятия решений определяется на множествах решающих функций, функций связи, функций потерь ЛПР и априорных для ЛПР решающих функций сторон, контролирую щих (создающих) условия принятия решений. Будем считать, что вве денные функции составляют соответствующие пространства непрерыв ных функций, а множества их задания — компакты. Тогда формально в математических терминах решение ЛПР представляет результат реали зации принципа оптимальности, т.е. результат оптимизации функцио нала качества как условного апостериорного или априорного риска, вы игрыша, представимого в общем случае вальдовским риском [2] в форме интеграла Стилтьеса или дискретного его аналога — в случае ко нечных множеств. Действительно, потери, связанные с выбором реше ний, объективно (при отмеченных выше особенностях) могут оцени ваться усредненной функцией потерь по распределениям вероятностей альтернатив, выборки при условии альтернатив и решений при условии
14
выборки, т.е. функционал качества определяется как математическое ожидание; последний же есть интеграл Стилтьеса.
Сложившаяся к настоящему времени теория выбора решений, по существу, охватывает концепции, языки и механизмы решения различ ных экстремальных задач. Концепции в общем случае — это системы взглядов ЛПР на постановку и выбор решения в конкретных ситуациях, формально они представляются функциями выбора [10; 50; 131].
Языки в задачах выбора решений сложились в виде критериев каче ства, бинарных отношений, функций выбора, систем аксиом. Так, если X однозначно определено, отображение С(Х) обосновано, записано в
виде конкретной функции или функционала и не зависит от субъектив ных особенностей ЛПР и факторов, то используется язык критериев ка чества, т.е. С(Х) обозначает критерий (функционал) качества выбора ре шения. Если же множество X определено однозначно, а С(Л) не может
быть записано однозначно и представляется вектором критериев и век тором ограничений, выбор решения зависит от ЛПР, а также от условий и информации, которой располагает ЛПР, то используется язык бинар ных отношений или систем аксиом.
1.2. Отношения предпочтения. Элементарные действия и свойства
В настоящее время в задачах принятия решений в основном исполь зуются бинарные отношения нестрогого (слабого) и строгого предпоч тения, а в математической экономике также слабая и сильная аксиомы выявленного предпочтения.
Определение. Бинарным отношением на множестве X называется лю бое подмножество R упорядоченных пар элементов из X, т.е. R c ^ X x X , и это означает, что для Vx, у е X соотношение xRy имеет место тогда, ко гда (х,у) е R. При этом совокупность всех пар (х,у) может быть задана:
— п х п матрицей, элемент а0 которой на пересечении i-й строки и j -го столбца равен единице, если XjRxj, i, j — \,п, и нулю — в противном случае;
—графом, когда каждому элементу х, е X, i = Tpi, однозначно соот ветствует вершина графа, которая соединяется дугой с вершиной х, е X и направлена от х, к хр если x^Rxp а когда / = j, то дуга представляется пет лей при вершине х,\
—верхними и нижними сечениями R+(x) и R~(x) Vx е X,
х е |
R+(x) = {у € Х/(урс) е R] — верхнее сечение (срез) для фиксированного |
X, |
|
|
R~(x) = {у е Х/(х,у) е R) — нижнее сечение (срез) для фиксированного |
х е |
X, |
|
для пустого отношения R = 0 , т.е. когда R не выполняется ни для од |
ной пары
(х,у) е X, R+(x) = R~(x) = 0 , Ъ ( х ) = X \R +(x), R~(x) = X\R~(x) Vx e X,
15
edejl — отрицание (дополнение) отношения R, т.е. xRy =yRx, R = X x X\R и R = R
Вводят различные отношения:
— R~' = {(у,х)/(х,у) е |
R) — обратное к R отношение yR~'x <=> xRy; |
— XxRX2 —отношение включения, если Хх, Х2 — подмножества мно |
|
жества X; |
___ |
—двойственное к R отношение — R d = R~x;
—рефлексивное отношение — Ух е X xRx, т.е. в графе отношения
имеется петля при каждой вершине;
—нерефлексивное отношение — Ух е X (х,х) е R — в графе нет пе
тель;
—симметричное отношение — Ух е X xRy и yRx;
—асимметричное отношение — R n R ~ l = 0 ;
—антисимметричное отношение — из xRy и yRx -> х = у;
—транзитивное отношение — Уд:^,z € Л- из xRy, yRz -* xRz;
—отрицательно-транзитивное — R —транзитивно;
—полное отношение — Vx е X либо xRy, либо yRx, либо xRy и yRx;
— |
слабо-полное отношение — Уде € X, х * у либо xRy, либо yRx; |
— |
ациклическое отношение — из x,Rx2, x2Rx} ..., x„_,Rx„ х, * х п; |
— транзитивно полное отношение — x iRx2, x2Rx3 ..., x„_{Rx„ -4 или x xRx„ или x„Rxt;
—сильно транзитивное отношение — R одновременно транзитивно
иотрицательно транзитивно;
—отношение строгого порядка — R антирефлексивно, антисиммет
рично, транзитивно;
—отношение предпорядка (квазипорядка) — R рефлексивно и
транзитивно;
—отношение эквивалентности — R рефлексивно, симметрично,
транзитивно.
Имеют место и другие отношения предпочтения, и все возможные отношения могут изменяться во времени.
Слабая аксиома выявленного предпочтения. Если альтернатива (набор товаров) х, явно предпочтительнее альтернативы х2, то альтернатива х2 не может быть явно предпочтительнее альтернативы х х; иначе — это асимметричное бинарное отношение предпочтения.
Сильная аксиома выявленного предпочтения. Из альтернатив
x l > x 2, x 2> x i, ..., дс„_ >дс„
не следует альтернатива х„ > х х.
Очевидно, что при п = 2 сильная аксиома включает слабую.
Лемма. Если бинарное отношение предпочтения R есть слабое упоря дочение на X, то оно обладает свойствами полноты (связности, совершен ности),эквивалентности, транзитивности, строгого упорядочения на мно жестве классов эквивалентности — на разбиении исходного множества X.
16
Д о к а з а т е л ь с т в о . Согласно определению отношения слабого упорядочения имеем, что оно асимметрично, отрицательно транзитивно и характеризуется отсутствием строгого предпочтения. Отсюда непо средственно следует выполнение для любых пар элементов х,у е X од ного из отношений: х < у, х > у, х ~ у. Но это означает наличие свойст
ва полноты.
Покажем здесь, что отношение ~ является эквивалентностью, то есть оно рефлексивно, симметрично и транзитивно. Так, утверждение рефлексивности следует из очевидного факта: для заданного х е X име ем х ~ х] утверждение симметричности следует из того, что для х е X и у € X отношение х ~ у означает и отношение у ~ х, а транзитивности — из того, что при заданных x , y , z е X, если х ~ у и у ~ z, то справедливо и соотношение х ~ z-
Свойство транзитивности R непостредственно следует из ассиметричности и отрицательной транзитивности отношения R. Действитель но, пусть х < у и y < z , x , y , z e X , при этом, по определению отрица тельно транзитивного отношения, имеем для x , y , z e X, что xRy => xRz или zRy, т.е. должно иметь место и x < z или х < у и у < х или х < z- Но из-за асимметрии отношения R отношения z < у и у < z вместе не вы полнимы, поэтому должно быть х < z. В результате обнаруживаем свой ство транзитивности: у < х , x < z = * z < y . Естественно, это свойство и свойства исходного отношения R распространяются на множество клас
сов эквивалентности, но тогда последнее обладает строгой упорядочен ностью.
Элементарные операции над бинарными отношениями. О п е р а ц и я в к л ю ч е н и я . Отношение R, включено в отношение R2, т.е. R . < R 2, если множество пар (х„ху), i,j — 1,л, находящихся в отношении л,, со держатся также в множестве пар элементов, состоящих в отношении R2.
Покажем, что при Я, ч R2 справедливы соотношения
a ^ R x) ч a,j(R2) Vi,j, Д + (х) с R2 (х), |
Л,' (х) 2 |
Д2"(*). е X, |
||
где X — исходное множество элементов, на котором заданы Л, и R2, |
||||
|
fl, |
если x.Rx, |
„ |
. . — |
a J R ) = \ ’ |
1 J |
|||
* |
10, |
если не выполнено х, R x j, |
i,j = \,п, |
a,j (К) — правило задания отношений, согласно которому можно со ставить матрицу бинарного отношения R.
Действительно, по определению, имеем Л, £ Л2, но это выполняется только тогда, когда для каждой пары (х„ху) е Л, выполняется также (х„ху) е R2.
Отсюда непосредственно следует, что aij(Rt) ч aij(R2) V/, j.
Справедливость Rf (х) с |
R2 (х) исходит из того, что, по определению |
верхнего сечения, имеем |
R f ( x v) = {х, е X / x v £х,} Vxv е X. Но при |
2-5396 |
17 |
R { £ R2 для _отношения Д2 количество элементов xh удовлетворяющих условию х, ч х„, не меньше, чем для отношения Д,; поэтому Д + (x v) как
конус при вершине в точке x v будет охвачен конусом Д2+ (x v), т.е. R*(xv) c R2 (X v). Для нижних сечений, очевидно, будет иметь место ут верждение Д,'( х„ )э R2(X V).
_ О п е р а ц и я о т р и ц а н и я о т н о ш е н и я Д — д о п о л н е н и я Д; Д — это отношение, состоящее из пар элементов множества X, которые
не входят в Д, т.е.
av(R) = 1 - a0(R), i ,j = 1,л.
Например, отношение Д для элементов множества {(х,у) € € E-Jx1 + у2 = 1} состоит из всех пар (х,у) € Еъ удовлетворяющих усло
вию х2 +У2* 1.
О п е р а ц и и п е р е с е ч е н и я и о б ъ е д и н е н и я о т н о ш е н и й . Пересечение отношений — это отношение, содержащее только общие пары элементов для заданных исходных отношений на множестве X.
Объединение отношений — это отношение, содержащее все воз можные пары элементов исходных заданных отношений на X. Пока жем, что для произвольно заданных Д, и Д2 на X имеют место соотноше
ния
а,у(Д, п Д2) = а,у(Д,) л оДД2); аь{Д, и Д2) = ah{R{) v a0(R2),
где л — И, v —ИЛИ;
(Д, П Д2)+ (х) = R* (х) п Д2+ (х); (Д, и Д2)"(х) = Д,‘ (х) и Д2 (х).
Для доказательства, например, первого равенства воспользуемся оп ределением правила задания отношений д/у(Д); так, для левой части имеем
1 |
если (xi R x j ) n ( x , R 2x J), |
aij(R[ r>R2) = О |
если не выполнено (х, Дху)п (х,Л ху). |
Здесь условие равенства единице будет выполняться, очевидно, только при совместном выполнении отношений х,Л,ху и x,R-pCj, т.е. когда au{R\) - 1 и av(R2) = 1 или, что то же, когда а/у(Д,) л а,у(Д2) = 1; анало
гичным образом устанавливается условие равенства нулю для рассмат риваемого первого равенства. Так же доказывается справедливость и других равенств.
О п е р а ц и я о б р а щ е н и я о т н о ш е н и я Д . Определяется выра жением хД“'у и имеет место тогда и только тогда, когда уЛх; или, иначе, матрица обратного отношения Д-1 является транспонированной к мат рице исходного отношения Д.
18
Докажем, чтоa0(R~l) = a0{R) V i,j =1,л, (Д-1) = (Л)'1, (Д-1)-1 = й и чт о для верхних и нижних сечений справедливы равенства (Л_1)+(х) = R~(x), (R-'Пх) = Д+(х).
По определению правила задания отношений, имеем
)1 |
если |
x,R~lXj, |
х, Д~' ху, /,_/ = 1 л, |
О |
если не выполнено |
||
1, |
если |
XjRx, , |
|
О |
если не выполнено |
XjRx,, i,j = l,n. |
Но когда не выполняется XjRx,, то выполняется х,Дху а этому соот
ветствует в,//?-1) = 1. Значит, при совместном рассмотрении правил за дания отношений Д-1 и R получаем а//? -1) = av(R).
Для доказательства равенства (Л*1) = (ДГ‘ воспользуемся определе нием операций дополнения и обращения отношения. Имеем, по опре делению операции дополнения, а^Д) = 1 — а,/Д); применим это к рас сматриваемому случаю; в результате получим
а4.( Р ’) = 1 -а й.(Л-1) = 1-цуД/?), а*((ЯГ') = я,ДД)=1-ауД/г).
Равенство (Л-1)-1 = R есть следствие равенств х(Л-1)-|у = yR~'x = xRy. Для установления равенства (R~')+(x) = Д“(х) воспользуемся опреде
лениями сечений применительно к Л-1 и Л, т.е. выражениями
(Д"')+(ху) = {х/ € X / х, £ х у}, / r ‘(xv) = {x, е X / х, ?х„}, Vx„e X.
Видно, что из этих выражений следует требуемое. Аналогичным об разом доказывается и равенство (Д~')~(х) = R+(x).
Д в о й с т в е н н о е к Л о т н о ш е н и е Rd. Двойственное отношение Rd является дополнением к обратному, т.е. определяется равенством
Rd = Д' 1.
Покажем, что справедливы следующие равенства:
(Д У = R, (Л, n R2)d = R? u R d, (Л, и Д 2)' = Л,' n Rd.
Воспользуемся определением двойственного отношения и равенст
вом (Д-1) = (Д)’1:
(ДV = (<*''))' = ((ДГ1У = ((Д)-')'' = (Д) = Д.
2* |
19 |
Теперь запишем для (Л, n R2)d соотношения
(Л, nR2)d= (/?, nR2y' =(Rln R2)"' =(/ti иЛ гГ' = (*■)*' u(/?2)-‘ =
= (Л,-, )и (Л 2-1) = < и Л / ,
т.е. получаем требуемое — второе равенство; аналогичным образом до казывается и последнее равенство.
О п е р а ц и я п р о и з в е д е н и я о т н о ш е н и й — к о м п о з и ц и я Л, ° R2. Композиция отношений есть булево произведение соответст
вующих им матриц отношений. Операция произведения ассоциативна (/?! ° R2) ° R3 = R ,° (R2 о R3), некоммутативна R t ° R2* R2 ° Rt.
Свойства бинарных отношений.
Если R рефлексивно, то Rd антирефлексивно, а если R антирефлексивно, то Rd рефлексивно.
Это свойство обусловлено тем, что, по определению рефлексивного отношения, имеем xRx; тогда справедливы равенства
xRdх = х R 1х = xR 1х = xRx, xRdx = xR~' x = xRx.
Если R симметрично, mo R = R~K Действительно, воспользуемся ра венством R = (Л-1)"'- Тогда имеем xRy = x(Rrl)~'y — yR -'x = xRy. Из этих трех равенств следует требуемое, если yRr'x выполняется.
Другое доказательство заключается в следующем. Пусть R ч RT1, то гда из R~' 3 (R~1)"' следует R~' 3 R, откуда R ~ /Г 1 -» xRy = yR~' х, если
yR~lx выполняется. При условии же R у R~l , получаем /Г 1 >-(R~l )-1; но последнее и означает R ~ R~' и xRy = yRr'x, если yRr'x выполняется.
Если отношение R асимметрично, то оно должно быть антирефлексивным. R асимметрично, если R n Rrx= 0 .
Пусть R рефлексивно, т.е. xRx выполняется для Vx е X. Тогда вы полняется и xRr'x и, очевидно, пересечение R n R ~ l непусто. Однако
последнее противоречит определению свойства асимметричности ис ходного отношения. Таким образом, R антирефлексивно и xR~'x не вы полняется, а пересечение R о Л-1 не может быть не пустым; отсюда сле дует, что R асимметрично.
Антисимметричное в широком смысле отношение не симметрично и не асимметрично, оно отрицательно транзитивно, т.е. отношение R анти симметрично в широком смысле, если имеет место xRy и не выполняется yRx, когда х * у . Если же xRy и yRx выполняются, то это означает, что х = у , такое отношение называют слабополым или слабосвязным.
Если отношение R полное, то оно симметрично, рефлексивно, транзи тивно и представимо объединением отношения слабого упорядочения с со ответствующим ему отношением равенства.
20