18. Многокритериальная оптимизация. Множество Парето.

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

Задача многокритериальной оптимизации формулируется следующим образом:^[3]

где это() целевых функций. Векторы решенийотносятся к непустой области определения.

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

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

Метод Парето

Он широко ис­пользуется при ранжировании вариантов решений, объектов и т.п. Состояние А (множество параметров) называется Парето-оптимальным, если не существует другого со­стояния В (множества других параметров) доминирующего состоя­ние А относительно целевой функции. Состояние А доминирует со­стояние В, если хотя бы по одному параметру А лучше В, а по ос­тальным не хуже.

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

Рассмотрим на плоскости (U, V) множество ω. Каждая его точка обладает одним из следующих свойств: либо все точки, ближайшие к ней, принадлежат множеству ω (такая точка называется внутренней точкой множества ω), либо сколь угодно близко от нее расположены как точки множества, так и точки, множеству не принадлежащие (такие точки называются граничными точками множества). Множе­ство всех граничных точек множества называется его границей. Гра­ничная точка может как принадлежать множеству, так и не принадле­жать. Здесь рассмотрим только такие множества, которым принадле­жат все точки границы.

Точки множества со можно разбить на три класса:

1 класс - точки, которые, оставаясь во множестве со, можно сдви­нуть так, чтобы одновременно увеличились обе координаты (в этот класс попадают все внутренние точки множества ω и часть его гра­ничных точек) (на рис. 6.1 это точкиMl, М2 и МЗ);

2 класс — точки, перемещением которых по множеству со можно увеличить только одну из координат при сохранении значения второй (вертикальный отрезок АВ и горизонтальный отрезокPQна границе множества ω);

3 класс - точки, перемещение которых по множеству со способ­но лишь уменьшить либо одну из координат, либо обе(дугаBQгра­ницы множества ω).

Множество точек третьего класса называется множеством Парето или границей Парето данного множества ω .