Условия оптимальности по Парето.

Условия оптимальности по Парето.

Проблемы поиска оптимальных решений многокритериальных задач. Наиболее развитый метод поиска оптимальных решений является метод решения детерминированных однокритериальных задач, то есть задач, которые имеют следующий вид: где Х – множество допустимых вариантов решений, а- вектор известных детерминированных значений параметров задачи, х – вектор значений управляемых переменных, которые может выбирать ЛПР. Решением задачи, в общем виде, является , то есть такое значение вектора переменных, для которого достигается максимальное значение критерия качества, и это решение называется оптимальным.

При всей полезности идеи оптимизации и однокритериальности следует достаточно аккуратно пользоваться ею, из-за:

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

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

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

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

Оптимальность по Парето и Слейтеру. Возникает детерминированная многокритериальная задача принятия решений, общий вид которой следующий:

.

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

Принцип отбора для дальнейшего рассмотрения не доминирующих альтернатив называют принципом Эджворта-Парето. Согласно принципу Эджворта-Парето отношения доминирования во множестве допустимых альтернатив формально определяется следующим образом. Рассмотрим отношение «³» в пространстве критериев. Будем считать, что и - векторные оценки альтернатив х и у соответственно. Так же считаем, что Q(x) ³Q(y), если выполняется условие

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

Множество оптимальных по Парето (или эффективных) решений eff(X) определяется как

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

Рассмотрим отношение «>» в пространстве критериев. Считаем, что Q(x) >Q(y), если выполняется условие

,

то есть по всем критериям альтернатива х лучше альтернативы у. В этом случае альтернатива х доминирует над альтернативой у по Слейтеру, . Слабо эффективные (оптимальные по Слейтеру) решения определяются как

.

Таким образом между множеством допустимых альтернатив Х, множеством слабо эффективных альтернатив S(X) и множеством эффективных альтернатив P(X) существует очевидное соотношение P(X)ÍS(X) ÍX.

Необходимые и достаточные условия оптимальности по Парето. Пусть множество значений векторного критерия, составляющими которого являются два критерия, имеет вид изображенный на рисунке 1.Множество значений векторного критерия, которое доминирует по Парето значения Q(x), совпадает с неотъемлемым ортантом С(х), вершина которого перенесена в точку Q(x).

Действительно для произвольной точки аÎС(х) этого ортанта выполняются неравенства , при этом если а¹Q(x), то хотя бы одно из неравенств будет строгим, то есть произвольная точка множества , кроме точки Q(x), будет доминировать над Q(x) по Парето. Поэтому на рисунке 1а значения векторного критерия Q(x) (то есть альтернатива х) не принадлежит к множеству оптимальных по Парето, а альтернатива х* оптимальная по Парето, потому что выполнено условие , то есть пересечение создает одна точка - Q(x).

Опорной гиперплоскостью к выпуклому множеству называется такая гиперплоскость, которая имеет как минимум одну точку этого множества, и все точки этого множества расположены в одном из полупространств этой гиперплоскости. Строго выпуклым множеством называется такое множество, которой принадлежат все точки отрезка, который соединяет две произвольные точки этого множества. Таким образом если множество значений векторного критерия строго выпуклое, теорема, которую вывел С. Карлин, дает условие оптимальности по Парето(рис 1(б)).

Теорема. Пусть множество значений векторного критерия Q является строго выпуклым, ограниченным и замкнутым. Для того, чтобы альтернатива х*ÎХ была оптимальной по Парето, необходимым и достаточным является существование таких неотъемлемых коэффициентов,

для которых

,

для любой другой альтернативы хÎХ.

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

Существование опорной к множеству значений векторного критерия Q плоскости в каждой точке, оптимальной по Парето, гарантируется и в том случае, когда множество альтернатив Х является выпуклым, а все составляющие векторного критерия - строго вогнутые функции.

Получение условия оптимальности по Парето для не выпуклых задач в следующем виде: для того, чтобы альтернатива х* была оптимальной по Парето, необходимо и достаточно, чтобы некоторая скалярная функция , зависящая от составляющих векторного критерия качества Q₁,…,Q_n достигла максимума в точке Q(x*). Для того чтобы такое утверждение было конструктивным, необходимо указать вид этой скалярной функции.

Считаем, что множество значений векторного критерия Q является ограниченным, замкнутым и находится целиком в средине неотъемлемого ортанта Rⁿ, то есть

Рисунок (4.5). Поскольку пересечение ортанта С(х*) с множеством Q дает лишь одну точку Q(х*), целесообразно считать С(х*) множеством уровня некоторой функции ,

 

которая достигает своего максимума на Q в точке Q(x*). В этом случае стороны ортанта являются линиями уровня этой функции, то есть описывают множество точек , которые . Проведем через начало координат и точку Q(x*) прямую. Эта прямая описывается соотношениями

где >0, i=1,n.

В точке Q(x*) выполняется соотношение . Возвращаясь к рисунку (4.5), видим что под прямой линия уровня функции является лучом, который выходит из точки Q(x*), для которого выполняются условия Туту уже выполняется неравенство .

Аналогично над прямой имеем , а соответственная часть линии уровня задается как Вследствие этого функция записывается в виде .

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

при этом равенство достигается тогда и только тогда, когда .