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

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

· исключение альтернативы по сочетанию оценок по ряду критериев:

· последовательное исключение по отдельным критериям.

Одна из модификаций варианта исключения по отдельным критериям - это исключение альтернатив, у которых некоторые оценки выходят за установленные (ранее) граничные или удовлетворительные значения. (Речь идет о проверке допустимости альтернатив в методе главного критерия).

Другой эвристический прием - сокращение числа критериев, по которым сравниваются и оцениваются альтернативы, путем отбрасывания (исключения) менее значимых критериев (эвристика Б).

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

Одной из наиболее известных ЧМП оценки векторов является процедура Дайера-Джиофриона (Д-Д). Она начинается с выбора какой-либо точки в критериальном пространстве (рис.1).

Рис. 1. Поиск решения в критериальном пространстве

В этой точке ЛПР определяет градиент глобальной целевой функции следующим образом. Один из критериев считается опорным. Берется небольшое изменение значения этого критерия (в сторону улучшения) от начального. Перед ЛПР ставятся вопросы типа: какое изменение по иному критерию эквивалентно заданному изменению опорного критерия? Ответы ЛПР определяют вектор (направление), вдоль, которого изменение глобального критерия будет наиболее эффективным. Вдоль этого направления делается шаг определенной длины и получаются новые значения по всем критериям. Совокупность этих значений (вектор) предъявляется ЛПР вместе с первоначальным решением (соответствующим начальной точке). Далее перед ЛПР ставится вопрос: какое из решений лучше? Если лучше новое решение (назовем его ), то делается еще шаг вдоль этого же направления и вычисляется решение . Далее и предъявляются ЛПР. Если лучше, то делается еще шаг в прежнем направлении, и т.д. Если лучше, чем , то в точке определяется новый градиент (направление) изменения глобальной целевой функции (см. рис.1), и т.д. Процедура заканчивается, если ЛПР признает очередное решение вполне для него удовлетворительным.

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

) предпочтительнее смежный критериальный вектор;

) предпочтительнее начальный критериальный вектор;

) нет четкого предпочтения.

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

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