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

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

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

Она может состоять из несвязных кусков и содержать изолированные точки (см. рис. 5). Компромиссная кривая (КК) строго монотонно убывает в следующем смысле. Пусть Y₁ и Y₂ произвольные точки, принадлежащие КК. Обозначим их координаты Y₁(y1,y2) и Y₂(y3,y4), если y1y4. Таким образом, КК не содержит ни горизонтальных, ни вертикальных отрезков и её уравнение может быть представлено в форме 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 — множество Парето). Участок КК в этом случае определяется параметрическими уравнениями:

F1=F1(1(), …, 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).

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

В данном случае можно получить уравнение этой кривой в декартовых прямоугольных координатах. Для этого решаем эти уравнения относительно параметра. Получим Приравнивая правые части и разрешая относительно 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); находим значения F2(-0.5,1)=0.25, F1(-0.5,1)=4.25.
• 2. Находим частные производные

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

• 2x₁=- (x₁+1),
• 8x₂=- (x₂-1).

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

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

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

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

F₁()=.

F₂()=.

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

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

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

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

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

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

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