Множество Парето

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

Ограничимся рассмотрением случаев, когда решение принимается по двум критериям.

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

Пусть W и V - критерии, по которым необходимо выбрать оптимальное решение (при этом желательно по возможности максимизировать значения W и V). Рассмотрим на плоскости (W, V) множество возможных решений, которому на рисунке 3.1 соответствует заштрихованная область.

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

Пусть М - произвольная точка множества , внутренняя или граничная, и (W, V) - ее координаты. Поставим следующий вопрос: можно ли, оставаясь в множестве , переместиться из точки M в близкую точку так, чтобы при этом увеличились обе ее координаты? Если М - внутренняя точка, то это, бесспорно, возможно. Если же М - граничная точка, то такое возможно не всегда. Из точек вертикального отрезка АВ можно переместиться, увеличивая лишь координату V (координата W при этом остается неизменной). Перемещая точку горизонтального отрезка CD вправо, мы увеличиваем координату W (при этом координата V сохраняет свое значение). Что же касается дуги BD, то перемещение вдоль нее способно лишь увеличить одну из координат при одновременном уменьшении другой.

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

- к первому классу относятся точки, которые можно сдвинуть так, чтобы одновременно увеличились обе координаты и при этом точки остались в множестве (в этот класс попадают все внутренние точки множества и часть его граничных точек);

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

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

Множество точек третьего класса BD (выделено на рисунке 3.1 утолщенной линией) называется границей (множеством) Парето данного множества .

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

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

3.2. Постановка задачи в общем виде

Пусть на плоскости (x, y) задано множество w, представленное на рисунке 3.2 заштрихованной областью, и в каждой точке этого множества определены две непрерывные функции:

(3.1)

Рассмотрим следующую задачу: на множестве w найти точку (x⁰, y⁰) в которой

Обычно это записывается следующим образом:

Сразу же отметим, что в общем случае поставленная задача решения не имеет. В самом деле, изобразим на плоскости (V, W) все точки, координаты которых вычисляются по формулам (3.1). Обозначим полученное множество через . Из рисунка 3.3 видно, что W_max (наибольшее значение W) и V_max (наибольшее значение V) достигаются в разных точках, а точка M^* с координатами (W_max, V_max) лежит вне множества .

Таким образом, в исходной постановке задача, вообще говоря, неразрешима - удовлетворить обоим требованиями одновременно невозможно. И, следовательно, нужно искать какое-то компромиссное решение.

Среди известных стоит отметить два метода:

1) метод уступок;

2) метод идеальной точки.

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

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

Метод идеальной точки состоит в отыскании на границе Парето точки, ближайшей к точке утопии, задаваемой ЛПР (точка M^* на рисунке 3.3). Обычно ЛПР формулирует цель в виде желаемых значений показателей, и часто в качестве координат целевой точки выбирается сочетание наилучших значений всех критериев (обычно эта точка не реализуется при заданных ограничениях, поэтому ее и называют точкой утопии).

3.2.1. Метод идеальной точки

Рассмотрим реализацию метода идеальной точки на конкретном примере.

Пример 3.1. (случай непрерывного множества)

Пусть на множестве плоскости (x, у), определяемом системой неравенств

(3.2)

заданы две линейные функции:

(3.3)

Требуется найти решение задачи

Р е ш е н и е

В соответствии с ограничениями (3.2) множество w представляет собой пятиугольник, на рисунке 3.4 его вершины имеют следующие координаты (X, Y): A(2,0); B(2,6); C(5,6); D(10,3); E(10,0).

В силу линейности критериев W и V пятиугольник ABCDE переходит в пятиугольник A^*B^*C^*D^*E^*, представленный на рисунке 3.5, координаты вершин которого (W, V) вычисляются по формулам (3.3): А^*(7, 0), B^*(1, 6), C^* (4, 9), D^*(12, 11), E^* (15, 8).

Находим границу Парето. Это отрезок D^*E^*. Точка утопии М^*(15,11) считается заданной (ее координаты - суть наибольшие значения W и V).

Требуется найти на множестве Парето точку, ближайшую к точке утопии М^*. Из рисунка 3.5 видно, что искомая точка должна лежать на отрезке D^*Е^*. На рисунке 3.6 проведем через точки D^* и Е^* прямую. Пусть

(3.4)

- ее уравнение.

Чтобы отыскать конкретные значения коэффициентов , подставим в (3.4) координаты обеих точек - D^* и Е^*. Получим

(3.5)

(3.6)

Вычитая из равенства (3.5) равенство (3.6), после простых преобразований придем к соотношению

откуда

Положим Тогда любое из равенств(3.5) или (3.6) дает в результате и

W + V = 23

- искомое уравнение прямой.

Теперь стоит напомнить, как ищется расстояние между точками, заданными своими координатами.

На рисунке 3.7 M₁(W₁, V₁) и M₂(W₂, V₂) - точки на плоскости (W,V). Для того чтобы найти расстояние между ними, достаточно вычислить длину гипотенузы построенного прямоугольного треугольника M₁M₂M₃ (заштрихованная область на рисунке 3.7). Воспользовавшись теоремой Пифагора, вычислим длину гипотенузы

(3.7)

По условию задачи нам нужно определить на прямой D^*E^*, которую описывает уравнение

W + V = 23, (3.8)

идеальную точку M⁰(W⁰, V⁰), минимально удаленную от точки утопии М^*. Подставим в (3.7) координаты точки утопии М^*(15, 11), обозначим полученное подкоренное выражение через z и решим следующую задачу поиска экстремума:

(3.9)

Так как согласно (3.8) W = 23 - V, то соотношение (3.9) можно переписать в виде

Возводя в квадрат и приводя подобные, получаем

(3.10)

Для решения оптимизационной задачи (3.10) вычислим первую производную и приравняем её нулю:

,

отсюда найдем координату V⁰ идеальной точки М⁰

В соответствии с (3.8) найдем координату W⁰ идеальной точки М⁰:

W⁰=23 - V⁰=23 -

Минимальное расстояние от точки утопии M^* до прямой D^*E^* найдем с учетом (3.7) и (3.10):

На рисунке 3.8 представлена идеальная точка с координатами (W⁰, V⁰)=, которая находится на расстоянии от точки утопии М^* (15, 11).

Соответствующие значения х⁰ и у⁰ легко находятся из системы линейных уравнений (3.3):

Имеем:

Ответ: Выбор решения =(10, ) на множестве w обеспечивает паретооптимальное решение (W⁰, V⁰)= на множестве W.

Замечание. Мы рассмотрели задачу, в которой необходимо выполнить условие

На практике часто встречаются случаи, когда требования выглядят по-иному, например:

или даже так:

Можно, конечно, решать такие задачи и непосредственно. Но значительно удобнее поступить по-другому, если учесть, что функция

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

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

Предлагаю ознакомиться с аналогичными статьями: