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

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

При достижении некоторого порогового значения числа пользователей (а в настоящее время их число превышает 150) необходимо создание полноценного call-центра для обслуживания и систематизации запросов пользователей.

Внедрение АИСУ позволило избавиться от дублирования данных в различных подразделениях, формализовать и регламентировать их бизнес-процессы, организовать единое информационное пространство для совместной работы подразделений, обеспечить доступ руководства как к первичным, так и к статистическим документам системы. Компания Oracle включила АИСУ ПГУПС в список лучших примеров внедрения технологий Oracle в вузах России (www.oracle.com/glo-bal/ru/academy/spb_gu_transport.doc).

Литература

1. Marti Harris, Michael Zastrocky, Jan-Martin Lowendahl Magic Quadrant for Higher Education Administrative Suites, 2007, Gartner, Inc., September 26, 2007.

2. Яблонский С.А., Сухоногов А.М., Темплинг А.А., Самонина О.А. Автоматизированная информационная система управления Петербургского государственного университета путей сообщения (АИСУ ПГУПС) // Информационная среда вуза XXI века: тр. II Всерос. науч.-практич. конф. Петрозаводск, 2008. С.177-179.

3. Яблонский С.А., Сухоногов А.М., Темплинг А.А., Самонина О.А. Подсистема приемной комиссии АИСУ ПГУПС // Там же. С. 171-174.

4. Яблонский С.А., Сухоногов А.М., Темплинг А.А., Самонина О.А. Расчет численности штата профессорско-преподавательского состава университета // Там же. С. 175-177.

5. Яблонский С.А., Сухоногов А.М., Темплинг А.А., Самонина О.А. Автоматизация ведения приемной кампании 2009 года на основе АИСУ ПГУПС // Информационная среда вуза XXI века: тр. III Всерос. науч.-практич. конф. Петрозаводск, 2009.

ИНСТРУМЕНТАЛЬНАЯ СИСТЕМА ДЛЯ РЕШЕНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА

С.В. Микони, д.т.н.; Д.П. Бураков, к.т.н.; М.И. Гарина, к.т.н.

Описывается программная система СВИРЬ-Р, предназначенная для решения задач многокритериального выбора на конечном множестве альтернатив. Система реализует основные методы выбора, функционирует автономно, ком-плексируется с информационными системами общего назначения и может конфигурироваться под заданный класс задач. Она успешно применяется в учебном процессе и научных исследованиях.

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

К задачам многокритериального выбора на конечном множестве альтернатив относятся нахождение наилучшего (наихудшего, среднего) объекта, отбор допустимых объектов, упорядочение объектов по предпочтению, а также отнесение объекта к одному из заданных классов [1].

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

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

В Петербургском государственном университете путей сообщения работа над системой с перечисленными свойствами ведется в течение 10 лет. За этот период было разработано и внедрено в учебном процессе и на практике несколько редакций системы выбора и ранжирования СВИРЬ [2]. В настоящей статье описываются свойства последней редакции системы, названной СВИРЬ-Р, с учетом возможности ее реконфигурации.

Модель многокритериального выбора

Модель выбора в системе, реализующей различные методы многокритериальной оптимизации

и классификации, должна быть инвариантна по отношению к этим методам. Данному требованию отвечает теоретико-множественная модель [3]:

МВ=<Х, Р, У, Н, Р, Х>.

Она содержит:

• множество оцениваемых альтернатив (объектов) X;

• множество функций Р, характеризующих различные свойства объектов;

• области определения и значений У функций из множества Р;

• множество целей (целевых состояний) Н, задаваемых для оцениваемых признаков;

• отношения предпочтения (предикаты) Р, определяемые на множествах X, Р, У, Н;

• степень соответствия альтернативы х1 целевому состоянию Ик.

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

При сопоставлении альтернатив \| и хк, хь хкеХ, истинность двухместного предиката Р„|Ч|(\|, хк) означает, что х1 ^ хк. Если предикат Рога(х15 \к)И'а^с(0). то имеет место либо обратное предпочтение -< хк. либо равнозначность х^хк сравниваемых альтернатив. Бинарное отношение Ког(1 ^ХхХ является решением задачи выбора на языке бинарных отношений. При критериальном выборе каждой альтернативе ставится в соответствие величина ^¡еУ, отражающая ¡-с свойство альтернативы и вычисляемая с применением функции X—»У. Отношение КОГ(1сХхХ формируется на основе количественных оценок альтернатив, то есть отношения ^„^сУхУ.

Для нахождения наилучшей альтернативы выполняется ранжирование отношения Я^. Оно заключается в присвоении каждой альтернативе \|ёХ целого числа из диапазона [1, N1: НП11111сХх1\. К„„т={(х1,1),...,(хк,р),...,(х8Д)}, где N=1x1. Число р задает рейтинг (ранг) альтернативы - указывает ее место по предпочтению среди остальных альтернатив.

Модель (1) предоставляет всю необходимую информацию для решения задач отбора, упорядочения и классификации объектов в п-мерном пространстве признаков.

Создание и редактирование модели выбора

Отношение Кисх<=ХхР, которое характеризует исходные данные, представляется таблицей «Объекты/Признаки». Строки таблицы образуют объекты из множества X, а столбцы - признаки из множества Р. Клетки таблицы заполняются значениями признаков Уу=^(х|). Таким образом, 1-й объект, 1= , характеризуется вектором значений

yi=(yii, ...,Уу,...,Уш), поэтому второе название таблицы - «Характеристика объектов».

Таблица «Объекты/Признаки», описывающая заданную предметную область (ПрО), либо создается в системе СВИРЬ-Р с клавиатуры, либо вводится из табличного процессора MS Excel или из типовой СУБД. При создании с клавиатуры задаются размерность таблицы (число строк и столбцов), имя ПрО, имена объектов и признаков. Данные в таблицу могут заноситься с клавиатуры или из названных систем при условии совпадения имен вводимых объектов и признаков с именами, введенными в таблицу.

При формировании иерархической модели дочерние таблицы создаются на основе признаков таблиц предыдущего уровня иерархии (технология построения сверху вниз). Режим создания таблицы нижнего уровня выбирается правой кнопкой мыши. В появляющемся окне задаются число и имена детализирующих признаков. Структура модели выбора представляется деревом таблиц. Для отображения дерева иерархии в левой части главного окна системы СВИРЬ используется стандартное средство Tree-View операционной системы MS Windows.

Редактирование модели осуществляется перемещением признаков из одной таблицы в другую с помощью технологии drag-and-drop. Она же применяется для подчинения (переподчинения) одной таблицы другой в дереве иерархии.

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

Для формулирования задач выбора в системе СВИРЬ-Р используется контекстно-зависимый интерфейс. В его основу положены два класса задач: многокритериальной оптимизации и классификации. Методы оптимизации, в свою очередь, тоже делятся на два класса: методы векторной и скалярной оптимизации. Методы векторной оптимизации различаются отношением доминирования, реализуемого на векторных оценках объектов: Парето-доминирования, лексиминного и лексикографического (метод приоритета критериев). Первые два метода характеризуются минимальным использованием экспертной информации, но не гарантируют получение линейного порядка объектов при решении задачи упорядочения. Качество решения задачи упорядочения характеризуется показателями доминирования, неразличимости и несравнимости объектов, а также коэффициентом полноты порядка [3].

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

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

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

Требования к признакам

Формирование требований к признакам зависит от решаемой задачи и глубины проникновения в предметную область. При решении задач упорядочения объектов на основе признаков формируются критерии оптимизации. Если ЛПР неизвестно пороговое значение признака, формируется целевой критерий, а если известно - ограничительный [3]. Для целевого критерия задается направление оптимизации (min или max), а для ограничительного критерия - ограничение значения признака снизу, сверху, в точке или интервале. По умолчанию этим критериям ставятся в соответствие функции полезности - линейные и кусочно-линейные. Если ЛПР известна информация о приращении полезности признака, линейные функции полезности преобразуются в нелинейные. Для выполнения нормализации признака задаются границы его шкалы. Они формируются либо ЛПР, либо автоматически, по выборке объектов.

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

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

Анализ модели и результатов выбора

В системе СВИРЬ-Р предусмотрены различные табличные и графические средства анализа. Анализ независимости критериев осуществляется с помощью корреляционной матрицы. Результаты многокритериального выбора выводятся в таблицу «Решение». В графической форме представляются: функции полезности и принадлежности классам, графы зависимости признаков и графы доминирования объектов, многокритериальные оценки полезности, вклад в них различных критериев, сравнительные оценки рейтинга объектов, полученных различным способом, деревья иерархии признаков и весовых коэффициентов в иерархии. Для пояснения результатов используются специальные таблицы, а для их различения - цветовая окраска.

Выделение ресурсов под задачи выбора

Под выделяемым ресурсом понимается одна или группа функций системы, использование которых требует специального разрешения. Ресурсы системы делятся на внешние и внутренние. Их выделение осуществляется по-разному. Внешние ресурсы, оформленные в виде динамических библиотек, включаются в комплект поставляемой программной системы. Внутренние ресурсы входят в состав исполняемой программы СВИРЬ-Р. Они делятся на следующие группы: отбор объектов, критерии оценивания, скалярная оптимизация, обобщающие функции, векторная оптимизация, классификация, критерии классификации, иерархия, сервисные функции.

Базовая конфигурация системы СВИРЬ-Р представляет собой совокупность ресурсов, требующихся для проектирования модели выбора, решения контрольной задачи и обмена информацией с процессором MS Excel. В качестве контрольной задачи принята задача нахождения рейтинга объектов относительно общей цели. Для выполнения лабораторного практикума по теории принятия решений [4] выделяются ресурсы для применения всех методов выбора с ограничением на размерность модели и на сервисные функции.

Литература

1. Микони С.В. Теория и практика рационального выбора. М.: Маршрут, 2004. 462 с.

2. URL: www.pgups.ru/nauka/mikoni/ (дата обращения: 10.07.2009).

3. Микони С.В. Многокритериальный выбор на конечном множестве альтернатив: учеб. пособие. СПб: Лань, 2009. 273 с.

4. Микони С.В., Гарина М.И. Лабораторный практикум по дисциплине «Теория принятия решений»: учеб. пособие. СПб: ПГУПС, 2009. 97 с.

СИСТЕМА ВЫЧИСЛЕНИЯ ПРИОРИТЕТОВ НА ОСНОВЕ МАТРИЦ ПАРНЫХ СРАВНЕНИЙ

И.С. Киселёв; С.В. Микони, д.т.н.

Описывается система, функционирующая в составе программной системы СВИРЬ-Р в качестве динамической библиотеки. Она предназначена для формирования матриц парных сравнений, анализа их согласованности и вычисления приоритетов сущностей. Алгоритм вычисления приоритетов инвариантен относительно четырех типов матриц, реализуемых в системе. Метод анализа иерархий реализуется совместно с системой СВИРЬ-Р относительно сформированной в ней модели выбора.

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

Усилиями американского математика Томаса Саати метод анализа иерархий (МАИ) получил широкое распространение [1]. Он имеет многочисленные программные реализации. Метод основан на использовании матриц парных сравнений (МПС), содержащих кратные предпочтения. Под кратным предпочтением ак"у понимается превосходство ¡-й сущности \| над .¡-й сущностью х^ ^еХвкраз, ке[0,1; 10].

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

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

Создание МПС

Программная система СВП реализована в виде динамической библиотеки системы выбора и ранжирования СВИРЬ-Р. Из системы СВИРЬ-Р задаются перечень сопоставляемых сущностей, размерность и тип матрицы. В саму систему возвращается вектор нормированных приоритетов, сформированный на основе МПС. Тип МПС (кратности предпочтений, фактов предпочтений, долей от 1 или отношения «Выигрыши/Потери») может задаваться также и внутри системы СВП.

Содержимое МПС может вводиться напрямую экспертами через клавиатуру либо из табличного процессора Excel, содержащего известные предпочтения - экспертные или объективные. Матрица может формироваться автоматически на основе вектора приоритетов, заданного в интервальной шкале. Такая матрица имеет стопроцентную согласованность и в случае количественных предпочтений называется сверхтранзитивной. Пример задания вектора приоритетов (в процентах) для четырех признаков приведен на рисунке 1. В правой части вкладки «Задание» выбираются тип МПС, максимальная кратность предпочтения (по умолчанию 10), а также способ автоматического формирования содержимого матрицы.

Содержимое МПС, полученное вручную или автоматически, фиксируется на вкладке «Предпочтения» (рис. 2).

Ручное задание и редактирование предпочтений осуществляются на правой стороне вкладки.