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

Введение

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

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

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

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

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

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). Полученные таким образом совокупность ядер и ранги альтернатив могут использоваться для построения частичного (так как не все альтернативы сравнимы) упорядочения.

жүктеу/скачать 0.56 Mb.

Достарыңызбен бөлісу: