Изменения
Нет описания правки
Парето-фронт не может быть вычислен за полиномиальное время
=== Лексикографический порядок ===
Если одни целевые функции важнее других, критерий оптимальности можно определить по лексикографическому порядку.
Отношение лексикографического порядка <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>
