«ПРИНЯТИЕ РЕШЕНИЙ Метод анализа иерархий Перевод с английского Р. Г. Вачнадзе Москва Радио и связь 1993 ПРЕДИСЛОВИЕ ПЕРЕВОДЧИКА Советскому читателю предлагается перевод книги известного американского ученого Томаса ...»

Наконец, если не все изолированные блоки примитивны, то, как было отмечено, каждый имеет индекс импримитивности. Рассмотрим их наименьшее общее кратное, которое представляет собой цикличность c системы. Используя степени W, ПОП получаем в виде W называют средним ПОП, – средним ПАП.

Если имеется единственный изолированный блок, то средний ПАП является независимым от начальных приоритетов и определяется единственным образом как решение Это в точности соответствует случаю неприводимой импримитивной системы.

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

В обоих случаях задача определяется очень кратко, вместе с диаграммой, представляющей систему и ее связи. Здесь не приводятся 68 матриц парных сравнений для элементов и одна для компонент в первом примере, и 33 – для элементов и 4 – для компонент во втором примере, за исключением последних четырёх матриц.

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

Важным является вопрос о том, как взвешивать компоненты. Каждый блок в столбце, который соответствует компоненте суперматрицы, взвешивается соответствующим коэффициентом собственного вектора, полученным из матрицы парных сравнений, включающей те компоненты (с ненулевыми элементами блока в том столбце блоков), которые воздействуют на данную компоненту столбца. (На диаграммах эти компоненты имеют стрелки, направленные от них к заданной компоненте столбца.) В обоих примерах интерес представляет аппроксимация ПОП, получающаяся при возведении W в большие степени. В наш век компьютеров мои ученики (Н. Бамани, который работал над первым примером, и А. Челсон и С. Паркер, работавшие над вторым) предпочли возводить матрицу в большие степени, не используя формул для W, приведенных в разд. 8.5.

В первом примере дана невзвешенная суперматрица. Она соответствует полному графу компонент системы. Следовательно, она положительна и более того – примиW одинаковы и вектор ПАП может быть любым из тивна. Для ПОП все столбцы этих столбцов. Достаточно выдать аппроксимацию ПАП с W. Для удобства читателя вектор этого решения помещен рядом с начальными определениями факторов и компонент.

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

Отметим, что в нашей совместной работе с Дж. Бенеттом по терроризму [135] показано, что правильно построенная иерархия может дать результаты, близкие к результатам, получаемым для системы с обратной связью.

Наш первый пример касается воспитания ребенка. Ребенок в ранние годы находится под влиянием некоторых сил. Желательно установить приоритеты этих влияний. Так как при взаимодействии этих сил имеется обратная связь, задача может быть представлена сетью. Основные группы источников влияния и их существенные характеристики даны в табл. 8.1.

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

Сеть взаимодействий показана на рис. 8.5.

Пример со сталелитейной промышленностью В этом примере рассматриваются компоненты и факторы системы торговли сталью для нахождения изменений в текущих приоритетах. Факторы и компоненты показаны на рис. 8.6.

Эффективность измеряется тем, как производится продукция, и тесно связана с современной технологией.

Избыточная продукция: Япония произвела сталь в большом количестве, превышавшем потребление, и, следовательно, может дешево ее продавать.

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

Позиция правительства направлена против инфляции, которая появляется из-за повышения цены на сталь.

Торговая политика правительства выражает нежелание защищать отечественную промышленность.

Цена капитала: низкие процентные ставки в сталелитейной промышленности в зарубежных странах и высокие процентные ставки в США, косвенно вызывающие рост других цен. Невзвешенная суперматрица представлена в табл. 8.3. Для взвешивания суперматрицы (превращения ее в стохастическую по столбцам) взвешиваются компоненты в соответствии с их воздействием на каждый столбец блоков.

Таблица 8.2. Невзвешенная суперматрица для примера о воспитании ребёнка

W RWC TC RHC S SO C

R RE ED H R RE PI RP PL PE PR ME

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

столбец столбец столбец столбец Взвешивая суперматрицу и используя полученные выше веса, получаем следующую стохастическую по столбцам матрицу (см. табл. 8.4) и её 89-ю степень (см. табл. 8.5).

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

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

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

ШКАЛИРОВАНИЕ

И МНОГОКРИТЕРИАЛЬНЫЕ МЕТОДЫ

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

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

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

Существующие шкалы приводятся ниже в порядке увеличения эффективности:

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

2. Шкала порядков, которая упорядочивает объекты по рангам и инвариантна по отношению к монотонно возрастающим преобразованиям.

3. Шкала интервалов, единственная с точностью до положительного линейного* преобразования вида y = ax + b, a > 0.

4. Шкала разностей, инвариантная по отношению к преобразованию вида y = x+b.

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

Формально шкала – это тройка, состоящая из множества элементов S, бинарной операции « » на элементах S и преобразования F элементов в действительные числа. В нашем случае Бинарный оператор « » – бинарное, или попарное, сравнение элементов для выявления превосходства одного из них по отношению к заданному свойству. Например, мы пишем Si S j, указывая этим на то, что Si, сравнивается с S j, для выявлеОбычно такое преобразование называют афинным. – Прим. перев.

ния сравнительного превосходства, например, относительно веса, если элементы S – камни. Для определения преобразования F переводим парные сравнения в форму численных значений, представляющих парные сравнения, и составляем из них матрицу A, затем решаем задачу нахождения собственного значения, чтобы определить точное соответствие между объектами и действительными числами. Весь этот процесс определяет преобразование.

Почему получается шкала отношений, когда используется МАИ? Нужно показать, что парные сравнения, определенные посредством бинарной операции, отображаются в шкалу отношений действительных чисел, соответствующих сравниваемым элементам. Например, если В общем случае бывает трудно показать, какой вид шкалы используется, особенно когда преобразование сложное и включает физические операции, например такие, как подъем и опускание ртути при изменении температуры. Для задачи, связанной с физической системой, вид используемой шкалы устанавливают эмпирически. Тем не менее, когда имеют дело с абстрактной системой, нужен теоретический метод определения вида шкалы. Теперь мы знаем, что решение задачи нахождения главного собственного значения для положительных матриц единственно с точностью до положительного постоянного множителя. Поэтому преобразование дает множество действительных чисел a1, …, an, по одному для каждого элемента S1, …, S n, где a – произвольное положительное число, что точно соответствует определению шкалы отношений. Следует отметить, что шкала отношений, полученная из матрицы суждений, является нашей оценкой принятой основной шкалы отношений, которая получилась бы, если матрица суждений была бы согласованной.

Дальше следуют полезные выводы по шкалам отношений. Можно сложить пару элементов одной и той же шкалы отношений и получить третий элемент, принадлежащий той же самой шкале отношений. Следовательно, если y = ax и y = ax, то y + y = a ( x + x ) и множитель остается по-прежнему равным a. Однако ни произведение, ни частное двух таких элементов не принадлежит той же шкале отношений.

Следовательно, если принадлежит шкале отношений y = ax, так как множитель a 1 отсутствует у обоих.

Полезно отметить, что сумма двух элементов из двух различных шкал отношений не принадлежит шкале отношений. Тем не менее произведение и частное принадлежит шкале отношений, отличающейся от исходных шкал отношений, если a или b не равны единице. Чтобы убедиться в этом, напишем y = ax и y = bx, получим y + y = ax + bx и yy = ( ab ) xx, y y = ( a b ) x x. Итак, работая с двумя различными шкалами отношений и желая получить значимые числа в новой шкале отношений, следует умножать и делить, но никак не складывать или вычитать. Вот почему бессмысленно складывать такие величины, как время и расстояние, но можно извлечь смысл из деления длины на время, получая скорость.

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

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

В своей диссертации Л. Варгас показал, что МАИ является методом измерения.

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

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

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

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

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

Процедура, разработанная в [77] и применённая для решения проблемы аэропорта города Мехико, основана, по существу, на использовании многомерной функции полезности.

Желательно оценить множество альтернатив с целью выбора наилучшей в зависимости от их воздействия на n аспектов. Воздействия описываются вектором чисел ( x1, x2, …, xn ). В момент принятия решения не может быть уверенности в последствиях. Поэтому вводится функция плотности вероятности p ( x1, …, xn ), описывающая правдоподобность каждого итога. Используя эту функцию плотности, можно «опреu ( x ). Затем можно вычислить ожидаемую полезность делить» функцию полезности каждой альтернативы. Выбирается альтернатива с наибольшей ожидаемой полезностью.

Определять полезность с одновременным учетом более чем двух аспектов чрезвычайно трудно, в результате делаются упрощающие допущения для получения такой функции f, что ui ( xi ) – функция полезности относительно аспекта i.

где

9.4. КРАТКОЕ СРАВНЕНИЕ МЕТОДА СОБСТВЕННОГО

ЗНАЧЕНИЯ С ДРУГИМИ МЕТОДАМИ, ИСПОЛЬЗУЮЩИМИ

ШКАЛЫ ОТНОШЕНИЙ

В своей краткой статье Шепард [146] указывает, что исследования по матрицам превосходства и соответствующим измерениям не были такими обширными, какими были исследования по трем другим типам: близости, сечению и совместимости. Мы, по существу, интересовались матрицами превосходства и их использованием для получения шкал отношения и далее для измерения иерархических воздействий.

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

В модели сравнительных суждений Терстона [162] требуются парные сравнения объектов только в том смысле, что один более предпочтителен, чем другой. Он собирает информацию о стимулах в предположении нормальности процесса суждений.

При дополнительных требованиях к параметрам, например при равных дисперсиях или нулевых ковариациях, он собирает различную «метрическую» информацию о стимулах.

Если k экспертов сравнивают n объектов и если f ij – эмпирическая частота, соi над объектом j, то доля ответствующая числу предпочтений экспертами объекта pij, с которой i предпочтительнее j, Терстон в [162] постулировал, что распределение всех различающихся процессов, которые определяются стимулом i, нормально относительно модального разлиsi0, ассоциируечающего процесса (или среднего). Средний различающий процесс i, называется значением в шкале стимула, а дисперсия различаюмый со стимулом щего процесса обозначается через i. В предположении о нормальности pij может быть выражено как стандартное нормальное отклонение pij = 0,5, когда zij = 0, и это имеет место в случае si0 = s 0. Если zij > 0, то считается, что различающий процесс j выше, чем i. Имеем Распределение разностей si s j нормально со стандартным отклонением Имеем закон сравнительных суждений Каждая пара будет обладать таким разложением. Для четырёх объектов имеется шесть таких уравнений с 14 неизвестными: 4 искомых значения шкалы, 4 стандартных отклонения и 6 взаимных корреляций. Известны только zij. Поэтому невозможно получить единственное решение системы. В качестве первого приближения можно предположить, что все стандартные отклонения равны а все взаимные корреляции равны r. В результате получим Величина в скобках – постоянная и может служить как общая единица разделения шкал различных пар стимулов: ее можно установить равной единице.

Если обозначить то, полагая С подходом Терстона связывают ряд ограничений. Например, Гилфорд [59] рекомендует ограничить диапазон вероятностей.

Торгерсон [163] систематизировал и распространил метод Терстона на шкалирование, в частности на случай, когда ковариационные члены постоянны, корреляции равны, а распределения гомоскедастичны.

Льюс предложил то, что Кумбс [26] называет моделью Брэдли-Тэрри-Льюса (БТЛ), используя логистическую кривую, которая является логарифмическим преобразованием распределения вероятностей. Хотя это отличается от предположения нормальности, практически трудно провести различие между моделью БТЛ и случаем из работы Терстона, где он предполагает нормальность распределений и равенство дисперсий. Модель БТЛ более строго основана на теории выбора поведения.

Кумбс рассматривает существенное различие между двумя моделями.

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

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

Использование метрической информации в матрице суждений субъектов создает аналогии с анализом главных компонент, за исключением того, что данные дают информацию о превосходстве, а не о подобии или ковариациях. (Дальнейшие рассуждения см. в конце этого раздела.) При анализе главных компонент выделяется max, однако решение получают также и для всех остальных. Тем не менее результаты должны быть интерпретированы по-другому (см. [67]).

В проводимом анализе природа стимулов и задача, которая ставится перед субъектами, также подобны «психофизическому» шкалированию, как оно мыслится Стивенсом и Галантером [156]. В последнее время оно широко используется во многих попытках построить составные меры политических переменных, включая «силу страны». Техника Стивенса навязывает согласованность тем, что экспертов просят сравнить одновременно каждый стимул со всеми другими, формируя только одну строку матрицы. Это означает, что гипотеза одномерности не может быть проверена непосредственно. Если используется метод Стивенса, то следует обратить внимание на то, чтобы суждения о стимулах были согласованными или близкими к согласованным. Вдобавок не существует способа отнести одну шкалу к другой, как это имеет место в иерархии.

Крантц [86] аксиоматизировал альтернативные процессы, связывающие стимулы с суждениями, и получил теоремы существования для шкал отношений. Подобная аксиоматизация не была распространена на иерархии шкал отношений.

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

Формально задача построения шкалы в виде нормализованного собственного вектора в уравнении A = (для максимального ) подобна выделению первой главной компоненты. Когда экспертов просят заполнить клетки только одной строки или одного столбца, а другие клетки вычисляются по ним (для обеспечения «совершенной согласованности»), первое собственное значение n воспроизводит, 100% изменения матрицы. Если «совершенная согласованность» накладывается на данные за исключением того, что к каждой клетке матрицы добавляется нормально распределенная случайная компонента, то теория приводит к анализу главных факторов, и получится «однофакторное» решение. Следовательно, если совершенная согласованность навязывается экспериментатором, то получается неинтересный результат точного шкалирования, которое было гарантировано, когда эксперимент представлялся в виде одного сравнения. В действительности можно убедиться, что если субъект заполняет только одну строку или столбец матрицы и если задачей субъекта является генерация отношений между парами стимулов, то процедура формально эквивалентна тому, как если бы субъекты располагали каждый стимул вдоль полупрямой с нулём на одном конце: это и есть метод «непосредственной интенсивности» психофизического шкалирования.

Не существует простого взаимоотношения между решением, полученным с помощью собственного значения, и решениями, полученными методом наименьших квадратов, хотя имеются статьи (например, [31, 72, 80]), в которых рассматривается аппроксимация матрицы данных матрицей более низкого ранга, минимизирующей сумму квадратов разностей. В общем случае оба решения одинаковы при наличии согласованности. Общепринятого критерия сравнения не существует. Следовательно, неясно, какой из методов лучше. Повторные применения процедуры нахождения собственного значения помогают достичь согласованности, которая является наиболее предпочтительным для нас критерием.

В [164] предлагается метод «определения параметров функционального отношения посредством факторного анализа». Однако утверждается, что «задача вращения осей остается нерешённой...», т. е. факторный анализ определяет параметры только в пределах линейного преобразования. В [24] обсуждаются методы определения таких преобразований, где априорный теоретический анализ или наблюдаемые величины позволяют сформулировать критерий, по отношению к которому происходит вращение решения относительно произвольного фактора.

Иерархическая композиция является индуктивным обобщением следующей идеи.

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

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

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

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

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

В [4] также акцентируется внимание на том, что принятая шкала реакции должна удовлетворять критерию, который налагает алгебраическая модель суждений.

Таким критерием в нашем случае вновь оказывается согласованность.

Наконец, может быть полезным краткое рассмотрение графо-теоретического подхода к согласованности. Направленный граф с n вершинами, который предполагается полным (так как любая пара его вершин соединяется направленной дугой), называется турниром. Его можно использовать для представления доминантных парных сравнений между n объектами, тогда контуры будут представлять нетранзитивность. Например, каждые три вершины определяют треугольник, но не все треугольники образуют 3-контуры. Число контуров заданной длины используется для определения индекса нетранзитивности данного порядка, например тройки или четвёрки. Несогласованность определяется (см. [100]) в зависимости от отношения числа трех, четырех или более контуров в заданном графе к максимальному числу контуров данного порядка. Для 3-контуров максимальное число будет для нечетного (n n ) ( n 3) 48 для нечетного n и ( n3 4n ) ( n 3) 48 для четного n. Эти резульk -контуры. Тем не менее среднее число k -контуров для таты не были обобщены на случайной ориентации дуг полного графа – ( k 1) !( k ) (1 2 ). До сих пор не найдена зависимость между этим определением несогласованности и нашим, относящимся к собственному значению. Непохоже, что зависимость будет найдена. Приведённый выше результат для 3-контуров вместе с его статистическими следствиями принадлежит Кендаллу. Он подробно обсуждается в обычной статистической справочной литературе (см., например, [108]).

Выше мы ссылались на анализ главных компонент. Обсудим кратко эту процедуру.

Рассмотрим случайный вектор X с p компонентами, вектор с нулевым средним чает операцию математического ожидания.

Нормализованные линейные комбинации bT b = 1 получаются из функции Лагранжа, определенной в виде условии где – множитель Лагранжа.

Приравнивая производную по получим b X. Поэтому в качестве максимальной дисперсии нам следует использовать max.

Если нормализовать соответствующее решение b1, разделив его на сумму квадратов ций с максимальной дисперсией. Затем получаем новую нормализованную комбинаbT X с максимальной дисперсией всех линейных комбинаций, некоррелированцию ных с b X, т. е.

bT b1 = 0 в качестве нового ограничения, образуем новую функцию Лагранжа.

скольку как ковариационная матрица симметрична, все её собственные значения деиствительны). Действуя как и прежде, теперь получим соответствующий собстbT X имеет максимальные дисперсии из всех норвенный вектор при условии, что мализованных линейных комбинаций, не коррелированных с b1 X и b2 X и т. д.

Когда собственные векторы получены таким образом, отношение каждого собственного значения ко всей сумме собственных значений представляет долю всей дисперсии, отраженную в соответствующих компонентах. Поэтому первым (и практически важным) приближением считают главную компоненту и ищут изменения в условиях, ведущих к изменениям в выражении В [115] сделана попытка определить влияние отдельных журналов, проверяя число цитирований. Устанавливается матрица цитирования числа статей из каждого журнала, упомянутого в каждом источнике. Столбцы затем нормализуются, чтобы принять во внимание различные размеры журналов. Далее следует вычисление весов влияние в соответствии с разработанной ими процедурой нахождения собственного вектора общей матрицы (которая не ориентирована на шкалу отношений).

9.5. ПОДХОД, ОСНОВАННЫЙ НА ВОЗМУЩЕНИЯХ:

МЕТОД ЛОГАРИФМИЧЕСКИХ НАИМЕНЬШИХ КВАДРАТОВ

В случае несогласованности задачу можно поставить следующим образом:

определить такие 1, 2, …, n, чтобы где для параметров возмущения имеем Здесь аргумент в fij. Отметим, например, что мультипликативный параметр следует устремить к единице, а аддитивный параметр – к нулю. Другими словами, если есть надежда восстановить хорошие оценки i j из aij, то возмущения должны быть малы. Отметим, например, что Можно зависать (9.1) в виде Это основная, недоопределённая система j и gij, требуется n дополнительных уравнений относительно gij, чтобы система стала разрешимой. Выбор этих отношений может быть свободным. Тем не менее оказывается, что эти n отношений могут быть получены, если основываться на выходе, связанном с возмущением рассмотренного выше идеального случая. Исходя из соображений о генераторе бесконечно малых величин требуем, чтобы следующая система соотношений всегда выполнялась:

и множество этих условий зависит от Задача 1: Найти Системы соотношений (9.2), а также (9.3), часто используются в качестве необходимых условий, возникающих при решении задачи оптимизации. Например, (9.2) можно записать в виде равенства и суммируя по i и j, получим задачу минимизации ошибки относительно Задача 2 заключается в нахождении Это – задача логарифмических наименьших квадратов. Однако она имеет точно такое же решение которое получается при рассмотрении произведения по жет быть интерпретировано как решение, порождающее ближайшую согласованную матрицу к заданной матрице в смысле логарифмических наименьших квадратов.

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

Полезно взять уравнения возмущений (9.2) и создать таблицу условий, налагаемых на различные методы вместе с соответствующими решениями. Назовём левый собственный вектор, который является решением задачи, сформулированной в терминах гармонического среднего, вектором антиприоритетов. Он представляет меру того, насколько элемент доминируется другими элементами того же уровня. Соответствующий вектор, полученный посредством иерархической композиции, измеряет воздействие иерархии на каждый элемент уровня (см. табл. 9.1).

Замечание. Решения задачи логарифмических наименьших квадратов, связанной с двумя матрицами оптического примера из гл. 2, будут (0,61; 0,24; 0,10; 0,05) и (0,61; 0,23; 0,10; 0,06).

Если связать арифметические, геометрические и гармонические средние в нашей задаче шкалирования, то табл. 9.1 легко объясняется.

рическое по таблицам 9.6. МЕТОД НАИМЕНЬШИХ КВАДРАТОВ

ДЛЯ АППРОКСИМАЦИИ МАТРИЦЫ МАТРИЦЕЙ МЕНЬШЕГО РАНГА

W = (i j ) ранга один получается после решения задачи о собственМатрица ном значении. Она является приближением к матрице факт, что любая матрица может быть аппроксимирована другой матрицей меньшего ранга. Это делается следующим образом. Во-первых, отметим, что Теперь для любой матрицы значения действительны. Кроме того, X и X положительны. Поэтому XX положительна и имеет единственное действительное положительное наибольшее собственное значение.

Согласно Джонсону [72] – диагональная матрица, элементами которой являются собственные знагде чения A в порядке убывания величины; собственные векторы матрицы AA являются соответствующими столбцами матрицы P, а собственные векторы матрицы AT A – соответствующими строками матрицы QT. Наконец, отметим, что наилучшее приближение методом наименьших квадратов матрицы A матрицей ранга r может быть задано выражением Pr и QrT – части P и QT, соответственно связанные с первыми r столбцами.

где Пусть r = 1, тогда P – собственный вектор матрицы AA, ассоциируемый с макT циируемый с максимальным собственным значением. Если, как в согласованном случае, где то наше решение в согласованном случае будет наилучшим приближением методом наименьших квадратов. Это может быть не так в несогласованном случае.

Проиллюстрируем идею наилучшего приближения методом наименьших квадраT T тов на одной из матриц A примера из оптики, сформировав AA, A A и получим их собственные значения и собственные векторы. Собственные значения, одинакорасполовые для обеих матриц, являются диагональными элементами матрицы ответствующими столбцами матрицы P, а матрицы A A – со строками матрицы Q.

Имеем Используя подход, при котором находится максимальное собственное значение, получаем вектор в качестве оценки основной шкалы отношений. Основываясь на га (в нашем случае единичного), которая является наилучшим приближением в смысле наименьших квадратов к заданной матрице суждения. Естественно, что эта ровать квадраты их элементов, то можно легко показать, что первая сумма равна tr ( FF ) = tr s, где s – диагональная матрица собственных значений, не включенr (в нашем случае r – наибольшее собственное значение матрицы AT A и ных в tr ( A W ) ( A W ) tr ( FF ), как и должно быть на самом деле. Однако задача заT ключается в получении вектора шкалы из аппроксимированной методом наименьPr 1/ 2QrT. Если предположить, что эта матрица почти соглаших квадратов матрицы r сованна, то можно использовать любой из ее столбцов (нормализованных) как приближение к основной шкале. Но теперь возникает вопрос, насколько хорош этот вектор по сравнению с максимальным собственным вектором. В нашем примере использовалось среднеквадратичное отклонение от известных основных шкал в задачах, где желательно было провести сравнение. Как будет показано в приведенном ниже примере, максимальный собственный вектор явно превосходит вектор, полученный методом наименьших квадратов (как мы его интерпретировали), если его рассматривать как приближение к реальности.

Если образовать r, полагая, что все диагональные элементы, кроме первого, наибольшего из них, равны нулю в Если сформировать Fr = A Pr r Qr и просуммировать квадраты ее элементов, получается 1,6, но сумма остальных собственных значений tr s также равна 1,6.

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

Хотя этот вектор не является таким хорошим приближением, как собственный вектор, находим, что его среднеквадратичное отклонение от фактического вектора ( 0, 61; 0, 22; 0,11; 0, 06 ) равно 0,00155, по сравнению с 0,00005 для максимального показывает, что для данного примера решение, полученное с помощью собственного вектора, лучше решения методом наименьших квадратов.

Теперь используем элементы и s для формирования матрицы отношений W = (i j ) и S = ( si s j ). Затем вычислим A W и, просуммировав квадраты ее элементов, получим 13,42. Проделав то же самое для A S, получим 11,45, что близко к первому результату, однако несколько лучше. Это означает, что аппроксимация методом наименьших квадратов лучше для минимизации суммы квадратов разностей. Для этого примера можно сделать вывод: так как нас интересует шкала, а не матрица отношений, ответ, полученный с помощью собственного вектора – лучше; и это несмотря на то, что он не удовлетворяет критерию минимума квадратов.

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

В [152] рассмотрены ранние обзоры по следующим методам оценки весов, приведенным в [151, 13];

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

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

3. Взвешивание частных критериев с целью максимизации разности стимулов в величине общего критерия.

4. Взвешивание частных критериев с целью максимизации объясненной дисперсии (с помощью факторного анализа).

5. Взвешивание частных критериев пропорционально их надежности.

6. Равновесное взвешивание частных критериев.

7. Взвешивание частных критериев с целью уравновешивания «эффективных весов» (т. е. долей дисперсии общего критерия).

8. Взвешивание на основе денежного критерия.

9. Взвешивание частных критериев по суждениям экспертов.

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

Эти методы исследуются или критикуются с точки зрения трех основных критериев: релевантности, многомерности и измеримости. Методы 1–7 имеют недостаточную релевантность. Она игнорируется, используются произвольные статистические цели, или релевантность учитывается непрямым и несовершенным образом через другие частные критерии, а не через глобальный критерий. Методы 5–9 содержат смешенную оценку, так как выносится суждение относительно одного частного критерия, а затем независимо относительно другого. Поэтому результирующий многомерный вектор имеет смешение между компонентами, выражающееся подчас в двойном подсчете важности частного критерия. Методы 8–10 страдают сложностью получения мер, которые имеют смысл при взвешивании относительно глобального критерия. Ниже представлены примеры методов взвешивания.

Сопоставление исходов с целями. Допустим, имеются исходы O1, O2, …, Om.

Этапы процедуры следующие [1, 54]:

1 Ранжировать цели по порядку значений.

2. Присвоить значение 1,00 первой цели и присвоить приемлемые значения другим целям:

значение 3. Сравнить наиболее важную цель с совокупностью остальных целей. Короче, сравнить O1 с O2 + … + Om. Если 1 2 + … + m, то сравнить O2 с O3 + … + Om. Если 1 < 2 + … + m 1все еще выполняется, то сравнить O1 с O2 + … + Om 2 и т. д., до тех пор, пока O1 не станет предпочтительнее остальных или пока не завершится сравнение O1 с O2 + O3, тогда следует возвратиться к этапу 3.

Предположения, лежащие в основе этой процедуры, следующие:

С каждым исходом мы сопоставляем действительную неотрицательную величину.

Если Oi предпочтительнее O j, то i > j.

но исключающие друг друга исходы.

Когда имеется большое число исходов, эта процедура очень трудоемка. К тому же она не формирует единственную шкалу и с ее помощью нельзя справиться с задачами иерархического типа. В [82] использован метод непосредственного сравнения n объектов. Во-первых, объекты располагаются в ряд по порядку от наиболее предпочтительного к наименее предпочтительному. Сравниваются наиболее предпочтительный объект со вторым по предпочтительности, второй с третьим и т. д., при этом каждый раз этому отношению приписываются численные значения. По завершении процесса число 1 приписывается наименее предпочтительному из n объn 1) -го объекта 1 умножается на отношение, полуектов и для получения веса ченное в результате сравнения ( n 1) -го с n -м объектом, и т. д., продвигаясь в обратном направлении и получая относительную шкалу оценок для n объектов. В этом методе отсутствует способ оценки согласованности.

Сопоставление исходов с функциями целей. В [40, 43] предлагается подход, основанный на использовании теории аддитивной полезности, что означает выполнение условия: полезность целого равна сумме полезностей, приписываемых его частям. Если все цели O j соответствующим образом определены и для каждого плана измерен его вклад в реализацию каждой цели, то результаты могут быть записаны в следующем матричном виде:

планы для определения того, который следует использовать. Согласно теории поui (которую обозначим V ( ui ) ) получается как функлезности общая мера вклада n -мерного вектора ( xi1, xi 2, …, xin ), т. е. V ( ui ) = V ( xi1, xi 2, …, xin ). Используя усция ловие аддитивности можно получить, что значение цели для каждого плана определяется как произве- значенной через линейных функций полезности, которые нормализованы так, что получают значение от 0 до 1. Для целей, меры которых прямо пропорциональны уровням полезности (например, вклад в национальный доход), можно считать а для тех целей, которые обратно пропорциональны уровням полезности (например, вклад в загрязнение окружающей среды) наибольшему так, что где номера целей соответствуют рангам. Иногда эксперта просят перенумеровать цели в порядке убывания предпочтительности. Существуют и другие методы упорядочивания – разновидности этого метода.

2. Метод непосредственного оценивания. Целям могут быть приписано бесконечное или конечное число дискретных значений, например числа от 0 до 10. Для кажO j ) дого эксперта просят оценить важность данной цели. Эксперту может быть дозволено выбирать точки с учетом десятых долей, например 2,7, и он может приписать одно и то же значение из шкалы более чем одной цели.

3. Метод сопоставления исходов с целями (описан выше).

ключается в образовании цепочки половинных значений следующим образом. Начk, близкого к n, и оценим такое j, что ( O j ) + ( O j + 2 ) = ( Ok ) и положим нем с формирование цепочки половинных значений до тех пор, пока это будет возможно.

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

Допустим ( O3 ) = 1, можно получить графическую оценку функции полезности.

полагая гда ранжирование по упорядоченной метрике в бинарном случае будет ранжированием смежных разностей ( O3 ) + ( O2 ). Сравнение производится непосредственно, когда одно и то же ( Oi ) 6. Метод кривых безразличия. Во многих задачах желательно определить функцию полезности или ценности распределения ресурсов на различные виды деятельности и максимизировать ее при ограничивающих условиях, которые могут быть наложены на имеющиеся величины в связи с их ценой и денежными фондами. Однако обычно такую функцию построить трудно и вместо нее определяют кривые безразличия для пар видов деятельности в обход численного подхода. Чтобы построить такую кривую, экспертам задают вопросы для определения компромиссов между двумя сравниваемыми показателями. На кривой безразличия значения обоих показателей имеют одинаковую ценность. Здесь получаются двумерные кривые, с помощью которых должна быть получена некоторая многомерная поверхность и на ней найден максимум. Недостатком метода является потеря количественной информации.

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

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

Методы математического программирования Глобальная функция цели. Здесь главная задача – свести вместе многие цели для оптимизации результата при ограничениях в рамках линейного программирования. Идея заключается в том, чтобы использовать выпуклую комбинацию этих функций цели при различных параметрах и решить в итоге задачу параметрического программирования. Мы получаем конечное семейство решений, соответствующих мозаике из ячеек пространства параметров.

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

Цели в ограничениях; целевое программирование. Все глобальные оптимумы являются в более широком контексте локальными оптимумами. Мы знаем, что решения оптимальны только в ограниченном контексте. Оптимальное решение – это не та стратегия, которой нужно следовать, это дополнительная информация, которую следует учесть в контексте большой системы, для которой данная задача является компонентой. В большинстве случаев наша цель – максимизация прибыли всего производства. Это создает впечатление, что у нас только одна цель – прибыль. Но предположим, что принята более широкая точка зрения, включающая несколько отдельных целей, которые нельзя легко объединить в одну оптимизируемую функцию.

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

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

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

Рассмотрим следующий пример:

цель 1: 60 x1 + 50 x2 = 1500 (цель – чистая прибыль);

x1 и x2 – количество единиц изделий 1 и 2 соответственно; 80 и 60 – соответственно время работы машин A и B, которое не может быть превышено. Эти три цели несовместимы. Для решения проблемы несовместимости принимаем высший приоритет цели 1, следующий по величине приоритет будет у цели 2, а затем у цели 3.

Припишем следующие точные значения приоритетам:

цель 1 следует удовлетворить как можно лучше, каковы бы ни были результаты приближения к целям 2 и 3;

как только цель 1 достигнута, следует удовлетворить цель 2 как можно лучше при условии, что это не поставит под угрозу реализацию цели 1;

как только цель 2 достигнута, следует удовлетворить цель 3 как можно лучше при условии, что это не поставит под угрозу реализацию цели 2.

Итак, задача ставится следующим образом:

минимизировать при условиях лишка соответственно.

Если P, P2 и P рассматриваются как коэффициенты переменных, то мы будем тальные переменные – в часах. Чтобы устранить эту трудность, будем считать, что P, P2 и P3 – ярлыки, определяющие порядок приоритета соответствующих целей, а не коэффициенты. Итак, вычислить d1 + d1+ возможно малым при единственном условии – неотрицательности всех пеP2 d 2+ означает: сделать d 2+ возможно малым, не угрожая реаременных. Вычислить тов P, P2 и P таково, что P намного больше P2, которое, в свою очередь, намного больше P. Связь между целевым программированием и иерархиями проходит через концепцию согласованных сценариев в планировании. В сложной ситуации планирования применение иерархического подхода позволяет получить обобщенный сценарий, который устраивает всех лиц, принимающих решение. Однако этот сценарий должен быть реалистическим и совместимым со всеми размерностями задачи. Например, реалистический означает, что мы не можем использовать ресурсов больше, чем имеем. Совместимый означает, что цели не должны быть конфликтующими. Если определить сценарий посредством вектора состояния переменных – X, а множество зических потоков в системе. Метод собственного значения и принцип иерархической композиции могут быть использованы для построения обобщенного сценария, переменные состояния которого принимают значение R. Если R не может быть получеg (Y * ), где Y * – конкретно в виде функции от переменных решения, т. е. в форме ное подмножество решений задачи, то R не согласованно, и тогда используется целевое программирование для пересмотра целей планирования, представляемых R.

В частности, предположим, что A – матрица прямых затрат заданной экономической системы. Пусть X – валовая продукция, а Y – конечный спрос. Известно, что X = ( I A ) Y. Предположим, что значение переменной состояния X * обеспечивает некоторый уровень потребления определенного ресурса, стоимость, зависящую от технологии, а также эмиссию полютантов при этой технологии. Общие коэффициенты воздействия и модель «вход–выход» D воспроизводят процесс функционироX * = DX при X = ( I A ) Y. Чтобы величины R обобщенвания системы. Имеем ного сценария были согласованны, должно соблюдаться следующее условие:

X * = R. Если оно не соблюдается, то основу для получения реалистических и совместимых R представляет следующая задача оптимизации.

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

Локальные цели: интерактивное программирование. Рассматриваемую задачу со многими критериями можно записать в виде:

f – r -мерный вектор вещественных функций, x – n -мерный вектор вещестгде венных переменных, X – допустимая область в R, связанная с x, и U – функция полезности лица, принимающего решение, определенная на области значений f.

Можно предположить, что U – возрастающая по каждому f i функция и что X – выпуклая и компактная; U по каждой компоненте f – вогнутая и непрерывно дифференцируемая.

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

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

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

1. Строится матрица несходства ij, на главной диагонали которой стоят нули.

Матрица симметрична относительно главной диагонали.

2. Из матрицы ij получается матрица расстояний между стимулами dij.

3. Требуется удовлетворение условия монотонности ( dij – расстояние между точками начальной конфигурации).

Задача заключается в минимизации монотонности.

В подходе по изучению маркетинга, предложенном в [58], исследуются пять показателей проекта, включающих наименование, цену, оформление упаковки и гарантию. В данной специфической задаче существует 108 комбинаций этих пяти показателей. Из всех альтернатив было выбрано 18 и проранжировано. С помощью ЭВМ проводился поиск значений в шкале для каждого показателя. Значения в шкале выбраны таким образом, что при их суммировании общая полезность каждой комбинации соответствует рангам. Меры того, насколько лучше каждая альтернатива, не приводится.

В [20] предлагается метод в помощь специалистам по планированию при формулировке стратегий и прогнозировании исходов при последовательном применении этих стратегий. Формируется матрица перекрестных воздействий условных вероятностей. Далее вычисляются меры несходства пар событий и определяется евклидово расстояние между строками матрицы перекрестных воздействий (причин), а затем – евклидово расстояние между столбцами (эффектами).

В [183] определяется матрица несходства (расстояния). В качестве заголовков строк и столбцов используются элементы из множества понятий, где каждое определяет отношение понятия ко всем другим. Данные собираются в последовательность прямых парных сравнений и затем трактуются как точки в пространственном многообразии (неевклидовом N -мерном пространстве). Определяется местоположение этих точек и затем минимизируются квадраты расстояния между ними.

В [165] исследуется математическая структура полиномиальной теории измерений (применимой к структуре данных в том и только в том случае, если для нее выполнена аксиома иррефлексивности), и устанавливается взаимосвязь различных моделей измерений в общих концептуальных рамках, приводящих к математическим задачам, решение которых считается полезным. У теории нет простых эмпирически проверяемых условий. Этот подход предусматривает анализ данных с помощью многомерного шкалирования и факторных методов. Упорядочение расстояний между парами задает определенный порядок между ними, который может быть выражен в виде полиномиальной функции координат. Теория описывает погружение этого полинома в действительное n -мерное пространство с фиксированной размерностью.

В [118] проведено исследование по «выбору «наилучших» линий поведения из ряда альтернативных возможностей, где каждая линия поведения оценивается в терминах степени достижения множества целей». Предложенный метод основан на технике многомерного шкалирования, развитой Кендаллом для вычерчивания карт на основе фрагментарной информации.

Экспериментальная проверка метода анализа иерархии была проведена в [142], где он сравнивается с подходами множественной регрессии (МР), многоаспектной полезности (МАП) [79] и простой непосредственной оценкой (НО). Эти четыре метода отличаются следующим: они требуют суждений различного типа, они требуют различных форм отклика (от порядкового до отношений) и, наконец, каждый из них имеет область приложений с ограниченным применением других методов.

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

Тридцати трем экспертам предложили высказать предварительные суждения о парах альтернатив. Требовалось указывать как направление, так и степень предпочтения для каждой пары. Для линейных аддитивных моделей, использовавших МАИ, МР, МАП и НО, было получено соответственно 84, 57, 86 и 84% правильных предсказаний по этим предварительным суждениям. Пирсоновские корреляции произведений моментов между предсказанными и наблюденными степенями предпочтений были 0,72; 0,19; 0,75 и 0,77 соответственно.

Этими методами авторы проверяли только то, что каждый из методов должен был предоставить по аддитивному, линейному представлению многоаспектных предпочтений. Приоритеты показателей или критериев, определенные посредством МАИ, были использованы как веса линейной функции полезности, что позволило авторам сравнить их.

Хотя методы и различны, каждый из них имеет определенное преимущество перед другими. Для МАИ не требуется допущения о согласованности в предпочтениях, в то время как построение функции полезности при использовании подхода МАП требует транзитивности отношения предпочтений. Кроме того, при парных сравнениях в МАИ информация более детализирована и применима в сферах, где существуют неизмеримые показатели.

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

В [79] обсуждается методика оценки функции полезности. Процесс МАП приводит к одному из немногих установленных типов функций. Метод анализа иерархий генерирует функциональные значения функции полезности, а не саму функцию.

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

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

Относительно метода МР отмечается, что «использование МАИ предпочтительнее, чем метода МР в любой неповторяющейся ситуации по принятию решений, такой, как стратегическое планирование или технологический прогноз, поскольку эти ситуации не позволяют легко вывести измеримые свойства». Однако в МАИ возникает одна операционная проблема – для получения суждений он требует больше времени, чем необходимо для одного заседания, и должен быть растянут на несколько заседаний. Это неудобство не кажется очень важным по сравнению с тем, что при МАП выводится функция полезности, процесс, при котором люди могут чувствовать себя не очень удобно. Их предпочтения могут оказаться несогласованными с функцией полезности*.

Разбор некоторых работ последних лет, в которых МАИ сравнивается с другими методами, приведен в дополнении. – Прим. перев.

Хирш [66] провёл тщательный анализ аксиоматических методов, используемых для изучения как порядкового, так и количественного ранжирования. Синтезировав информацию, содержащуюся в аксиомах, он смог сформулировать минимальный набор аксиом, из которых далее вывел около сорока аналитических условий для суждений о пригодности многокритериальных методов. Вероятно, чем большему количеству условий удовлетворяет метод, тем более он предпочтителен.

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

Для сравнения и оценки многокритериальных методов Хирш дает их основные структурные характеристики. Каждая характеристика должна быть определена по шкале характеристик, так что любой многокритериальный метод идентифицируется множеством его характеристических уровней, измеренных по каждой шкале характеристик. Сначала определяются шкалы измерений: количественно абсолютную, количественно относительную, количественно интервальную, упорядоченной метрики, порядковую и номинальную. Над шкалами измерений определяются пять характеристических шкал, а именно: I, O, G, D и W. I -характеристическая шкала отражает степень определенности, необходимую в шкалах измерений для нескольких критериев (степень количественности); O -характеристическая шкала – качество полученного ранжирования; W -характеристическая шкала – некоторую информацию об относительной важности критериев. Мерами относительной важности критериев являются одномерные показатели. Они могут быть порядковыми или количественными. Однако порядковые меры относительной важности недостаточны, так как не могут быть использованы для получения глобального ранжирования. Поэтому Хирш вводит еще две шкалы, основанные на сравнениях межшкальных расстояний:

G и D -характеристические шкалы. Основываясь на этих шкалах, определяются некоторые объективные меры оценки многокритериальных методов: рациональные условия.

Среди исследованных Хиршем методов – целевое программирование, многоцелевое линейное программирование и некоторые другие, появившиеся в последнее время. Он рассмотрел «преаналитические» условия: нейтральности/независимости, упорядоченности, устойчивости, откликаемости, парето-оптимальности, степени структуры, анонимности и гомогенности.

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

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

система может быть расчленена на классы (компоненты) сравнимости в рамках направленной сети;

элементы в каждой компоненте могут сравниваться относительно некоторых или всех элементов смежной компоненты (начальной вершины дуги);

можно проводить сравнения в абсолютной численной шкале для формирования отношений;

при парных сравнениях применяются обратносимметричные матрицы (необязательно);

допускается нетранзитивность и исследуется ее воздействие на согласованность результатов;

приоритет или обобщенный показатель элемента получается с помощью композиции или взвешивания;

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

Аксиоматические основы МАИ из работы Т. Саати (Axiomatic Foundation of the Analytic Hierarchy Process, Management Science v 32, № 7, 1986, приведены в дополнении. – Прим. перев.

МАТРИЦЫ И СОБСТВЕННЫЕ ЗНАЧЕНИЯ

В этом приложении приводится краткое введение в алгебру матриц и задачи о собственном значении.

Матрица A – это прямоугольная таблица, включающая массив из m n чисел, расположенных в m строк и n столбцов. Число или элемент матрицы A в i -й строj -м столбце обозначается через aij. Таким образом, имеем ( m n ) -матрицу A :

A обозначают через ( aij ) и определяют число ее строк и столбОбычно матрицу цов. Индексы i и j относятся к той строке и столбцу соответственно, в которых расположен элемент. Матрица называется квадратной порядка n, если m = n.

Строки и столбцы матрицы A называют векторами. Матрица A может состоять из единственного вектора-строки или вектора-столбца. В этом случае достаточно строка. Диагональные элементы квадратной матрицы i = 1, …, n. Диагональная матрица A обладает свойством iij = 0 для всех i и j при i j. Некоторые из диагональных элементов – ненулевые. Если также все aii = для всех i, то A называют нулевой матрицей и обозначают O. Единичная матрица I – это диагональная матрица с aii = 1 для всех i. Треугольная матрица A – это квадратная матрица с aij = 0 для i > j, или aij = 0 для i < j. Транспонированная A в положении i, j элементом в положении j, i, т. е. для получения AT нужмента но поменять местами строки и столбцы A, поворачивая.матрицу относительно главной диагонали. Так как две матрицы равны, если равны их соответствующие эле- a ji = aij (элемент aij является комплексно-сопряженным с элементом aij ). Опре- A = ( aij ) положительна, если aij > 0 для всех i и j, и неотрицательна, если рица aij 0. Кроме того, A B, если aij bij для всех i и j.

Существуют правила сложения, вычитания, умножения и «деления» матриц A и B. Эти операции составляют алгебру матриц, в некотором роде подобную алгебре обычных чисел, однако следует быть осторожным, так как не все правила, пригодные для обычных чисел, применимы к матрицам, составляющим более общую алгебру. В то же время матрица порядка 1 1 – это просто число, которое называется скаляром, и все правила, применимые для матриц вообще, могут применяться к этому специальному виду матриц, т. е. к обычным числам.

Исторически матрицы появились как стенографический метод записи коэффициентов системы уравнений. В общем случае система из m уравнений с n неизвестными обычно бывает задана в виде x j. Тогда xi, который повторяется в каждой строке, можно залить от переменных писать только один раз таким образом:

x j в виде столбца, то правило для восстановления исходной сисЕсли записать темы таково: каждый a32 x2. Таким образом, двигаясь вдоль строк коэффициентов и одновременно вниз по столбцу x, можно получить соответствующее соединение. Эта простая операция – основа для общего правила умножения матриц.

Можно обозначить x1, x2, …, xn как вектор x, а y1, y2, …, yn – как вектор y. Отметим, что в общем случае число элементов x не равно числу элементов y. Произведение ( m n ) -матрицы на ( p q ) -матрицу возможно только в случае p = n, в результате получается матрица размерности m q. Поэтому, если q = 1, т. е. вторая матрица суть вектор, то произведение также будет вектором. Чтобы избежать путаницы, следует помнить, что буквы с индексами обозначают элементы матриц или векторов, а буквами без индексов обозначены вся матрица или вектор. Сложение и умножение матриц можно соотнести с операциями над системами уравнений.

Рассмотрим вновь систему уравнений:

и предположим, что есть другая система уравнений:

Поскольку элементы x являются общими для обеих систем, для объединения этих двух систем следует сложить первое уравнение первой системы с первым уравнением второй системы, сгруппировать подобные члены, перейти ко вторым уравнениям, проделав то же самое и т. д.:

Это дает тот же результат, что и применение для матриц коэффициентов правила сложения. Допустим, A – матрица коэффициентов первой системы, а B – матрица коэффициентов второй системы. Тогда для их сложения описанным выше образом A и B должны быть одного и того же порядка. Правило такое:

соответствующие элементы в матрицах суммируются.

Имеем Конкретнее Правило сложения может быть распространено на любое число матриц одного и того же порядка:

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

скаляр следует каждый ее элемент умножить на.

Сочетанием умножения на скаляр и сложения можно выразить правило для линейной комбинации матриц Рассмотрим следующий набор уравнений, выражающих Рассмотрим также второй набор уравнений, выражающих Выразим zk через xi, i = 1, 2, 3, 4. Это реализуется подстановкой y j, j = 1, 2, 3 из первой системы во вторую. Получаем Здесь коэффициент при Это произведения коэффициентов при y1, y2 и y3 соответственно в выражении для z1 на соответствующий коэффициент при x1 из трёх уравнений для y1, y2 и y3.

Аналогично получаются коэффициенты при x2, x3 и x4. Для z2 получаем:

Всё это можно проделать, умножая матрицу коэффициентов первой системы на матрицу коэффициентов второй системы.

Для этих матриц запишем Умножение производится для получения коэффициентов в скобках, связывающих x1, x2, x3 и x4 с z1 и z2. Так, элемент в позиции 1,1 результирующей матрицы получается умножением элементов первой строки исходной матрицы, расположенной слева, на соответствующие элементы первого столбца исходной матрицы, расположенной справа, и суммированием, т. е.

Элемент 2 в позиции 2,3 получается в результате умножения элементов второй строки исходной матрицы, расположенной слева, на элементы третьего столбца исходной матрицы, расположенной справа. Имеем В общем случае, при умножении матриц C = cij, т. е. AB = C, имеем для элемента в позиции i, j матрицы C A и j -й столбец B умножаются на коэффициенты в соответствуют. е. 1-я строка щих позициях, указанных индексом k, и затем суммируются. Ясно, что умножение имеет смысл только в том случае, если A – матрица размерности m n, а B – матрица размерности n q.

Для приведенных ниже A и B матрица C будет следующей:

где Произведения матриц удовлетворяют:

закону ассоциативности В общем случае произведение матриц некоммутативно. Например, если Это означает, что AB = 0 при A 0, B 0. Также из AB = AC имеем A ( B C ) = 0. Но отсюда нельзя заключить, что либо A = 0, либо B = C.

Тем не менее сложение матриц удовлетворяет всем свойствам сложения чисел.

Например, из A + B = A + C следует, что B = C.

Умножение любой матрицы на скалярную матрицу (диагональную матрицу, все диагональные элементы которой равны) есть не что иное, как умножение матрицы на константу. Так, например, Отметим, что AI = IA = A. Обратная матрица A, если она существует, представляет собой матрицу, которая обозначается A А "' и удовлетворяет соотношению AA1 = I. Имеем ( AB ) = B 1 A1 и ( AB ) = BT AT. Две матрицы A и B называются ортогональными, если Примечание. Заметим, что в произведении матриц AB = C cij формируется при участии i -го вектора-строки A и j -го вектора-столбца B. В общем случае произv = ( v1, …, vn ) и w = ( w1, …, wn ) называется скалярным или ведение двух векторов v = ( v12 + … + vn ), что является евклидовой длиной. Из аналитической геометрии известно, что угол Поэтому ( v, w ) = v w cos Заметим, что два вектора (1, 3, 2 ) и ( 4, 0, 2 ) – ортогональны.

A порядка n ассоциируется число, которое называется ее опредеС матрицей лителем (детерминантом) и обозначается A или det ( A ). Определитель – это алгебраическая сумма всех возможных произведений n элементов, в каждом из которых имеется один элемент из каждой строки и каждого столбца A. Можно расположить элементы каждого члена этой суммы в порядке, соответствующем порядку столбцов A. Получим n вариантов для элементов первого столбца, затем n 1 вариантов для элементов из второго столбца, два варианта для элементов предпоследнего столбца и один для элементов последнего столбца. Это дает N = n ( n 1)… 2 вариантов. (Произведение первых n положительных целых чисел называется n -факториал и обозначается n !.) Каждому варианту соответствует отдельное слагаемое. Следовательно, определитель порядка n состоит из n ! слагаемых.

В алгебраической сумме каждому слагаемому придается положительный или отрицательный знак в соответствии со следующим правилом. Расположим элементы каждого слагаемого в соответствии с порядком столбцов матрицы и рассмотрим последовательность индексов соответствующих строк. Эту последовательность можно построить перестановками пар элементов в последовательности натуральных чисел 1, 2, …, n. Если число перестановок четное (нечетное), знак слагаемого будет полоs становок. Например, слагаемое 3 3 приводит к последовательности строчных индексов 2, 3, 1. Чтобы привести эту последовательность к форме 1, 2, 3, следует провести две перестановки: переставить 1 и 2, а затем переставлять 2 и 3. Две перестановки приводят к положительному знаку слагаемого. Слагаемому a11a32 a23 со строчными индексами 1, 3, 2 требуется одна перестановка элементов 3 и 2 для приведения к форме 1, 2, 3. Следовательно, слагаемое получает отрицательный знак. Применяя это правило, легко увидеть, чему равен определитель матрицы Из многих известных свойств определителей отметим следующие:

A ; перестановка двух строк или двух столбцов в матрице A изменяет изменяет A ; определитель равен нулю, если два столбца или две строки матрицы A знак идентичны или же один из них получается умножением другого на постоянную; если столбец двух определителей; первый столбец первого определителя будет второго – b11, b21, …, bn1, остальные столбцы остаются неизменными как у A. Отсюда следует, что определитель не меняется, если добавить к любому столбцу другой столбец, умноженный на постоянную; если A – треугольная матрица, то A = a11, a22, …, ann.

Ранг матрицы A есть порядок наибольшего квадратного массива (подматрицы), детерминант которого не равен нулю. Квадратная матрица – невырожденная, если ной. Например, матрица, каждая строка которой может быть получена умножением одной строки на некоторую постоянную, не только вырожденная, но и имеет единичный ранг.

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

Сомножитель Для разложения Аналогично проводится разложение по столбцу.

adj ( A ) называют присоединенной к матрице A, если ее i, j -м элеменМатрицу том является Следовательно, матрица A обратима (т. е. имеет обратную матрицу) тогда и только тогда, когда A 0 (т. е. матрица A – невырожденная), и в этом случае Рассмотрим линейную систему уравнений В матричной записи эта система имеет вид где A – матрица коэффициентов:

x и b – векторы-столбцы:

Когда b 0, т. е. некоторые из элементов bi ненулевые, система называется неоднородной; в противном случае систему называют однородной.

Если матрица записать единственное решение неоднородной системы x = A b. Правило Крамера обеспечивает удобный способ решения неоднородной системы, эквивалентный вышеприведенному способу, но оно включает использование определителей, а не обращение матриц. Компонента xi вектора x – это дробь, числитель которой – определитель матрицы, полученной из A заменой i -го столбца A вектор-столбцом b, а знаменатель – определитель A. Отметим, что при решении однородной системы числитель xi всегда равен нулю и, следовательно, не существует иного решения, лю, то нужен удобный способ получения ненулевого решения, так как правило Крамера приводит к неопределенному выражению (нуль, деленный на нуль) для xi.

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

Условимся все векторы считать вектор-столбцами и будем применять транспонирование для обозначения соответствующих векторов-строк. Чтобы это не привело к путанице, иногда будем применять символ без знака транспонирования. Система векторов v1, …, vn будет линейно независимой, если для любых чисел a1, a2, …, an из равенства (где правая часть является нулевым n -компонентным вектором) следует, что Поэтому ни один из векторов линейно независимой системы не может быть получен в результате умножения других на постоянную и сложения. В противном случае векторы будут линейно зависимыми, т. е. приведенное выше условие выполняется не для всех ai, i = 1, …, n, не равных нулю.

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

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

В пространстве n -векторов базис должен состоять n векторов. В частности, сисvi, i = 1, …, n, элементы которой равны нулю, кроме i -го, равного тема векторов единице, формирует базис пространства n -векторов.

Отметим, например, что v1 = (1, 0, 0 ), v2 = ( 0, 1, 0 ) и v3 = ( 0, 0, 1) – линейно независимые, так как Для того чтобы этот вектор был нулевым вектором a2 = 0, a3 = 0. Векторы v1 = (1, 0 ), v2 = ( 0, 1), v3 = (1, 1) – линейно зависимые, так как a1 + a3 = 0, a2 + a3 = 0, что выполняется при a1 = a3, a2 = a1, которые могут быть и не нулями. Для нахождения коэффициентов в v = a1v1 +… an vn нужно решить систему ниям Множество всех векторов, которые являются линейными комбинациями n линейно независимых векторов (единичных векторов), называется n -симплексом (единичным n -симплексом).

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

Два вектора v1 и v2 (как и две матрицы) ортогональны, если v1v2 = 0, где v1 заv2 – как вектор-столбец. Существует стандартная процеписан как вектор-строка, а дура преобразования множества n линейно независимых векторов в множество попарно ортогональных векторов. Если исходное множество формирует базис, новое множество также формирует базис, и он называется ортогональным базисом.

левой вектор w, что Aw = w, или (1 ) A преобразует w в w, т. е. оставляет w инвариантным. Величины, соответствующие такому w, называются собственными значениями (характеристическими значениями) матрицы A. Следовательно, w будет собственным вектором, если он является нетривиальным (т. е. ненулевым) реA I ) w = 0.

ляют множество решений однородной линейной системы с матрицей A I. Такая система фактически имеет тривиальное решение w = ( w1, …, wn ). Но для получения нетривиального решения матрица A I должна ределитель представляет собой полином n -й степени от. Он имеет вид n a1 n 1 + … + ( 1) det ( A ) и называется A. Условие равенства определителя нулю называется характеристическим уравнением матрицы A. Это уравнение согласно теореме Гамильтона–Кэли тождественно равно нулю, если заменить на A, (т. е.

A I = 0 являются искомыми собственными значениями. Основная уравнения теорема алгебры утверждает существование n -корней для полиномиального уравнения степени n. Собственные векторы получаются в результате решения соответствующей системы уравнений Avi = i vi. Следует обратить внимание на получение всех собственных векторов, когда имеются кратные корни.

Отметим, что и корни характеристического уравнения, являясь корнями уравнения удовлетворяют кратные корни, и, следовательно, общее число различных корней может быть меньше, чем n. Очевидно, что кратный корень i, кратности k появится в факторизации чение Пример. Рассмотрим матрицу Так как в данном случае характеристическое уравнение квадратное, решим его, используя хорошо известную квадратичную формулу для нахождения корней такого уравнения. Для собственных значений имеем т.е.

или откуда ками, и поэтому второе уравнение не содержит новой информации. Собственный вектор w получается в результате присваивания произвольного значения w2 и выw1 согласно полученному выше соотношению. Присвоим w2 значение 1.

числения Тогда имеем Можно нормализовать каждый коэффициент на сумму w1 + w2, которая равна ( 1 + 1)( 1 1). Получим результирующий нормализованный вектор Поскольку умножение на постоянную не влияет на решение уравнения Aw = w, будем рассматривать собственные векторы w всегда в нормализованном виде. Аналогично можно получить собственный вектор, соответствующий Собственные значения как корни любого полиномиального уравнения можно получить, используя различные стандартные численные методы. В настоящее время существуют пакеты компьютерных программ для нахождения этих корней. Для уравнения, являющегося характеристическим уравнением матрицы, существуют компьютерные программы, которые для данной матрицы находят собственные векторы.

Собственные значения матрицы, будучи корнями ее характеристического уравнения, могут быть комплексными числами и, следовательно, попарно комплексноa + ib, где i = 1, a сопряженными. Напомним, что комплексное число имеет вид и b – действительные числа. Модуль такого числа обозначается a + ib и равен. Если элементы матрицы – действительные и она симметричная, все ее собственные значения действительны. Собственные ректоры, соответствующие различным собственным значениям, ортогональны. Этим же свойством обладает эрмиT това матрица. Матрицы A и A имеют одни и те же собственные значения, но в общем случае не одни и те же собственные векторы.

Следующая теорема (см. [48]) может быть применена к если использовать непрерывное преобразование, например логарифмическую функцию. Теорема утверждает, что собственные значения матрицы непрерывно зависят от ее коэффициентов (это то же, что непрерывная зависимость корней полинома от его коэффициентов).

Теорема. Если произвольная матрица ниями Доказательство. Определим min f ( µ, A ) определен, так как f – непрерывная функция µ. Также rj > 0, поf ( µ, A ) = 0 являются центрами окружностей.

скольку корни Определитель i, j = 1, …, n, и, следовательно, для некоторых > 0, f ( µ, B ) 0, для µ на любой C j, j = 1, …, s, если ij, i, j = 1, …, n. Из теории функций комплексной переm j корней µ уравнения f ( µ, B ) = 0, лежащих внутри менной известно, что число окружности которая из-за ны и иметь общее значение известных:

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

Часто встречаются функции матрицы A, такие, как степени и экспоненты. Имеет смысл рассмотреть такие функции. Существует следующая теорема из этой области, принадлежащая Сильвестру (см. [49]):

k – количество различных характеристических значений матрицы A ; mi – кратность вычисленная при – полные ортогональные идемпотентные матрицы матA, т. е. они обладают свойствами рицы I и O – единичная и нулевая матрицы соответственно.

где При различных характеристических значениях для матрицы [64] Для иллюстрации того, как это получается когда A, отметим, что из полинома n -й степени I A = 0 матрица An может быть выражена через низшие степени A и, следовательно, f всегда может быть сведена к полиному степени, не превышающей n 1. Если написать f ( A ) vi = f ( i ) vi, то получим что и дает искомый результат.

f ( A ) = exp ( At ) и различных характеристических значениях A имеем спекПри тральное разложение Случай кратных характеристических корней выводится из иного варианта теоремы Сильвестра. Если напишем для краткости k – количество различных корней, тогда Здесь есть производная Заметим, например, что Рассмотрим систему или просто Исходя из формулы Сильвестра при 1 = 2, 2 = 2, имеем и применим ее для получения решения системы.

Аналогично можно показать, что если

НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

Граф – это множество точек V, вершин или узлов, и множество простых кривых E, граней или ребер, связь которых с вершинами, называемыми его концевыми точками, описывается определенным правилом. Говорят, что вершины инцидентны ребру. Открытое ребро инцидентно в точности двум различным вершинам. Замкнутое ребро (называемое петлей) инцидентно в точности одной вершине и, следовательно, его концевые точки совпадают. Ребра не имеют общих точек, за исключением вершин.

На рис. П.1 v1 и v2 – примеры вершин; e1 – петля, концевая точка которой – v5 ;

e2 – открытое ребро с концевыми точками v2 и v3.

Два ребра с общей вершиной, или две вершины, являющиеся концевыми точками ребра, называют смежными. Вершина является изолированной, если она не инG = (V, E ).

цидентна никакому ребру. Обозначим граф следующим образом:

G – это подмножество V1 множества вершин V и подмножество Подграф графа E1 множества ребер E с теми же связями между вершинами и ребрами, что и в G.

Граф называют простым, если он не имеет ни петель, ни параллельных ребер, т. е. кратных ребер между парами вершин. В основном будем рассматривать простые графы, но поскольку в определение графов введены петли и параллельные ребра, при рассмотрении непростых графов будем вносить ясность.

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

значают дуг, направленных от v. При определении степени инцидентная вершине петля считается дважды. Для изолированной вершины имеем d ( v ) = 0.

ветственно, Граф называется конечным, если и бесконечный. Рассматривать будем только конечные графы. Степень рис. П.З равна 5:

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

Последовательность n ребер e1, …, en в графе G называется маршрутом, если существует соответствующая последовательность n + 1 (не обязательно различных) вершин v0, v1, …, vn, таких, что ei инцидентно vi 1 и vi, i = 1, …, n. Маршрут замкнут (циклический), если v0 = vn, в противном случае разомкнут. Если ei e j для всех i и j, i j, маршрут называют цепью. Замкнутая цепь называется циклом (контуром). Если все вершины различны, маршрут называется простой цепью, в то время как при v0 = vn и различных всех остальных вершинах имеем простой цикл при усn 3. Пример простой цепи дан последовательностью ребер ловии на рис. П.1. Здесь каждое ребро в последовательности заменено парой вершин, которые являются его концевыми точками, так как следуют друг за другом в маршруте v6, v1, v5, v2, v3. Аналогичные определения могут быть даны для направленных графов, если учитывать направление каждой дуги. Здесь речь идет о направленных (ориентированных) маршрутах, путях и контурах, а также о простых путях и простых контурах.

Граф называют связным (сильно связным) в ненаправленном (направленном) смысле, если существует простая цепь (путь) между любой парой вершин. Граф с n + 1 вершинами является n -связным, если после удаления n 1 или менее вершин он остается связным. Две цепи называют параллельными, если у них нет общих вершин, за исключением их концевых точек.

Компонента C графа G – максимальный связный подграф (т. е. каждая вершина, которая смежна вершине в C, также принадлежит C, и все ребра G инцидентные вершинам C, также принадлежат C ).

Поддерево – это связный подграф, не имеющий циклов. Перекрывающее дерево – это (максимальное) поддерево, которое содержит все вершины графа. Ребро графа, не принадлежащее дереву, называют хордой. Ребро графа, принадлежащее дереву, называют ветвью. Когда хорда добавляется к перекрывающему дереву, в результате получается цикл, который называется фундаментальным циклом. На рис. П.4 приводится перекрывающее дерево для направленного графа. Корень дерева находится в вершине v0, из которой начинаются все пути, существующие на дереве.

Специальный тип цикла в графе, важный для практических применений, назван в честь известного ирландского математика Уильяма Гамильтона (1805–1865). Мы называем цикл, который проходит через каждую вершину графа только однажды, гамильтоновым циклом. В то же время отметим, что имя швей царского математика Л. Эйлера (1707—1783) ассоциируется с эйлеровым графом, в котором ребра формируют цепь с каждым ребром графа, включенным в цепь только однажды. Цепь может быть разомкнута или может образовать цикл.

Два графа взаимно однозначное соответствие между V и V и между E а E, сохраняющее инцидентность. Например, два графа, показанные на рис. П.5, изоморфны.

Простой граф ребром, называется полным графом для n -вершин. Легко убедиться, что полный граф имеет n ( n 1) 2 ребер. Так как любые два полных графа, имеющие одинаковое число вершин, изоморфны, говорят о полном графе для n -вершин.

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

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

Граф не связан (или несвязный), когда множество вершин V может быть раздеV1 и V2 так, что нет ребра, соединяющего вершину в V1 с лено на два множества V2, в противном случае говорят, что граф связный. Хотя две вершины вершиной в могут не быть прямо связанными ребром, оказывается возможно достижение одной из этих вершин из другой простой цепью. Если такая цепь, соединяющая любую пару вершин, имеется, то говорят, что граф связный. Иногда предпочитают применение первого определения, но чаще используется эквивалентное ему второе определение. В действительности второе определение намного богаче, так как охватывает целую область проблем достижимости графа или подграфов этого графа. Например, можно начать требовать большего. Можно ли начать с вершины и пройти по ребрам графа последовательно без повторения? Можно ли проделать это и закончить перемещение на начальной вершине? Можно ли, стартуя с вершины, пройти простую цепь через все вершины с возвращением или без возвращения к начальной вершине? Можно ли проделать это, если рассматривать только подграфы n 1 вершин?

Другой вопрос касается того, насколько велика связность графа. Имеются два пути исследования этой проблемы: через ребра графа и через его вершины. Граф можно сделать несвязным, убрав одновременно несколько ребер.

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