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

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

Напомним введенное ранее понятие ценности решения МЗН для ЛПР как функции совокупности назначений, формирую­щих решение МЗН: F ({ C i – O j }).

Далее предлагается несколько различных процедур поиска окончательного решения МЗН, выбор которых зависит от типа рассматриваемой задачи [12]. СППР лишь рекомендует воз­можные подходы для тех или иных типов задач. Однако выбор процедуры поиска решения остается за ЛПР – он может учи­тывать рекомендации системы, но волен поступать, исходя из своих реальных возможностей и потребностей. Любой из вы­бранных путей приведет к цели, но некоторые будут более бы­стрыми и потребуют меньших затрат. Эти соображения и по­зволяют рекомендовать следующие стратегии выбора процедур поиска решений МЗН.

9.1. Поиск решения мзн типа а

При малом числе критериев, объектов и субъектов проце­дура решения МЗН может выглядеть следующим образом:

•  анализ данных;

•  основная и, если необходимо, вспомогательная процеду­ры выявления предпочтений ЛПР.

Второй этап является завершающим для данного типа задач.

9.2. Поиск решения мзн типа в

При большом числе критериев и сравнительно небольшом числе объектов и субъектов рекомендуется следующий порядок поиска решения МЗН:

•  анализ данных;

•  формирование области допустимых решений (ОДР);

•  формирование структуры предпочтений ЛПР – основная и вспомогательные процедуры (рекомендуется упорядочивать КС а по ценности лишь для реально существующего пространст­ва КС, что позволяет существенно уменьшить нагрузку на ЛПР; эта рекомендация особенно касается уникальных задач);

•  ранжирование векторов соответствия по ценности;

•  формирование ранговой матрицы «объекты—субъекты», элементами которой являются числа, отражающие ранги век­торов соответствия;

•  решение однокритериальной задачи о назначениях на ранговой матрице с оптимизацией по критерию максимального числа наилучших назначений.

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

9.3. Поиск решения мзн типа с

При большом числе объектов и субъектов, но малом числе критериев рекомендуются два подхода к поиску решения МЗН.

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

Второй подход рекомендуется для уникальных задач типа С. Этот подход основан на идеях, предложенных в [5,9], и оп­ределяет следующий порядок поиска решения МЗН.

•  Формальный анализ.

•  Формирование структуры предпочтений ЛПР.

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

В j -м элементе i -й строки первой ранговой матрицы нахо­дится ранг вектора соответствия { C i – O j }, в j -м элементе i -й строки второй таблицы — ранг вектора соответствия { O j – C i }. В результате строки первой таблицы отражают точку зрения ЛПР на предпочтения каждого субъекта относительно каждого из объектов, а строки второй – на предпочтения каждого объекта относительно каждого из субъектов.

Ранги в таблицах замещаются соответствующими числа­ми – высший ранг замещается нулем.

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

•  Автоматическое формирование единой ранговой матрицы «объекты – субъекты», элементами которой являются числа, отражающие ранги векторов соответствия. В каждой клетке единой матрицы находится сумма чисел, расположенных в со­ответствующих элементах двух ранговых матриц.

•  Поиск решения однокритериальной задачи о назначени­ях на единой ранговой матрице с оптимизацией по критерию максимального числа наилучших назначений.

•  Предъявление назначений одинакового ранга ЛПР для дополнительного анализа. СППР предупреждает о последствиях принимаемых решений.

•  Уменьшение размерности задачи и редуцирование таблиц за счет удаления сделанных назначений, изменение рангов в каждой из исходных таблиц, т. е. присвоение в каждой отдель­ной строке нулевого значения высшим из оставшихся в строке рангов.

•  Повторение этапов 4–6 до получения полного решения МЗН.

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

В [5] доказана теорема о существовании наилучшего (нуле­вого) элемента ранговой матрицы на каждом цикле процесса, т.е. сходимости рассмотренного процесса при условии, что упо­рядочения векторов соответствия транзитивны.

Процесс обеспечивает эффективное решение, соответствую­щее максимальной ценности решения для ЛПР (критерию оп­тимальности).