Основные алгоритмы решения

Многокритериальной задачи о назначениях

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

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

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

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

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

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

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

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

3. Абсолютное соответствие. При этом способе на основе предпочтений ЛПР определяется ранг каждого из возможных назначений, т. е. каждой клетке матрицы М(n´n) присваивается ранг, который рассматривается как индекс соответствия.

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

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