Различные типы задач о назначениях
В рамках сформулированной МЗН содержатся несколько существенно различающихся по своим особенностям типов задач, требующих разных подходов к их решению. Для наших целей удобно воспользоваться двумя основаниями классификации задач о назначениях - характером задачи и ее размерностью.
По характеру будем различать уникальные задачи, для которых решение каждой новой задачи требует осуществить весь комплекс подготовки исходных данных заново (разработка критериев, шкал), и повторяющиеся МЗН, требующие периодического решения с одним и тем же набором критериев, но различающиеся составом субъектов, объектов и набором экспертных оценок.
Другим основанием классификации служит размерность МЗН. В приведенном примере нетрудно перебрать все возможные назначения, сравнить их между собой и выбрать лучшие. Ясно, что такая возможность существует при небольшом количестве элементов двух множеств и малом числе критериев. Однако в задачах о назначениях количество элементов может меняться от десятков до тысяч, а число критериев - от трех-четырех до десяти и более, при этом количество оценок на шкалах, как правило, три - пять [1,2,3]. В связи с этим в каждом из классов уникальных и повторяющихся задач целесообразно выделить следующие типы МЗН, различающиеся размерностью своих характеристик:
| Тип МЗН | Количество элементов | Число критериев, оценок на шкалах |
| A | Небольшое | Малое |
| B | Небольшое | Большое |
| C | Большое | Малое |
| D | Большое | Большое |
|
|
|
В задачах типа А имеется небольшое число элементов и малое число критериев (точнее, произведение числа оценок соответствующих шкал критериев). Задачи этого типа легко обозримы, и ЛПР может без труда найти наилучшее решение.
Для задач типа В, С и D, в которых элементов больше 10, критериев больше 5 или оба эти параметра достаточно велики, особенно необходимы системы поддержки принятия решений (СППР). Эти системы помогают ЛПР при анализе, поиске и выборе лучших вариантов решения. СППР обладают особенностями, связанными с типом МЗН, для которых они предназначены.
Для задач типа В требуются средства, позволяющие реализовать детальные алгоритмы выявления предпочтений ЛПР и построения общего решающего правила.
Для задач типа С необходимы в первую очередь средства анализа данных и средства, реализующие способы решения локальных задач о назначениях, которые возникают при конфликтных критериальных оценках.
Для задач типа D следует реализовать более упрощенный подход, ориентированный прежде всего на исключение недопустимых назначений.
Повторяющиеся задачи характеризуются неизменным набором критериев и шкал. Поэтому их удобно решать, построив единый порядок, отражающий ценность критериальных соответствий, и используя полученные результаты для каждого нового варианта задачи.
|
|
|
Для задач уникального типа более подходящим может оказаться подход, основанный на построении порядка только для того набора критериальных соответствий, который характеризует конкретную рассматриваемую задачу.
Далее будут изложены подходы, методы и способы решения, применяемые в системе поддержки решения МЗН для различных типов задач. Предварительно рассмотрим проблемы, общие для СППР, предназначенной для поддержки решения многокритериальных задач о назначениях.
Основные алгоритмы решения многокритериальной задачи о назначениях
Существенные трудности, с которыми связан поиск решения рассматриваемой задачи, заключаются в многокритериальности, в необходимости рассматривать задачи достаточно большой размерности и в стремлении построить такой метод решения, при реализации которого требуемая от ЛПР информация соответствовала бы возможностям системы переработки информации человеком.
Различные индексы соответствия
|
|
|
Подход к решению МЗН основан на поиске ответов на два основных вопроса:
1) как определить ранги всех возможных назначений в матрице назначений М(n´n)?
2) как, зная ранги, найти решение, соответствующее введенному выше критерию оптимальности?
Ответ на первый вопрос будет получен, если есть способ определения соответствия характеристик объекта и субъекта. В свою очередь, целостное соответствие будет зависеть от определения критериального соответствия. Мы будем использовать далее три способа ранжирования назначений и определения целостного соответствия характеристик объекта и субъекта.
1. Формальное соответствие. При этом способе на основе характеристик элементов рассчитывается индекс соответствия характеристик объекта и субъекта. Эти индексы используются в качестве ранговых показателей в матрице М(n´n).
2. Относительное соответствие. При этом способе на основе предпочтений ЛПР ранжируются по качеству назначений все субъекты по отношению к каждому из объектов и все объекты по отношению к каждому из субъектов. Суммы соответствующих рангов для пары объект-субъект используются как индексы соответствия и формируют матрицу М(n´n).
3. Абсолютное соответствие. При этом способе на основе предпочтений ЛПР определяется ранг каждого из возможных назначений, т. е. каждой клетке матрицы М(n´n) присваивается ранг, который рассматривается как индекс соответствия.
|
|
|
Легко увидеть связь способов определения критериального соответствия с введенными выше типами МЗН. Ясно, что формальный индекс удобно использовать при решении задач типа D и на первых этапах решения задач типа В и С. Как мы увидим далее, определения относительного индекса соответствия менее трудоемки для ЛПР. Этот способ удобен для решения задач уникального характера, особенно типа С. Способ определения абсолютного индекса соответствия подходит для решения повторяющихся задачах, особенно задач типа В.
Дата добавления: 2019-09-13; просмотров: 228; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!