Общие понятия о формировании множества Парето-оптимальных решений

Для формализации задачи формирования множества Парето-оптимальных решений в множестве допустимых решений в рассмотрение введены следующие обозначения:

1) - множество допустимых решений многокритериальной задачи определения эффективных решений;

2) – локальные частные критерии, соответствующие целям функционирования системы, тогда - векторный критерий принятия решений; для определения значений векторных оценок в рассмотрение введено обозначений , тогда - критериальное пространство значений векторного критерия , используемого при выборе решений;

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

Способ определения наилучших вариантов (решений) при многих критериях предполагает определение множества Парето в пространстве допустимых решений Х.

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

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

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

В соответствии с введёнными отношениями предпочтения и доминирования может быть определено условие формирования множества недоминируемых решений:

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

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

Решение не доминирует решение , а не доминирует решение , если:

, ,.., ,.., ; (1)

, ,.., ,.., . (2)

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

Для случая двух критериев и условие (1) может быть представлено в следующем виде:

и , (4)

либо

и . (5)

По аналогии условие (2) для двух критериев примет следующий вид:

и , (6)

либо

и . (7)

Те решения и , для которых выполняются либо условия (4), (5) либо условия (6), (7) не могут быть сравнимы с использованием отношения .

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