close

Вход

Забыли?

вход по аккаунту

?

Вероятностно-лексикографический максимин для многокритериальных задач принятия решений в условиях риска при наличии количественной информации о важности критериев.

код для вставкиСкачать
Методическое обеспечение
В.В. Подиновский
УДК 519.816
Вероятностно-лексикографический
максимин для многокритериальных
задач принятия решений в условиях
риска при наличии количественной
информации о важности критериев
В статье представлено решающее правило, реализующее принцип максимина для
многокритериаль-ных задач принятия решения, когда известно распределение вероятностей
значений неопределенного фактора и имеются количественные оценки важности критериев.
Ключевые слова: многокритериальные задачи принятия решений, вероятностная неопределенность, принцип максимина, теория важности критериев.
PROBABILISTIC LEXICOGRAPHIC MAXMIN PRINCIPLE FOR MULTIPLE CRITERIA
DECISION MAKING PROBLEMS UNDER RISK WHEN THE QUANTITATIVE
INFORMATION ABOUT THE CRITERIA IMPORTANCE IS GIVEN
This paper presents the decision rule implementing the maximin principle for multiple criteria
decision-making problems, when the probability distribution of an uncertain factor’s values is known
and quantitative estimates of the criteria importance are given.
Keywords: multiple criteria decision making problems, probabilistic uncertainty, maxmin principle,
criteria importance theory.
Введение
Принцип максимина, или принцип наилучшего гарантированного результата, согласно которому при анализе решений в условиях неопределенности следует ориентироваться на учет наиболее неблагоприятных значений неопределенного фактора, является одним
из основных в теории принятия решений и ее приложениях [1–5]. Развитием этого принципа на случай
принятия решений в условиях риска (когда известно распределение
вероятностей значений неопределенного фактора) является принцип
вероятностно-лексикографического
максимина [6, 7].
В данной статье представлено решающее правило, реализующее принцип вероятностнолексикографического
максимина
для многокритериальных задач принятия решения в условиях риска,
в которых имеется точная количеОткрытое образование  5/2012
ственная информация о важности
критериев, определяемая согласно
теории важности критериев [8, 9].
Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (грант № 10-01-00371)
и Международной научно-учебной
лаборатории анализа и выбора решений (исследование осуществлено в рамках программы фундаментальных исследований НИУ ВШЭ
в 2012 году).
1. Математическая модель
проблемной ситуации
Математическая модель ситуации принятия индивидуального решения, принимаемая в теории важности критериев, выглядит так:
M = <X, N, f, Y, P>,
где X – множество стратегий (планов,
альтернатив, вариантов решений) x;
N – модель неопределенного фактора,
в состав которой входит область Λ его
значений (множество «состояний природы») λ;
f = (f1, …, fm) – векторный критерий, где
fi: X × Λ → Y0 – частные, или локальные, критерии;
Y0 – (общая) область значений критериев, или множество шкальных оценок
(критерии однородны и имеют общую
шкалу);
Y0m – множество векторных оценок, или
область значений векторного критерия f;
P – модель предпочтений.
Векторный критерий f = (f1, …, fm)
служит для характеристики исхода, к которому приводит стратегия
x ∈ X, если неопределенный фактор
принимает значение λ ∈ Λ. Предполагается, что векторная оценка
y = f(x, λ) полностью характеризует
исход для ситуации (x, λ). Далее будем полагать, что множество Λ конечно: Λ = {λ1, …, λτ}, где τ ≥ 2. Тогда оказывается удобным характеризовать стратегию x ∈ X кортежем
z(x) = < f(x, λ1), …, f(x, λτ) >
11
Методическое обеспечение
В.В. Подиновский,
д.т.н., профессор
Тел.:8 (495) 621-13-42
E-mail: podinovski@mail.ru
Национальный исследовательский
университет «Высшая школа
экономики»
http://www.hse.ru
и ввести в рассмотрение множество Z всех кортежей z = (z1, …, zτ),
элементами zt которых являются
векторные оценки y ∈ Y.
Модель предпочтений P служит для формализованного описания предпочтений лица, принимающего решение (ЛПР). Примем,
что на множестве Z существует отношение нестрогого предпочтения
ЛПР, обозначаемое RZ: z′RZ z″ означает, что кортеж z′ не менее предпочтителен, чем z″. Отношение RZ
порождает отношения предпочтения RZ и безразличия IZ: соотношение z′IZ z″ верно, когда справедливо z′RZ z″ и z′RZ z″, а z′RZ z″ выполняется тогда, когда z′RZ z″ верно,
но z″RZ z′ неверно. Предполагается, что отношение RZ есть квазипорядок (т.е. оно рефлексивно и транзитивно). Это отношение неизвестно и подлежит восстановлению на
основе информации о предпочтениях ЛПР и отношении его к риску
и представлениях ЛПР о неопределенном факторе.
Решающим называется правило,
которое на основе накопленной информации Σ указанного содержания
вводит на множестве кортежей Z отношение нестрогого предпочтения
RΣZ – квазипорядок, вложенный в
RZ, т.е. удовлетворяющий условиям:
RΣZ ⊆ RZ и PΣZ ⊆ PZ. Отношение
RΣZ индуцирует на множестве стратегий X отношение нестрогого предпочтения RΣZ: x′RΣZx″ ⇔ z(x′)RΣZ z(x″).
Отношение RΣZ может быть использовано для формирования решения
исходной многокритериальной задачи.
2. Сведения из теории
важности критериев
Приведем сведения из теории важности критериев, необходимые для даль-нейшего изложения [10–12]. Далее полагается, что
Z0 = {1,…, q}, q ≥ 2. Считается, что
каждый из критериев независим по
предпочтению от остальных и его
большие значения предпочтительнее меньших, так что если v(k) –
(неизвестная) ценность шкальной
оценки k ∈ Z0, то v(1) < … < v(q).
Если о величинах v(k) известно
лишь, что они удовлетворяют указанным неравенствам, то шкала
критериев является порядковой.
12
Точная полная количественная
информация о важности критериев Θ позволяет получить значения
степеней превосходства в важности
hij для любой пары критериев fi и fj.
Положительные числа β1, …, βm, такие, что hij = βi/βj, называются величинами важности критериев. Они
определяются с точностью до положительного множителя. Если их
сумма равна единице, то они называются коэффициентами важности
и обозначаются αi.
Если предположить, что все
положительные числа hij являются рациональными, то информация Θ порождает N-модель, где
N = (n1,…, ni,…,nm), причем hij =
= ni/nj. Натуральные числа ni могут играть роль величин важности,
а после нормализации (деления на
n = n1 + … + nm) – роль коэффициентов важности. Каждой исходной
векторной оценке y соответствует
N-оценка yN, полученная повторением каждой ее компоненты ni раз:
y N ( x) = ( y1 ( x), ... , y1 ( x), y 2 ( x), ... , y 2 ( x), ... ,
n1
n2
y ( x), ... , y m ( x)).
m
nm
Все компоненты N-оценки рассматриваются как значения n равноважных критериев. Отношение
нестрогого предпочтения RΘY, порождаемое информацией Θ на множестве векторных оценок Y, задается следующим образом:
y ′RYΘ y ′′ ⇔ y↑′ N ≥ y↑′′ N .
(1)
Здесь и далее под a↑ = (a(1),…,a(n))
понимается вектор, полученный из
вектора a = (a1,…,an) упорядочением его компонент по неубыванию.
Например, (3,4,1,3)↑ = (1,3,3,4). Неравенства для векторов понимаются как покомпонентные.
В том случае, когда все критерии равноважны (такая информация обозначается S), решающее
правило записывается непосредственно для векторных оценок:
y ′RYS y ′′ ⇔ y↑′ ≥ y↑′′.
(2)
Дополнительная к S информация о том, что уменьшение меньших значений одних критериев
не компенсируется увеличением
бóльших значений других критериев, используется симметрическилексикографическим [10], или лекОткрытое образование  5/2012
Методическое обеспечение
симинным, [13] решающим правилом, задающим на Y отношение нестрогого предпочтения лексикографического типа RY Slex:
y ′RYSlex y ′′ ⇔ y↑′ ≥ lex y↑′′ ⇔
⇔ (y′(1) > y′(1)) ∨ ((y′(1) = y″(1)) ∧ (y′(2) =
= y″(2))) ∨ … ∨ (y′(i) = y″(i), i = 1 ..., m). (3)
Решающее правило (3) в определенном смысле соответствует
принципу гарантиро-ванного результата.
3. Решающее правило
вероятностнолексикографического
максимина
Предположим, что получена
полная точная количественная информация о важности критериев Θ и известен закон распределения вероятностей значений неопределенного фактора, т.е. этот фактор является случайной величиной λ̃ с заданной функцией распределения F. Допустим вначале, что
λ̃ является дискретной случайной
величиной: известны вероятности
Pr(λt) = pt её значений из множества
Λ = {λ1,…,λt,…,λτ}, причем pt = lt /l,
где lt – натуральные числа, l = l1 +
+ … + lτ. Пусть p = (p1, …, pτ) и
L = (l1,…,lτ). Используя терминологию из теории принятия
многокрите-риальных решений в
условиях риска [12], можно сказать, что каждая стратегия x представляется лотереей, в которой выигрыш y(x, λ1) имеет вероятность
p1, выигрыш y(x, λ2) – вероятность
p2, и т.д.
Приняв известную аксиому о
дроблении [6], заменим множество Λ
множеством ΛL = { λ11 ,..., λ1l1 ,..., λτ1 ,..., λτlτ }
и вместо λ̃ будем рассматривать
случайную величину λ̃L с равновероятным распределением на
ΛL: вероятность любого значения
из ΛL равна 1/l. Примем допущение о том, что предпочтения между двумя лотереями зависят только от маргинальных, или частных,
распределений вероятностей, присущих этим лотереям. (Это свойство в теории ожидаемой многокритериальной полезности называется аддитивной независимостью [12].)Теперь можно ввести в
рассмотрение NL-модель с nl равноважными критериями, поставив
Открытое образование  5/2012
в соответствие каждой стратегии x
её NL-оценку:
y NL ( x) = ( y N ( x, λ1 ), ..., y N ( x, λ1 ), ...,
l1
τ
y ( x, λ ), ..., y N ( x, λτ ))
N
lτ
(для краткости записи вместо компонент N-оценок yN(x,λt) записаны
сами N-оценки).
Если для сравнения стратегий при помощи их NL-оценок
воспользоваться симметрическилексикографическим решающим
правилом, то придем к следующему решающему правилу, порождающему на X отношение нестрогого
предпочтения – полный (связный)
квазипорядок R XΘFSlex :
x′RΘXFSlexx″ ⇔ y↑ NL(x′) ≥ lex y↑ NL(x″) ⇔
⇔ (y(1N)L(x′) > y(1N)L(x″)) ∨ ((y(1N)L(x′) =
= y(1N)L(x″)) ∧ (y(2N)L(x′) > y(2N)L(x″))) ∨
∨ (y(sN)L(x′) = y(sN)L(x″), s = 1 ..., nl). (4)
Решающее правило (4) является основой нового принципа
вероятностно-лексикографического
максимина, согласно которому все
стратегии оказываются сравнимыми по отношению RΘXFSlex, а оптимальной следует считать стратегию x*, которая является наибольшей по этому отношению, т.е. такую, что x*RΘXFSlexx верно для любой
стратегии x ∈ X.
4. Другие формы решающего
правила и его вероятностная
интерпретация
Введем следующие обозначения для k = 1, …, q:
nkN ( x, λt ) =
ni – число компо-
∑
i: yi ( x ,λt ) = k
нент в векторе yN(x,λt), равных k;
nkNL ( x) =
∑
τ
× nkN ( x, λt )) – число компонент в векторе yNL(x), равных k;
k
n≤NL
n NL ( x) – число комk ( x) =
j =1 j
понент в векторе yNL(x), не превосходящих k.
Пусть nNL(x) = (n1 NL(x), ..., nq NL(x)).
Отношение RΘXFSlex можно задать, согласно [4], и следующим образом:
(l
t =1 t
∑
x′RΘXFSlexx″ ⇔ nNL(x′) ≤ lex nNL(x″) ⇔
⇔ (n1 NL(x′) < n1 NL(x″)) ∨ ((n1 NL(x′) =
= n1 NL(x″)) ∧ (n2 NL(x′) < n2 NL(x″))) ∨ ...
∨ (nk NL(x′) = nk NL(x″), k = 1 ..., q). (5)
Обозначим суммарную важность градации k в yN(x,λt) – векторной оценке варианта x при λ = λt,
рассчитанную при помощи коэффициентов важности критериев,
через α=k(x,λt):
α = k ( x, λt ) =
=
∑
αi
i: yi ( x , λt ) = k
=
ni 1 N
= nk ( x, λt ).
n
n
i: y ( x , λt ) = k
∑
i
Разделив в (5) обе части каждого равенства и неравенства на nl,
перепишем (5) так:
x′R XΘFSlex x′′ ⇔
⇔ 

∑
τ
p α ( x′, λt )
t =1 t =1
<
∑ p α ( x′′, λ )  ∨
τ

∨   ∑ p α ( x′, λ ) =

τ
<
t =1 t =1
t
t =1 t =1
=
∑
t
τ
∧ 

p α ( x′′, λt )  ∧
t =1 t =1

∑
τ
p α ( x′, λt )
t =1 t = 2
<

p α ( x′′, λt )   ∨
t =1 t = 2

τ
p α ( x′, λt ) =
t =1 t = k
∑
∨ … ∨  ∑

= ∑ pα
<
τ
τ
k = 1, ..., q . (6)

Если α=k(x,λt) принять за условную вероятность выбора компоненты векторной оценки y(x,λt), равной
k, при λ = λt, то, согласно формуле
полной вероятности, величина
( x′′, λt ),
t =1 t = k
∑
τ
p α ( x, λt )
t =1 t = k
=
~
= Pr[ y ( x,λ ) = k ] = p= k ( x)
есть вероятность того, что из всех
векторных оценок, соответствующих варианту x, будет выбрана компонента, равная k (т.е. вначале реализуется значение λt случайной величины λ̃, а затем с вероятностью αi
выбирается i-я компонента векторной оценки y(x,λt), i = 1, …, m).
Введем обозначение: p=(x) =
= (p=1(x), ..., p=τ(x)). Теперь решающее правило (6) можно сформулировать следующим образом:
x′RΘXFSlexx″ ⇔ p=(x′) ≤ lexp=(x″) ⇔
⇔ (p=1(x′) < (p=1(x″)) ∨
∨ ((p=1(x′) = p=1(x″)) ∧ p=2(x′) < p=2(x″)) ∨
∨ ... ∨ (p=k(x′) = (p=k(x″), k = 1, ..., q). (7)
13
Методическое обеспечение
Примечание 3. Если к многокритериальной задаче принятия
решения в усло-виях полной неопределенности применить принцип недостаточного основания,
то все состояния природы следует считать равновероятными. Далее, при наличии количественной
информации о важности критериев можно применить предложенный выше принцип вероятностнолексикографического максимина.
5. Сравнение с известным
принципом вероятностнолексикографического
максимина
Для сравнения предложенного
принципа вероятностно-лексикографического максимина с известным [6, 7] рассмотрим следующий
Пример. В трехкритериальной задаче X = {x1, x2, x3}, Z0 = {1,
2, 3}. Количественная информация
о важности критериев Θ порождает N-модель с N = (3, 2, 2), так что
n = n1 + n2 + n3 = 7. Коэффициенты важности α1 = 3/7, α2 = α3 = 2/7.
Таблица
Стратегии
Примечание 1. Решающее правило в форме (7) можно принять за
определение RΘXFSlex для произвольной случайной величины λ̃ (т.е. с
любым множеством возможных значений Λ и законом распределения вероятностей на нём) и произвольных
(не обязательно рациональных) величинах важности критериев.
Примечание 2. Условие конечности шкалы критериев снимается, если обра-титься к общей формулировке [12] отношения RΘ, т.е. при
сравнении двух стратегий x′, x″ вместо Z0 = {1, …, k, …, q} использовать
множество Z0(x′, x″), составленное из
компонент их векторных оценок:
Z0(x′, x″) = {y1(x′)} ∪ … ∪ {ym(x′)} ∪
∪ {y1(x″)}∪ … ∪ {ym(x″)}.
Значения случайной
величины λ̃
Векторные оценки y↑N L(x);
векторы nNL(x) = (n1 NL(x), (n2 NL(x), (n3 NL(x))
λ1
λ2
x′
(2,1,3)
(2,1,1)
(1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,3,3,3,3); (8,9,4)
x″
(1,2,2)
(2,3,1)
(1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,3,3); (8,11,2)
Множество состояний природы
Λ = {λ1, λ2}, вероятности Pr(λ1) =
= p1 = ⅔, Pr(λ2) = p2 = ⅓; L = (2,1).
Значения векторных оценок y(x, λ)
для двух стратегий приведены в таблице:
Согласно (4) и (5) верно x′RΘXFSlexx″.
Проанализируем задачу при
помощи
известного
принципа
вероятностно-лексикографического
максимина [6, 7] для рассматриваемой задачи. Согласно этому принципу при сравнении двух стратегий
надо сопоставить соответствующие
им худшие исходы и считать более предпочтительной ту из стратегий, для которой такой исход предпочтительнее; при безразличии худших исходов предпочтительнее считать ту из стратегий, для которой вероятность получения худшего исхода меньше, и т.д. Применяя решающее правило (3) к yN(x, λ) , получим:
N
2
y↑N ( x′, λ1 ) RYSlex
N y↑ ( x ′, λ ),
N
1
y↑N ( x′′, λ2 ) RYSlex
N y↑ ( x ′′, λ ) .
N
2
Поскольку y↑N ( x′′, λ1 ) RYSlex
N y↑ ( x ′, λ ) ,
то стратегия x″ предпочтительнее,
чем x′. Заметим, что здесь использовать вероятности не потребовалось.
Проведенный анализ приводит
к следующему выводу: если задача является уникальной – выбранная стратегия будет использоваться всего один раз, – то выбирать
следует x″: она обеспечивает лучший гарантированный уровень.
Если же задача является повторяющейся достаточно большое число
раз, то лучше выбрать x′: для обеих стратегий среднее число единиц
в N-оценках полученных исходов
(или в векторных оценках с учетом
относительной важности их компонент) будет одинаково (и равно 8),
но среднее число двоек для x′ будет
меньше, чем для x″ (9 < 11).
Заключение
В статье предложен новый
принцип
вероятностнолексикографического
максимина, или наилучшего гарантированного результата, для случая, когда имеются точные оценки важности критериев с порядковой шкалой. Дано несколько форм задания отношения нестрогого предпочтения согласно этому принципу и его вероятностная интерпретация. Показано, что применение
этого принципа к многокритериальным задачам может приводить
к результатам, отличным от результатов, получаемых при помощи
известного принципа вероятностнолексикографического максимина.
Предложенный принцип представляется перспективным для
применения в повторяющихся задачах, когда выбранная стратегия
реализуется многократно.
Литература
1. Льюс Р., Райфа Х. Игры и решения. Введение и критический обзор: Пер с англ. – М.: ИЛ, 1961.
2. Гермейер Ю.Б. Введение в теорию исследования операций. – М.: Наука, 1971.
3. Maskin E. Decision-making under ignorance with implications for social choice // Theory and Decision. 1979. V.
11. P. 319–337.
4. Подиновский В.В. Принцип гарантированного результата для частичных отношений предпочтения // Журнал вычислительной математики и математической физики. – 1979. – №6. – С. 1436–1450. Английский перевод:
Podinovskii V.V. The principle of guaranteed result for partial preference relations. USSR Computational Math-ematics
and Mathematical Physics. 1980. V. 19. P. 77–90.
5. Blume, L., Brandenburger, A., Dekel, E. An overview of lexicographic choice under uncertainty // Annals of
Operations Research. – 1989. – V. 19. – P. 231–246.
14
Открытое образование  5/2012
Методическое обеспечение
6. Подиновский Вик. В. Критерий вероятностно-лексикографического максимина // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. – 1983. – №2. – С. 33–38. Английский перевод:
Podinovski Vic. V. The probabilistic-lexicographic maximin criterion. Moscow University Computational Mathematics
and Cybernetics. – 1983. – №2. – P. 39–45.
7. Подиновский Вик. В. Лексикографический подход к принятию решений в условиях неопределенности //
Программное обеспечение вычислительных комплексов. – М.: Изд-во МГУ, 1985. – С. 104–119.
8. Подиновский В.В. Введение в теорию важности критериев в многокритериальных задачах принятия решений: Учебное пособие. – М.: Физматлит, 2007.
9. Подиновский В.В., Потапов М.А. Важность критериев в многокритериальных задачах принятия решений:
теория, методы, софт и приложения // Открытое образование. – 2012. – №2. – С. 55–61.
10. Подиновский В.В. Многокритериальные задачи с однородными равноценными критериями // Журнал вычислительной математики и математической физики. – 1975. – №2. – С. 330–344. Английский перевод: Podinovskii
V.V. Multicriterial problems with uniform equivalent criteria. USSR Computational Mathematics and Mathematical
Physics. – 1975, V. 15. – №2. – P. 47–60.
11. Podinovski V.V. The quantitative importance of criteria for MCDA // Journal of Multi-Criteria Decision Analysis.
– 2002. – V. 11. – P. 1–15.
12. Подиновский В.В. Количественная важность критериев // Автоматика и те-лемеханика. – 2000. – №5. – С.
110–123.
13. Vilkas E. An axiomatic definition of the leximin // European Journal of Political Economy. – 1986. – V. 2/4. – P.
455–463.
14. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения: Пер. с англ. –
М.: Радио и связь, 1981.
Открытое образование  5/2012
15
1/--страниц
Пожаловаться на содержимое документа