Многокритериальные задачи ПР в условиях определенности

Предположим теперь, что каждому решению хХ попрежнему соответствует единственный элемент уY , где у = (х), но в отличие от предыдущего случая “качество” или “полезность” исхода у или, что то же самое, решения х оцениваются не одним числом f(y), а несколькими. Иначе говоря, предполагается, что существует несколько показателей качества решения, описываемых функционалами f_i: Y E, причем каждый из функционалов f_i требуется оптиимизировать (см. пример 2 из введения). Таким образом, каждому решению х соответствует исход у = (х), а последнему соответствует вектор (f₁,f₂,...,f_m) его числовых оценок. С помощью суперпозиции I_i(x) f_i ( (х)), i = 1,...,m, мы имеем возможность непосредственно оценивать качество самого решения х и работать с векторным отображением:

I:Х E^m, I = (I₁,...,I_m).

Рассмотрим две точки X. Если выполняются неравенства ( для всех

i = 1,...,m, причем по крайней мере одно из неравенств строгое, то будем говорить, что точка предпочтительнее, чем . Если для некоторой точки не существует более предпочтительных точек, то будем называть х⁰ эффективным или Парето-оптимальным решением многокритериальной задачи

I_i(x) , i = 1,2,...,m. (2)

Множество, включающее в себя все эффективные решения, обозначается P_I(X) или просто P(X) (если ясно, о каком векторном критерии I идет речь) и называется множеством Парето для векторного отображения

I: Х E^m, I = (I₁,I₂...,I_m).

Очевидно, P(X)X. Образ множества P(X) в пространстве критериев E^m обозначается P(I). Множество P(I) = I(P(X)) называется множеством эффективных оценок. Множество эффективных оценок часто также называется множеством Парето в пространстве критериев.

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

Точка X называется слабо эффективным решением задачи (2), если не существует такой точки X , для которой выполняются строгие неравенства I_i()>I_i(), i = 1,2,...,m. Иначе говоря, решение называется слабо эффективным, если оно не может быть улучшено сразу по всем m критериям “полезности”, задаваемым с помощью функционалов I_i(x), i =1,2,...,m. Множество слабо эффективных решений будет обозначаться через S_I(X). Очевидно, P(X)S(X) (докажите это). Аналогично вводим обозначение: S(I) I(S(X)).

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

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

Бинарное отношение R₁ называется отношением строгого доминирования или отношением Слейтера, а отношение R₂ - отношением Парето. Ядра этих отношений, т. е. множества максимальных в Х элементов, совпадают, соответственно, с уже введенными множествами S_I(X), P_I(X) (дайте прямое доказательство этого утверждения).

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

Легко показать, что отношения R₁,R₂ не являются, вообще говоря, линейными, т.е. существуют несравнимые по R₁ и R₂ элементы множества Х. В качестве примера таких несравнимых решений можно указать прообразы точек А и В на рисунке 2 (сами точки А и В заданы в пространстве критериев, а не в пространстве решений).

Упражнение.

Исследуйте вопрос: верно ли, что ядро P_I(X) отношения Парето на множестве Х отображается в ядро P_f(Y) отношения Парето на множестве Y: (P_I(X)) = P_f(Y)?

Предлагаю ознакомиться с аналогичными статьями: