Analysis of decision maker's preferences structure with standard aggregative functions.pdf Известно, что если структура предпочтений лица, принимающего решение (ЛПР), отвечает требованиям «рациональности», т.е. соответствует аксиоматике Эджворта-Парето, то альтернатива, выбираемая в задаче определения оптимальной на основании учета многих критериев, должна находиться в множестве Парето XP, т.е. недоминируемых по всем критериям альтернатив [1]. Таким образом, если для альтернативы a е X имеется доминирующая ее по Парето-альтернатива b е X (т.е. выполняется b ^a), то P при любом способе упорядочения альтернатива b должна занять более высокое место, чем a. Этап формулирования предпочтений ЛПР предшествует выбору оптимальной альтернативы через выбор соответствующего ей недоминируемого вектора y(x). Поэтому полученные результаты выбора могут не соответствовать интуитивным ожиданиям, которыми ЛПР руководствовался при формулировании предпочтений. Предпочтения ЛПР, представленные отношением векторного доминирования, могут быть описаны одной из трех обобщающих функций FO [3]: аддитивной АОФ, мультипликативной МОФ или максиминной функцией Гермейера mОФ [2], которые монотонны относительно этого отношения. Указанные функции используют векторный параметр w > 0, компоненты которого выражают относительную важность критериев с точки зрения ЛПР. Поставим следующую задачу. Существует ли для векторной оценки y(x), выбранной в множестве Y = F(X), Y с R", такая функция FO и такой вектор весов w (w > 0, = 1, w, e, 0 е R", e = (1, ..., 1), 0 = (0, ..., 0)), которые доставили бы указанной точке наибольшее значение скалярной обобщающей функции FO? И если да, то какая это функция и каковы компоненты w = (w1, w2, ..., w"). 1. Модель оценивания В многокритериальных задачах рассматриваются альтернативы, характеризуемые набором из " признаков, выражающихся функциями/i(x), ...,f"(x) так, что альтернативе x в соответствие ставится векторная оценка y(x) = f1(x), f2(x), ...,f"(x)), а множеству альтернатив Х - множество их векторных оценок Y (если функции f(x) числовые, то Y с R") [2]. На наборе признаков ЛПР определяет набор критериев видаf(x) ^ extr, j = 1, ..., " (этого всегда можно добиться, введя соответствующие замены на множестве признаков и требований ЛПР). После этого отношение доминирования Парето индуцируется отношением покомпонентного векторного доминирования на Y так, что Va,b е X : y(a) > y(b) ^ a >b, а множество недоминируемых векторов YP с Y образует образ XP с X. Назовем Парето-оболочкой множества Y convP(Y) множество векторных оценок из Y, которые образуют объединение множеств Парето, получаемых на Y при всех сочетаниях направлений оптимизации критериев. Точки, входящие в Парето-оболочку, принадлежат поверхности тела (необязательно выпуклого) минимального объема, заключающего в себе множество Y целиком. В простейшем случае (рис. 1) это тело может представлять собой невыпуклый многогранник, вершинами которого являются точки convP(Y). Ясно, что для любой внутренней точки y е Y \ convP(Y) при любом сочетании направлений опти- * мизации критериев найдется такая точка у* е convP(Y), что y > y . Следовательно, точка y ни при каких условиях и способах упорядочения на данном наборе критериев не может получить первое место. Рис. 1. Парето-оболочки: a - Парето-оболочка и линейная оболочка Y; b - двумерный случай использования аддитивной ОФ b a Предлагается алгоритм тестирования предпочтений ЛПР на соответствие ожидаемым им результатам выбора. Для этого ЛПР указывает произвольную альтернативу x е X. Первый тест заключается в определении потенциальной оптимальности указанной альтернативы. Чтобы альтернатива была потенциально-оптимальной, она должна принадлежать convP(Y) - Парето-оболочке множества Y, получаемой объединением 2" множеств Парето YP для всех возможных сочетаний направлений оптимизации критериев. Если y(x) g convP(Y), то ни при каком сочетании требований вида fj(x) ^ extr альтернатива x не может являться оптимальной. Следовательно, если ЛПР предполагает, что эта альтернатива оптимальна, то ему следует добавить дополнительные признаки и критерии (так как | YP | растет с увеличением "). Если y(x) е convP(Y), то имеется способ выбора указанной альтернативы х в качестве оптимальной, более того, среди указанных функций FO найдется такая, для которой можно подобрать w, делающий y(x) оптимальной. 2. Аддитивная обобщающая функция В силу линейности аддитивной обобщающей функции (АОФ) ее поверхности безразличия (изокванты) представляют собой гиперплоскости в R", подмножеством которого является Y. Поэтому АОФ может доставить наибольшее значение (при некотором конкретном векторе весов w) только тем точкам Y, которые входят в его выпуклую линейную оболочку, conv^Y), т.е. являются вершинами выпуклого многогранника минимального объема, полностью включающего в себя Y (см. рис. 1, а). Для любой конфигурации множества Y выполняется conv^Y) с convP(Y) с Y с R". В этом смысле АОФ схожа с целевой функцией стандартной задачи линейного программирования, которая всегда в качестве оптимального решения выбирает одну из вершин выпуклого многогранника или в случае перпендикулярности одной из его граней - любую из точек, принадлежащих этой грани. Рассмотрим двумерный случай. Пусть имеются две векторных оценки a и b и скалярная АОФ: FA(w; y) = , где w - вектор весов, w > 0, w-eT = 1. Чтобы векторные оценки a и b имели одинаковую оценку АОФ, необходимо, чтобы градиент АОФ был перпендикулярен прямой, проходящей через точки a и b. Так как градиент АОФ - вектор w, то это равносильно условию = 0 - скалярное произведение равно нулю. Это условие равносильно = . Заодно заметим, что по правилам матричного умножения FA(w; a) = wTa , а FA(w; b) = wTb . Следовательно, если требуется найти такой вектор w, чтобы выполнялось FA(w; a) > FA(w; b), он должен удовлетворять системе (w, a) >(w, b) Г( w,(a - b) > 0 < w > 0 , или, что равносильно: < w > 0 (w, e) = 1 [( w, e) = 1. Нарушение требования неотрицательности w сигнализирует, что для достижения векторной оценкой наибольшего значения АОФ соответствующий критерий должен минимизироваться (в исходной постановке задача неявно требует максимизации всех критериев). Иллюстрация для двумерного случая приведена на рис. 1, б. В «-мерном случае любые n векторных оценок ai, ..., an образуют в Rn гиперплоскость. Чтобы они имели одинаковые оценки АОФ FA(w; a,) = wT-a;, требуется выполнение условия (w,(a, - a.}) = 0, Vj = 1,...,N,i ф j. Следовательно, чтобы некоторая оценка a. в данной гиперплоскости имела наибольшую величину АОФ, необходимо найти вектор w, удовлетворяющий условию (w,(a, - a/) > 0, Vj = 1,., N, i ф j. В матричной форме совокупность строк ^w,(a.. - a..) = 0 имеет вид w ■ ДЛТ = 0, где ДА - матрица, строками которой являются векторы (a.. - a.). Если точка a - вершина многогранника, т.е. лежит на пересечении k граней, то для ее оптимальности достаточно взять в качестве w любой вектор, являющийся выпуклой комбинацией векторов wi1, ..., wik нормалей соответствующих граней. 3. Мультипликативная обобщающая функция Если точка лежит на грани, но не является вершиной многогранника, АОФ сможет сделать альтернативу, соответствующую этой точке, оптимальной (при w, являющемся нормалью к этой грани), но не сможет различить ее с другими точками этой грани. Для различения точек можно привлечь мультипликативную обобщающую функцию (МОФ). Например, на рис. 2, а, АОФ FA(w; y) с вектором весов w = (1/3, 2/3) присвоит одинаковые оценки точкам A, B, C и D, но любое изменение весов сделает наилучшей по АОФ точку A или D; не удастся подобрать вектор w, выбирающий B или C. Рис. 2. Изокванта МОФ: а - различающие свойства МОФ; b - логарифмическое преобразование МОФ в АОФ МОФ FM (w;y) = П ._ y,Wj может различить точки внутри грани. Например, для того же вектора X X j =1 J весов w = (1/3, 2/3) МОФ упорядочивает точки грани следующим образом: B у C у D у A. На рис. 2 в виде гипербол показаны изокванты МОФ для случая R2. Задача поиска вектора w, такого, чтобы МОФ FMw; y) в качестве наилучшей выбрала бы указанную точку у грани, сводится к уже рассмотренной выше задаче на поиск вектора w, доставляющего наибольшее значение АОФ для указанной точки логарифмированием FMw; y): In(FM (w;y)) = In(ПП=ij ) = ХП_W • ln(yj) = fc^y)) . В множестве логарифмированных оценок 1п(У) точки A, B, C и D перестанут лежать на одной грани, а образуют выпуклую поверхность, как показано на рис. 2, b. Следовательно, можно решить задачу о подборе вектора весов, находящегося внутри конуса, образованного нормалями граней, пересекающихся в указанной вершине (например, вектор w = (1/3, 2/3), доставляющий наибольшее на грани значение МОФ для точки B и изображенный штрих-пунктирной линией, находится внутри конуса, образованного нормалями для граней AB и BC, пересекающихся в точке B). 4. Максиминная обобщающая функция (тОФ) МОФ не может ни при каком векторе w сделать лучшей точку, лежащую в области convp(T) \ convey) ниже изокванты МОФ, проходящей через вершины соответствующей грани линейной оболочки convi(y). Однако это может сделать максиминная функция Fm(w, y) = minj=i _ n {jj-wj}, способная в качестве лучшего выбрать любой недоминируемый вектор - как находящийся выше, так и ниже максимальных на У изоквант FA и FM [4]. Это связано с тем, что у этой ОФ самая нелинейная форма изокванты, представляющая собой поверхность прямоугольного конуса, направленного противоположно конусу доминирования точки. Наилучшее место получает точка, расположенная на наиболее удаленной от начала координат линии уровня. Для определения вектора w можно провести вектор w' из начала координат непосредственно в интересующую точку. Он всегда будет внутри конуса предпочтения этой точки по тОФ. Назовем его вектором «квази»-весов, потому что для предпочтения выбранной точки по тОФ надо взять вектор w, являющийся одной из перестановок w'. Для двумерного случая w будет вектором w', отраженным относительно главной диагонали, а в случае размерности пространства n > 2 таких векторов потенциально оказывается (n! - 1). Заключение Таким образом показано, что тип используемой для выбора оптимального решения функции определяется местоположением y(x) в оболочке У: если y(x) econvp(y) n convey), то можно использовать АОФ, если ln(y(x)) е conv^(ln(y)) n conv^(ln(y)), то можно использовать МОФ, а в противном случае - максиминную функцию. При y(x) е conv^(y) можно определить пару , позволяющую сделать указанную ЛПР альтернативу x оптимальной. При этом ЛПР имеет возможность провести тест предпочтений с указанием своего вектора w или с указанным им порядком предпочтения на множестве критериев, порождающем семейство векторов {w}, компоненты которых удовлетворяют заданному отношению порядка. В этом случае проверяется, могут ли указанные предпочтения быть описаны одной из трех типовых FO. Если такое описание возможно, считается, что структура предпочтений ЛПР пред-ставима типовой обобщающей функцией. Если же подобное описание противоречит предпочтениям ЛПР, то он имеет возможность как скорректировать свои предпочтения, заменив w на автоматически определенный, так и использовать другой способ решения. В предельном случае с согласия ЛПР осуществляется автоматическая настройка предпочтений под требуемый результат, т. е. в результате указания оптимизируемой альтернативы x ЛПР получает автоматическую настройку задачи выбора, гарантирующую оптимальность указанной альтернативы. Предлагается следующий алгоритм исследования предпочтений ЛПР: 1. Поиск оболочки Парето и линейной выпуклой оболочки convP(Y) и convL(Y) для облака векторных оценок Y. 2. Проверка возможности сделать выбранную ЛПР точку наилучшей и при утвердительном ответе - поиск подходящей ОФ и вектора весовых коэффициентов: a. Если точка входит в Y \ convP(Y), она не может стать наилучшей. b. Если точка входит в convP(Y) \ convL(Y), она может стать наилучшей при использовании тОФ. c. Если точка входит в convL(Y) и является вершиной, она может стать наилучшей, причем имеется аналитический способ определения направлений оптимизации и вектора w для АОФ. d. Если точка входит в convL(Y), но не является вершиной, то сделать ее первой среди вершин ее грани сможет МОФ, причем имеется аналитический способ определения направлений оптимизации и вектора w.

Скачать электронную версию публикации