Методы поддержки принятия решений в условиях определенности

Пусть заданы критерии K₁,…,K_n; X = { x | x = (x₁,…,x_n) } – множество векторных оценок вариантов по этим критериям. Как уже говорилось, числовая функция f: X →R, называется функцией полезности (ценности, предпочтительности), если она обладает следующим свойством: f(x)≥f(y) ⇔ xRy.

Если известна функция полезности, то поиск оптимального варианта сводится к задаче нахождения x* = arg max f(x), x∈X – аргумента максимума функции полезности на множестве X.

Как найти функцию полезности? Методы построения функции полезности делятся на эвристические и аксиоматические.

К эвристическим методам можно отнести метод главного критерия и метод обобщенного критерия.

Метод главного критерия сводится к оптимизации по одному выбранному критерию, который объявляется главным, при условии, что остальные критерии не больше (или не меньше) приемлемых значений.

Метод обобщенного критерия заключается в свёртке набора критериев в числовую функцию, которая и будет являться функцией полезности.

Виды свёрток:

1) аддитивная свёртка: f(x) = α ₁K₁(x)+…+α_nK_n(x);

2) мультипликативная свёртка: f (x) =K₁^α1 *...*K₁^α1 ;

3) приведенная свёртка: f(x) = min(Ki(x)/α _i) по всем i=1, …, n (или f(x) = max(K_i(x)/α_i) по всем i=1, …, n).

Взаимная независимость критериев и аддитивная функция ценности

Аксиоматические методы построения функции полезности – это формальные методы, основанные на том, что формулируются специальные предположения (аксиомы) о свойствах предпочтения, выполнение которых гарантирует существование функции полезности конкретного вида.

Обычно, при использовании таких методов функцию полезности строят в аддитивном виде – как сумму функций полезности по каждому критерию с некоторыми весовыми коэффициентами α ₁,…, α _n
f(x ₁, ...,x_n)=∑ _i=1 ⁿα_if_i(x_i) ,         (4.1)
где f_i – функция полезности критерия K_i.

Введем несколько определений и обозначений.

Пусть K_I ⊂ K = {K₁,…,K_n} – подмножество Ī, т.е. группа критериев с номерами I = {i₁,…,i_m} из множества {1,…,n}. Обозначим через Ī множество {1,…,n}\I, тогда KĪ – множество всех критериев, не вошедших в I. Векторную оценку x будем записывать в виде (x_I,x_Ī).

Говорят, что критерии K_Iне зависят по предпочтению от критериев K_Ī, если предпочтения для любых двух векторных оценок x = (x_I,x_Ī) и x’ = (x_I’,x_Ī), содержащих одинаковые компоненты с номерами из Ī, не зависят от самих значений этих компонент.

Пример 4.1. Поясним введенные обозначения. Пусть n=5, I={1,3,4}, Ī={2,5}.

x = (7,1,2,8,2) = (x_I,x_Ī), где x_I = (7,2,8),x_Ī = (1,2).

y = (4,1,8,3,2) = (y_I,y_Ī), где y_I = (4,8,3), y_Ī= (1,2).

Таким образом, x_Ī = y_Ī.

Если критерии K_I не зависят по предпочтению от критериев K_Ī и векторная оценка x предпочтительнее, чем векторная оценка y, то и, например, векторная оценка x₁ = (7,4,2,8,5) будет предпочтительнее, чем y₁ = (4,4,8,3,5), потому что их значения по критериям из группы K_I совпадают с соответствующими значениями оценок x и y, а оценки по остальным критериям одинаковые. Таким образом, вместо x_Ī=y_Ī=(1,2) можно подставить любую оценку (a,b) и предпочтение сохранится: (7,a,2,8,b) предпочтительнее, чем (4,a,8,3,b).

Пример 4.2. Поясним понятие зависимости критериев на следующем примере. Рассмотрим задачу принятия решения, в которой лицом, принимающим решения, является группа туристов-байдарочников. Их цель – выбрать место для стоянки. Они оценивают место предстоящей стоянки по трем критериям: К₁ – наличие дров (шкала критерия {«много», «мало»}), К₂ – качество места для купания (шкала критерия {«хорошее», «плохое»}), К₃ – наличие комаров (шкала критерия {«много», «мало»}). В этом примере множество критериев {K₁,K₂} зависит от оставшихся критериев, т.е. от множества {K₃}, т.к. вполне вероятно, что вариант с векторной оценкой x=(«много», «плохое», «много») окажется предпочтительнее варианта с векторной оценкой y=(«мало», «хорошее», «много»), т.к. наличие большого количества комаров обесценивает качество купания и добавляет весомости критерию «наличие дров». Однако если значение оценки по критерию K₃ изменится, то скорее всего, изменятся и предпочтения ЛПР – вариант с векторной оценкой y’=(«мало», «хорошее», «мало») окажется предпочтительнее варианта с векторной оценкой x’=(«много», «плохое», «мало»). Чтобы добиться независимости критериев необходимо иначе их сформулировать. Критерий K₂ сформулируем как «возможность комфортного купания». Тогда критерии будут независимы.

Критерии K₁,…,K_n такие, что любой набор K_I из них не зависит по предпочтению от остальных критериев K_Ī, называются взаимно независимыми по предпочтению.

Теорема Дебре (критерий существования аддитивной функции полезности). Функция полезности может быть задана в аддитивном виде (4.1) тогда и только тогда, когда критерии K₁,…,K_n взаимно независимы по предпочтению (при n≥ 3).

При n=2 кроме взаимной независимости критериев требуется выполнение условия соответственных замещений (при n≥ 3 оно выполняется автоматически): Для любых x₁, x₂, y₁, y₂, a, b, c, d, если (x₁, x₂) I (x_1-a, x_2+b) и (x₁, y₂) I (x_1-a, y_2+c), то (y₁, x₂) I (y_1-d, x_2+b) и (y₁, y₂) I (y_1-d, y_2+c). То есть если увеличение на b и c разных значений x₂ и y₂ критерия K₂ при некотором опорном значении x₁ критерия K₁ компенсируется одним и тем же уменьшением этого значения x₁ критерия K₁, то такие же увеличения b и c тех же значений x₂ и y₂ критерия K₂ сохраняются и при любом другом опорном значении y₁ критерия K₁ (см. рис. 4.1).

Рис. 4.1. Условие соответственных замещений.

                                                                                                                Рис.4.1. Условие соответственных замещений

Как осуществляется проверка взаимной независимости критериев по предпочтению?

Непосредственно по определению проверить независимость критериев затруднительно, т.к. даже при небольших n возникает большое число наборов критериев, которые надо сравнить. Однако результаты, полученные Леонтьевым и Горманом, позволяют существенно облегчить проверку. Сформулируем один из них.

Утверждение (Леонтьев-Горман). Если любая пара критериев {K_i, K_j} не зависит по предпочтению от остальных (n-2) критериев, то все критерии K₁,…,K_n взаимно независимы по предпочтению.

Таким образом, проверка сводится к установлению независимости только каждой из пар критериев от всех остальных критериев.

На практике для проверки на независимость по предпочтению наборов K_I и K_Ī можно поступить следующим образом. Берём набор x_Ī+ наилучших (явно хороших) значений K_Ī и подбираем (запрашиваем у ЛПР) два разных набора x_I' и x_I'' таких, что (x_I', x_Ī+) I (x_I'', x_Ī+). Затем берём набор x_Ī– самых плохих оценок и спрашиваем у ЛПР, сохранилось ли безразличие (x_I', x_Ī) I (x_I'', x_Ī). Если нет, то критерии K_I зависят от критериев K_Ī. Если да, повторяем процедуру еще для некоторых других x_I' и x_I''. Если по-прежнему безразличие имеет место, задаём вопрос в общем виде (сохранится ли безразличие при любых наборах). Если да, то наборы критериев K_I и K_Ī независимы.

Рассмотрим два метода построения аддитивной функции полезности для n=2.

1. Шаговый метод совместного шкалирования

Пусть условие соответственных замещений выполнено. Функцию ценности в соответствии с теоремой Дебре будем искать в виде

                                                                                                                        f(x₁ ,x₂ ) = f₁ (x₁ ) + f₂ (x₂ ).

Обозначим диапазоны изменения оценок x₁ и x₂: x₁* ≤ x₁ ≤ x₁*, x₂* ≤ x₂ ≤ x₂*.

Полагаем f(x₁*,x₂*) = f₁(x₁*) = f₂(x₂*) = 0 (начало отсчета).

Берем любое значение x₁¹ > x_1*, достаточно близкое к нему. Устанавливаем f₁(x₁¹) = 1 (единица измерения).

От ЛПР требуем указать значение x21 такое, что (x11, x2*) I (x1*, x21), для этого значения также f1(x21) = 1.

Затем у ЛПР запрашиваем значения x₁² и x₂²такие, что:

(x₁², x_2*) I (x₁¹, x₂¹) I (x_1*, x₂²).

f(x₁¹,x₂¹) = 1+1 = 2 ⇒ f₁(x₁²) = f₂(x₂²) = 2.

Такая процедура оправдана, поскольку выполняются условия соответственных замещений.

Далее у ЛПР запрашиваем значения x₁³ и x₂³ такие, что:

                                                                                                        (x₁³, x_2*) I (x₁², x₂¹) I (x₁¹, x₂²) I (x_1*, x₂³) ⇒ f₁(x₁³) = f₂(x₂³) = 3.
Продолжив этот процесс, получаем наборы значений f₂(x_2*), f₁(x₁¹), f₁(x₁²), f₁(x₁³)… и f₂(x_2*), f₂(x₂¹), f₂(x₂²), f₁(x₂³)…, по которым с помощью интерполяции строятся функции f₁(x) и f₂(x).

2. Метод половинного деления по ценности

Метод позволяет находить функцию полезности в виде f(x₁ ,x₂ ) = α₁ f₁ (x₁ )+α₂ f₂ (x₂ ), α₁ >0, α₂ >0, α₁ +α₂ =1.

Положим f₁(x_1*) = f₂(x_2*) = 0, f₁(x_1*) = f₂(x_2*) = 1

Построим функцию f₁.

ЛПР просим указать среднюю по полезности оценку x₁^0.5 ∈ [x_1*; x₁^*], то есть такую, что изменение полезности на [x_1*; x₁^0.5] равно изменению полезности на [x1₁^0.5; x₁^*]. Устанавливаем f₁(x₁^0.5) = 0,5.

Далее аналогично получаем x₁^0.25 ∈ [x_1*; x1₁^0.5], для которой устанавливаем f₁(x₁^0.25) = 0,25 и x₁^0.75 ∈ [x₁⁰⁵; x₁^*] , для которой устанавливаем f₁(x₁^0.75) = 0,75 и т.д.

С помощью интерполяции восстанавливаем функцию f₁ по её значениям в точках x₁^0.5, x₁^0.25, x₁^0.75 и т.д.

Функция f₂ строится аналогично.

Для нахождения весового коэффициента α₁ достаточно запросить у ЛПР пару одинаковых по предпочтительности оценок (x₁^', x₂^') I (x₁'', x₂’’). Тогда f(x₁’,x₂’) = f(x₁’’,x₂’’), следовательно, α₁f₁(x₁’)+(1- α₁)f₂(x₂’) = α₁f₁(x₁’’)+(1-α₁)f₂(x₂’’), а из этого равенства уже можно выразить α₁ и α₂ = 1 – α₁.

Аксиоматическая теория важности критериев

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

Рассмотрим многокритериальную модель, в которой каждый вариант s представляется его векторной оценкой x=(x₁,...,x_n), где числоx_i – оценка варианта по критерию K_i ,n – количество критериев. Будем считать, что критерии K_i,...,K_n однородны, то есть имеют общую шкалу.

ЛПР, как правило, имеет определенные представления о сравнительной важности критериев K₁,...,K_n . Эта информация Ω составляется из сообщений о равноценности и превосходстве в важности критериев. Точный смысл этих понятий дается следующими определениями, в которых через x^r,t обозначена векторная оценка, полу¬ченная из x перестановкой компонент x_r и x_t (например, если x =(5,3,2,4), то x^1,3 =(2,3,5,4)):

- критерии K_r и K_t равноценны (это – сообщение K_r˜ K_t или же K_t ˜ K_r ) означает, что всякие две векторные оценки x и x^r,t одинаковы по предпочтительности;

- критерий K_r, важнее, чем K_t (это – сообщение K_r> K_t ) означает, что векторная оценка x , у которой x_r > x_t , предпочтительнее, чем y=x^r,t .

Таким образом, сообщение ω₀ о равноценности критериев K_r и K_t задает на n -мерном числовом пространстве Rⁿ симметричное отношение безразличия
                                                                                                                                  I^ω1: xI^ω1y ⇔ y=x^r,t ,
а сообщение ω₂ о превосходстве в важности K_r над K_t – асимметричное отношение предпочтения
                                                                                                                        P^ω2:xP^ω2y ⇔ y=x^r,t, x_r x_t

Говорят, что множество Ω информационных сообщений типа Ω₁,Ω₂ о сравнительной важности критериев непротиворечиво, если для каждой пары критериев K_r,K_t оно содержит не более одного сообщения из трех: K_r ˜ K_t , K_r > K_t или K_t > K_r .

Набор Ω информационных сообщений типа ω₁,ω₂ о сравнительной важности критериев порождает отношение нестрогого предпочтения R^Ω , определяемое как транзитивное замыкание объединения отношений I^ω и P^ω для всех ω∈Ω и отношения Парето R⁰
                                                                                                                        R^Ω= Rt[∪ _ω∈Ω R^ω∈R⁰]
(здесь символом обозначена операция транзитивного замыкания бинарного отношения,R^ω=P^ω ∪ I^ω,P^ω1=I^ω2= ∅ ). Согласно этому определению, xR^Ωy выполняется тогда и только тогда, когда существуют гипотетические варианты с векторными оценками z⁽ⁱ⁾, i=1,...,k , такие, что
                                                                                                                      x=z⁽⁰⁾R⁽¹⁾z⁽¹⁾...z^(k-1)R^(K+1)y,        (4.1)
где каждое R^(j) есть R^ω(ij) для некоторого ω^(ij)∈ Ω или R⁰ , причем xI^Ωy (xP^Ωy ) тогда и только тогда, когда все R^(j) суть I^ω(ij) или I⁰ (хотя бы одно R^(j) есть P^ω(ij) или P⁰ ). Цепочку вида (4.1) называют опорной цепочкой от x к y , а число k – ее длиной. ~f

Пример 4.3. Рассмотрим две векторные оценки x=(4, 5, 3, 2) и y=(3, 2, 4, 5). Покажем, что, если на множестве критериев K={K₁, K₂, K₃, K₄} предпочтения ЛПР описываются информацией Ω={K₁≻K₂, K₂∼K₃, K₃≻K₄}, то xR^Ωy.

Для этого построим опорную цепочку вида (4.1) от x к y. Рассмотрим гипотетический вариант с векторной оценкой z⁽¹⁾=x^2,3 =(4,3,5,2), тогда z⁽⁰⁾=xI^{f2 ∼ f3}. Аналогично z(²= x^1,2=(3,4,5,2), z⁽¹⁾ p^{f2 > f3} z². Аналогично z³= x^3,4=(3,4,2,5,), z⁽²⁾ p^{f3> f4} z³. Аналогично z⁽⁴⁾=x^2,3 =(3,2,4,5), z³I^{f2 ˜ f3} z⁴=y.

Информация Ω о сравнительной важности критериев K₁,...,K_n задает на множестве {K₁,...,K_n } бинарное отношение Q, состоящее из пар K_i ,K_j и K_j,K_i для информационных сообщений типа ω₁= K_i ˜ K_j и пар K_i ,K_j для сообщений типа ω₂ =K_i > K_j . Отношение Q является отношением предпочтения на множестве критериев. Тогда отношению R^Ω= Tr[∪ _{ω ∈ Ω}R^ω∪ R⁰] однозначно соответствует расширенный набор сообщений, кото¬рый обозначим Ω^{^} . Если Ω=Ω^{^} , то будем говорить, что информация Ω является полной. Если информация Ω не полна и содержит сообщения только типа ω₁ , то легко проверить, что в этом случае R^Ω=R^{Ω^} , если же имеются также сообщения типа ω₂ , то можно утверждать только, что R^Ω⊆ R^{Ω^} . Однако, транзитивность отношений предпочтения (в данном случае – отношения предпочтения на множестве критериев) в теории принятия индивидуальных решений по ряду известных соображений связывают с рациональностью поведения. В связи с этим расширим определение R^Ω так, чтобы отношения для неполной и полной информации совпадали:

                                                                                                                 R^Ω= Tr[∪ _{ω ∈ Ω}R^ω∪ R⁰]

Пример 4.4. Дополним информацию Ω из примера 4.3 так, чтобы отношение предпочтения Q на множестве критериев было полным: Ω^ ={K₁≻K₂, K₁≻K₃, K₁≻K₄, K₂∼K₃, K₂≻K₄, K₃≻K₄}. В этом случае для проверки того, что xR_Ωy можно указать более короткую опорную цепочку:

                                                                                        x=(4, 5, 3, 2)p^{k1 > k3} z⁽¹⁾=(3, 5, 4, 2) p^{k1 > k3} (3, 2, 4, 5) =y.

Для случаев когда информация Ω отвечает определенным требованиям известны результаты, позволяющие осуществлять проверку условия xR^Ωy , не прибегая к построению опорных цепочек (4.1) [12]. Сформулируем один из таких результатов.

Для задач с равноважными критериями (т.е. для задач, в которых информация Ω такова, что всякие два критерия равноважны) справедливо следующее утверждение. Пусть ψ(x) – вектор-функция, располагающая в порядке убывания все компоненты вектора x так, что ψ₁(x)=max x_i и ψ_n(x)=min xψ_i .

Tеорема 4.1. Если критерии K₁,...,K_n равноваж¬ны, то xR^Ω y(xP^Ωy,xI^Ωy) тогда и только тогда, когда ψ(x)R⁰ ψ(y) (соответственно ψ(x)P⁰ ψ(y) , ψ(x)I⁰ ψ(y) )).

Пример 4.5. Рассмотрим две векторные оценки x=(4, 5, 3, 2) и y=(3, 2, 4, 5). Покажем, что, если K₁∼K₂∼K₃∼K_i4, то xI_Ωy. В самом деле ψ(x)= ψ(y)=(5, 4, 3, 2), то есть ψ(x)I⁰ψ(y) , следовательноxI^Ωy .

Опишем алгоритм сравнения пары вариантов по отношению R^Ω , то есть проверки справедливости условия xR^Ω y. Он основан на переборе опорных цепочек вида
                                                                                                                        x=z⁰R⁽¹⁾z⁽¹⁾...z^(k-1)R^(k)R⁰y,          (4.2)
где z⁽ⁱ⁺¹⁾ получается из z⁽ⁱ⁾ с помощью перестановки (r t), если R⁽ⁱ⁺¹⁾ есть I^ω для ω=K_r∼K_t, и если R⁽ⁱ⁺¹⁾ есть P^ω для ω=K_r≻K_t при условии Z_r⁽ⁱ⁾ > Z_t⁽ⁱ⁾

Нетрудно видеть, что для данной пары векторных оценок x, y опорная цепочка вида (4.2) существует тогда и только тогда, когда существует опорная цепочка вида (4.1). Действительно, опорная цепочка (4.2) является частным случаем опорной цепочки (4.1). С другой стороны, по опорной цепочке (4.1) можно построить опорную цепочку вида (4.2), включая в нее лишь те R⁽ⁱ⁾, которые являются I^ω или P^ω , и последовательно совершая в векторной оценке соответствующие перестановки компонент.

Построим непротиворечивое множество Ω^={ω¹, … , ω^{l^}} , состоящее из сообщений множества Ω и сообщений, получающихся из них из соображений транзитивности отношения предпочтения на множестве критериев.

Перебор осуществляется среди опорных цепочек вида (4.2), длины не более чем n(n-2)/2, в которых каждое R^ω есть R^ω для некоторого ω∈Ω^ . Обоснование такому ограничению перебора дается в [13].

Очевидно, что все возможные опорные цепочки вида (4.2) можно получить, осуществляя обход дерева, изображенного на рисунке 4.1, и осуществляя в векторной оценке x последовательно соответствующие перестановки компонент, соответствующих вершинам-сообщениям дерева, составляющим цепь от корневой вершины до текущей. Очевидно также, что если в ходе построения одной из опорных цепочек получена векторная оценка z^I, совпадающая с векторной оценкой z⁽ⁱ⁾, i<I, то дальнейшее построение этой опорной цепочки проводить бессмысленно, так как те же векторные оценки могут быть получены из векторной оценки z⁽ⁱ⁾. В соответствии с этим построен алгоритм.

Алгоритм 4.1. Проверка условия xR^Ωy

Шаг 1. Корень дерева ω назначить текущей вершиной. Текущей вершине поставить в соответствие векторную оценку x.

Шаг 2. Сделать шаг левостороннего обхода дерева и назначить очередную вершину текущей. Если обход закончен, то выполнить шаг 6. Если текущей вершиной является вершина ω^'i (то есть, сообщение о r-том и t-том критерии), то поставить в соответствие текущей вершине векторную оценку с переставленными r-той и t-той компонентами по сравнению с векторной оценкой, соответствующей родительской вершине.

Шаг 3. Если ω^'i =Kr≻Kt и r-тая компонента текущей векторной оценки меньше t-той компоненты, то сделать текущую вершину концевой и перейти к шагу 2.

Шаг 4. Если текущая векторная оценка равна одной из оценок, соответствующих вершинам ветви дерева от корня до родительской вершины текущей вершины, то сделать текущую вершину концевой и перейти к шагу 2.

Шаг 5. Если векторная оценка, соответствующая текущей вершине, превосходит по отношению Парето оценку y, то xR^Ωy и опорной цепочкой является список соответствующих вершинам дерева от корня до текущей вершины векторных оценок (конец), иначе перейти к шагу 2.

Шаг 6. xR^Ωy не верно, конец.

                                                

                                                                                                                  Рис 4.1. Дерево алгоритма