Поиск решения многокритериальной задачи о назначениях

В процедуре поиска решения МЗН можно выделить следующие основные этапы.

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

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

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

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

Рассмотрим эти этапы подробнее.

Этап анализа данных и проверки существования идеального решения

Основной целью данного этапа является поиск возможности идеального решения МЗН и выработка рекомендаций по стратегии дальнейшего решения МЗН.

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

Идеальные назначения формируют область поиска идеального решения МЗН. Если удается найти n идеальных пар, дающих полное решение задачи, то это означает, что идеальное решение МЗН, удовлетворяющее всем требованиям, получено без вмешательства ЛПР и анализ проблемы закончен.

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

Формально отношения между элементами двух множеств (субъектов и объектов) могут быть охарактеризованы вектором соответствия R_ij (i,j=l,2,...,n), k-й компонент которого отражает степень соответствия характеристик элементов по k-му критерию. Таким образом, на этапе анализа данных эквивалентом понятия «критериальное соответствие по k-му критерию» является компонент вектора соответствия, который подсчитывается следующим образом:

здесь - требование i-го элемента одного множества (субъекта или объекта), выражаемое р-й по порядку оценкой на шкале требований по k-му критерию; - соответствующие возможности j-гo элемента другого множества, выражаемые q-й оценкой на шкале возможностей того же k-гo критерия; r_k - число оценок на шкале k-гo критерия, на которой требования превышают возможности.

Поскольку оценки на шкале имеют две формулировки (см.выше) и упорядочены от лучшей к худшей, то = 0, если р ³ q, где p,q - номера оценок на шкалах требований и возможностей k-гo критерия. Таким образом, условие = 0 означает, что требования по k-му критерию удовлетворены, а условие > 0 - неудовлетворенность требований. Если требования по k-му критерию удовлетворены, то по определению КС по этому критерию является идеальным и обладает наивысшим качеством.

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

Множество векторов соответствия R_ij образует (n´n) таблицу сходства, в клетке (i,j) которой помещен вектор соответствия субъекта C_i и объекта O_j.

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

Предполагая равноценность компонентов вектора соответствия и их шкал, значение свертки вычисляют как сумму отклонений по каждому из компонентов вектора соответствия. Тогда суммарная величина критериальных соответствий G_ij=SUM( ), k= 1,2,...,N, при сделанных выше предположениях может служить формальным индексом качества назначения, которое является наилучшим при G_ij = 0 (идеальное назначение) и ухудшается с увеличением G_ij.

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

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

Проиллюстрируем применение процедур этапа анализа данных на приведенном выше примере. Исходные данные - оценки по критериям трех субъектов и трех объектов - можно представить в виде табл. 12.1.

Таблица 12.1

Значения оценок по критериям субъектов и объектов

Субъект	Критерии			Объект	Критерии
Субъект	K₁	K₂	K₃	Объект	K₁	K₂	K₃
С₁	2	1	2	O₁	1	1	2
C₂	2	2	2	O₂	2	1	2
C₃	2	2	3	O₃	2	2	2

Таблица сходства, составленная из векторов соответствия, имеет вид табл. 12.2. Легко увидеть, что при заданных условиях существуют три идеальных назначения (векторы со всеми нулевыми компонентами): {C₁ - O₂}; {C₁ – О₃}; {С₂ – О₃}.

Таблица 12.2

Векторы соответствия

	С₁	С₂	С₃
O₁	100	110	111
O₂	000	010	011
O₃	000	000	001

Для того чтобы проверить, возможно ли идеальное решение МЗН, сформируем таблицу формальных индексов соответствия. Таблица сходства (см. табл. 12.2) может быть представлена в виде таблицы свертки (табл. 12.3).

Таблица 12.3

Индексы соответствия

	С₁	С₂	С₃
O₁	1	2	3
O₂	0	1	2
O₃	0	0	1

Воспользуемся решением однокритериальной ЗН на множестве элементов этой таблицы. Из решения задачи следует, что в приведенном примере идеального решения МЗН не существует. Любое возможное решение для рассматриваемого примера содержит, по меньшей мере, одно неидеальное назначение. Например, решение [{C₁ - O₂} {C₂ – О₃} {С₃ – O₁}] включает назначение {С₃ – O₁}, отличное от идеального (G₃₁=3). Следовательно, для рассматриваемого примера процедуры поиска решения МЗН должны быть продолжены.

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

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

Дата добавления: 2019-09-13; просмотров: 178; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 59 60 61 62 636465 66 67 68 Следующая ⇒

Мы поможем в написании ваших работ!