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

Даничев Алексей Александрович

На правах рукописи

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

в порядковых шкалах для систем поддержки принятия решений

05.13.01 — системный анализ, управление и обработка информации (по отраслям: информатика, вычислительная техника и управление)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Красноярск 2005

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования "Красноярский государственный технический университет"

Научный руководитель: доктор технических наук, доцент

Бронов Сергей Александрович

Официальные оппоненты: доктор технических наук, профессор

Медведев Александр Васильевич

доктор физико-математических наук, профессор Носков Михаил Валерьянович

Ведущая организация: Институт вычислительного моделирования

Сибирского отделения Российской Академии наук (г. Красноярск)

Защита состоится 16 декабря 2005 года в 14:00 на заседании диссертационного совета Д 212.098.04 при Красноярском государственном техническом университете по адресу: ул. академика Киренского, 26, Красноярск, 660074, ауд.Д 501.

Факс: (3912) 43-06-92 (КГТУ, для каф. САПР)

E-mail: sovet@front.ru

Телефон: (3912) 91-22-95 (каф. САПР)

С диссертацией можно ознакомиться в библиотеке Красноярского государственного технического университета.

Автореферат разослан 15 ноября 2005 г.

Ученый секретарь диссертационного совета д.т.н. 1 С.А. Бронов

? тот

¿и>ззг

Общая характеристика работы

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

Для обработки качественной информации используются функции предпочтений пользователя, математическое программирование в порядковых шкалах, специальные методы для особых типов данных. В настоящее время методы и алгоритмы обработки информации в порядковых шкалах недостаточно проработаны для включения их в математическое обеспечение СППР, что затрудняет создание соответствующих программных компонент. Проблемам обработки информации в порядковых шкалах и методам получения результирующего ранжирования посвящены работы зарубежных ученых (Р. Л. Кини, X. Райфа, Р. Р. Девидсона, Д. Блэка), а также работы В. В. Подиновского, Б. Г. Литвака, Д. Б. Юдина и др. Одна из основных задач обработки данных в порядковых шкалах — получение результирующего ранжирования (задача группового выбора), для решения которой известно более десятка методов. При высокой согласованности данных все методы, как правило, приводят к одинаковым результатам. На практике, когда согласованность данных невысока, применение известных методов дает противоречивые результаты, что затрудняет использование их в СППР. Необходима более глубокая теоретическая переработка существующей совокупности методов, рассмотрение их с единых позиций, представление в виде комплекса методов с возможностью их сравнения по выработанным критериям.

РОС. НАЦИОНАЛЬНАЯ { БИБЛИОТЕКА {

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

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

Предметом исследований являются методы, модели и алгоритмы обработки данных в порядковых шкалах.

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

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

Для достижения поставленной цели в диссертации поставлены и решены следующие задачи:

1) классификация исходных данных для выбора алгоритмов их предварительной обработки и методов получения результирующих ранжирований;

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

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

4) разработка диалоговых процедур для управления процессом обработки данных в порядковых шкалах;

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

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

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

Основные результаты:

1. На основе анализа существующих методов получения результирующего ранжирования выполнена унификация их математического описания, обоснованы рекомендации по их применению и выполнена их модификация в части реализующих их алгоритмов, а также вновь разработаны и алгоритмизированы методы для специальных типов данных (модифицированный метод большинства, метод минимального несогласия, модификация метода ELECTRE, k-медиана и мультипликативная свертка критериев качества, метод преобразования рангов, а также для неполный парных сравнений—линейная модель, пропорциональный метод, методы зависимостей и пополнения матриц). Предложены и обоснованы оценки чувствительности и достоверности решений.

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

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

4. Предложена и реализована процедура оценивания в порядковых шкалах результатов тестирования в форме ранжирований объектов или разделения объектов на классы эквивалентностей.

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

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

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

Научная новизна полученных результатов.

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

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

слабо согласованных данных и алгоритм определения компетентности эксперта на основе статистики его ответов.

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

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

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

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

Результаты диссертации использованы в системе менеджмента качества подготовки специалистов Красноярского государственного технического университета (КГТУ) и в региональной системе управления качеством медицинской помощи на территории Красноярского края, что подтверждено соответствующими актами.

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

Результаты диссертации были апробированы на Всероссийской научно-методической конференции в 2004 году (Даничев, А. А. Обработка экспертной информации в порядковых шкалах / М. А. Воловик, А. А. Даничев // Материалы Всероссийской научно-методической конференции 24-26 марта 2004. — Совершенствование системы управления качеством подготовки специалистов. — Красноярск. ИПЦ КГТУ), а так же на семинарах кафедр САУП и САПР КГТУ.

Публикации по материалам диссертации включают 5 работ, из них: 4 — статьи в сборниках научных работ; 1 — программа для электронных вычислительных машин, зарегистрированная в "Национальном информационном фонде неопубликованных документов".

Общая характеристика диссертации. Диссертация состоит из 5 разделов, содержит основной текст на 130 с., 29 иллюстраций, 23 таблицы, список использованных источников из 103 наименований.

Основное содержание работы

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

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

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

Формат исходных данных унифицирован в виде суммарных матриц отношений и матрицы весов. Это позволило избежать многократно повторяющихся расчетов, упростить алгоритмы и расширить функциональные возможности известных методов. Например, элемент И,, суммарной матрицы отношений равен числу случаев, когда объект а, предпочтительнее объекта а,. Так как экспертам могут быть назначены (согласно их компетентности, важности) веса т е [0,1], то

Предложена матрица весов, элемент которой уи равен (для строгих ранжирований) числу экспертов, поставивших в ранжировании 1-й объект на 7-е место:

Для нестрогих ранжирований (когда объекты могут иметь равные ранги) в диссертации предложен следующий алгоритм получения весов у„:

1) у,, =0, для г,у' = 1../я; к = \;

2) Мк = шах Кк; шаги 2.1 и 2.2 можно пропустить;

(0

п

(2)

2.1) Если Мк = 1, то А,к = 1, В,к = т для г = 1 ..т ; шаг 5;

2.2) Если Мк = т , то А,к = В,к = г, для г = 1 ..т; шаг 5;

----W¡c

5) Для ; = 1..тя и j = Д* .В, увеличить v,, на-;

1 + Bf — А,

6) Увеличить к на I; Если к < п , то шаг 2;

7) Конец.

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

= (3)

С введением меры близости на отношениях предлагается введение новых критериев качества: dk(R) = d{R,Rt). Для вычисления результирующего ранжирования можно воспользоваться сверткой критериев. Подробно рассмотрена аддитивная свертка без весовых коэффициентов, известная как медиана Кемени: -

= min. (4)

*=i

Вычисление медианы через суммарные матрицы позволило учитывать различные заложенные в них параметры и значительно сократить время вычислений. Если искомое ранжирование нестрогое, его можно представить в виде упорядочения множеств R = (u\,ui,...,um). Множества Uf={pk\,...,pkm} содержат индексы равноценных объектов. Задача оптимизации в этом случае:

т 1 т' mti mil m' "»ai —1 m*i

£ I (^U -Nl„Ptíl) -> ™n . (5)

ti=i 1=1 j=I+i

Также предложены две свертки. К-медиана:

Мультипликативная свертка:

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

суммарной матрицы и для матрицы весов линейная свертка вычисляется по формулам:

V,, (т - у)

Л = - и 5, = -. (8)

(т-\)п (т-Х)п

Мультипликативная свертка представляет собой взвешенное произведение нормированных оценок по квалиметрическому методу Руссмана:

=ГТ (1-£г)-- + £ , где У т = 1, Мк = тахг,*. (9)

Мк-\ 1 кЗ "1™

Разработана оценка достоверности решений, основанная на сравнениях

строчных сумм с их некоторыми табличными значениями. Объект а, превосходит

объект а,, если разница между и больше порога различия <1 - Мо,

с1а = 1/(т -1). На основе вычислительных экспериментов определено

рекомендуемое значение к = 0.3 . При этом оценки достоверности с, е [-1,1]:

и

О,-т,)

с,=и '\ , (Ю)

М]-о,)

где ] = г,, / = 1..т. т,,М,,0,— минимальные, максимальные и оптимальные значения х,. Коэффициент с, = 0 означает, что г -я сумма существенно отличается от ближайших сумм. Из |с,| = 1 следует, что ранг г-го объекта определен приблизительно (с, >0 — возможно объект имеет меньший ранг, с, < 0 — больший).

Далее рассмотрены методы, использующие матрицу весов. Подробно изложены такие известные методы — метод Копленда, правило большинства, квантильный метод. Показано, что квантильный метод связан с задачей (4).

Разработанный "модифицированный метод большинства" состоит в следующем. Введем переменную /1,< = л

(О-впротивном случае. Если матрица ||х'||шх„, соответствует результирующему ранжированию, представленному вектором рангов (п',г{,...,г„), то сумму

(12)

можно рассматривать как количество голосов, отданных экспертами за то, что г-е объекты находятся на г,' местах. Возникает следующая оптимизационная задача: ^УдХц -» тах (13)

'.У

при ограничениях

1,если объект а, находится на_/-м месте (ранг г, = 7); ^

in __^ _

2^x„ = 1, ( = 1 ..m ; xv = 1, j = 1 ..m ; xv e [0,1], (14)

i <=i

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

IKIHK'i. V = пик{««<*>} , (15)

где _

||jc<t)|| и max'1', к = \..т находятся из

v,jxlk) -> max (16)

¡■j

при ограничениях

W __/я

= 0, f = ГЗЙ, j = Jc+Tjn; £ £4*' = ml 4" = [0,1].

(17)

.,=1 1=1

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

Разработан новый метод получения результирующего ранжирования, основанный на построении матрицы потерь для матриц отношений и сводящийся к решению задачи о назначениях — метод минимального несогласия. Рекомендации к применению данного метода такие же, как и у медианы Кемени, но возможно получать решения для ббльшего числа ранжируемых объектов. Исходные данные: Я,, ... Я„ — векторы рангов, указанные экспертами, 71, ... Т„ — соответствующие им матрицы отношений. Пусть некоторый вектор Я = (г ... гт) отличается от вектора рангов Як только 1-й компонентой и г, = у (объект а, находится на у-м месте). Составим матрицу отношений Т = ||/||„,жт, соответствующую вектору Я . Тогда

(18)

характеризует "несогласие" к-то эксперта с назначением объекта а, на у'-е место. Элемент матрицы потерь

щ = . (19)

/U1

Оптимизационная задача:

—> min (20)

и

►

при ограничениях (14) Далее разработан алгоритм, снижающий вычислительные затраты при формировании матрицы потерь. При расчете и* можно ограничиться вычислением только 2(т -1) элементов матрицы Т:

1) и*=0,1' = 1;

2) Если /" = г, то шаг 6;

3) Если г, <г,', то = 1, шаг 5;

4) Если г, >г,', то и,■ = -1 ; иначе = 0 ;

5) Увеличить и* на |;

6) Если ¡' = у , то шаг 10;

7) Если < г,' , то = 1, шаг 9;

8) Если г, > п , то /„ = -1; иначе = 0;

9) Увеличить и,* на - гу |;

10) Если г' < /я , то увеличит г' на 1, шаг 2;

11)- Конец. -

Для случая нестрогих ранжирований в диссертации предложен следующий алгоритм получения щ:

1) щ = 0 , для /,_/ = 1 ..т, к = 1;

2) Л/* = тахг* ;

1=1 т

2.1) Если Мк = 1, то А,к = 1, В,к =т для i = 1 ..т ; шаг 5;

2.2) Если Мк -т, то Ал = В,к = г, для / = 1../и; шаг 5;

.ч „ т-1 , 7г-ТТ-

3) = У-+ 1,для ) = 0..Мк ;

Мк

4) Д* = ОкруглитъВверх{1^), В* = Округлить В низ (/,*), /=1..т;

5) Для I = 1../И и 71 = 1..Л/4 :

5.1) Рассчитать элемент матрицы потерь ;

5.2) Для у = Л* ..В' : увеличить и9 на м,'*';

6) Увеличить к на 1; если к <п , то шаг 2;

7) Конец.

Задача оптимизации для вычисления нестрогого результирующего ранжирования аналогична (15).

Предложенный метод преобразования рангов (рисунок 1) обобщает класс методов, работающих непосредственно с рангами объектов. Различные процедуры голосования задаются эквивалентными рангами Я = (п,г2,...гт) и весами для рангов б, е [0,1]. С помощью этих параметров выполняется преобразование матриц отношений: 71 -» Нк—»Л* -» 7* Тк", после чего применяется метод строчных сумм, либо любой другой метод.

В разделе приводятся такие известные методы, как турнирные показатели и оценка объектов правым собственным вектором, рассмотрено получение

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

Обобщает класс методов:

Метод строчных сумм Метод Борда С = (1,1,1,1,1)

Метод Копленда в = (1, 0, 0, 0, 1)

Правило большинства в = (1, 0, 0, 0, 0) Только голоса против 6 = (0, 0, 0, 0,1)

Защита от манипулирования в = (0, 1,1, 1, 0)

Рисунок 1 — Метод преобразования рангов

Третий раздел посвящен неполным парным сравнениям. Разработаны новые методы нахождения результирующего ранжирования для данных, представленных неполными^ матрицами парных сравнений. Подробно рассмотрены известные методы (модели Цермело-Бредли-Тири, Леонардо, Девидсона и метод Чеботарева). Приведены формулы для вычислений и предложены способы выбора неизвестных коэффициентов.

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

max X-min X , ,, ... . „

х, <--=-=-ln(1 + х, - min X) + min X .

In (max_X - min_X +1)

На рисунке 2 изображены при фиксированном Xj - 601 следующие функции: Р(а, > а,) — точками, Р(а, < cij) — пунктиром, Р(а, =а,) — сплошная (для линейной модели); тонкими линиями— аналогичные кривые для модели Девидсона.

I АО) 1201 1801

Рисунок 2 — Вероятности того, что один объект лучше, хуже или равноценен другому при фиксированном весе второго объекта (я, = 601)

Ранги R = (1, 2. 3, 4, 5)

Эквивалентные Л- R = (1, 1,2,3,3)

ранги

Веса рангов G = (1,0.8, 0.1)

Матрицы отношений '.Ч-'-Ч*

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

выполнено следующим образом:

М, = N,J+(n-N!J)P(a, > а,),1 * )А,} = \.м, (21)

где М' —число сравнений объектов. Вероятности Р(а, > а,) соответствуют той статистической модели, по которой получены параметры х,. Для пополнения матрицы весов из ранжирования /?', соответствующего параметрам х,, получаем матрицу весов \\у'„\\пкт:

(хихг,...,хт)^ К||„„т • (22)

Затем вычисляются

и задаются начальные значения у,, = . Новые элементы матрицы весов вычисляются по формуле:

V, г, =1>,п+^п(ги,-¥,), 1 = 1. .т. (24)

Пропорциональным методом заполняются пропуски, обусловленные тем, что объекты сравнивались не всеми экспертами. В соответствие с параметром доверия данным ^б[0,1] увеличиваются значения элементов суммарных матриц. Этот параметр равен 0, если результаты парных сравнений случайны (результаты сравнений объектов попарно независимы) и равен единице при транзитивных

экспертных оценках. Например:

+ (25)

Если в суммарной матрице отношений много пропусков, то известные методы, как правило, приводят к ошибочным итоговым ранжированиям. Предлагаемый метод зависимостей предназначен для транзитивных данных для заполнения пропусков, обусловленных тем, что объекты ни разу не сравнивались между собой. Идея метода состоит в следующем. В грйфе, соответствующем суммарной матрице отношений ||Л^||Ихт (например, рисунок 3), производится поиск всех путей между всеми парами несмежных вершин. Для каждого пути согласно некоторой функции рассчитываются веса— число голосов "за" и "против" того, что один объект предпочтительней другого. Если найден хотя бы один путь между несмежными вершинами и сумма полученных весов отлична от нуля, то получено новое ребро. Если некоторые ребра получить не удалось, можно повторно воспользоваться алгоритмом, используя вновь полученные ребра. Если число вершин и отсутствующих ребер велико, то длину пути следует ограничить (например, путь составляет только два ребра). Предлагаются формулы расчета весов и соответствующий алгоритм вычислений.

Рисунок 3 — Граф суммарной матрицы отношений (ребро ас и соответствующие ему элементы матрицы получены методом зависимостей)

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

Для предварительной обработки данных в диссертации предложены:

■ коэффициенты для определения числа пропусков и степени согласованности данных;

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

■ определение весов ранжирований на основе наборов ответов экспертов и соответствующих им результирующих ранжирований.

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

Выделение ядер с

высокой согласованностью

Рисунок 4 — Выбор методов получения результирующего ранжирования

процесс выбора методов получения результирующего ранжирования для решения практической задачи. Широкими линиями показаны требования и настройки, вводимые ЛПР. Тонкие линии — автоматические действия системы. На выбор методов также влияет число объектов Если объектов больше 12, то вместо методов, отмеченных символом '*', применяются аналогичные свертки рангов. Жирным шрифтом отмечены методы, разработанные в диссертации. На рисунке 5 представлен процесс выбора методов для случая неполных парных сравнений.

Рисунок 5 — Выбор методов для неполных парных сравнений

Разработанная диалоговая процедура поиска итогового ранжирования включает следующие функции.

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

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

■ Формирование множества Парето на множестве исходных данных или на множестве результирующих ранжирований, рассчитанных различными методами.

■ Фиксирование рангов. Если ЛПР зафиксировал г -й объект на /' -м месте (г' =}), то г -й объект исключается из исходных данных, но в итоговом ранжировании остается на j -м месте.

■ Фиксирование отношений. ЛПР (с помощью матрицы множества Парето) указывает отношение между / -м и ] -м объектами, затем изменяются суммарные матрицы отношений, что повышает согласованность данных.

■ Повторный расчет результирующих ранжирований и множества Парето с учетом предпочтений ЛПР как для исходных данных, так и для множества результирующих ранжирований.

В разделе приводится определение множества Парето для ранжирований. Предложено представлять множество Парето в виде одной матрицы, что позволяет использовать множество Парето в диалоговой процедуре поиска результирующего ранжирования. Разработан эффективный алгоритм формирования такой матрицы. На рисунке 6 представлен пример построения множества Парето для четырех исходных ранжирований Знак ">" на пересечении строки а и столбца Ь означает, что все эксперты считают объект а предпочтительней объекта Ь. Знак "о" на пересечении строки Ь и столбца с означает, что часть экспертов считают объект Ъ предпочтительней объекта с, часть экспертов — наоборот.

(а, е, Ь, с, (!) (а, с, е, Ъ, ф

(а, е, Ь, 6, с) (а, с), с, е, Ь)

а) Исходные ранжирования

а Ь с й е

а * > > > >

Ь < * о о <

с < о * о о

й < о о * о

е < > о о *

б) Матрица множества Парето

(а, е, Ъ, с, (1) (а, с, е, Ь, сГ)

(а, е, Ъ, <1, с) (а, д., е, Ь, с)

(а, е, с, Ъ, Л) (а, с, е, (1, Ь)

{а, е, <1, Ъ, с) (а, й, е, с, Ь)

(а, е, с, с1, Ь) (а, с, ¡1, е, Ь)

(а, е, с1, с, Ь) (а, й, с, е, Ь)

в) Возможные оптимальные ранжирования (выделено результирующее ранжирование) Рисунок 6 — Множество Парето для ранжирований

Анализ решений основан на:

■ оценке достоверности решения;

* сравнении получаемых решений с помощью частотной гистограммы расстояний; вычислении расстояний до других решений.

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

Также поддерживается оценка результатов тестирования и поиск оптимального распределения ресурсов.

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

Выполнена постановка задачи о назначениях, в которой каждая должность и каждый претендент на эти должности имеют собственные характеристики —

ранжирования. Предложен и реализован подход сведения этой задачи к классической задачи о назначениях с помощью меры близости на отношениях. Задача наглядно представляется двудольным неориентированным графом Г = (Х" и^'/) (рисунок 7), где X" и Хь —независимые множества вершин и для каждого ребра у,, = (*,,*,) е У имеет место х, е X", х, е Хь. Каждой вершине х, е X" сопоставлено ранжирование а, е А и каждой вершине х, е Хь сопоставлено ранжирование Ь, е В . Ребро у,, = (х,,х,) присутствует в графе Г в том случае, если 1-й претендент претендует на у-ю должность. Решением будет некоторое паросочетание (например, выделенные ребра).

Претенденты "программирование"" "математика" "английский"

"математика" "программирование' "английский"

"английский" "программирование' "математика"

математика "английский" "программирование'

Рисунок 7 — Пример задачи о назначениях

Должности 'программирование'7, "математика" "английский"

"английский" программирование" "математика"

"математика" 'программирование" "английский"

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

1. Анализ эффективности коэффициентов согласованности и методов поиска результирующего ранжирования (таблица 1). Начальные данные представляют

Таблица 1 — Тестирование методов и коэффициентов

Объектов— 5

Ранжирований — 500

Испытаний—1000

Максимально возможное расстояние между ранжированиями—20

г ч П Стат хар-ки Методы Коэффициенты согласованности данных

и М1/ М2/ мз/ М4/ К4/ К1/ К1/ К1/ К1/ К1/ К2/ К2/ К2/ К2/ К2/ КЗ/ КЗ/ КЗ/ КЗ/ КЗ/

К4 К4 К4 К4 СР М1 М2 МЗ М4 К4 М1 М2 МЗ М4 К4 М1 М2 МЗ М4 К4

95 0 0 Ср 3 71 2 53 2 32 0 86 1 94 0 06 0 12 0 01

Ср кв 2 69 3 00 3 05 2 63 1 82 0 01 0 19

Корр 0 75 0 67 0.67 0 34 0 73 -07 -0 5 -0.4 -0 2 -0.4 04 04 04 05 04 -05 -03-03 -0 1 -0 4

Н ср 0.19 0 13 0 12 0.04 0.10

0 4 3 Ср Ср кв 0 11 0 44 0.00 0 00 0 05 0 32 2 30 1 77 0 06 0 23 0 22 0 02 0.00 0 00 0 05 0 01

Корр 0 95 0 00 0 66 0 11 0 42 -0 0 -0 0 -0 0 00 -0 1 0303030301 -0 0 -0 0 -00 00 00

Н ср 001 0 00 000 0 11 0 00

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

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

3. Пример решения задачи о назначениях для 1000 претендентов на 500 должностей, размерность ранжирований — 15.

4. Тестирование студентов для проверки владения понятийным аппаратом предмета "Общая психология" (совместно со специалистами Института информатизации социальных систем КГТУ). Студентам предоставляется набор терминов изучаемой дисциплины. Им необходимо выполнить следующие задания.

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

■ Разбить набор терминов на произвольные группы. В каждой группе должны содержаться термины, близкие по смыслу.

■ Разбить, как и во 2-м задании, набор терминов на группы. При этом указывается, сколько должно получиться групп и по сколько должно быть терминов в каждой группе).

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

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

Заключение

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

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

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

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

Разработаны новые методы и алгоритмы: "модифицированный метод большинства", метод минимального несогласия, "модификация метода ELECTRE", k-медиана и мультипликативная свертка критериев качества, метод преобразования рангов, а также для неполный парных сравнений — линейная модель, пропорциональный метод, методы зависимостей и пополнения матриц.

Модифицированы алгоритмы для квантильного метода, вычисления медианы Кемени, правила k-большинства, Борда, Копленда.

Алгоритмизированы известные методы Цермело-Бредли-Тири, Леонардо, Девидсона, Чеботарева, Блэка, турнирные показатели, рассмотрены особенности применения среднегеометрического строчных элементов и соотношения левого и правого собственных векторов с целью программной реализации в рамках созданной подсистемы "Обработка информации в порядковых шкалах". Для ряда из них предложены способы выбора незаданных коэффициентов.

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

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

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

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

н^ 2 4 5 8

шкалах" позволяет находить результ решении прикладных задач из раз вспомогательные задачи обработки инструментом для дальнейших исследоЕ

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

Публикации автора ________________

1. Даничев, А. А. Задача о назначениях в порядковых шкалах для системы поддержки принятия решений / М. А. Воловик, А. А. Даничев // Информатика и системы управления : межвуз. сб. науч. тр. / Отв. редактор С. А. Бронов. — Вып. 7. — Красноярск: ГУ НИИ информатики и процессов управления, 2002. — С. 334—339.

2. Даничев, А. А. Программная система поддержки принятия решений: обработка информации в порядковых шкалах / М. А. Воловик, А. М. Даничев, А. А. Даничев // Бюллетень "САО/САМ/САЕ/САЬБ. — Красноярск: КГТУ, научно образовательный центр интегрированных компьютерных технологий, 2004. — С. 32—46.

3. Даничев, А. А. Алгоритм формирования множества Парето для ранжирований / А. А. Даничев // Информатика и системы управления : межвуз. сб. науч. тр. / Отв. редактор С. А. Бронов.— Вып. 10.— Красноярск: ГУ НИИ информатики и процессов управления, 2004. — С. 220—224.

4. Даничев, А. А. Метод минимального несогласия / А. А. Даничев П Информатика и системы управления : межвуз. сб. науч. тр. / Отв. редактор С. А. Бронов. — Вып. 10. — Красноярск: ГУ НИИ информатики и процессов управления, 2004. — С. 225—232.

5. Даничев, А. А. Система поддержки принятия решений "Обработка информации в порядковых шкалах" Е88/31Ф : Свидетельство об отраслевой регистрации разработки №5652 / М. А. Воловик, А. А. Даничев // Отраслевой фонд алгоритмов и программ, 2005. — 17 с.

Даничев Алексей Александрович Методы и алгоритмы обработки данных в порядковых шкалах для систем поддержки принятия решений. Автореф. дисс. на соискание учёной степени кандидата тех. наук. Подписано в печать 14.14.2005. Заказ № 6/Д, Формат 60x90/16. Усл. печ. л. 1. Тираж 100 экз. Отпечатано в ИПЦ КГТУ 660074, Красноярск, ул. Киренского, 28

РНБ Русский фонд

2006-4 20355

Введение.

1 Проблематика обработки данных в порядковых шкалах для систем поддержки принятия решений.

1.1 Общее состояние.

1.2 Основные понятия.

1.2.1 Основные понятия о структурировании множества объектов.

1.2.2 Отношения и представления отношений. 1.2.3 Меры близости на отношениях.

1.2.4 Коллективные решения, результирующее ранжирование.

1.2.5 Аксиомы Эрроу.

1.3 Научная проблема.

1.4 Постановка задач исследований.

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

2.1 Исходные данные

2.1.1 Суммарные матрицы отношений.

2.1.2 Матрица весов.

2.2 Методы, использующие меру близости на отношениях.

2.2.1 Медиана Кемени.

2.2.2 Тривиальные методы нахождения Медианы Кемени.

2.2.3 Эвристический алгоритм.

2.2.4 Полный перебор строгих ранжирований.

2.2.5 К-медиана.

2.2.6 Мультипликативная свертка.

2.3 Метод минимального несогласия.

2.3.1 Метод минимального несогласия для векторов предпочтений.

2.3.2 Меры близости на отношениях порядка.

2.3.3 Метод минимального несогласия.

2.3.4 Вычисление элемента матрицы потерь.

2.3.5 Случай нестрогих ранжирований.

2.4 Свертки рангов.i.

2.4.1 Линейная свертка рангов.

2.4.2 Оценка достоверности ответа.

2.4.3 Мультипликативная свертка рангов.

2.5 Методы, использующие матрицу весов. г. 2.5.1 Модифицированный метод большинства.

2.5.2 Правило большинства.

2.5.2.1 Алгоритм 1. л ' 2.5.2.2 Алгоритм 2.

2.5.2.3 Алгоритм 3.

2.5.3 Метод Коплен да.

2.5.4 Правило Блэка.

2.5.5 Квантильный метод.

2.6 Преобразование рангов.

2.7 Спортивный турнир.

2.8 Собственные вектора.

2.9 Метод ELECTRE .'.

2.10 Получение ранжирования из матрицы отношений.

2.11 Выводы.

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

3.1 Общее состояние.

3.2 Модель Цермело-Бредли-Тири.

3.3 Модель Леонардо.

3.4 Модель Девидсона.

3.5 Обобщение метода строчных сумм.

3.6 Линейная модель.

3.7 Коррекция итоговых весов объектов.

3.8 Пополнение матриц.

3.9 Пропорциональный метод.

3.10 Метод зависимостей.

3.11 Выводы.

4 Методы и алгоритмы предварительной обработки данных и анализа решений.

4.1 Предварительная обработка данных.

4.1.1 Согласованность данных.

4.1.2 Разреженность матриц отношений.

4.1.3 Определение значимости ответов.

4.1.4 Статистический анализ рангов.

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

4.2 Анализ решений.,.

4.2.1 Построение частотных гистограмм расстояний до образца.

4.2.2 Чувствительность решения.

4.3 Множество Парето.

4.3.1 Множество Парето для ранжирований.

4.3.2 Алгоритм формирования матрицы множества Парето.

4.4 Диалого-машинная процедура поиска итогового ранжирования.

4.4.1 Выделение наилучших и наихудших объектов.

4.4.2 Выбор методов получения результирующего ранжирования.

4.5 Оценки данных анкетирования.

4.5.1 Классы эквивалентностей.

4.5.2 Алгоритм вычисления максимально возможного расстояния до фиксированной группировки.

4.6 Задача о назначениях в порядковых шкалах.

4.7 Выводы.

5 Программная реализация и примеры практического применения.

5.1 Программная система "Обработка информации в порядковых шкалах".

5.1.1 Общее описание.

5.1.2 Особенности применения.

5.1.3 Настройка системы на предметную область задачи.

5.1.4 Ввод и редактирование исходных данных.

5.1.5 Расчет оптимальных ранжирований и их характеристик.

5.1.6 Тестирование.

5.1.7 Задача о назначениях.

5.2 Практическое применение.

5.2.1 Анализ эффективности коэффициентов согласованности и методов поиска результирующего ранжирования.

5.2.2 Рейтинг крупнейших банков России.

5.2.3 Задача о назначениях.

5.2.4 Тестирование студентов.

5.3 Выводы.

Актуальность. Управление организациями в условиях функционирования систем менеджмента качества (СМК) возможно только на базе систем поддержки принятия решений (СППР) как инструмента использования информационных технологий. В сложных организационно-технических системах информация представлена как в количественных, так и в порядковых шкалах. Порядковая шкала позволяет устанавливать соотношения равенства, неравенства и последовательности между уровнями при отсутствии точки отсчета и расстояния между ними. Такие шкалы — естественный инструмент получения экспертных данных. Ранжирование объектов на основе экспертной информации играет важную роль для принятия решений в вопросах экономики, управления, политики, здравоохранения, спорта, образования и в других областях [1-6]. Так же упорядочивание объектов по предпочтению используется в ряде методов многокритериальной оптимизации [7I

11]. В СППР может быть много компонентов накопления и обработки разнородной информации (формирование баз данных, оптимизация, статистическая обработка количественной информации и др.). В результате с помощью СППР формируется набор допустимых решений. Предложенные решения необходимо представить в виде упорядоченной последовательности (ранжирования) для выбора окончательных вариантов. Поэтому важнейшими компонентами СППР являются подсистемы обработки информации в порядковых шкалах. Такая обработка данных необходима как на нижних уровнях СППР (обработка первичной информации), так и на верхних — для принятия окончательных решений. Таким образом, математическое и алгоритмическое обеспечение СППР обязательно включает методы и алгоритмы обработки информации в порядковых шкалах. Сравнение в порядковых шкапах выполняется с помощью бинарных (или /¡-арных) отношений, обладающих некоторыми специальными свойствами (отношения порядка). В данной работе рассматриваются ранжирования (отношения линейного и частичного порядка) и классы эквивалентностей.

Для обработки качественной информации используются функции предпочтений пользователя, математическое программирование в порядковых шкалах, специальные методы для особых типов данных. В настоящее время методы и алгоритмы обработки информации в порядковых шкалах недостаточно проработаны для включения их в математическое обеспечение СППР, что затрудняет создание соответствующих программных компонент. Проблемам обработки информации в порядковых шкалах и методам получения результирующего ранжирования посвящены работы зарубежных ученых (Р. Л. Кини, X. Райфа, Р. Р. Девидсона, Д. Блэка), а также работы В. В. Подиновского, Б. Г. Литвака, Д. Б. Юдина и др. [12-41]. Общие вопросы обработки экспертной информации и поддержки принятия решений освещены в работах [42-53], [54-65] и [66-72]. Одна из основных задач обработки данных в порядковых шкалах — получение результирующего ранжирования (задача группового выбора), для решения которой известно более десятка методов [1, 2, 9, 18, 20, 72]. При высокой согласованности данных все методы, как правило, приводят к одинаковым результатам. На практике, когда согласованность данных невысока, применение известных методов дает противоречивые результаты, что затрудняет использование их в СППР. Необходима более глубокая теоретическая переработка существующей совокупности методов, рассмотрение их с единых позиций, представление в виде комплекса методов с возможностью их сравнения по выработанным критериям.

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

Объектом исследований в диссертации является система поддержки принятия реI шений для задач, в которых часть данных представлена в порядковых шкалах.

Предметом исследований являются методы, модели и алгоритмы обработки данных в порядковых шкалах.

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

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

Для достижения поставленной цели в диссертации поставлены и решены следующие задачи:

1) классификация исходных данных для выбора алгоритмов их предварительной обработки и методов получения результирующих ранжирований;

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

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

4) разработка диалоговых процедур для управления процессом обработки данных в порядковых шкалах;

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

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

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

Основные результаты:

1. На основе анализа существующих методов получения результирующего ранжирования выполнена унификация их математического описания, обоснованы рекомендации по их применению и выполнена их модификация в части реализующих их алгоритмов, а также вновь разработаны и алгоритмизированы методы для специальных типов данных (модифицированный метод большинства, метод минимального несогласия, модификация метода ELECTRE, k-медйана и мультипликативная свертка критериев качества, метод преобразования рангов, а также для неполный парных сравнений— линейная модель, пропорциональный метод, методы зависимостей и пополнения матриц). Предложены и обоснованы оценки чувствительности и достоверности решений.

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

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

4. Предложена и реализована процедура оценивания в порядковых шкалах результатов тестирования в форме ранжирований объектов или разделения объектов на классы эк-вивалентностей.

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

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

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

Научная новизна пЬлученных результатов.

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

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

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

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

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

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

Результаты диссертации использованы в системе менеджмента качества подготовки специалистов Красноярского государственного технического университета (КГТУ) и в региональной системе управления качеством медицинской помощи на территории Красноярского края, что подтверждено соответствующими актами.

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

Результаты диссертации были апробированы на Всероссийской научно-методической конференции в 2004 году [73] (Даничев, А. А. Обработка экспертной информации в порядковых шкалах / М. А. Воловик, А. А. Даничев // Материалы Всероссийской научно-методической конференции 24-26 марта 2004. — Совершенствование системы управления качеством подготовки специалистов. — Красноярск: ИПЦ КГТУ), а так же на семинарах кафедр САУП и САПР КГТУ.

Публикации по материалам диссертации включают 5 работ, из них: 4 — статьи в сборниках научных работ [74-77]; 1 — программа для электронных вычислительных машин, зарегистрированная в "Национальном информационном фонде неопубликованных документов" [78].

Общая характеристика диссертации. Диссертация состоит из 5 разделов, содержит основной текст на 130 с., 29 иллюстраций, 23 таблицы, список использованных источников из 103 наименований. I 9

5.3 Выводы

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

Рассмотренные примеры иллюстрируют работоспособность и многофункциональность системы. I

Заключение

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

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

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

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

Разработаны новые методы и алгоритмы: "модифицированный метод большинства", метод минимального несогласия, "модификация метода ELECTRE", k-медиана и мультипликативная свертка критериев качества, метод преобразования рангов, а также для неполный парных сравнений — линейная модель, пропорциональный метод, методы зависимостей и пополнения матриц.

Модифицированы алгоритмы для квантильного метода, вычисления медианы Кеме-ни, правила k-болыпинства, Борда.

Алгоритмизированы известные методы Цермело-Бредли-Тири, Леонардо, Девидсо-на, Чеботарева, Копленда, Блэка, турнирные показатели, рассмотрены особенности применения среднегеометрического строчных элементов и соотношения левого и правого собственных векторов с целью программной реализации в рамках созданной подсистемы "Обработка информации в порядковых шкалах". Для ряда из них предложены способы выбора незаданных коэффициентов.

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

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

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

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

Разработанные методы и алгоритмы успешно опробованы при выполнении научно» исследовательских работ в региональной системе управления качеством медицинской помощи на территории Красноярского края и в системе менеджмента качества подготовки специалистов КГТУ.

1. Жилин, Б. Б. Экспертные оценки в социологических исследованиях / Б. Б. Жилин, С. Б. Крымский, В. И. Паниотто и др.; (отв. ред. С. Б. Крымский). — Киев: Наукова думка, 1990. —320 с.

2. Литвак, Б. Г. Экспертная информация: методы получения и анализа/ Б. Г. Лит-вак. — М.: Радио и связь, 1982. — 255 с.

3. Миркин, Б. Г. Проблема группового выбора / Б. Г. Миркин. — М.: Наука, 1974. —256 с.

4. Клигер, С. А. Шкалирование при сборе и анализе социологической информации / С. А. Клигер, М. С. Косолапов, Ю. Н. Толстова. — М.: Наука, 1978.

5. Леванков, В. А. Математические методы моделирования процессов управления в социальной сфере / В. А. Леванков, Ю. Д. Максимов, М. Ф. Романов, А. В. Ястребов. — СПб.: Нестор, 1999. — 174 с.

6. Колядюк, Р. Интервью представителей целевой аудитории с использованием априорного ранжирования факторов / Р. Колядюк. — Киев: Энран Акрос, 1998.

7. Подиновский, В. В. Оптимизация по последовательно применяемым критериям /

8. B. В. Подиновский, В. М. Гаврилов. — М.: Сов. радио, 1975.

9. Гафт, М. Г. О построении решающих правил в задачах принятия решений. / М. Г. Гафт, В. В. Подиновский // Автоматика и телемеханика. — 1981. — №6.

10. Анохин, А. М. Методы определения коэффициентов важности критериев / А. М. Анохин, В. А. Глотов, В. В. Павельев, А. М. Черкашин // Автоматика и телемеханика. — 1997, —№8, —С. 3—35.

11. Машунин, Ю. К. Методы и модели векторной оптимизации / Ю. К. Машунин. — М.: Наука, 1986. — 142 с.

12. Семенкин, Е. С. Оптимизация технических систем: Учеб. пособие / Е. С. Семен-кин, О. Э. Семенкина, С. П. Коробейников. — Красноярск: СИБУП, 1996. — 284 с.

13. Кини, Р. Л. Принятие решений при многих критериях: предпочтения и замещения / Р. Л. Кини, X. Райфц. — М.: Радио и связь, 1981. — 560 с.

14. Тюрин, 10. Н. Статистические модели ранжирования / Ю. Н. Тюрин, А. П. Васильевич, П. Ф. Андрукович // Статистические методы анализа экспертных оценок. Уч. зап. по статистике. — Т. 29. — М.: Наука, 1977.

15. Шрейдер, Ю. А. Равенство, сходство, порядок/ Ю. А. Шрейдер.— М.: Наука,1971.

16. Юдин, Д. Б. Отношение Канторовича и задачи обобщенного матеметического программирования/ Д. Б. Юдин, Э. В. Цой// Экономика и мат. методы.— 1989.— Т. XXVI. — Вып. 5. — С. 885—889.

17. Юдин, Д. Б. Отношение Канторовича и задачи обобщенного матеметического программирования / Д. Б. Юдин, Э. В. Цой // Техническая кибернетика. — 1987. — №1. —1. C. 25—37.

18. Юдин, Д. Б. Вычислительные методы теории принятия решений / Д. Б. Юдин. — М.: Радио и связь, 1989. — 304 с.I

19. Руа, Б. Классификация и выбор при наличии нескольких критериев (метод е1екЦ-а)/ Б. Руа// Вопросы анализа и процедуры принятия решений/ Под редакцией И. Ф. Шахнова. — М.: Мир, 1976. — С. 20—58.

20. Тюрин, Ю. H. К проблеме обработки рядов ранжировок / Ю. Н. Тюрин, А. П. Васильевич // Статистические методы анализа экспертных оценок. Уч. зап. по статистике. — Т. 29. —М.: Наука, 1977.

21. Чеботарев, П. Ю. Обобщение метода строчной сумм для неполных парных сравнений / Чеботарев П. Ю. // Автоматика и телемеханика. — 1989. — №8. — С. 125—137.

22. Шмерлинг, Д. С. Экспертные оценки. Методы и применение / Д. С. Шмерлинг, С. А. Дубровский, Т. Д. А'ржанова, А. А. Френкель // Статистические методы анализа экспертных оценок. Уч. зап. по статистике. — Т. 29. — М.: Наука, 1977. — С. 290—382.

23. Дубровский, С. А. Об одном подходе к задаче скаляризации векторных кривых / С. А. Дубровский // Статистические методы анализа экспертных оценок. Уч. зап. по статистике. — Т. 29. — М.: Наука, 1977.

24. Подиновский, В. В. Задача оценивания коэффициентов важности как симметрически-лексикографическая задача оптимизации / Подиновский В. В. // Автоматика и телемеханика. — 2003. — №3. — С. 150—162.

25. Березовский, Б. А. Бинарные отношения в многокритериальной оптимизации / Б. А. Березовский, В. И. Борзенко, JI. М. Кемпнер. — М.: Наука, 1981.

26. Ушаков, И. А. Задача о выборе предпочтительного объекта / И. А. Ушаков // Техническая кибернетика. — 1971. — №4. — С. 3—7.

27. Гольдштейн, Г. Я Инновационный менеджмент / Г. Я. Гольдштейн. — Таганрог: Изд-воТРТУ, 1998. ,

28. Подиновский, В. В. Количественная важность критериев / Подиновский, В. В. // Автоматика и телемеханика. — 2000. — №5.

29. Ларичев, О. И. Наука и искусство принятия решений / О. И. Ларичев. — М.: Наука, 1979.

30. Ларичев, О. И. Объективные модели и субъективные решения / О. И. Ларичев. — М.: Наука. 1987.

31. Микрин, Б. Г. Группировки в социально экономических исследованиях методы построения анализа / Б. Г. Микрин. — М.: Финансы и статистика, 1985. — 223 с.

32. Панкова, Л. А. Организация Экспертизы и анализ экспертной информации / Л. А. Панкова, А. М. Петровский, М. В. Шнейдерман. — М.: Наука, 1984.

33. Ларичев, О. И Теория и методы принятия решений, а также Хроника событий в Волшебных Странах: Учебник. Изд. Второе, перераб. И доп / О. И. Ларичев. — М.: Логос, 2003. ,

34. Ларичев, О. И. Многокритериальные методы принятия решений / C.B. Емельянов, О. И. Ларичев. — М.: Знание, 1985.

35. Литвак, Б. Г. Экспертные оценки и принятие решений / Б. Г. Литвак. — М.: Патент, 1996. —271 с.

36. Литвак, Б. Г. Разработка управленческого решения: уч. для вузов/ Б. Г. Литвак. — М.: Дело, 2004. — 392 с.

37. Емельянов, С. В. Подход к формализированному синтезу структур систем бинарного вида / С. В. Емельянов. — М.: МНИПУ, 1987.

38. Вертинская, Н. Д. Математическое моделирование многофакторных и многопараметрических процессов / Н. Д. Вертинская. — Иркутск: Изд-во ИрГТУ, 2001. —286 с.

39. Жуковский, В. И. Многокритериальное принятие решений в условиях неопределенности. / В. И. Жуковский, В. С. Молоствов. — М.: МНИИПУ, 1988.

40. Батыщев, Д. И. Многокритериальный выбор с учетом индивидуальных предпочтений / Д. И. Батыщев, Д. Е. Шапошников. — РАН, Ин-т прикл. физики, 1994.

41. Айзерман, М. А. Проблемы логического обоснования в общей теории выбора вариантов / М. А. Айзерман, А. В. Малишевский. —М.: Ин-т пробл. упр., 1982.

42. Алескеров, Ф. Т. Интервальный выбор и его разложение / Алескеров Ф. Т. // Автоматика и телемеханика. — 1980. — №6. — С. 129—134.

43. Борисов, В. И. Проблемы векторной оптимизации / В. И. Борисов // сб. исследование операций / Отв. ред. А. А. Ляпунов. — М.: Наука, 1972.

44. Венцель, Е. С. Исследование операций: задачи, принципы, методология/ Е. С. Венцель. — М.: Наука, 1980.

45. Гафт, М. Г. Принятие решений при многих критериях / М. Г. Гафт.— М.: Знание, 1979.

46. Глотов, В. А. Координатно-модульные отношения / Глотов В. А. // Автоматика и телемеханика, 1984.—№2.

47. Моисеев, Н. Н. К/1етоды оптимизации / Н. Н. Моисеев, Ю. П. Иванилов, Е. М. Столярова. — М.: Наука, 1978.

48. Хоменюк, В. В. Элементы теории многоцелевой оптимизации / В. В. Хоме-нюк. — М.: Наука, 1983.

49. Елтаренко, Е. А. Решение многокритериальных задач при совершенствовании информационных систем / Е. А. Елтаренко. — Ин-т информэлектро. — 1982. — 48 с.

50. Макаров, И., М. Теория выбора и принятия решений / Т. М. Виноградская, И. М. Макаров, В. Б. Соколов. — М.: Наука, 1982. — 328 с.

51. Мамиконов, А., Г. Принятие решений и информация / А. Г. Мамиконов. — Москва, 1983.

52. Шипунов,В. Г. Основы управленческой деятельности/ В. Г. Шипунов, Е. Н. Кишкель. — М.: Высшая школа, 2000.

53. Льюс, Р. Игры и решения / Р. Льюс, X. Райфа. — М.: Иностр. лит-ра, 1961.

54. Белкин, А. Р. Принятие решений: комбинаторные модели аппроксимации информации / А. Р. Белкин, М. Ш. Левин. — М.: Наука, 1990.

55. Зайченко, Ю. П. Исследование операций: нечеткая оптимизация / Ю. П. Зайчен-ко. — Учебное пособие. — Киев: Высш. шк., 1991.

56. Коршунов, Ю. М. Математические основы кибернетики / Ю. М. Коршунов. — Учебное пособие. — М.: Энергия, 1987.

57. Кудрявцев, Е. М. Исследование операций в задачах, алгоритмах и программах/ Е. М. Кудрявцев. — М.: Радио и связь, 1984.

58. Макаров, Ч. M. Теория выбора и принятия решений / Ч. М. Макаров и др. — Учебное пособие. — М.: Наука, 1982.

59. Мелихов, А. Н. Ситуационные советующие системы с нечеткой логикой. / Л. С. Берштейн, С. Я. Коровин, А. Н. Мелихов. — М.: Наука, 1990.

60. Мушик, Э. Методы принятия технических решений / Э. Мушик, П. Мюллер. — Пер. с нем. — М.: Мир, 1990.

61. Орловский, С. А. Проблемы принятия решений при нечетких исходных данных / С. А. Орловский. — М.: Наука, 1981. — 206 с.

62. Розен, В. В. Цель, оптимальность, решение. Математические модели принятия оптимальных решений. / В. В. Розен. — М.: Радио и связь, 1982.

63. Taxa, X. Введение в исследование операций (2 тома) / X. Taxa. — M.: Мир, 1985.

64. Нэш, Жд. Бескоалиционные игры / Жд. Нэш // Сб. переводов / Под ред. H. Н. Воробьева. — Матричные игры. — М.: Физматгиз, 1961. — С. 205—221.

65. Губанов, В. А. Введение в системный анализ / В. А. Губанов, В. В. Захаров, А. Н. Коваленко. — Л.: ЛГУ, 1988.

66. Кендэл, М. Ранговые корреляции / М. Кендэл; пер. с англ. Е. М. Четыркина и Р. М. Энтова. — М.: Статистика, 1975.

67. Левина, Н. Б. Об условиях применения средних взвешенных показателей при оптимизации систем / Н. Б. Левина, И. Б. Погожев // Исследование систем: сб. ст. / Гл. ред. Е. В. Золотов. — Вып. 1. — Хабаровск: Дальневосточный ВЦ АН СССР, 1973.

68. Орлов, А. И. Сертификация и статистические методы / А. И. Орлов // Заводская лаборатория. —Т. 63.— 1997. —№3. —С. 55—62.

69. Орлов, А. И. Современная прикладная статистика / А. И. Орлов // Заводская лаборатория. — Т. 64. — 1998. — №3. — С. 52—60.

70. Подиновский, В. В. Парето-оптимальные решения многокритериальных задач/ В. В. Подиновский, В. Д. Ногин. — М.: Наука, 1982.

71. Катулев, А. Н. Математические методы в системах поддержки принятия решений: Учеб. пособие / А. Н.' Катулев, Н. А. Северцев. — М.: Высш. Шк., 1980. — 311 с.

72. Даничев, А. А. Метод минимального несогласия /А. А. Даничев // Информатика и системы управления: межвуз. сб. науч. тр. / Отв. редактор С. А. Бронов.— Вып. 10.— Красноярск: ГУ НИИ информатики и процессов управления, 2004. — С. 225—232.

73. Даничев, А. А. Система поддержки принятия решений "Обработка информации в порядковых шкалах" ESS/3RD : Свидетельство об отраслевой регистрации разработки №5652 / М. А. Воловик, А. А. Даничев // Отраслевой фонд алгоритмов и программ, 2005.— 17 с. '

74. Трахтенгерц, Э. А. Компьютерная поддержка принятия решений: Научно- практичное издание. Серия "Информатизация России на пороге XXI века" / Э. А. Трахтенгерц. — М.: СИНТЕГ, 1998.

75. Гаврилова, Т. А. Базы знаний интеллектуальных систем / Т. А. Гаврилова, В. Ф. Хорошевский. — СПб.: Питер, 2000. — 384 с.

76. Глухов, В. В. Теория автоматического управления: основы теории и элементы. Ч. 1 / В. В. Глухов. — Москва, 1991. — 68 с.

77. Евланов, JI. Г. Основы теории принятия решений / JI. Г. Евланов. — Академия народного хозяйства при СМ СССР. — М.: Экономика, 1981. — 212 с.

78. Михалевич, В. С. Вычислительные методы исследования и проектирования сложных систем. / В. С. Михалевич, В. Я. Волкович. — М.: Наука, 1982.

79. Перегудов, Ф. И. Основы системного анализа / Ф. И. Перегудов, Ф. П. Тарасен-ко. — Томск, 1997. — 396 с.

80. Попов, Э. В. Экспертные системы: Решение неформализованных задач в диалоге с ЭВМ / Э. В. Попов. — М.: Наука, 1987.

81. Поспелов, Г. С. Искусственный интеллект / Г. С. Поспелов. — М.: Наука, 1988.

82. Хованов, Н. В. Матем. основы теории шкал измерения качества / Н. В. Хова-нов. — Л.: ЛГУ. — 1982. — 185 с.

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

84. Саати, Т. Принятие решений. Метод анализа иерархий. / Т. Саати. — М.: Радио и Связь, 1993.

85. Андрейчиков, А. В. Анализ, синтез, планирование решений в экономике / А. В. Андрейчиков, О. Н. Андрейчикова. — М.: Финансы и статистика, 2002. — 368 с.

86. Бомас, В. В. Применение системы поддержки решений DSS/UTES в задачах мониторинга иерархических структур / В. В. Бомас, В. В. Сурков, Г. Ф. Хахулин, В. А. Судаков // Приборы и системы. Управление, контроль, диагностика. — 2001. — №12. — 9 с.

87. Липский, В. Комбинаторика для программистов / В. Липский. — М.: Мир, 1988. —213 с.

88. Корбут, А. А. Дискретное программирование / А. А. Корбут, Ю. Ю. Финкель-штейн. — М.: Наука, 1969. — 368 с.

89. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. — М.: Мир, 1978. —432 с.

90. Бронштейн, И. Н. Справочник по математике / И. Н. Бронштейн, К. А. Семендя-ев. — М.: Наука, 1980. — 976 с.

91. Бобровский, С. И. Самоучитель программирования на языке С++ в системе Borland С++ Builder 4.0 / С. И. Бобровский. — М.: ООО "ДЕСС", 1999. — 287 с.

92. Теллес, М. Borland С++ Builder: библиотека программиста / М. Теллес. — СПб.: Питер Ком, 1998. —512 с.

93. Дегтярев, Ю. И. Исследование операций / Ю. И. Дегтярев. — М.: Высш. шк. —1986.

94. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део; пер. с англ. Е. П. Липатова; под ред. В. Б. Алексеева. — М.: Мир, 1980.

95. Пападимитриу, X. Комбинаторная оптимизация / X. Пападимитриу, К. Стайг-лиц. — М.: Мир, 1985. — 512 с.

96. Глухов, В. В. Математические модели для менеджмента/ В. В. Глухов, М. Д. Медников, С. Б. Коробко. — СПб.: Лань, 2000. — 480 с.