Многокритериальные оптимизационные механизмы выбора и их свойства

План лекции №18

1. Понятие и виды многокритериальных механизмов выбора
2. Преобразование лексикографического механизма к скаляризованному векторному
3. Понятие и виды координатных отношений
4. Отношение векторного предпочтения. Наилучшие оценки
5. Свойства механизма выбора наилучших решений (МВНР)

Многокритериальные механизмы выбора характеризуются тем, что в качестве структуры используется векторный критерий (множество вариантов отображается на несколько критериальных шкал).

Правило выбора должно учитывать все компоненты векторного критерия, используемые для сравнения вариантов.

1. Скаляризованные многокритериальные механизмы
2. Лексикографические векторные механизмы выбора
3. Векторный механизм выбора наилучшего решения
4. Векторный механизм выбора эффективного решения (механизм Парето)
5. Векторный механизм выбора слабоэффективного решения (механизм Слейтера)

Примеры многокритериальных механизмов выбора

1. Выбор компьютеров и\или программного обеспечения для решения разнородных задач (обработка текстов, обработка таблиц, взаимодействие с базами данных, обработка графической информации и т.д.)

2. Метод «стоимость-эффективность» в экономике (выбор конкурирующих образцов системы, каждый из которых оценивается а) по стоимости (С) создания (производства) системы, б) по эффективности ( Э) выполнения поставленных перед системой задач.

3. Метод «стоимость-эффективность-время» как обобщение предыдущего метода.

Графическая иллюстрация метода «стоимость-эффективность»

Эффективность желательно увеличивать, а стоимость - уменьшать.
Поэтому 4 лучше чем 2, 3 лучше чем 5, 1 лучше чем 6.
Вырожденный скаляризованный механизм 1 : Э
Вырожденный скаляризованный механизм 2 : С

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

В общем случае при суперпозиции свойство наследования не сохраняется, но сохраняется свойство константантности, характерное для однокритериальных функций выбора.

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

Порядок скаляризованного преобразования лексикографического механизма

Пусть число критериев J₁, J₂, ... , J_m равно m.
1. Перенумеровать критерии, расставив их в порядке убывания степени важности.
2. Преобразовать критерии так, чтобы требовалось увеличивать (а не уменьшать) их значения.
3. Путем смещения по шкале преобразовать критерии так, чтобы все их значения были бы положительными.
4. Найти максимальное значение каждого критерия на множестве всех возможных вариантов.
5. Найти самое большое значение для всех критериев (max) и увеличить его на единицу
    (h >= max + 1).

Формула скаляризации лексикографического механизма и пример

Скаляризация – это сворачивание векторного критерия в один скалярный, производимое по следующей формуле:

Пример скаляризации лексикографического механизма

Варианты: a, b, c, d ;     Критерии: 1, 2, 3, 4, 5.
m = 5. Критерии упорядочены по уменьшению степени важности
Значения критериев в зависимости от вариантов приведены в следующей таблице

Координатные отношения – отношения между векторами, построенные путем использования числовых отношений над компонентами вектора.

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

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

Блокировочное преобразование однокритериального механизма выбора

Отсутствие связи означает однокритериальную эквивалентность вариантов

Вырожденные координатные отношения для скаляризованных механизмов выбора

Отсутствие связи означает эквивалентность вариантов по соответствующей координате вектора

Координатные отношения предпочтения для скаляризованных механизмов выбора

Отношения предпочтения являются двойственными для соответствующих отношений блокировки

Лексикографические координатные отношения предпочтения и блокировки

Лексикографические отношения блокировки являются двойственными для соответствующих отношений предпочтения

Виды координатных отношений

Пусть имеется 2 вектора a = [a₁, a₂, ... a_m] и b = [b₁, b₂, ... b_m] , в которых содержатся многокритериальные оценки двух вариантов.

Рассмотрим 4 координатных отношения:
R1- отношение векторного предпочтения,
R2- отношение Парето,
R3- отношение Слейтера,
R4- отношение предпочтения хотя бы по одной координате вектора.

a R1 b ↔ a_i ≥ b_i , для всех i = 1 .. m ,
a R2 b ↔ a_i ≥ b_i , для всех i = 1 .. m , но a ≠ b,
a R3 b ↔ a_i > b_i , для всех i = 1 .. m ,
a R4 b ↔ a = b или a_i > b_i хотя бы для одного i.

Примеры координатных отношений

Отношение векторного предпочтения можно рассматривать как структуру в механизме попарных предпочтений. Этот частный случай называется векторным механизмом выбора наилучшего решения (МВНР), а результатом выбора являются «наилучшие оценки».

Описание отношения векторного предпочтения:
    a R1 b ↔ a_i ≥ b_i , для всех i = 1 .. m .

Обозначим векторный критерий как функцию F( ), а варианты (x, y, ... ) как аргумент.
Тогда вариант x выбирается, если для любого y : F_i(x) ≥ F_i(y) , для всех i = 1 .. m . Поэтому:

Векторный механизм выбора наилучшего решения является пересечением однокритериальных механизмов для каждой компоненты F_i вектора F.

Пример отношения векторного предпочтения R₁

Пусть имеется 5 вариантов, на которых заданы 2 критерия.

Как построить отношение векторного предпочтения по блокировочным отношениям критериев?

Отношение векторного предпочтения R1 (добавить петли!):

Свойства отношения векторного предпочтения

Описание отношения векторного предпочтения:
    a R1 b ↔ a_i ≥ b_i , для всех i = 1 .. m .

1. Рефлексивность
    a R1 a т.к. a_i = a_i , для всех i = 1 .. m .

2. Транзитивность
    Если a R1 b и b R1 c , т.е. a_i ≥ b_i и b_i ≥ c_i
    следовательно a_i ≥ c_i , для всех i = 1 .. m , то есть a R1 с .

3. Асимметричная часть отношения векторного предпочтения совпадает с асимметричной частью объединения блокировочных отношений критериев

4. Если векторные критериальные оценки вариантов совпадают, то эти варианты связаны кольцами.

Порядок построения отношения векторного предпочтения

а) по значениям векторного критерия

1. Если векторные оценки двух сравниваемых вариантов совпадают, то они соединяются кольцом.
2. Каждый вариант соединяется с собой петлей.
3. Если каждая компонента векторной оценки одного варианта превосходит соответствующую компоненту другого варианта (или компоненты равны), то они соединяются дугой от второго варианта к первому.
4. Если разные компоненты векторных оценок вариантов противоречат друг другу, то они не соединяются.

б) по блокировочным отношениям отдельных критериев

1. Найти асимметричную часть объединения блокировочных отношений критериев
2. Добавить петли для всех вариантов
3. Добавить кольца для всех пар вариантов, имеющих одинаковые векторные оценки

1. Наиболее частым результатом выбора в векторном случае является пустое множество, т.е. отказ от выбора.
2. Механизм МВНВ фактически является пересечением однокритериальных механизмов, использующих каждый критерий в отдельности. Так как свойства наследования и\или согласия при пересечении сохраняются, то МВНР порождает нормальные функции выбора.
3. Отношение векторного предпочтения R1 МВНР является пересечением аналогичных отношений для отдельных критериев.
4. Оно обладает свойствами транзитивности и рефлексивности.

Двухкритериальный индикатор для МВНР

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

Идеальная точка для МВНР

Положение овала указывает на идеальную точку в пространстве критериев. Она ориентирует разработчиков на поиск новых вариантов, имеющих лучшие значения критериев, чем у существующих вариантов.