Понятие компромиссов Парето
Способ многокритериального выбора состоит в сравнении альтернатив между собой по всем сформированным критериям и выделении подмножества наилучших альтернатив. В данном подходе отказываются от поиска одной единственной наилучшей альтернативы. Решающее правило в этом случае строится на основе аксиомы В. Парето, которая формулируется следующим образом: «Если в задаче принятия решений частные критерии независимы по предпочтению и значение каждого из них желательно увеличивать, то из двух альтернатив, характеризуемых набором частных критериев, предпочтительнее та, для которой выполняются соотношения q1i(x) > q2i(x) по всем i, где первый индекс характеризует номер стратегии, второй индекс - номер частного критерия. То есть первая альтернатива предпочтительнее второй только в том случае, когда значения ее частных критериев не меньше значений частных критериев второй альтернативы. Если все значения частных критериев одной альтернативы равны значениям критериев другой, то альтернативы равнозначны». Таким образом, предпочтение одной альтернативе перед другой можно отдавать только если первая по всем критериям лучше второй. В результате попарного сравнения альтернатив все худшие по всем критериям альтернативы отбрасываются, а все оставшиеся несравнимые между собой принимаются. Если все максимально достижимые значения частных критериев не относятся к одной и той же альтернативе, то принятые альтернативы образуют множество Парето и выбор на этом заканчивается.
Численные методы построения множества Парето
Если для некоторой пары возможных решений имеет место неравенство f(x’)≥f(x’’), то первое решение будет предпочтительнее второго, т. е. x’>x’’. Тогда второе решение ни при каких обстоятельствах не может оказаться выбранным и его можно исключить из последующего учета в процессе принятия решений. Исключение всех подобного рода решений приводит к множеству Парето. Множество Парето-оптимальных решений обозначается P(X)f и определяется равенством:
P (X ) f = {x* ∈ X | не существует такого x ∈ X , что f (x) ≥ f (x*)}.
Алгоритм нахождения множества Парето:
Пусть множество возможных решений X состоит из конечного числа элементов, а отношение предпочтения является иррефлексивным и транзитивным. Пронумеруем все возможные решения: Х=Х1={x1,x2,…xn}
Первый шаг алгоритма нахождения множества решений заключается в последовательном сравнении первого решения x1 со всеми остальными x2 ,..., xn. Это сравнение заключается в проверке справедливости соотношения x1≥xi и соотношения xi≥x1 при каждом i = 2,..., n. В случае истинности для некоторого i первого соотношения x1≥xi доминируемое решение xi следует удалить из множества x1 и продолжить указанную проверку для следующего за xi решения. При выполнении второго соотношения xi≥x1 удалению подлежит первое решение x1 , после чего сразу же следует перейти ко второму шагу. Если же ни одно из двух приведенных соотношений x1≥xi
и xi≥x1 не является истинным, ничего удалять не нужно. В том случае, когда сравнения х1 были проведены со всеми остальными решениями x2 ,..., xn, и ни для какого i = 2,..., n не оказалось выполненным соотношение xi≥x1, первое решение следует запомнить и удалить его из (оставшегося) множества возможных решений. Указанные действия описывают первый шаг алгоритма.
Если после выполнения первого шага во множестве возможных решений не осталось ни одного решения (т. е. все оказались удаленными), то алгоритм заканчивает работу. При этом в памяти будет храниться одно решение х1 . Оно и представляет собой
множество решений. В противном случае (т. е. когда не все решения оказались удаленными), необходимо перейти ко второму шагу.
Обозначим множество, оставшееся после выполнения первого шага х2. Второй шаг
полностью аналогичен первому. А именно, сначала нужно перенумеровать элементы множества х2 . После этого следует провести последовательное сравнение первого решения этого множества со всеми остальными его элементами. При этом сравнение осуществляется совершенно аналогично тому, как это было описано на первом шаге. Выполнение сравнений на втором шаге любо закончится удалением первого решения множества х2, либо такого удаления не произойдет. Во втором случае это решение следует запомнить, а затем удалить его из множества х2 . Если после этого во множестве
возможных решений не останется ни одного решения, то вычисления заканчиваются; в памяти будет храниться множество решений. В противном случае к оставшемуся непустому множеству возможных решений нужно применить аналогичный третий шаг
алгоритма и т. д. В результате, после окончания работы алгоритма в памяти будет храниться множество всех решений.
