книги / Математические методы в системах поддержки принятия решений
..pdfd3(F,G) = JT O -G (*)]2W(z))dG(z),
z
где \|/(G (z)) — весовая функция, например \у(<7(г)) = 1.
Если вычисленная статистика не превосходит пороговый уровень с(а), установленный согласно допустимому значению вероятности ошибки первого рода а, то выбор решения делается в пользу гипотети ческого распределения — гипотезы в противном случае принимает ся решение в пользу гипотезы # 0, т.е. решение о несоответствии рас пределения G распределению F. Величина порога с(а) находится из
соотношения
mm, wz)) >cm= а,
где P(d(F(z), G(z)) > c|#i) — закон распределения вероятности статисти ки d. Этот закон табулирован для указанных статистик, соответствую
щие таблицы значений </„ / = 1, 2, 3, в зависимости от а, приведены в [65; 66].
Тест согласия х2 Пирсона. Гипотетическое распределение G(z) из вестно полностью. Область изменения величины Z разбивается на I под множеств Д„ i = 1,/. Далее вычисляются вероятности Р„ / = 1,/, принад
лежности Z e |
Д, по распределению G(z), ^ Р , =1; определяются числа |
|
|
|
/=| |
mh i = T j — |
количества элементов |
выборки z е Z, попавших в |
интервалы-подмножества Д„ i — 1,/, ^ т , |
= п, где п — объем выборки, а |
|
|
/=i |
|
затем вычисляется мера расхождения данных выборки т{, тг, ..., т, с гипотетическими данными прь пръ ..., пр, по выражению
/ |
(т, - п р ,) г |
|
;=1 |
пр, |
|
Выбор решения осуществляется в результате сравнения X2 с |
~ |
процентной точкой случайной величины, имеющей ^-распределение с (п - 1) степенями свободы, т.е. Р(%2 > х«) = а >если для G(z) параметры неизвестны и они оцениваются по выборке объема п, то число степеней свободы для х2_распределения равно п — г — 1, где г — количество
оцениваемых параметров. Если вычисленное значение X2 > %2, т° гипо тетическое распределение G(z) отклоняется; оно принимается, когда
Х2^Х«- Процентные точки х2-распределения приведены в таблицах [65]. Заметим, что х2-тест может быть выведен из метода максимума правдоподобия [62]. Действительно, пусть для Z/e А, каждой подсово
купности Z c Д, известна функция правдоподобия (вероятность попада-
Ш
ния измерений Z в интервал Д,) р "' (Z |Д, ,(3), зависящая от неизвестного
параметра. Тогда функция правдоподобия принадлежности всей выбор ки интервалу Д = иД„ иД, = 0 , при независимых измерениях определя ется выражением
т = Г Р Я" (21д<»р)=П/>”'<р>-
<=1
Умножим правую часть этого выражения на |
и пролога- |
рифмируем:
пР,Ф)
гф) = X 7" '1п
/=1
здесь «Р,(Р) = Zi — ожидаемое количество измерений , которые должны принадлежать интервалу Д(. Составим разность Zi — т ,— пР£Р), тогда
Х « , - Х * ( -»Х^|(Р) — «-о и пР^ф)-т,-ц,
/=1 1=1 1=1
при этом
*Р) = Х >я,1п
/=1
и если i i |
|
т. |
|
тг |
2 ,=i |
|
|
|
m |
|
|
Учитывая, что т, = пР,(Р) |
и максимуму функции правдоподобия |
||
п/оч |
|
-Л (т, - п ^ ф ) ) 2 |
|
А р) соответствует минимум для выражения > |
— ---------------- , приходим |
||
|
|
/«1 |
mi |
к критерию minx2.
Тест Колмогорова—Смирнова. Когда распределение G(z) неизвестно
или представляется неточно заданной сложной гипотезой, проверка ре шения о тождественности эмпирического и гипотетического распреде лений осуществляется по двум выборкам, одна из которых получена из эксперимента, а другая сформирована как обучающая — опорная. В этом случае статистика различения распределений G(z) и F(z) записы
вается в виде
112
d(F„ (z),Gm (z)) = sup \F„(z)-G m(s)|, z
где n и m — объемы одной и другой выборок. Иначе говоря, осуществ ляется проверка однородности смешанной выборки объема п + т. Ре шение принимается в пользу тождественности распределений Gm и F„,
когда выполняется условие
d(F„,GJ < da,
где da — пороговое значение, установленное согласно допустимой ошибке первого рода а, в противном случае гипотеза Gm(z) отклоняется. Значение da вычисляется по распределению Колмогорова для статисти ки d(F,G) [65].
Знаковый тест. Тест основан на подсчете положительных и отрица тельных знаков независимых выборочных данных — наблюдений отно сительно нулевой медианы. Пусть z = (s,, s2, •••> z„) — выборка объема п из независимых одинаково распределенных значений; тогда знаковой статистикой называется вектор
sign* = (signs,, signs2, .... signs„),
1,s, >0, / = 1,и,
где signs, = •0,s, =0,
- l ,s , <0.
Если случайная выборка описывается симметричной плотностью вероятности, т.е. P(z,) = Д —s,), i = 1,л, то статистика signs имеет распре
деление
Д signs = у) = (1/2)", у = -1 ; 1.
Для выбора решения в пользу гипотезы # 0 о том, что медиана гипо тетического распределения G(z) равна нулю, против альтернативы состоящей в том, что медиана распределения F(z) больше нуля, вычис
ляется статистика вида
I
/(s) = £ signs,, /=i
которая затем сравнивается с пороговым уровнем л(а), установленным для допустимой ошибки первого рода а. Если /(s) ^ л(а), то гипотеза Я0 отвергается, в противном случае она принимается. Статистика l(z) имеет биномиальное распределение с параметром р = P(z, > 0), / = 1,я, и
при этом [61; 64] функции правдоподобия имеют вид
Г т = к\Н 1) = С кяр к(1 -р У -к,
/(/(s) = * |tf,) = C „*(l/2)\ к = 0, 1, 2, ..., «;
8 - 5396 |
113 |
вероятность правильного выбора решения в пользу Я0 равна
/> (у,|я,)= Х О * а - / > Г * ;
*=я(а)+1
пороговое значение вычисляется из выражения
£ с я*(1/«Г = «,
*=к(а)+1
из которого видно, что а не зависит от G(z), т.е. знаковый тест — непа раметрический при симметричном распределении G(z).
Ранговый тест. В основе этого теста перестановки наблюденных и опорных — обучающих данных в порядке их возрастания
*<’>< t 2) <... £ & < ... £ z?*mK
где 2е0 — /-я по величине компонента вектора смешанных данных. По лученный таким образом вариационный ряд называется порядковой статистикой. Пусть в этом ряду компоненты упорядочиваются строго, тогда рангом R, & компоненты называют число компонент, не превос ходящих R, — это ранговая статистика элемента г(0. Ранговая стати стика обладает свойством инвариантности относительно нелинейных
монотонных преобразований, так как они не нарушают расположения элементов выборки в вариационном ряду. Поэтому до выбора реше ния можно пользоваться отношением порядка между компонентами выборки.
Для однородной независимой наблюденной и опорной выборки значение ранга какого-либо элемента, очевидно, должно быть равнове роятно независимо от распределения G(z), так как наблюденные данные
перемешаны равномерно в вариационном ряду. Однако если справедли ва гипотеза F(z) < G(z), то опорные данные должны располагаться пре
имущественно в правой части ряда, т.е. будут иметь место различия в значениях рангов опорных и выборочных — наблюденных данных. Од ним из простых и наиболее распространенных ранговых тестов выбора решения является тест Вилкоксона [671: гипотеза о получении экспери ментальной выборки из симметричного распределения G(z) отвергается,
если сумма рангов обучающей выборки превышает пороговый уровень, который устанавливается согласно допустимому значению ошибки пер вого рода.
Ранговый тест можно преобразовать в мажоритарный выбор или, что то же, в выбор наилучшего элемента независимой выборки по боль шинству голосов индивидуумов (см п.1.7) , когда каждый элемент ха рактеризуется многими признаками и параметрами, а число элементов больше или равно трем. В этом случае вводится функция
114
1, |
|
если по мнению v-ro индивидуума существует единст |
ный z, |
с индексом /, такой, что z, у Z, для каждого z, е z, |
|
8vU/) = -j j e [ M l , ; * / , |
c*v |
|
0 — в противном случае, например когда хотя бы для одной |
||
пары (/, J) z, |
~ Z,, / ФЛ (/, J) из п(п - 1) пар. |
|
|
|
/ЧГ J |
Здесь стСу v е |
[1,/и], т > п — система предпочтений v-ro индивидуу |
|
ма на выборке z |
объема п. Естественно считать систему предпочтений |
индивидуума не зависящей от его индекса v, индекса элемента выбор ки, а также от систем предпочтения других индивидуумов.
В результате реализации индивидуальных систем предпочтения
т
формируется коллективное предпочтение в виде ^ 8 „ (г,) как ранговой
___ v=l
статистики для каждого / = \,п, и осуществляется упорядочение элемен тов Zi в порядке убывания значений этих статистик. Далее выбор наи лучшего h е Z осуществляется на основе учета только максимального
значения ранговой статистики и сравнения его с пороговым уровнем. При этом могут иметь одинаковые максимальные значения статистики больше одного элемента из z. Это случай, когда значения таких стати
стик принадлежат множеству Парето, но тогда принципиально для вы бора окончательного решения требуется дополнительная информация. В связи с этим реализуется многостепенное голосование [68].
Г л а в а пятая
Необходимые и достаточные условия оптимальности выбора решения при конфликте
5.1. Необходимые и достаточные условия выбора решений по принципу максимина
Принцип максимина используется при исследовании, например, конфликта двух сторон или двух коалиций, когда каждая из них стре мится максимизировать свой минимальный выигрыш. Этот принцип называется также принципом наилучшего гарантированного результата.
Соответствующие оптимальные стратегии сторон могут составлять и си туацию равновесия — седловую точку, а в бескоалиционных конфлик тах — точку status quo.
5.1.1. Необходимые условия оптимальности стратегий для статических задач принятия решений
Рассмотрим статическую задачу выбора решений с распадающимися переменными
max min/Хх, у)-» х° е М 0,
хеЛ/о y e N
где х® — оптимальная (гарантирующая) стратегия ЛПР; F(x,y) — не
прерывная вместе с — функция на М'0 — открытом множестве,
М0 е Л/0'; N — компакт; М0 — выпуклый компакт.
Если х° е М0 — оптимальная стратегия, то с учетом свойства диффе
ренцируемости функций minF(x,y) должно выполняться необходимое
условие |
,tN |
|
|
|
max |
mm ЭF ( x \y ) |
20, |
( 1) |
|
gehдс°)j-6/t(je°) |
Эх |
•*) |
|
|
IUIN |
|
|
где Дх°) — множество всех допустимых направлений в точке х°, т.е. на правлений, не выводящих из М0>
116
/J(x°) = Aigmin/:'(x0,y) при x = x°. yeN
Действительно, так как х° — оптимальная стратегия, то по определе нию имеем
Ц(х°)= max min Д х , у) £ ц(х) = min Д х, у) V xe М0,
откуда получаем производную по направлению g
дц(*°) _ limH(*° + o g )-p (x °) «-»0 а
вследствие того, что числитель в этом выражении всегда меньше или равен нулю для Vg е Дх°). Таким образом, становится обоснованным и
сформулированное необходимое условие оптимальности стратегий х° € Л/0; очевидно, оно эквивалентно выражению
max min |
ЭДх°,у) , Х - |
= 0 |
х е Щ У 6Л(Х°) |
Эх |
|
или выражению в виде включения |
|
|
-Г (х°) п Дх°) * 0 , |
|
где Д х ) « JZ = ^ a . kZ k\Zk е Я (х),а к * 0 |
, а* = 1 — выпуклая оболоч- |
|||
[ к= |
к= |
ЭДх,у). |
||
ка, натянутая на точки множества Я(х) = jz = |
||||
Эх |
Ц уе /?(х)>, /Д х) - |
|||
|
|
>}■ |
конус, сопряженный конусу Дх) возможных направлений множества М0 в точке х, Дх) — замыкание конуса Дх) = {V= X(z —х)|А, > 0, z е М0).
Например, при отыскании стратегии
х° = arg max minF(x,y),
где х е [0,11, У ~ 1» 2, Дх,1) = - х 2, Дх,2) = - ( х - I)2, множество
Д х) = {2}, если х е [0, 0,5), Д х) = {1,2}, если х = 0,5 и Д х) = {1}, если
хе (0,5, 1];
Дх е [0; 0,5)) — точка из множества [2, 1); Д х е (0,5; 1]) — точка из
множества (-1 ,-2 ];
L(x = 0,5) — отрезок, соединяющий точки Z\ = ЭДх,1)/Эх = - 1 и 1г —ЭДх,2)/Эх = 1.
_ Дх) — прямая, представляющая всю ось абсцисс, при этом Дх) = Дх);
/Дх) — прямая, перпендикулярная оси абсцисс в точке х. В этом примере только в точке х = 0,5 выполняется необходимое условие
- Д х = 0,5) п /Д х = 0,5) Ф0 .
117
На рис. 3 дана геометрическая интерпретация необходимого усло вия в Е* с иллюстрацией полной совокупности операций по его уста новлению, когда на М0 заданы две вогнутые критериальные функции
Fi(x) и F2(X ).
Совокупность включает следующие операции:
1. Построить исходное множество М0 — множество допустимых аль
тернатив, на котором должно быть найдено искомое оптимальное реше ние XQ.
2.Построить линии равных уровней — значений критериев F,(x) и F2(x), указать их максимальные значения maxF,(x) и maxi^x).
3.Установить области в виде вложенных один в другой выпуклых секторов, образовавшихся в результате пересечения линий равных уров ней; на рисунке они обозначены штриховыми черточками, направлен ными во внутрь секторов и непосредственно связанными с соответст вующими линиями равных уровней критериев. Такие секторы обозначены min{/’1(x), F2(x)}.
4.Выявить точки, принадлежащие одновременно какому-то выпук лому сектору и границе исходного множества М0 (границе потому, что в
рассматриваемом случае значения тах/^х) и т а х /’2(х) находятся за пре делами множества М0); на рисунке имеются две такие точки, одна из них х0 — это точка пересечения границы множества М0 и выпуклого
Рис. 3. Геометрическая интерпретация необходимого условия в Е2:
I — оптимальная по Слейтеру альтернатива в точке х®; 2 — исходное множество допустимых альтернатив; 3 — линии уровней критериев F\(x), F2(x); 4 — максимальные значения критериев /^(х), F2(x); 5 — градиенты функций /^(дс0), F2(х°); 6 — конус Дх°), аппроксимирующий множество Щ в точке д^; 7 — сопряженный конус Г*(х9) для конуса Ддс°); 8 — конус - Г ¥{х9), противоположный конусу Г+(х°); 9 — выпуклая оболочка ЦхР), относящаяся к точке х°; 10— выпуклая оболочка L(x), относящаяся к точке дг, II — неоптимальная альтернатива дг, 12 — градиент функций ^(дс), F2(x) в точке х; 13 — конус Дх), ап проксимирующий множество М0 в точке дг, 14 — конус / ’♦'(дс), сопряженный для конуса Дх); 15 — конус
- Г ¥(х), противоположный конусу Г*(х)
118
сектора с более частой штриховкой, а другая — точка х, являющаяся точкой пересечения границы М0 и выпуклого сектора с более редкой
штриховкой (внутри этого сектора располагается сектор с более частой штриховкой).
5.В точке х0 построить векторы градиенты функций F,(x) и F2(x); на
рисунке они обозначены как gradf,(x°) и gradF2(x°).
6.Построить выпуклую оболочку для этих градиентов; на рисунке она обозначена через Дх°) как отрезок прямой, соединяющий концы векторов градиентов grad/^x0) и grad/^x0).
7.Линеаризовать в точке Хф множество М0, т. е. построить в этой точке конус Дх°) как линеаризованное множество М0. Этот конус охва
тывает полупространство, указанное на рисунке черточками возле обо значения Дх°).
8.Построить в точке XQсопряженный конус Д(х°) для конуса Дх°).
9.Построить в точке х0 противоположный конусу Г+(х°) конус, на рисунке противоположный (обратный) конус обозначен как - Г +(х°).
10.Проверить пересекается ли построенный конус - / ’+(х°) с выпук лой оболочкой Дх°); если пересечение установлено, то это означает, что
вточке выполняется необходимое условие оптимальности альтернативы XQ из допустимого множества М0. Необходимое условие на рисунке при
ведено в виде выражения —Г+(х°) n Z,(x°) * 0 , видно, что в точке Хо оно выполняется, х0 — оптимальная альтернатива. Это условие тождествен но условию пересечения выпуклой оболочки Дх°) с выпуклым конусом Дх°) только в одной единственной точке, оно однозначно соответствует проиллюстрированному на рисунке условию оптимальности решения х° по Слейтеру.
Если теперь выполнить все перечисленные действия для точки х, являющейся точкой пересечения границы множества М0 и выпуклого
сектора с более редкой штриховкой, то придем к выводу, что необхо димое условие в этой точке не выполняется, а значит точка х, (как и любая другая не совпадающая с х0) не является оптимальным реше нием.
В случае нахождения значений maxF^x) и maxF2(x) внутри множест ва М0 конус Дх°) будет охватывать все пространство, т.е. в условиях рас сматриваемой задачи Дх°) = В , и тогда необходимое условие оптималь
ности представляется фактом накрытия выпуклой оболочкой начала координат, что записывается выражением вида 0 е Дх°) или {0} е Дх°). Это условие тождественно пересечению выпуклой оболочки Дх°) с ко нусом Дх°) только в одной единственной точке — точке х0 (см. также п. 3.2).
Необходимое условие в случае вогнутости функции
ц(х) = ш ш Дх.у) yeN
является и достаточным для оптимальности х° е М0.
Проиллюстрируем реализацию условия (1) на трех частных случаях
(С) [6].
119
C l. Теорема. Пусть F (x,y) и F x(x, у) непрерывны на М0х N, где М0 = [а, Ь] — отрезок, N — компакт метрического пространства. Тогда для того чтобы х °е М0была оптимальной стратегией, необходимо, чтобы выполнялось хотя бы одно из условий:
а) х° = а либо х° = Ь;
б) существуют две различные стратегии у1 у 2е N(x°), такие, что F(x° У ) = F(x° , у 2) = min F(x° ,у);
в) существует единственная стратегия у 1е Ы У ) и F j y , у1) = 0.
Д о к а з а т е л ь с т в о . Если выполнено условие а) или б), то теорема доказана. Пусть ни а) ни б) не выполнены; тогда верно условие в). Дей ствительно, если а) не выполнено, то а < х° < Ь, если б) не выполнено,
то JV(X°) = у1. При этом в точке х° имеем два допустимых направления g = 1, g = -1 и, воспользуясь выражением
max min
g e U x ° ) y e R ( x a )
получаем
= Fx'(x °У |
)ЛйО и ^ 7 = № с, У И - 1 ) ^ |
dg |
d(-g) |
Отсюда вытекает утверждение — условие в) Р 'ХУ , у 1) = 0.
Следствие. Пусть N = {у е F\cj <уу < dj,j = 1,л} и существует F ’ (х,у)
на [а, b ]x N, j = 1 ,п. Тогда для оптимальной стратегии х° должно выпол
няться хотя бы одно из условий: |
|
|
1) существует у 1€ |
ЩхР), при котором |
|
F 'x iA УК*0 - а )У |
- Ь ) = F;t У |
у )(У - c)(yj - d) = 0 у / 6 [1;л]; |
2) существуют у1 У € N(xP), у' * у 2 такие, что |
||
F ’yj У У ) ( у ) - с ;) У |
- d j ) = FI У |
, у 2)(у] - C j ) ( y j - d}) =0 V/ € [1;«J |
И
F y , у1) = F y , У) = minF(x°,y). yeN
Д о к а з а т е л ь с т в о . Так как x° — оптимальная стратегия, то вы полнено условие а), или б), или в) теоремы. Если выполнено а) или в), то существует единственная у1€ Й У ) и выполняется условие 1), а вы-
120