Сужение множества Парето

Я на практических занятиях Вам приводил пример «Выбор места работы». Мы нашли множество Парето оптимальных решений.

Было определено, что оптимизация по Парето использует отношение Парето-доминирования, которое отдаёт предпочтение одному объекту перед другим только» том случае, когда первый объект по всем критериям не хуже второго и хотя бы но одному из них лучше. При истинности этого условия первый объект считается доминирующим, а второй - доминируемым. Два объекта, для которых предпочтение хотя бы, по одному критерию расходится, считаются несравнимыми.

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

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

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

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

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

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

Указание верхних/нижних границ критериев. Дополнительная информация об оптимальном исходе Xopt ÎD в этом случае имеет вид

Число Ci рассматривается здесь как верхняя граница по i – му критерию. Соответственно для установления нижних границ используется знак «больше или равно».

Наложим, например, следующие ограничения на оптимальное решение:

· зарплата — не менее 500 рублей;

Отбрасывается 5 вариант

· длительность отпуска — не менее 30 дней;

Остаются все варианты

· время поездки — не более 40 минут.

Отбрасывается 4 и 7 варианты

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

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

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

Пусть в качестве главного критерия выступает критерий зарплата; ограничения

· длительность отпуска — не менее 30 дней;

· время поездки — не более 40 минут.

Отбросим варианты, которые не удовлетворяют данным ограничениям: {4, 7}. Из них максимальную зарплату имеет вариант 3. Этот вариант и будет оптимальным.

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

Упорядочим критерии по относительной важности. Например, следующим образом:  (т.е. важнейший критерий — зарплата, следующий за ним по важности время поездки, наименее важный критерий длительность отпуска).

Максимальное значение по критерию Зарплата имеют вариант 7. Далее сравниваем эти варианты по второму по важности критерию Время поездки. Потом переходим к третьему критерию Длительность отпуска. Лучшим является вариант 7, который и является здесь оптимальным.

При упорядочении  оптимальным является вариант 6, а при упорядочении  – оптимальным становится вариант 5.