Для двух решений <math>x</math> и <math>x'</math> говорят <math>x \sim x'</math> тогда и только тогда, когда <math>\exists i \in 1..K \colon f_i(x) > f_i(x') \land \exists j \in 1..K, j \ne i \colon f_j(x') > f_j(x)</math> - такую пару решений называют '''несравнимой'''
}}
== Критерий оптимальности ==
Перечислим основные критерии оптимальности
=== Критерий Парето ===
Вектор решения <math>\vec x\in S</math> - оптимальный по Парето, если <math>\not\exists\vec x'\in S</math>:<math>f_i(\vec x) \le f_i(\vec x')</math> для всех <math>i=1, \dots, k</math> и <math>f_i(\vec x) < f_i(\vec x')</math> для хотя бы одного <math>i</math>.
<math>P(S)</math> - множество оптимальных по Парето решений.
Целевой вектор является оптимальным по Парето, если соответствующий ему вектор из области определения также оптимален по Парето.
<math>P(Z)</math> - множество оптимальных по Парето целевых векторов.
Множество оптимальных по Парето векторов является подмножеством оптимальных по Парето в слабом смысле векторов. Вектор <math>\vec x'\in S</math> является слабым оптимумом по Парето тогда, когда не существует вектора <math>\vec x\in S</math> такого, что <math>f_i(\vec x) < f_i(\vec x')</math> для всех <math>i=1, 2, \dots, k</math>.
Множество оптимальных по Парето решений также называют Парето-фронтом.
Парето-фронт не может быть вычислен за полиномиальное время
=== Лексикографический порядок ===
Если одни целевые функции важнее других, критерий оптимальности можно определить по лексикографическому порядку.
Отношение лексикографического порядка <math><_{\mathrm{lex}}</math> между векторами <math>\vec a</math> и <math>\vec b</math> выполняется, если <math>a_q < b_q</math>, где <math>q = min \left\{k : a_k \neq b_k\right\}</math>. То есть, первая <math>q</math> компонента вектора <math>\vec a</math> меньше компоненты вектора <math>\vec b</math>, а компоненты <math>q+1</math> — уровни (если есть). Лексикографический порядок для случая действительных чисел является линейным.
Вектор <math>\vec x \in X</math> является лексикографическим решением, если не существует вектора <math>\vec x' \in X</math>, такого, что <math>f(\vec x') <_{\mathrm{lex}} f(\vec x)</math>.
Поскольку отношение лексикографического порядка является линейным, можно доказать, что вектор <math>\vec x</math> является лексикографическим решением, если для всех <math>\vec x' \in X</math> выполняется:
: <math>\vec f(\vec x) <_{\mathrm{lex}} \vec f(\vec x').</math>
== Получение оптимальных по Парето решений ==
