5. Основные алгоритмы решения многокритериальной задачи о назначениях

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

5.1. Различные индексы соответствия

Подход к решению МЗН основан на поиске ответов на два основных вопроса:

•  как определить ранги всех возможных назначений в матрице назначений М( n ? n )?

•  как, зная ранги, найти решение, соответствующее вве­денному выше критерию оптимальности?

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

•  Формальное соответствие. При этом способе на основе характеристик элементов расчитывается индекс соответствия характеристик объекта и субъекта. Эти индексы используются в качестве ранговых показателей в матрице М( n ? n ).

•  Относительное соответствие. При этом способе на ос­нове предпочтений ЛПР ранжируются по качеству назначений все субъекты по отношению к каждому из объектов и все объ­екты по отношению к каждому из субъектов. Суммы соответст­вующих рангов для пары объект–субъект используются как индексы соответствия и формируют матрицу М( n ? n ).

•  Абсолютное соответствие. При этом способе на основе предпочтений ЛПР определяется ранг каждого из возможных назначений, т. е. каждой клетке матрицы М( n ? n ) присваивает­ся ранг, который рассматривается как индекс соответствия. Легко увидеть связь способов определения критериального соответствия с введенными выше типами МЗН. Ясно, что фор­мальный индекс удобно использовать при решении задач типа D и на первых этапах решения задач типа В и С. Как мы уви­дим далее, определения относительного индекса соответствия менее трудоемки для ЛПР. Этот способ удобен для решения задач уникального характера, особенно типа С. Способ опреде­ления абсолютного индекса соответствия подходит для решения повторяющихся задачах, особенно задач типа В.

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

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

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

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

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

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

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