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

Министерство образования и науки Российской Федерации

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ
(государственный университет)

ФАКУЛЬТЕТ РАДИОТЕХНИКИ И КИБЕРНЕТИКИ

КАФЕДРА ИНФОКОММУНИКАЦИОННЫХ СИСТЕМ И СЕТЕЙ

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

Выпускная квалификационная работа

студента 517 группы

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

, к. ф.-м. н., доцент

г. Москва

2009

Содержание

Введение.. 3

Обзор источников.. 5

Общий обзор методик принятия решений.. 5

Решение многокритериальных задач с субъективными моделями. 5

Задача о назначениях (оптимальное распределение работ) 6

Методы для многокритериальных задач с субъективными моделями. 7

Классические методы многокритериального ранжирования.. 8

Метод Парето. 8

Метод ELECTRE (ELimination Et Choix Traduisant la Realite — исключение и выбор, отражающие реальность) 9

Методы, основанные на многокритериальной теории полезности (MAUT – Multi-Attribute Utility Theory) 10

Многометодный подход к проблемам принятия решений.. 12

Комбинирование многокритериальных методов путем построения сходящегося итерационного процесса.. 14

Описание «простейшего» итерационного процесса.. 15

Описание «базового» итерационного алгоритма с использованием нескольких методов многокритериальной оценки альтернатив.. 16

Анализ сходимости итерационного процесса.. 19

Программная реализация.. 23

Результаты... 29

1. 29

2. 29

Заключение.. 30

Список использованных источников.. 32

Введение

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

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

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

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

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

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

1.  Обзор разнообразных подходов к многокритериальной оценке альтернатив – в том числе, и многометодных

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

3.  Построение итерационных и многометодных алгоритмов – в том числе, с использованием одно - и разнородных методов на отдельных шагах построения решения.

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

Обзор источников

Общий обзор методик принятия решений

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

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

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

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

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

Задача о назначениях (оптимальное распределение работ)

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

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

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

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

Методы компенсации основаны на идее компромисса между противоречивыми оценками по паре (или большему количеству) критериев.

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

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

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

Метод ЗАПРОС (Замкнутые Процедуры у Опорных Ситуаций). Каждая векторная оценка создает у ЛПР образ некоторого объекта, обладающего свойствами, которые характеризуются оценками по критериям качества. Наиболее яркими для ЛПР являются два образа (опорные ситуации), соответствующие сочетаниям только лучшим или только худшим оценок по всем критериям. Например, рассматривается идеальная альтернатива как опорная ситуация, содержащая только лучшие оценки по критериям, и, ориентируясь на нее, сравниваются между собой понижения качества вдоль шкал двух критериев. Значения только по двум критериям могут меняться, значения по остальным критериям фиксируются. Сначала ЛПР предъявляется для сравнения пара альтернатив: первая – лучшая по i-ому критерия, вторая – по j-ому, все остальные оценки являются лучшими. Затем худшая альтернатива в первой паре сравнивается с альтернативой, получаемой из лучшей путем понижения на одну градацию худшей оценки, и т. д. По результатам этих сравнений строится единая порядковая шкала (ЕПШ) оценок двух критериев, которая содержит ценную информацию о предпочтениях ЛПР. С увеличением числа критериев увеличивается и количество избыточной информации, получаемой от ЛПР, что позволяет осуществить ее проверку на непротиворечивость. На основе ЕПШ для пар критериев строится ЕПШ для всех критериев. Реальные альтернативы, представленные векторами критериальных оценок, сравниваются попарно. Вывод о превосходстве одной альтернативы над другой (либо об их эквивалентности) сделается исходя из попарного сравнения упорядоченных по ЕПШ оценок этих альтернатив. Если информации ЛПР недостаточно, то альтернативы несравнимы. На основе бинарного отношения в исходном множестве альтернатив выделяется первое ядро, то есть все неподчиненные альтернативы (доминирующие над другими или несравнимые). Среди альтернатив, оставшихся после удаления первого ядра, выделяется второе ядро и т. д. Альтернативе, входящей в i-ое ядро, присвоим i-ый ранг, если над ней доминирует какая-либо альтернатива из (i-l)-го ядра и она сама доминирует над какой-либо альтернативой из (i+l)-го ядра. Если j-я альтернатива подчинена альтернативе из k-го ядра и доминирует над альтернативой из (k+p)-гo ядра, то ее ранг находится в пределах от (k+1) до (k+p-1). Полученные таким образом совокупность ядер и ранги альтернатив могут использоваться для построения частичного (так как не все альтернативы сравнимы) упорядочения.

Классические методы многокритериального ранжирования

Метод Парето

Метод многокритериального ранжирования Парето, пришедший из экономики, основывается на понятии Парето эффективности.

Рассмотрим множество всевозможных вариантов решений с n параметрами () для каждой точки пространства решений есть m критериев, по которым оценивается точка. Пусть F() -> – функция, которая позволяет количественно оценить каждую точку пространства решений, сопоставив ей точку из пространства критериев (назовем эту точку альтернативой)

Положим, что для каждого критерия более предпочтительным является большее значение. Определим операцию сравнения двух альтернатив следующим образом: альтернатива A строго лучше альтернативы B, если значение каждого из критериев альтернативы А не меньше, чем значение соответствующего критерия альтернативы В, а значение хотя бы одного критерия строго больше (Ai ≥ Bi для любого i и существует j: Aj > Bj => A строго лучше B)

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

Метод ELECTRE (ELimination Et Choix Traduisant la Realite — исключение и выбор, отражающие реальность)

Метод ELECTRE разработан группой французских ученых во главе с профессором Б. Руа.

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

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

Выдвигается гипотеза о превосходстве альтернативы A над альтернативой В. Множество I, состоящее из N критериев, разбивается на три подмножества:

I+ - подмножество критериев, по которым A предпочтительнее B;

I= - подмножество критериев, по которым A равноценно B;

I - — подмножество критериев, по которым B предпочтительнее А.

Индекс согласия подсчитывается на основе весов критериев. В использованном методе этот индекс определяется как отношение суммы весов критериев подмножеств I+ и I= к общей сумме весов:

=, 0 < 1.

Индекс несогласия с гипотезой о превосходстве A над B определяется на основе самого «противоречивого» критерия — критерия, по которому B в наибольшей степени превосходит А.

  , 0<<1. 

Где , – оценки альтернатив A и B по i-му критерию; – длина шкалы i-го критерия.

Введенные индексы используются при построении матриц индексов согласия и несогласия для заданных альтернатив. Бинарное отношение превосходства одной альтернативы над другой задается уровнями согласия и несогласия. Если > p и < q, где p, q – заданные уровни согласия и несогласия, то альтернатива A объявляется лучшей по сравнению с альтернативой B. Если же при этих уровнях сравнить альтернативы не удалось, то они объявляются несравнимыми.

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

Методы, основанные на многокритериальной теории полезности (MAUT – Multi-Attribute Utility Theory)

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

При построении функции полезности нужно учитывать, что она должна удовлетворять ряду условий (аксиом):

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

2. Аксиома транзитивности: из превосходства полезности альтернативы A над полезностью альтернативы B и превосходства полезности B над полезностью C следует превосходство полезности альтернативы A над полезностью альтернативы С.

3. Для соотношений между полезностями альтернатив A, B, C, имеющими вид U(A)>U(B)>U(C), можно найти такие числа a, b, которые меньше 1 и больше 0, так что: a*U(A)+ (1-a)*U(C)=U(B), U(A)*(l-b)+b*U(B)>U(B). Эта аксиома основана на предположении, что функция полезности непрерывна и что можно использовать любые малые части полезности альтернатив.

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

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

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

Существуют два основных недостатка подхода MAUT: во-первых, предположение, что человек может делать точные количественные измерения; во-вторых, от ЛПР требуется «немедленные» назначения всех основных параметров, не давая ему возможности провести исследования проблемы привычным для человека методом «проб и ошибок».

В данной работе использовались следующие функции полезности:

Арифметическая =

Геометрическая =

Гармоническая =

Степенная =

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

Наряду с «простыми», однометодными расчетными схемами, в ходе исследования проблем многокритериальной оптимизации были введены так называемые интерактивные (человеко-машинные) процедуры, где ЛПР и автоматизированная система по очереди вступают в процесс принятия решений. Положительные стороны такого подхода очевидны: применение различных, а возможно даже и разнородных методов при решении одной задачи повышает надежность результата, исключает, или, по крайней мере, занижает элемент «случайности», методологической ошибки в процессе. Эти же преимущества характерны и для полностью независимых от ЛПР многометодных алгоритмов, которые также допускают распараллеливание вычислительного процесса по методам (а это огромная выгода с точки зрения вычислительной математики)[6].

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

Здесь введены обозначения:

A – множество допустимых решений,

Р – начальная точка (полученное пробное решение),

I – идеальное решение,

N – наихудшее решение,

DM() – необходимость вмешательства ЛПР,

К – подмножество критериев,

w – вектор весовых коэффициентов,

Т – пороги согласия/несогласия,

Пустые ячейки соответствуют ситуации, в которой не происходит передача информации.

Среди перечисленных в таблице методов следует расшифровать следующее[3,5]:

AHP – Analytic Hierarchy Process, метод аналитической иерархии BIP – Bireference Procedure, метод двух ориентиров GDF – метод Джиоффриона – Дайра – Фейнберга. IGP – Interactive Goal Programming, метод интеллектуального целевого программирования STEM – Step Method, метод линейных ограничений LXG – метод лексикографической оптимизации

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

Комбинирование многокритериальных методов путем построения сходящегося итерационного процесса

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

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

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

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

Основная предлагаемая идея (итерационный многометодный алгоритм) заключается в том, чтобы рассматривать рейтинги некоторой альтернативы, получаемые разными методами, в качестве оценок этой альтернативы при решении задачи многокритериального ранжирования на следующем шаге некоторого итерационного процесса (где в качестве критериев выступают уже методы). Дополнительная идея состоит в том, чтобы интегральную оценку альтернативы экспертом (если таковая имеется) учитывать в том же качестве, что и результат метода (рейтинг альтернативы); различие между этими двумя рейтингами будет чисто количественное (отличие в весах, с которыми рейтинги выступают в качестве исходных данных). Если экспертов больше одного, то они (как и методы) могут иметь неравные веса – причем веса экспертов могут не только автоматически вычисляться в итерационном процессе (см. ниже), но и могут быть жестко заданы неравными (также возможен компромиссный вариант, чтобы изначально заданные веса экспертов не слишком сильно изменялись автоматически). С учетом близости методов и экспертов во многих отношениях, в дальнейшем для них будем использовать общий термин – «оценщик» (estimator).

Примечание. Разные эксперты (умеющие давать интегральные оценки) могут как выступать в качестве независимых оценщиков, так и вносить свой вклад в «единый экспертный» рейтинг альтернативы (выбор одного из этих двух вариантов подлежит исследованию). Аналогично, разные методы могут как смешиваться с экспертом(ами), так и не смешиваться, а давать «единый методический» рейтинг (который затем с некоторым весом войдет в общий «экспертно-методический» рейтинг). Весовой коэффициент a, обуславливающий «доверие к методам» (по сравнению с «доверием к интегральным оценкам экспертов»), может регулироваться в полуинтервале (0;1] и является единственным глобальным параметром алгоритма (если не считать глобальные параметры, формализующие неопределенность от отсутствующих данных). В случае смешения обоих видов оценщиков (в исходных данных одной многокритериальной задачи) их веса домножаются на a для методов и на (1–a) для экспертов. Кстати, при использовании арифметической функции полезности случаи смешивания и не-смешивания разных видов оценщиков являются эквивалентными.

Описание «простейшего» итерационного процесса

Входные данные:

m альтернатив, вектор альтернатив , ;

n критериев оценки альтернатив, ;

оценок альтернатив по соответствующим критериям ;

Опционально: вектор весов критериев (Может и не задаваться при первоначальной постановке задачи);

Метод решения – фунция на пространстве , возвращающая вектор конечных оценок альтернатив(«оценок по методу», рейтингов) .

Описание итерационного процесса:

На первом шаге решается данным методом исходная задача,

, причем, если веса критериев не заданы первоначально, можно принимать их равными 1 ( или , что нормирует сумму всех весов на единицу).

Переход от k-го шага к (k+1)-му сопровождается пересчетом вектора весов следующим образом:

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

В качестве нового значения параметра , т. е. вес j-го критерия, вычисленного на k-м шаге, возьмем значение косинуса угла между вектором результата и соответствущим вектором оценок . Иными словами**

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

Целесообразно ввести и на этом шаге нормировку весов на 1, то есть вычислить , и принять впоследствии.

На (k+1)-м шаге решается задача подобная исходной, разница лишь в векторе , входящем в качестве параметра в метод.

.

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

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

**Формула для веса может быть и другой, это лишь один из вариантов корректировки на основе скалярного произведения векторов.

Описание «базового» итерационного алгоритма с использованием нескольких методов многокритериальной оценки альтернатив

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

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

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