Аналитические методы построения множества Парето

Компромиссная кривая

Особый интерес для практики — m=2. В этом случае множество паретовских точек представляет собой одномерное многообразие на плоскости и допускает удобное графическое представление.

Опр. Множество паретовских точек в двухмерном пространстве критериев называют компромиссной кривой.

Она может состоять из несвязных кусков и содержать изолированные точки (см. рис. 5). Компромиссная кривая (КК) строго монотонно убывает в следующем смысле. Пусть Y₁ и Y₂ произвольные точки, принадлежащие КК. Обозначим их координаты Y₁(y1,y2) и Y₂(y3,y4), если y1<y3, то y2>y4. Таким образом, КК не содержит ни горизонтальных, ни вертикальных отрезков и её уравнение может быть представлено в форме F₂=u(F₁) и F₁=v(F₂).

Рис. 5. Примеры КК (компромиссная кривая выделена красным цветом)

Расчёт компромиссных кривых.

Аналитический подход. Если функции F₁(X) и F₂(X) дифференцируемы, то можно попытаться найти геометрическое место точек соприкосновения поверхностей уровня F₁(X)=b1 и F₂(X)=b2. В таких точках gradF₁=-gradF₂, 0  .

Последнее векторное уравнение равносильно n скалярным алгебраическим уравнениям которые определяет кривую в пространстве параметров x₁=₁(), ..., x_n=_n(). Если участок этой кривой, на котором 0 принадлежит множеству D, то он принадлежит и множеству P (P - множество Парето). Участок КК в этом случае определяется параметрическими уравнениями:

F₁=F₁(₁(), ..., _n()),

F₂=F₁(₁(), ..., _n()), 0.

Пример 1. В квадрате D={-1 x₁  1, -1 x₂  1} заданы два критерия

которые желательно минимизировать.

1. Находим минимумы функций F₁ и F₂ . Абсолютные минимумы находятся в точках (0,0) и (-1,1) и принадлежат D.

2. Находим частные производные

составляем систему уравнений

4x₁=- (x₁+1)

x₂=- (x₂-1).

Отсюда получаем параметрическое уравнение кривой в пространстве параметров

В данном случае можно получить уравнение этой кривой в более распространённой форме: y=f(x). Для этого решаем эти уравнения относительно параметра . Получим

Приравнивая правые части и разрешая относительно x₂, получим уравнение паретовской кривой P: .

Параметрическое уравнение КК будет иметь следующий вид

F₁()=

F₂()=.

Закономерность КК: F₁ возрастает от 0 до 5, а F₂ убывает от 2 до 0.

Построим графики паретовских кривых в области D и пространстве критериев (рис. 6 и 7).

Рис. 6. Область D и множество P Рис. 7. Компромиссная кривая

Пример 2. В области D₁={-0.5  x₁  0.5, 0  x₂  1} заданы два критерия

которые нужно минимизировать с учетом функциональных ограничений x₂-x₁-0.375  0.125.

а) рассмотрим сначала случай без функциональных ограничений

1. Находим минимумы функций F₁ и F₂. Абсолютные минимумы находятся в точках X_1opt=(0,0) и X_2opt=(-1,1) и первая точка принадлежат D, а вторая нет. Находим условный минимум для функции F₂: X_2услов=(-0.5, 1); находим значения функций в этой точке F₂(-0.5,1)=0.25, F₁(-0.5,1)=4.25.

2. Находим частные производные

составляем систему уравнений

2x₁=-2 (x₁+1),

8x₂=-2 (x₂-1).

Отсюда получаем параметрическое уравнение кривой в пространстве параметров

В данном случае можно получить уравнение этой кривой в более распространённой форме: y=f(x). Для этого решаем эти уравнения относительно параметра . Получим

Приравнивая правые части и разрешая относительно x₂, получим уравнение паретовской кривой P: . Найдём точку пересечения кривойс x₁=-0.5. Получим Xп=(–0.5; 0.2). Это соответствует случаю, когда λ меняется от 0 до 1 (0≤λ≤1). Для удобства введём новые обозначения: P₁ – паретовская кривая в области D₁ и КК₁ – соответствующая компромиссная кривая в области критериев.

Параметрическое уравнение КК будет иметь следующий вид (когда точки X_1opt=(0,0) и X_2opt=(-1,1) принадлежат области D)

F₁()=

F₂()=.

Построим графики паретовских кривых в области D и пространстве критериев (рис. 8 и 9).

Xп

X₁opt

X₂усл

Рис. 8. Область D₁ и множество P₁ Рис. 9. Компромиссная кривая КК₁

Рис. 10. Пространство оценок и компромиссная кривая

Таким образом, паретовская кривая P₁ будет состоять из двух кусков: от X_1opt Xп и от X_П до X_2усл. Как видно из рисунка 8 на отрезке [-0.5,0] P и P₁ совпадают.

Компромиссная кривая КК₁ также состоит из двух частей. Левая часть от 0 до 0.41, которая совпадает с компромиссной кривой КК и правая часть, которая соответствует второй части кривой P₁.

Закономерность КК: F₁ возрастает от 0 до 4.25, а F₂ убывает от 2 до 0.

б) введём функциональные ограничения. Область D₁ в этом случае будет иметь вид (см. рис. 11). Находим условный минимум для функции F₁ и F₂ . Они лежат в точках X_1opt=(0,0) и X_2opt=(-0.5, 1). Как видно из полученных результатов точки минимумов не изменились.

Рис. 11. Область D₁ Рис. 12. Пространство оценок

Рис. 13. Область D (синий цвет) и множество Парето (тёмно-синий цвет)

Из рассмотренного примера видно, что нахождение множества P в аналитическом виде является сложной задачей. Поэтому в настоящее время широко используются численные методы построения решений оптимальных по Парето (см. раздел "Численные методы получения множеств Парето").