Множество парето. 
Системы поддержки принятия решений

В результате изучения данной главы студент должен:

знать

• • что называется множеством Парето и какова его роль для принятия решений;
• • геометрическую интерпретацию множества Парето, понятия «угол предпочтения» и «конус предпочтения»;

уметь

• • выражать аксиомой Парето взаимную согласованность предпочтений и критериев оптимальности ЛПР;
• • выполнять сужение множества Парето;

владеть

• • методами, применяемыми для нахождения множества Парето в конкретных практических ситуациях, в случае дискретного и непрерывного множества альтернатив;
• • численными алгоритмами, наиболее эффективными для построения множества Парето в сложных многокритериальных задачах.

Ключевые слова Дискретное или непрерывное множество альтернатив, критерии оптимальности, критериальное пространство, отношение предпочтения, доминируемые альтернативы, сужение множества альтернатив, множество Парето, угол предпочтения, генетические алгоритмы построения множества Парето.

Критерии и отношения предпочтения

При постановке многокритериальной задачи принятия решений стремление ЛПР достичь одной из т заданных целей выражается математически в виде максимизации (или минимизации) соответствующего частного критерия f_k(x). Функции f_k(x), k= 1,2,…, т заданы на множестве альтернатив, т. е. на множестве всех возможных решений X. В роли функций f_k(x) чаще всего выступают или показатели качества (технические, экономические и т. п., показатели надежности, безопасности), или финансовые величины (стоимость реализации проекта, прибыль, затраты и т. д.). В зависимости от содержания проблемы функции f_k(x) именуют критериями оптимальности, эффективности, целевыми функциями, показателями (или критериями) качества. Как правило, предполагается, что ЛПР стремится достичь наибольшего значения f_k(x), т. е. требуется максимизация. Это отвечает критериям дохода, прибыли, цены продажи, надежности, показателям качества, темпа и объема производства и т. п. Однако нередко на практике ситуация обратная: ЛПР стремится достичь наименьшего значения f_k(x), т. е. требуется минимизация. В частности, это относится к показателям затрат, закупочных цен, экологических загрязнений, сроков изготовления или строительства, потерь, рисков и т.н. В этом случае математически несложно минимум любого из критериев превратить в максимум, например, умножив f_k(x) на -1. Такой подход удобнее всего применять для описания множества решений X и заданных на нем критериев f_k(x), чтобы не делить критерии на два типа и не изучать каждый из них отдельно. Поэтому в дальнейшем для простоты и наглядности (не теряя общности) будем использовать именно этот подход.

Обратите внимание!

Будем предполагать, что все частные критерии f_k(x) определены так, что они требуют максимизации согласно целям ЛГ1Р (т.е., например, все критерии, требующие минимизации, взяты с противоположным знаком).

При наличии у ЛПР одновременно т заданных целей все т критериев объединяют в один вектор f (x) = (J (x), f₂(x)_} …, f_m(x)), который называется векторной оценкой решения, или векторным критерием.

Определение Все возможные значения векторных оценок (y_vy₂,…"у_т) = (f (x), f₂(x), …,/_от(д:)) образуют множество Y возможных оценок. Это множество лежит в /"-мерном векторном пространстве R^m, которое называется критериальным пространством: Ya R^m.

Необходимость совместного, т. е. векторного рассмотрения т критериев fi (x), f₂(x), …, f_m(x) диктуется тем, что на практике локальные цели ЛПР, соответствующие различным компонентам /_к(х) векторного критерия, чаще всего оказываются взаимно противоречивыми. Например, повышение качества приобретаемого товара почти всегда означает более высокую цену, т. е. две цели ЛПР (купить дешевле и приобрести товар высокого качества) противоречат друг другу. Поэтому идеальный с точки зрения ЛПР вариант одновременного максимума всех критериев f_k(x) практически никогда не достижим на существующем в реальности множестве альтернатив. В математической терминологии это означает, что функции f_k(x) принимают максимальные значения в различных точках множества альтернатив X (в рассмотренном примере — самый дешевый и самый высококачественный товары всегда различны). Для наглядности поясним этот факт геометрически для случая т = 2, т. е. для двух критериев f_x(x) и /₂(х). При т = 3 критериальное пространство R^[1] становится трехмерным, и геометрическая интерпретация перестает быть наглядной.

Приведем два примера, отвечающие двум возможным (ив теории, и на практике) вариантам множества альтернатив X: дискретному и непрерывному случаям.

Пример 4.1.1.

Сопоставим каждой альтернативе х_к точку Y_k с координатами у_{ = f_x(x_k) и у₂ = f₂(^xk) — Критериями у_х и у₂ могут быть, к примеру, цена и качество (товара, проекта). Тогда графическое представление при п = 10 множества возможных оценок Y = {У, У₂, У₁₀} в критериальном пространстве R¹ представляет собой набор отдельных точек (рис. 4.1.1). Координаты каждой точки Y_k, k = 1, 2,10 на рис. 4.1.1 представляют собой величины критериев #, и у₂ для альтернативы с номером k. Отметим, что согласно введенному вначале предположению, критерий, отвечающий цене (скажем, #,), преобразуется так, что минимальной цене соответствует максимальное значение #,. Чтобы оставаться в более привычной области положительных значений критерия #, удобнее (вместо простого умножения цены на -1) преобразовать критерий путем вычитания всех цен из некоторой верхней ценовой планки, лежащей выше всех имеющихся альтернатив.

Рис. 4.1.1. Дискретное множество возможных оценок Y в двумерном критериальном пространстве R¹ и образ соответствующего множества Парето Если, как мы предположили, ЛИР стремится достичь наибольшего значения обоих критериев #, и #₂, т.с. требуется их максимизация, то очевидно, что для ЛИР представляют интерес лишь четыре альтернативы x_v х₂, х₄ и х₈, образы которых в критериальном пространстве У, У₂, У₄ и У₈ расположены на рис. 4.1.1 правее и выше всех остальных вариантов. Иными словами, при выборе наилучшего решения ЛИР может убрать из рассмотрения все остальные альтернативы и выбирать только из четырех: x_v х₂, х_А и х₈. Величины критериев #, и у₂ достигают максимума в различных точках: критерий у_х достигает максимума в точке У₈, тогда как величина у₂ — в точке У, т. е. одновременный максимум на множестве X не реализуется. Промежуточные варианты У₂ и У₄ представляют собой компромиссные решения, которые вполне могут соответствовать предпочтениям ЛИР.

Такое сужение множества альтернатив X с исходных 10 до четырех, само собой разумеющееся при взгляде на иллюстрацию, перестает быть очевидным в случае критериальных пространств более высоких размерностей п или же для более сложных множеств альтернатив X. Именно изучение в самом общем случае этого сужения, именуемого множеством Парето, и составляет предмет данной главы.

Пример 4.1.2.

Непрерывное множество альтернатив Пусть множество решений X бесконечно, а критериальное множества точек У= (#,#₂) ^е изображено на рис. 4.1.2. Подобная ситуация возникает, в частности, при выборе оптимальных значений двух управляющих параметров (финансовых регуляторов, технических показателей и т. п.) некоторой системы при условии, что регулировка этих параметров может осуществляться непрерывно.

Рис. 4.1.2. Непрерывное множество возможных оценок Y в двумерном критериальном пространстве R² и образ соответствующего множества Парето в некоторых пределах. Тогда графическое представление множества возможных оценок Y в критериальном пространстве R^[2] представляет собой уже не набор отдельных точек, а некоторую фигуру наподобие области У, заштрихованной на иллюстрации (рис. 4.1.2).

Как и на рис. 4.1.1, координаты каждой точки на рис. 4.1.2 (например, координаты точек А, В, С, Д М) представляют собой величины критериев г/, и у₂ для некоторой альтернативы из множества X. По здесь, если ЛПР стремится достичь наибольшего значения обоих критериев г/, и у₂, т. е. требуется их максимизация, то нетрудно догадаться, что для ЛПР представляют интерес лишь все альтернативы с образами из отрезка ВС границы заштрихованной области Y, расположенными, как и на рис. 4.1.1, правее и выше всех остальных вариантов. Иными словами, при выборе наилучшего решения ЛПР может убрать из рассмотрения все остальные альтернативы с векторными оценками из заштрихованной области Y и выбирать только точки отрезка ВС. В данном случае сужение множества альтернатив, само собой разумеющееся при взгляде на рис. 4.1.2, тем более (по сравнению с рис. 4.1.1) перестает быть очевидным в случае критериальных пространств более высоких размерностей п или же для более сложных множеств альтернатив X.

Обратите внимание!

Приведенные выше примеры показывают важность сужения множества возможных оценок Y. Если в примере 4.1.1 выбор из четырех альтернатив становится значительно проще, чем первоначальный выбор из 10 вариантов, то во втором — не просто уменьшается число альтернатив, но происходит качественное преобразование первоначальной области У с конечной площадью в отрезок кривой линии, имеющий нулевую площадь.

• [1] Дискретное множество альтернатив Пусть множество решений X конечно (Х= {xvx2, …, х"}). Например, такая ситуация может возникнуть, если имеется несколько (п = 10) вариантов приобретаемого товара, представленных проектов и т. п.
• [2] Для обобщения этих примеров на случай произвольных множеств альтернатив X и возможных оценок Y необходимо математически формализовать понятие предпочтения ЛПР. Определение Альтернативы х? и хк называются удовлетворяющими отношению строгогопредпочтения, если из пары решений хи хк ЛПР всегда выбирает (отдаетпредпочтение) первому из них, считая его лучшим (более эффективным).Обозначение: х} > хк.