Программные продукты и системы

Одним из современных и наиболее эффективных методов многоуровневого экспертного оценивания является метод аналитических иерархических процессов (метод АИП – МАИП), разработанный Т. Саати [1, 2]. Данный метод предназначен для решения задач ранжирования конечного множества сложных объектов, прямое попарное сравнение которых невозможно. МАИП включает декомпозицию проблемы на все более простые части и элементы и последующую обработку матриц парных сравнений (МПС), заполняемых экспертом, с переходом от уровня к уровню и получением конечной оценки с определением относительной степени (интенсивности) взаимного влияния элементов в иерархии. Вычислительная сложность метода – нахождение максимального собственного числа (СЧ) МПС и соответствующего ему собственного вектора (СВ), нормализация СВ и проверка согласованности МПС. Известен ряд программных систем, реализующих методологию АИП [1], а развитые возможности современных инструментальных средств для создания приложений, имеющихся, в частности, в составе офисного ансамбля Microsoft Office, позволяют сравнительно легко встроить поддержку МАИП в такой популярный пакет, как табличный процессор Excel.

В ходе обсуждения МАИП в научной литературе наряду с примерами успешного применения появляются критические замечания как по теоретическому обоснованию метода, так и по поводу его практических сложностей, к которым в первую очередь необходимо отнести необходимость полного заполнения МПС (n(n-1)/2 суждений эксперта; n – порядок МПС), эффект дробления цели (уменьшения весов наиболее важных целей при увеличении уровней иерархии), проблемы анализа чувствительности вариаций экспертных оценок (ЭО) и получения решений в случае интервальных ЭО (ИЭО).

Известные альтернативные методы решения задачи АИП – метод наименьших квадратов (МНК) и метод логарифмических наименьших квадратов (МЛНК) – в целом уступают методу собственного вектора (МСВ) Т. Саати [1].

При создании Интернет-центра по оказанию вычислительных и консультационных услуг в групповом экспертном оценивании в Тверском государственном техническом университете был разработан комплекс программных средств для нахождения МНК-решений в АИП, основанный на новых подходах в использовании МНК [3] и позволяющий избавиться от большей части присущих МСВ недостатков.

Алгоритмическое обеспечение комплекса

Полные сравнения. Предлагается использование теоретически разработанного аппарата МНК [4] применительно к решению задачи АИП в новой формулировке вида

                                        (1)

где A – полная МПС порядка n; E – единичная матрица; e – вектор-строка длины n (ei=1, i=1,2,…,n); x – нормализованный вектор ранжирования критериев (объектов).

С помощью обратноположительных матриц и их положительных расщеплений [5] доказаны теоремы о существовании x > 0, соотношениях для вычисления x и величины нормы ||(A-nE)x||2 как нового критерия согласованности МПС. Методом имитационного моделирования получены следующие средние индексы согласованности (ИС) для МПС порядка n=3¸15 (при n=1 и n=2 ИС равны 0), ЭО в которых генерировались с помощью датчика псевдослучайных чисел:

Отношение ИС для конкретной МПС к среднему ИС для МПС того же порядка, называемое отношением согласованности, меньшее или равное 0,10, считается приемлемым [1].

На представительном множестве примеров из [1] была показана практическая работоспособность предложенных алгоритмов и проведен сравнительный анализ полученных результатов, который позволяет сделать обоснованный вывод о том, что МСВ и предлагаемый вариант МНК дают практически совпадающие значения элементов векторов ранжирования при полном совпадении ранжирования критериев. Расчеты для примера из [6], демонстрирующего различие в ранжировании критериев при нахождении МСВ-решения y и МЛНК-решения z, также подтверждают практическое совпадение результатов для предлагаемого варианта МНК-решения x и МСВ-решения y:

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

                                        (2)

                                                            (3)

где ki – число недополученных суждений эксперта в соответствующей строке МПС A, в которой отсутствующие суждения заменены нулевыми значениями. Соотношение (3) получено в результате исследования предельных свойств решения (2) при изменении ki от 0 до n – 1. С помощью обратноположительных матриц и их положительных расщеплений доказаны теоремы о существовании x>0 и о возможности использования нормы ||(A-nE)x-c||2 как критерия согласованности неполной МПС. Работоспособность предлагаемого подхода к ранжированию критериев по неполной МПС проверялась на задаче выбора дома [2] с МПС порядка 8. В случае полных сравнений необходимо сделать 28 ЭО. При отсутствии суждений в нижнем диагональном блоке МПС порядка 5 (18 ЭО; степень заполнения МПС 64%) в полученном МНК-решении по сравнению с базовым МНК-решением для полной МПС имеется реверсирование 5-го и 7-го рангов критериев, что свидетельствует об эффективности предлагаемого подхода, поскольку аналогичное МСВ-решение имеет реверсирование 3-го и 4-го рангов по сравнению с исходным МСВ-упорядочиванием критериев по полной МПС.

Интервальные ЭО позволяют учесть неполноту знаний эксперта и возникают также при групповом экспертном оценивании вследствие разброса мнений экспертов [7, 8]. Одной из задач в случае ИЭО является нахождение вектора ранжирования объектов, при котором система ИЭО согласованная и решение x существует:

Для нахождения МНК-решения рассматриваемой задачи и усредненного мнения экспертов предложена следующая модификация соотношения (1):

В случае несогласованности системы ИЭО предлагается ряд оригинальных алгоритмов для минимального расширения исходных ИЭО с целью получения согласованной системы ИЭО. Их практическая работоспособность проверена на ряде известных тестовых примеров МПС с ИЭО. Для примера из [8] с несогласованной интервальной МПС A найдены согласованная интервальная МПС D и соответствующее ей допустимое решение x:

Анализ чувствительности обычно проводится с целями исследования влияния вариаций ЭО на изменения элементов векторов ранжирования критериев как для отдельной МПС [7], так и на различных уровнях иерархии [9]. Используемый в [7] метод приводит к завышенным оценкам вариаций элементов вектора ранжирования, поскольку не учитывает имеющейся функциональной зависимости ЭО (МПС – обратносимметричная матрица), и вариации ЭО также должны быть взаимозависимы. Разработан алгоритм анализа чувствительности, основанный на использовании номинального МНК-решения xN и нахождении комбинаций вариаций ЭО МПС, при которых достигается экстремум (минимум или максимум) нормы ||(A-nE)xN||2. С учетом того, что такие комбинации отличаются только знаками, достаточно решить всего одну задачу безусловной бинарной оптимизации с n(n-1)/2 переменными и далее найти два МНК-решения, ограничивающих вариации элементов вектора ранжирования. Предложен также и эвристический алгоритм решения рассматриваемой задачи, непосредственно находящий комбинации вариаций ЭО, близкие к оптимальным. Для примера из [7] с номинальной МПС A, матрицей вариаций ЭО D и решением y с помощью предложенного точного алгоритма найдены следующие интервальные решения xL и xH:

Особенности программной реализации

Встроенные программные системы поддержки МНК-методологии АИП реализованы в средах системы для математических расчетов MATLAB и табличного процессора Excel. Комплекс программных средств аналогичного назначения в составе Интернет-центра по оказанию вычислительных и консультационных услуг в групповом экспертном оценивании реализован на интрасетевой платформе корпорации Microsoft.

Реализация в MATLAB включает ряд программных систем, в том числе: версию для разработчиков – с режимом работы в командной строке MATLAB; для конечных пользователей – на основе приложения Excel Link; учебного назначения – на основе приложения Notebook и для IT-специалистов – на основе пакета проектирования событийно-управляемых систем Stateflow. Все версии имеют общее ядро – комплекс базовых модулей в виде М-функций MATLAB.

Интрасетевая реализация выполнена в архитектуре клиент-сервер с использованием объектных моделей и компонентного подхода. Использованы Web-технологии разработки приложений Dynamic HTML (DHTML) и Active Server Pages (ASP), объектные модели Active Data Objects (ADO) и Document Object Model (DOM), программные средства Internet Explorer 5.0/5.5, Internet Information Server 5.0 и MS Office 2000 Web Components, инструментальные ПС MS FrontPage 2000 и MS Development Environment, скриптовый язык программирования JScript и технология скриплетов (scriplets), расширенный язык гипертекстовой разметки документов Extensible Markup Language (XML).

Реализация в Excel использует возможности электронных таблиц и языка офисного программирования Visual Basic for Applications (VBA). Один из вариантов Excel-реализации позволяет найти на единой методологической основе МНК-решения в АИП в случаях совместного использования как полных, так и неполных ЭО, при этом автоматизируются многие операции по оформлению рабочих листов и представлению результатов вычислений. Возможности и особенности данного варианта демонстрируются на примере решения задачи выбора дома [9]. Пользователь должен подготовить исходную информацию на рабочем листе "Головной лист" шаблона AHP_LS_Template.xlt Excel (рис. 1).

Затем с помощью подпрограмм Build_WS и Build_WB VBA-модуля Create_WB в рабочую книгу шаблона Excel, первоначально содержавшую пустые листы "Головной лист" и "Матрица достижимости" (МД), добавляются новые рабочие листы с именами соответствующих узлов иерархической структуры (рис. 1) с выявлением дублирующих узлов некоторых уровней, необходимых для формального описания ситуации отсутствия узла на уровне иерархии. Рабочие листы предварительно заполняются информацией, автоматически заносимой в диапазоны для матриц, правых частей и решений систем линейных алгебраических уравнений (СЛАУ) с помощью подпрограммы Build_WS и пользовательских VBA-функций Right_Part_LE и Solve_LE, при этом реализуется вариант предельного неполного зкспертного оценивания (рис. 2).

Далее с помощью VBA-модуля для формы Create_TV (подпрограммы UserForm_Activate, TreeView1_NodeClick и TreeView1_DblClick) строится древовидная структура, отображаемая в диалоговом окне "Иерархия критериев" и используемая для доступа к конкретному рабочему листу (рис. 3).

VBA-модуль для формы Fill_Cell (подпрограммы UserForm_Activate и ListBox1_Click) используется для занесения в выделенную пользователем ячейку диапазона для матрицы СЛАУ ЭО, выбираемой из диалогового окна "Экспертные оценки", с автоматическим формированием обратносимметричного значения и пересчетом информации на листе (рис. 4).

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

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

Листинг подпрограммы UserForm_Activate демонстрирует возможности и особенности использования языка VBA в рассмотренном варианте Excel-реализации поддержки МНК-методологии АИП:

Private Sub UserForm_Activate()

Dim Root As String

Dim Node As String

Range("D6").Activate

ActiveCell.CurrentRegion.Select

n = Selection.Rows.Count

m = Selection.Columns.Count

TreeView1.Nodes.Add , , "1-1", Selection.Cells(1, 1).Value

For j = 2 To m

For i = 1 To n

If Selection.Cells(i, j - 1).Value <> "" Then k = i

If Selection.Cells(i, j).Value <> "" And _

Selection.Cells(i, j).Value <> Selection.Cells(k, j - 1).Value Then

Root = LTrim(Str(k)) & "-" & LTrim(Str(j - 1))

Node = LTrim(Str(i)) & "-" & LTrim(Str(j))

TreeView1.Nodes.Add Root, 4, Node, Selection.Cells(i, j).Value

End If

Next

Next

TreeView1.LineStyle = 1

TreeView1.Font.Size = 10

TreeView1.Font.Name = "Arial Cyr"

End Sub

Перечисленные модули, подпрограммы и функции использованы в вариантах обучающей, пользовательской и профессиональной реализации поддержки МНК-методологии АИП в среде Excel, а также модифицированы для реализации клиентских интрасетевых версий средствами языка JScript и Web-компонентов MS Office 2000.

Разработанный комплекс компонентных программных средств в виде элементов управления ActiveX и скриплетов может быть использован во встроенных системах поддержки МНК-методологии АИП для многих проблемных областей, в том числе таких актуальных, как стратегические анализ, планирование и управление, бизнес-реинжиниринг и управленческий консалтинг.

Список литературы

1. Саати Т. Принятие решений. Метод анализа иерархий. – М.: Радио и связь, 1993. – 320 с.

2. Саати Т., Кернс К. Аналитическое планирование. Организация систем. - М.: Радио и связь, 1991. – 224 с.

3. Демидов Н.Е. МНК-решения в аналитических иерархических процессах экспертного оценивания // Математические методы в технике и технологиях - ММТТ 2000: Сб. тр. Международ. научн. конф. - СПб.: СПбГТУ, 2000. - Т. 5. - С. 63-64.

4. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. – М.: Мир, 1998. – 575 с.

5. Peris J.E. A new characterization of inverse – positive matrices // Linear Algebra and Appl. – 1991, v. 154-156. – P. 45 – 58.

6. Saaty T.L. Eigenvector and logarithmic least squares //

European Journal of Operational Research. - 1990, v. 48. - №1. - P. 156 - 160.

7. Zahir M.S. Incorporating the uncertainty of decision judgements in the analytic hierarchy process // European Journal of Operational Research. - 1991, v. 53. - №2. - P. 206 - 216.

8. Kress M. Approximate articulation of preference and priority derivation - a comment // European Journal of Operational Research. - 1991, v. 52. - №3. - P. 382 - 383.

9. Masuda T. Hierarchical sensitivity analysis of priority used in analytic hierarchy process // Int. J. Systems Science. – 1990, v. 21. - №2. – P. 415 – 427.