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

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

005011207

МИРОНОВА Мария Сергеевна

МОДЕЛИРОВАНИЕ ПРОЦЕДУР КОЛЛЕКТИВНОГО ВЫБОРА НА ОСНОВЕ ЭКСТРАПОЛЯЦИИ ЭКСПЕРТНЫХ ОЦЕНОК

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание степени кандидата физико-математических наук

Воронеж-2011

005011207

Работа выполнена на кафедре информационных технологий моделирования и управления Воронежского государственного университета инженерных технологий.

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

доцент

Бугаев Юрий Владимирович (Воронежский государственный университет инженерных технологий)

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

профессор

Меньших Валерий Владимирович

(Воронежский институт МВД России)

кандидат физико-математических наук Каплиева Наталья Алексеевна (Воронежский государственный университет)

Ведущая организация: Тамбовский государственный технический университет

Защита состоится «22» декабря 2011 г. в 13 час. 30 мин. на заседании диссертационного совета Д 212.035.02 в ФГБОУ ВПО «Воронежский государственный университет инженерных технологий» по адресу: 394036, г. Воронеж, проспект Революции, д. 19, конференц-зал.

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

С диссертацией можно ознакомиться в библиотеке ВГУИТ. Автореферат разослан «22» ноября 2011 г. Автореферат размещен на официальном сайте Минобрнауки РФ http://wwvv.mon.gov.ru и ВГУИТ http://www.vgta.vrn.ru «21» ноября 2011 г.

Ученый секретарь

диссертационного совета * ' к.т.н., доц. И.А. Хаустов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Проблема выбора имеет место во всех сферах человеческой деятельности. В условиях растущей сложности производственных систем и управленческих процессов часто встречается ситуация, когда множество альтернативных решений имеет большую мощность для того, чтобы специалист смог непосредственно оценить и сравнить альтернативы между собой. Разработка и исследование процедур выбора на множестве альтернатив, необозримом для лица, принимающего решение, составляет фундаментальную научную проблему, в рамках которой выполнена предлагаемая работа. Решению данной проблемы посвящены исследования П.С. Краснощекова, В.В. Морозова, В.В. Федорова, Ю.А. Белова, C.B. Шафранского.

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

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

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

«Математическое и компьютерное моделирование в задачах проектирования и оптимизации функционирования информационных технологических систем» (ГК № 01.2006.06298), а также в рамках гранта ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 гг.» по теме «Разработка открытых информационных систем перерабатывающих производств» (ГК № П947).

Цель работы - разработка и применение методики и инструментального аппарата для сравнительного анализа процедур коллекгивного выбора, пригодных для использования в методе экстраполяции экспертных оценок (МЭЭО).

Задачи исследования:

1. Проверка процедуры, основанной на ММП (процедуры МЭЭО-ММП), на соответствие характеристическим условиям, принятым для оператора голосования.

2. Исследование характеристических свойств функции коллективного выбора, порождаемой процедурой МЭЭО-ММП.

3. Анализ процедуры МЭЭО-ММП на манипулируемость со стороны организатора голосования и избирателей.

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

5. Разработка комплекса программ, реализующего модели и методы анализа процедур коллективного выбора.

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

Научная новизна работы состоит в следующем.

1. Выявлены новые свойства, которыми обладает процедура МЭЭО-ММП, относящиеся к

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

- удовлетворению порождаемой процедурой функции коллективного выбора свойствам наследования и отбрасывания;

- устойчивости к манипулированию со стороны организатора голосования;

- статистическим свойствам найденного решения: состоятельность, асимптотическая несмещённость.

2. Синтезирована модель для исследования устойчивости процедуры МЭЭО-ММП к манипулированию со стороны избирателей, учитывающая различия вероятностей профилей упорядочения. Её адекватность подтверясдена вычислительными экспериментами.

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

Практическая значимость работы.

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

2. Разработано программное обеспечение, которое можно использовать для осуществления коллективного выбора при решении задач в различных сферах производства. Получено свидетельство о регистрации программы для ЭВМ. Программа прошла апробацию на предприятии ОАО «Кондитерская фабрика «Бело-горье».

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на международных научно-технических конференциях «Информационные и управляющие системы в пищевой и химической промышленности» (г. Воронеж, 2009 г.), «Актуальные проблемы прикладной математики, информатики и механики» (г. Воронеж, 2010 г.) «Математические методы в технике и технологиях - ММТТ-23» (г. Саратов, 2010 г.), «Математические методы в технике и технологиях - ММТТ-24» (г. Киев, 2011 г.); на Всероссийской научной конференции студентов, аспирантов и молодых ученых (г. Воронеж,

2009 г.); на отчетных научных конференциях ВГТА (г. Воронеж, 2009 г., 2010 г.).

Публикации. По теме диссертации опубликовано 11 печатных работ, из них 3 - в изданиях, рекомендованных ВАК РФ, и 1 свидетельство о регистрации программы для ЭВМ.

В работах, опубликованных в соавторстве, личное участие соискателя состоит в следующем: [1,6]- описание ранжирования на порядковой шкале; [2, 7] - разработка численного метода обеспечения условия положительной ненавязанности; [4, 8, 9] -исследование процедуры МЭЭО-ММП на характеристические условия, свойства функции выбора, манипулируемость; [3, 10] -разработка метода анализа и исследование четырех процедур на его основе; [И] - программный модуль реализации процедуры МЭЭО-ММП на порядковой и лингвистической шкале в случае трех альтернатив.

Структура и объём работы. Работа состоит из введения, четырех глав, заключения, списка литературы из 110 наименований и приложений. Основной материал изложен на 102 страницах, содержит 10 рисунков. Объем приложений - 25 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

Сформулированы цель и задачи исследования.

Во второй главе проводится исследование процедуры МЭЭО-ММП согласно наиболее применяемым подходам: проверка оператора голосования на соответствие типовым характеристическим условиям; исследование свойств функции выбора; анализ на манипулируемость.

Для этого были определены аксиомы, касающиеся подхода экстраполяции экспертных оценок.

1. Оцененная экспертом полезность /-й альтернативы - случайная величина = iv/ + s,-t где w, - истинная полезность; е, -случайная ошибка. Все s/ независимы и нормально распределены.

2. Существует такой вектор b коэффициентов функции обобщенного критерия (ФОК), что значение w, определяется значением ФОК: и', = F(x), где F(x) = 2>y/i(x) = bT f{x), fj{x), j =

= 1к - базисные функции; x' - вектор, компоненты которого равны значениям критериев качества альтернативы А/ (векторная оценка альтернативы).

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

4. Каждый эксперт полностью упорядочивает обучающую выборку по отношению «не хуже по полезности»:

(А,В) eRkнехуо:се о ¥к\А) > ]Vk\B), где (А, В) - сравниваемая пара; И/к\») - полезность соответствующей альтернативы с точки зрения к- го эксперта.

Также было введено понятие непараметрического варианта процедуры МЭЭО-ММП, который в отличие от её существующего варианта (назовём его параметрическим случаем) предполагает оценивание полезности w альтернатив без использования ФОК. Данное понятие было введено для более объективной оценки, поскольку в этом случае результаты сравнения процедур

не зависят от векторных оценок альтернатив выборки.

При исследовании оператора голосования на характеристические условия были получены следующие результаты.

1. Показана нейтральность процедуры МЭЭО-ММП по отношению к избирателям и вариантам.

2. Относительно условий положительной ненавязанности и принципа Парето доказаны утверждения 1-3.

3. Приведены контрпримеры, показывающие невыполнение монотонности и принципа Кондорсе.

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

Утверждение 2. Для того чтобы процедура МЭЭО-ММП в параметрическом случае удовлетворяла условию положительной ненавязанности, достаточно, чтобы векторное отображение набора предъявляемых вариантов X в пространство базисных функций / принимало значения из множества V, представляющего собой часть границы выпуклой области.

Утверждение 3. Для непараметрического случая процедуры МЭЭО-ММП справедлив принцип Парето. Иными словами, если во всех индивидуальных упорядочениях альтернатива А ставится на первое место, то она останется лучшей и в коллективном упорядочении.

Анализ процедуры на основе исследования функции коллективного выбора, привел к получению утверждений 4 и 5.

Утверждение 4. Область пространства функций выбора, порождённая отношением нестрогого слабого порядка, замкнута относительно процедуры МЭЭО-ММП.

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

При анализе процедуры МЭЭО-ММП на манипулируе-моеть на основании утверждения 5 был сделан вывод о защищенности данной процедуры от манипулирования со стороны организатора голосования.

Известные подходы к анализу проблемы манипулируемости

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

Вариант г упорядочения задаётся структуоной матрицей

Л?)

С , каждая строка которой содержит два ненулевых элемента, равные I и -1 в столбцах, соответствующих порядковым номерам лучшей и худшей альтернативе в паре. Пусть векторные оценки альтернатив выборки в пространстве базисных функций заданы строками матрицы 2 и Ъ* ~ вектор найденных оценок коэффициентов ФОК. Согласно вектору Ь* оценки нолезностей будут иметь некоторую упорядоченность, структурную матрицу' которой обозначим С. Тогда степень устойчивости предпочтения в паре А/С1 > А^ оценим величиной

/, (сгь*),г <к>

= • 100%, где = у-, к - номер пары; (С 2) - к-я

|рГН|

строка матрицы С2, ах- решение задачи линейного программирования (ЗЛП): х —> шах при ограничениях:

С>у>т-|(С)<А>|;

' т

5>г =1; щ > О,

Ь=1

где т - количество альтернатив.

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

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

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

Утверждение 6. ММП-оценка, получаемая процедурой МЭЭО-ММП, является асимптотически несмещенной и состоятельной.

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

1. Величина смещения математического ожидания оценки полезности конкретной альтернативы от ее истинного значения.

Математическое ожидание оценки полезности альтернативы Ah iе {1,..., т}, рассчитывается по формуле

z=1

где т - количество альтернатив; v = _j - число всех возможных профилей экспертных упорядочений; к - число экспертов; it>z(At) - нормированное значение оценки полезности альтернативы А„ полученное на выходе процедуры при z-м профиле экспертных упорядочений.

Вероятность каждого профиля экспертных предпочтений (iк\, к2,..., кт|), где kt - количество экспертов, выбравших t-й вариант упорядочения, вычислялось по формуле

где Р, - вероятность /-го варианта упорядочения (t ~ 1, т\):

Pt = \g{x)dx-, D,=\xzEm C(t)x>0 }; Ц

g(x) - плотность нормального совместного распределения экспертных оценок полезности альтернатив выборки.

2. Среднеквадратичное отклонение оценки полезности альтернативы от истинного значения, рассчитываемое по формуле:

где w - вектор истинных значений полезностей альтернатив.

3. Вероятность правильного ранжирования альтернатив на выходе процедуры, определяемая как Ру = где

Р2 (А'1, к.2,..., кт\), если в профиле г на выходе

п*

Рг получено верное ранжирование;

О, в противном случае.

Были исследованы четыре процедуры: Борда, Терстоуна-Мостеллера, первоначальный вариант процедуры МЭЭО и процедура МЭЭО-ММП. В силу того, что величина очень быстро растет с увеличением т, было решено ограничиться случаем пяти экспертов и трах альтернатив с известными полезностями IV = (1, №'2, 0)г, где )1'2 задавалось в диапазоне от 0 до 1. Варьированию подвергалось также значение среднеквадратичного отклонения экспертной оценки от 1/12 до 1/2.

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

1. Методика разбиения профилей индивидуальных упорядочений на классы по величине 5 с рекомендациями по выбору конкретной из четырех процедур.

2. Использование процедуры МЭЭО-ММП с лингвистической шкалой экспертного оценивания альтернатив.

Суть последнего метода в следующем. Пусть для пары альтернатив (Аь Л2) эксперт способен оценить величину разности в их полезности. На основании такой оценки пара должна быть отнесена к одному из классов ()о, Q\,..., каждый из которых характеризуется возрастающей степенью различия в полезности А] и А2. При выборке из трех альтернатив количество упорядочений на лингвистической шкале получилось вдвое больше, чем на порядковой, в силу того, что каждому упорядочению на порядковой шкале А^ >; А^ > А^ соответствуют два варианта на лингвистической:

{(42,43)еа; И \(Аь,А,3)е<22.

Исследования с помощью вероятностного метода показали, что использование лингвистической шкалы дает значительно лучшие показатели для процедуры МЭЭОММП по всем характеристикам 1-3. На рис. 1 приведены графики зависимости математического ожидания оценки полезности А2 от 5 при разных ^2. лад —;—| 1 лад

0.2»

а) м>2 — 0.24

б) м*2 = 0.83

Рис. 1. Зависимости ЩА2] от 5 для процедур: ■ * ■ Терстоуна-Мостеллера; МЭЭО-ММП на порядковой шкале; -—

МЭЭО-ММП на лингвистической шкале ЩАЦ

В четвертой главе приводится описание разработанных программных модулей, реализующих

- численный метод, обеспечивающий выполнение условия утверждения 2 (рис. 2);

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

В заключепив приведены основные выводы и результаты работы.

НАЧАЛО

Рис. 2. Схема численного метода обеспечения ненавязанности

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

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ

1. С помощью доказанных утверждений

- определены характеристические условия, которым удовлетворяет и не удовлетворяет процедура МЭЭО-ММП;

- определены тип механизма и свойства коллективной функции выбора в процедуре МЭЭО-ММП;

- установлено, что процедура МЭЭО-ММП защищена от манипулирования со стороны организатора голосования.

Это позволяет провести объективное сравнение процедуры МЭЭО-ММП с альтернативными вариантами и выбрать процедуру наиболее подходящую для конкретных условий.

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

3. Доказаны состоятельность и асимптотическая несмещённость решений, получаемых процедурой МЭЭО-ММП, что подтверждает эффективность данной процедуры.

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

5. Разработан численный метод обработки предъявления, обеспечивающий процедуре МЭЭО-ММП выполнение условия положительной ненавязанности.

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

Основные результаты опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Система поддержки принятия решений на основе экстраполяции экспертных оценок методом максимального правдоподобия [Текст] / Ю. В. Бугаев, М. С. Миронова, Б. Е. Никитин, А. С. Чайковсгсий // Вестн. Брянск, гос. техн. ун-та. - 2010. — № 1. - С. 84-90.

2. Обработка результатов групповой экспертизы в методе экстраполяции экспертных оценок [Текст] / Ю. В. Бугаев, Б. Е. Никитин, А. С. Чайковский, М. С. Миронова // Вестн. Воронеж. гос. технол. акад. Сер. Информационные технологии, моделирование и управление. - 2010. - № 2. - С. 73-75.

3. Бугаез, Ю. В. Исследование процедур голосования на основе вероятностного подхода [Текст] / Ю. В. Бугаев, Б. Е. Никитин, М. С. Миронова Н Вестн. Воронеж, гос. технол. акад. Сер. Информационные технологии, моделирование и управление. -2011. 2. -С. 42-46.

Статьи и материалы конференций

4. Бугаев, Ю. В. О некоторых функциональных свойствах оператора голосования, основанного на экстраполяции экспертных оценок [Текст] / Ю. В. Бугаев, М. С. Миронова, Б. Е. Никитин // Информационные и управляющие системы в пищевой и химической промышленности: материалы междунар. науч.-прак. коиф. / Воронеж, гос. технол. акад. - Воронеж : ВГТА, 2009. -С. 43-44.

5. Миронова, М. С. Анализ процедуры голосования, основанной на методе экстраполяции экспертных оценок [Текст] / М. С. Миронова // Всероссийская науч. конф. студентов, аспирантов и молодых ученых: тез. докл. / Воронеж, гос. технол. акад. -Воронеж, 2009. - С. 132-136.

6. Об одном способе экстраполяции групповых экспертных оценок [Текст] / Ю. В. Бугаев, М. С. Миронова, Б. Е. Никитин и др. // Финансы. Экономика. Стратегия. Сер. Инновационная экономика: человеческое измерение. - 2010. - № 2. - С. 22-24.

7. Бугаев, Ю. В. Геометрия принципа максимального правдоподобия в экстраполяции экспертных оценок [Текст] /

Ю. В. Бугаев, М. С. Миронова, Б. Е. Никитин // Математические методы в технике и технологиях - ММТТ-23: сб. тр. XXIII Меж-дунар. науч. конф.: в 12 т. Т. 2. Секция 2 / под общ. ред. В. С. Балакирева. - Саратов : Сарат. гос. техн. ун-т, 2010. - С. 68-70.

8. Бугаев, Ю. В. О некоторых свойствах метода экстраполяции экспертных оценок [Текст] / Ю. В. Бугаев, М. С. Миронова, А. С. Чайковский // Актуальные проблемы прикладной математики, информатики и механики: сб. тр. Междунар. конф. - Воронеж : Изд.-полиграф. центр Воронеж, гос. ун-та, 2010. - С. 64-67.

9. Бугаев, Ю. В. Применение чисел Соболя в экстраполяции экспертных оценок [Текст] / Ю. В. Бугаев, М. С. Миронова, А. С. Чайковский // Актуальные проблемы прикладной математики, информатики и механики: сб. тр. Междунар. конф. - Воронеж : Изд.-полиграф. центр Воронеж, гос. ун-та, 2010. - С. 67-70.

10. Бугаев, Ю. В. Сравнительный анализ метода экстраполяции экспертных оценок на порядковой и более сильной шкалах [Текст] / Ю. В. Бугаев, М. С. Миронова, Б. Е. Никитин // Математические методы в технике и технологиях - ММТТ-24: сб. тр. XXIV Междунар. науч. конф.: в 10 т. Т. 2. Секция 2, 8 / под общ. ред. В. С. Балакирева. - Киев : Национ. техн. ун-т Украины «КПИ», 2011.-С. 58-59.

11. Бугаев, Ю, В. Экстраполяция экспертных оценок при групповом выборе [Текст]: свидетельство о гос. регистрации программы для ЭВМ № 2011610601 / Ю. В. Бугаев, А. С. Чайковский, Б. Е. Никитин, М. С. Миронова. - № 2010617089; заявл. 13.11.2010; зарег. 11.01.2011.

ФГБОУВПО «Воронежский государственный университет инженерных технологий» (ФГБОУВПО «ВГУИТ») Отдел полиграфии ФГБОУВПО «ВГУИТ» Адрес университета и отдела полиграфии: 394036, Воронеж, пр. Революции, 19

Подписано в печать 18.11.2011. Формат 60 х 84 1/16 Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 312

61 12-1/407

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНЖЕНЕРНЫХ ТЕХНОЛОГИЙ

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

МИРОНОВА Мария Сергеевна

МОДЕЛИРОВАНИЕ ПРОЦЕДУР КОЛЛЕКТИВНОГО ВЫБОРА НА ОСНОВЕ ЭКСТРАПОЛЯЦИИ ЭКСПЕРТНЫХ ОЦЕНОК

Специальность 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

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

доктор физико-математических наук,

доцент Бугаев Юрий Владимирович

Воронеж-2011

Оглавление

Введение 4 ГЛАВА 1. Обзор процедур коллективного выбора и методов их

исследования 9

1.1. Описание задачи выбора 9

1.2. Процедуры коллективного выбора 12

1.3. Классификация процедур голосования по виду используемой информации 15

1.4. Традиционные методы анализа процедур голосования 20

1.5. Метод экстраполяции экспертных оценок 28

1.6. Экстраполяция на основе ММП 32 Выводы и задачи исследования 37

ГЛАВА 2. Применение традиционных методов анализа процедур

голосования к экстраполяции на основе ММП 39

2.1. Предварительный анализ свойств процедуры МЭЭО-ММП 39

2.2. Геометрическая интерпретация МЭЭО 42

2.3. Анализ на характеристические условия 47

2.3.1. Нейтральность по отношению к избирателям и вариантам 47

2.3.2. Положительная ненавязанность 48

2.3.3. Монотонность и принцип Кондорсе 50

2.3.4. Конечность решений и принцип Парето 52

2.4. Исследование функции выбора 56

2.4.1. Свойства отношения «не хуже по полезности» 56

2.4.2. Свойства функции выбора 57

2.5. Анализ на манипулируемость 57 Выводы по главе 64

ГЛАВА 3. Вероятностный метод анализа процедур коллективного

выбора 66 3.1 Исследование состоятельности оценок, полученных

процедурой МЭЭО-ММП 67

3.2. Параметризация процедур Терстоуна-Мостеллера с целью

их использования в МЭЭО 70

3.3. Описание вероятностного метода анализа 72 3.3.1 Вычисление вероятности определенного экспертного упорядочения 72

3.3.2. Вероятностный метод анализа 76

3.3.3. Методика разбиения профилей упорядочений на классы 81

3.3.4. Вероятностный метод анализа МЭЭО-ММП при использовании лингвистической шкалы 84

Выводы по главе 86

ГЛАВА 4. Описание алгоритмов и программных модулей 88

4.1. Обеспечение условия положительной ненавязанности

для процедуры МЭЭО-ММП 88

4.2. Вычислительные задачи процедуры МЭЭО-ММП при трех альтернативах 93

4.3. Программная реализация вероятностного метода анализа 95

4.3.1. Начальные расчеты 95

4.3.2. Расчет полезностей альтернатив 97

4.3.3. Расчет вероятностных характеристик 101 Выводы по главе 103

Заключение 104

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

Приложения 117

ВВЕДЕНИЕ

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

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

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

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

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

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

Диссертационная работа выполнена в соответствии с планом госбюджетных научно-исследовательских работ по теме «Математическое и компьютерное моделирование в задачах проектирования и оптимизации функционирования информационных технологических систем» (ГР № 01.2006.06298), а также в рамках гранта ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг. по теме «Разработка открытых информационных систем перерабатывающих производств» (ГК № П947).

Цель работы - разработка и применение методики и инструментального аппарата для сравнительного анализа процедур коллективного выбора,

пригодных для использования в методе экстраполяции экспертных оценок (МЭЭО).

Задачи исследования:

1. Проверка процедуры, основанной на ММП (процедуры МЭЭО-ММП), на соответствие характеристическим условиям, принятым для оператора голосования.

2. Исследование характеристических свойств функции коллективного выбора, порождаемой процедурой МЭЭО-ММП.

3. Анализ процедуры МЭЭО-ММП на манипулируемость со стороны организатора голосования и избирателей.

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

5. Разработка комплекса программ, реализующего модели и методы анализа процедур коллективного выбора.

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

Научная новизна работы состоит в следующем.

1. Выявлены новые свойства, которыми обладает процедура МЭЭО-ММП, относящиеся к

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

- удовлетворению порождаемой процедурой функции коллективного выбора свойствам наследования и отбрасывания;

- устойчивости к манипулированию со стороны организатора голосования;

- статистическим свойствам найденного решения: состоятельность, асимптотическая несмещенность.

2. Синтезирована модель для исследования устойчивости процедуры МЭЭО-ММП к манипулированию со стороны избирателей, учитывающая различия вероятностей профилей упорядочения. Ее адекватность подтверждена вычислительными экспериментами.

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

Практическая значимость работы.

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на международных научно-технических конференциях «Информационные и управляющие системы в пищевой и химической промышленности» (г. Воронеж, 2009 г.), «Актуальные проблемы прикладной математики, информатики и механики» (г. Воронеж, 2010 г.) «Математические методы в технике и технологиях - ММТТ-23» (г. Саратов, 2010 г.), «Математические методы в технике и технологиях - ММТТ-24» (г. Киев, 2011 г.); на Всероссийской научной конференции студентов, аспирантов и молодых ученых (г. Воронеж, 2009 г.); на отчетных научных конфе-

ренциях ВГТА (г. Воронеж, 2009 г., 2010 г.).

Публикации. По теме диссертации опубликовано 11 печатных работ, из них 3 - в изданиях, рекомендованных ВАК РФ, и 1 свидетельство о регистрации программы для ЭВМ.

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, списка литературы из 110 наименований и приложений. Основной материал изложен на 102 страницах, содержит 10 рисунков. Объем приложений - 25 страниц.

9

ГЛАВА 1

ОБЗОР ПРОЦЕДУР КОЛЛЕКТИВНОГО ВЫБОРА И МЕТОДОВ ИХ

ИССЛЕДОВАНИЯ

1.1. Описание задачи выбора

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

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

Формально задачу выбора D можно представить в следующем обобщенном виде [4]:

D = <A,x,S, М>,

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

Вектор показателей качества, описывающий альтернативы, может иметь различный смысл [50].

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

критериями К], К2, ..., Кп, и каждому варианту А^ сопоставить и-мерный вектор х1 - (х|, х12, —,х1п), компонентами которого будут числовые или словесные оценки Хд - Кц (Д-) характеристик варианта по шкалам Хд критериев Кд,

д = 1, ..., п. Вариант А^ в этом случае будет представлять собой точку х\ имеющую координаты х1д в и-мерном пространстве шкал критериев X = Х\ х...х Хп . Совокупность всех комбинаций оценок свойств вариантов

по критериям К], К2, ..., Кп образует в пространстве Xмножество Ха с1,

которое называют множеством допустимых значений признаков, множеством допустимых решений (рис. 1.1, а).

Если же решение проблемной ситуации связывать с достижением многих различных целей, то в этом случае вариант А^ оценивается по многим

критериям, которые называются критериями оценки качества решения, показателями эффективности, критериями оптимальности, целевыми функциями, или функциями ценности. Такой критерий является числовой функцией У (*) скалярной х или векторной переменной х = (хь ..., хи). Качество варианта при наличии многих различных целей характеризуется /г-мерным

вектором у1 координатами которого будут оценки по част-

ным критериям качества у^ = /^(хг), принадлежащие множествам значений Уд. с Я, к = 1, к Иными словами, качество варианта А\ представляется векторной функцией У -Дх1) = (/\(х), ...,/фс)). Множеству допустимых значений соответствует в пространстве У = У\ х...х Т^ = множество

7а=/(Ха)с7, называемое множеством оценок качества решений, множеством достижимых целей (рис. 1.1,6).

/2(Х)

О

о

Ж*)

(а)

(б)

Рис. 1.1. Множества допустимых значений признаков и достижимых

целей

Под предпочтением ЛПР понимается его суждение о наличии или отсутствии преимущества какого-либо варианта по отношению к другому.

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

Нейтральное предпочтение альтернатив, которое обозначают как

Аг- ~ Ар характеризуется симметричным отношением (сходство, эквивалентность; несходство, противоположность) и свидетельствует либо о некоторой равноценности, либо о неопределенной ценности обоих вариантов для ЛПР,

например: «варианты А\ и А] эквиваленты» или «варианты А\ и А^ несопоставимы».

Слабая, или нестрогая, предпочтительность вариантов, которую обозначают как А} у Ар задается либо антисимметричным, либо рефлексивным и полным отношением (нестрогое превосходство, нестрогий порядок) и отражает как различимость, так и одинаковость вариантов для ЛПР: «вариант А^

не хуже, чем вариант А^>, «вариант А/, по крайней мере, такой же, как и вариант А;». Первая формулировка допускает, чтобы вариант А, был как лучше,

так и равноценен варианту Ау Вторая формулировка разрешает, чтобы оба

варианта А[ и А]- были одинаково приемлемыми («хорошими»), либо неприемлемыми («плохими») для ЛПР.

Сильная, или строгая, предпочтительность вариантов, которую обозначают как А; у Aj, выражается асимметричным отношением (строгое превосходство, строгий порядок) и отражает явно выраженное различие вариантов: «вариант А^ лучше варианта Ар.

Классическая теория выбора, описанная в работах К. Эрроу [70] и А. Сена [103, 104], основана на презумпции парнодоминантности, согласно которой рациональный выбор всегда может быть сведен к выбору лучших (доминирующих) вариантов при их попарном сравнении по бинарному отношению предпочтения.

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

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

1.2. Процедуры коллективного выбора

На данный момент не существует общепринятой классификации процедур коллективного выбора. В [50] условно выделяют процедуры, основанные на следующих механизмах: методы голосования, аксиоматические [9, 34, 68], игровые [42, 51] и экспертные методы, групповые разновидности методов многокритериального выбора [83, 110].

Обзор литературы показывает, что голосование получило наиболее широкое распространение среди методов принятия коллективного решения. Механизм проведения голосования включает в себя следующие основные моменты [20]:

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