И дискретная оптимизация

Медиана Кемени и законы больших чисел.С помощью расстояния Кемени находят итоговое мнение комиссии экспертов. Пусть А1, А2, А3,…, Ар - ответы р экспертов, представленные в виде бинарных отношений. Для их усреднения используют т.н. медиану Кемени

Arg min ∑ D (A_i ,A),

где Arg min - то или те значения А, при которых достигает минимума указанная сумма расстояний Кемени от ответов экспертов до текущей переменной А, по которой и проводится минимизация. Таким образом,

∑ D (A_i ,A) = D (A₁ ,A) + D (A₂ ,A) + D (A₃ ,A) +…+ D (A_р ,A).

Кроме медианы Кемени, используют среднее по Кемени, в котором вместо D (A_i ,A) стоит D² (A_i ,A).

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

Arg min ∑ D (A_i ,A) → Arg min М D (A₁ , A).

Здесь М - символ математического ожидания. Предполагается, что ответы р экспертов А₁ , А₂ , А₃ ,…, А _р есть основания рассматривать как независимые одинаково распределенные случайные элементы (т.е. как случайную выборку) в соответствующем пространстве произвольной природы, например, в пространстве упорядочений или отношений эквивалентности. Систематически эмпирические и теоретические средние и соответствующие различные варианты законов больших чисел изучены в ряде работ (см., например, [1, 2]).

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

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

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

Рассмотрим пример вычисления медианы Кемени. Пусть дана квадратная матрица (порядка 9) попарных расстояний для множества бинарных отношений из 9 элементов А₁ , А₂ , А₃ ,..., А₉ (см. табл.3). Найти в этом множестве медиану для множества из 5 элементов { А₂ , А₄ , А₅ , А₈ , А₉ }.

Таблица 3.

Матрица попарных расстояний

В соответствии с определением медианы Кемени следует ввести в рассмотрение функцию

С(А) = ∑ D(A_i ,A) = D(A₂ ,A)+D(A₄ ,A)+D(A₅ ,A)+D(A₈ ,A)+D(A₉ ,A),

рассчитать ее значения для всех А₁ , А₂ , А₃ ,..., А₉ и выбрать наименьшее. Проведем расчеты:

С(А₁) = D (A₂ ,A₁) + D (A₄ ,A₁) + D (A₅ ,A₁) +D (A₈ ,A₁) + D (A₉ ,A₁) =

= 2 + 1 +7 +3 +11 = 24,

С(А₂) = D (A₂ ,A₂) + D (A₄ ,A₂) + D (A₅ ,A₂) +D (A₈ ,A₂) + D (A₉ ,A₂) =

= 0 + 6 + 1 + 5 + 1 = 13,

С(А₃) = D (A₂ ,A₃) + D (A₄ ,A₃) + D (A₅ ,A₃) +D (A₈ ,A₃) + D (A₉ ,A₃) =

= 5 + 2 + 2 + 5 +7 = 21,

С(А₄) = D (A₂ ,A₄) + D (A₄ ,A₄) + D (A₅ ,A₄) +D (A₈ ,A₄) + D (A₉ ,A₄) =

= 6 + 0 + 5 + 8 + 8 = 27,

С(А₅) = D (A₂ ,A₅) + D (A₄ ,A₅) + D (A₅ ,A₅) +D (A₈ ,A₅) + D (A₉ ,A₅) =

= 1 + 5 + 0 +3 + 7 = 16,

С(А₆) = D (A₂ ,A₆) + D (A₄ ,A₆) + D (A₅ ,A₆) +D (A₈ ,A₆) + D (A₉ ,A₆) =

= 3 + 4 + 10 + 1 + 5 = 23,

С(А₇) = D (A₂ ,A₇) + D (A₄ ,A₇) + D (A₅ ,A₇) +D (A₈ ,A₇) + D (A₉ ,A₇) =

= 2 + 3 +1 + 6 + 3 = 15,

С(А₈) = D (A₂ ,A₈) + D (A₄ ,A₈) + D (A₅ ,A₈) +D (A₈ ,A₈) + D (A₉ ,A₈) =

= 5 + 8 + 3 + 0 +9 = 25,

С(А₉) = D (A₂ ,A₉) + D (A₄ ,A₉) + D (A₅ ,A₉) +D (A₈ ,A₉) + D (A₉ ,A₉) =

= 1 + 8 + 7 + 9 + 0 = 25.

Из всех вычисленных сумм наименьшая равна 13, и достигается она при А=А₂, следовательно, медиана Кемени - это множество { А₂ }, состоящее из одного элемента А₂.

-- 7.Экспертные оценки, бинарные отношения

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

Пример сравнения восьми проектов. Рассмотрим конкретный пример применения только что сформулированного подхода. По заданию руководства фирмы анализировались восемь проектов, предлагаемых для включения в план стратегического развития фирмы. Они были обозначены следующим образом: Д, Л, М-К, Б, Г-Б, Сол, Стеф, К (по фамилиям менеджеров, предложивших их для рассмотрения). Все проекты были направлены 12 экспертам, назначенным Правлением фирмы. В приведенной ниже табл.6 приведены ранги восьми проектов, присвоенные им каждым из 12 экспертов в соответствии с их представлением о целесообразности включения проекта в стратегический план фирмы (ранг 1 - самый лучший проект, который обязательно надо реализовать, ранг 2 - второй по привлекательности проект,..., ранг 8 - наиболее сомнительный проект).

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

Метод средних арифметических рангов. Сначала был применен метод средних арифметических рангов. Для этого прежде всего была подсчитана сумма рангов, присвоенных проектам (см. таблицу). Затем эта сумма была разделена на число экспертов, в результате рассчитан средний арифметический ранг (именно эта операция дала название методу). По средним рангам строится итоговая ранжировка (в другой терминологии - упорядочение), исходя из принципа - чем меньше средний ранг, чем лучше проект. Наименьший средний ранг, равный 2,625, у проекта Б, - следовательно, в итоговой ранжировке он получает ранг 1. Следующая по величине сумма, равная 3,125, у проекта М-К, - и он получает итоговый ранг 2. Проекты Л и Сол имеют одинаковые суммы (равные 3,25), значит, с точки зрения экспертов они равноценны (при рассматриваемом способе сведения вместе мнений экспертов), а потому они должны бы стоять на 3 и 4 местах и получают средний балл (3+4)/2 = 3,5. Дальнейшие результаты приведены в табл.7 ниже.

Табл.6. Ранги 8 проектов по степени привлекательности

для включения в план стратегического развития фирмы

№ эксперта	Д	Л	М-К	Б	Г-Б	Сол	Стеф	К
			2,5	2,5

Примечание. Эксперт № 4 считает, что проекты М-К и Б равноценны, но уступают лишь одному проекту - проекту Сол. Поэтому проекты М-К и Б должны были бы стоять на втором и третьем местах и получить баллы 2 и 3. Поскольку они равноценны, то получают средний балл (2+3)/ 2 = 5/ 2 = 2,5.

Итак, ранжировка по суммам рангов (или, что то же, по средним арифметическим рангам) имеет вид:

Б < М-К < {Л, Сол} < Д < Стеф < Г-Б < К. (1)

Здесь запись типа "А<Б" означает, что проект А предшествует проекту Б (т.е. проект А лучше проекта Б). Поскольку модели Л и Сол получили одинаковую сумму баллов, то по рассматриваемому методу они эквивалентны, а потому объединены в группу (в фигурных скобках). В терминологии математической статистики ранжировка (1) имеет одну связь.

Метод медиан рангов. Значит, наука сказала свое слово, итог расчетов - ранжировка (1), и на ее основе предстоит принимать решение? Но тут наиболее знакомый с современной эконометрикой член Правления вспомнил, что ответы экспертов измерены в порядковой шкале, а потому для них неправомерно проводить усреднение методом средних арифметических. Надо использовать метод медиан.

Что это значит? Надо взять ответы экспертов, соответствующие одному из проектов, например, проекту Д. Это ранги 5, 5, 1, 6, 8, 5, 6, 5, 6, 5, 7, 1. Затем их надо расположить в порядке неубывания (проще было бы сказать - "в порядке возрастания", но поскольку некоторые ответы совпадают, то приходится использовать непривычный термин "неубывание"). Получим последовательность: 1, 1, 5, 5, 5, 5, 5, 6, 6, 6, 7, 8. На центральных местах - шестом и седьмом - стоят 5 и 5. Следовательно, медиана равна 5.

Табл. 7. Результаты расчетов по методу средних арифметических

и методу медиан для данных, приведенных в табл.6.

	Д	Л	М-К	Б	Г-Б	Сол	Стеф	К
Сумма рангов			37,5	31.5
Среднее арифметическое рангов		3,25	3,125	2,625	6,333	3,25	5,333	7,083
Итоговый ранг по среднему арифметическому		3,5				3,5
Медианы рангов				2,25	7,5
Итоговый ранг по медианам		2,5	2,5

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

Б < {М-К, Л} < Сол < Д < Стеф < К <Г-Б. (2)

Поскольку проекты Л и М-К имеют одинаковые медианы баллов, то по рассматриваемому методу ранжирования они эквивалентны, а потому объединены в группу (кластер), т.е. с точки зрения математической статистики ранжировка (2) имеет одну связь.

Дата добавления: 2014-01-05