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

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

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

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

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

9.1. Поиск решения МЗН типа А

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

1) анализ данных;

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

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

9.2. Поиск решения МЗН типа В

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

1) анализ данных;

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

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

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

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

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

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

9.3. Поиск решения МЗН типа С

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9.4. Поиск решения МЗН типа D

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

1. Аанализ данных.

2. Формирование ОДР.

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

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

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