Козлов В.Н. Системный анализ и принятие решений

(

)

(

)

(

)

(

)

()

, \

,,

G

LL

ij

LQ

ij U U

ij adij

∈

+→

∑

()

,\

.

ij

ij UU

ad

ϕϕ

∈

∑

(7)

min

5). ним к приводит

ам вида:

минимаксная

моде

Ми а сная аппроксимация к

оптимизационным задач

()

,\

max min.

G

L

ij

LQ

ij UU

a

∈

→

(8)

Соответствующим образом формулируется

ль неравномерного типа:

()

(

)

,\

max , in.

G

L

ij

Q

ij U

ad i j

∈

→

Конкретные задачи аппрокс алогичные задачам (6) – (9),

будут рассматриваться далее

5. Методы линейного упорядочения ассмотрим н

модели ли

m

L

U∈

(9)

имации, ан

.

. Р екоторые

нейного упорядочения, изучив на первом этапе их

свойс «Разумно» сконструированные модели

обладать определенными свойствами.

е линейным

тва. должны

Опред ление 4. Произвольным упорядочением

объектов из множества

(

)

n

x, ..,x

1

.x

=

будем называть кортеж з

номеров

()

i,...,iI =

, где

()NI

– номер места объекта

x

в

и

упор

Множество всевозможных упорядочений (перестановок) над

n1

m

ядочении I.

()

x,...,xx =

обозначим

n1

!nII

**

==

. Поскольку задана матрица

парных равнений с

A

и некоторая м дель у рядочения, то

множество оптимальных

о по

с ее точки зрения упорядочений

, пробозначим

I

*

()

A

opt

ичем

(

)

1

opt

>AI

*

.

зможные изменения мно в

зависимости от допустимых изменений исходной матрицы

сравн

Рассмотрим во жества

()

AI

*

opt

парных

ений

A

, обращ инвариантность го ества

относительно стандартных преобразований.

ая это множ

181

Свойство 1(инвариантность к растяжению).

Умножения всех элеме трицынтов ма

A

на число

0K >

не изменяют

оптимальных упорядочений:

0>

∀

k

(

)

(

)

KA

.

**

opt opt

IAI=

Свойство 2(инвариантность к сдвигу). Замена всех

элементов

ij

a

на элементы

()

ij

ab

+

, где

0b >

не влияет на

(

)

(

)

***

opt opt opt

: 0,

n

I

bIAIAbE∀> = +

.

Свойство 3(транспонируемость). Замена всех

предпочтений на противоположные, т.е. инверсия всех дуг в

струк ений должна приводить к т та ьно и

птимальных упорядочений:

туре предпочт о л й инверси

(

)

(

)

T*T**

AIIAIIII

optopt

,

∈

⇔

∈

∀

, где

T

A

о

– тр нированная матрица парных сравнений, описывающая

инвертированную структуру пр

анспо

едпочтений;

T

I

–

, при котором если

1

( ,Ii=

зеркал

инвертированное упорядочение

ость «в малом»). Достаточно

малые допустимые изменения матрицы

ьно

о

..., )

m

i

, т

1

,..., )

m

.

Свойство 4 (устойчив

(

T

Iii=

A

должны сохранять

опти бы одного

(

)

AI

*

opt

мальность хотя мента из эле :

(

)

(

)

***

t

0, I

εε

∃>

A

–

opt op

BA BA B I A∈ − < ⇒ ⊆

где

∀

мно тво матриц

с заданной калибровкой.

жес

пределение 5. Оптимальное упорядочение будем называть

кусоч м упорядочением, е

произвольного количества объектов с самого начала или с самого

чная» оптимальность). Для любой

О

но-оптимальны если отбрасывани

конца его сохраняет оптимальность оставшегося фрагмента.

Свойство 5(«кусо

матрицы парных сравнений A любое упорядочение

(

)

AII

*

opt

∈

является кусочно-оптимальным.

6. Конкретные модели и их свойства. Используемые на

практике модели линейного упорядочения традиционно

разде

ским метода

ляются на две большие группы. В

моделях первой группы,

тяготеющих к статистиче м обработки матриц парных

182

сравнений у объе

i

опоста ляется определенный

интегральный по

, каждом кту с в

казатель

x

i

π

, оц вающий итоги его сравнения с

остал

по убыванию го ранжир

рой п

и м м

не от бъектов всего упорядочения в целом.

, м груп

и «по »

ом сумма очков:

ени

ьными объектами, а далее объекты просто упорядочиваются

значений это ующего фактора.

Модели вто группы ис ользуют комбинаторно-

логические теоретико-графовые етоды, при это оцениваются

показатели дельных о , а

Такое разделение условно поскольку етоды первой пы

характеризуют оптимизационные задачи:

*

1

max

n

i

II

t

τ

π

∈

=

⋅→

∑

.

Модел с ртивного типа. В качестве ранжируемого

фактора здесь используется набранная объект

,1,:

iij

ij

ij n S

=

∀= =a

∑

, (10)

что фактически соответствует суммированию элементов в строке

матрицы

.

A

орядочиваются

Д л в часто вс щейс

уп по убыванию . Обрабатываемая матрица может

имет

введем понятие интег

а ее наиболее тречаю я схеме объекты

i

S

ь калибровку турнирного типа или типа простой структуры.

Модель упорядочения, близкая к «спортивной». Модель

предложена В.Е. Жуковиным для кососимметричных матриц. Для

произвольной пары объектов ральной

степени превосходства

() ( )

∑

=

−=

n

t

jtitti

aaλx,x

1

Δ

Ф

, (11)

оценивающее превосходство

j

x

в сравнении с проч ми. ими объекта

Функцию

()

ji

,xxФ

можно пред ть в виде:

стави

(

)

(

)

(

)

jiji

xfxfx,x −=Ф

, (12)

при этом

()

(

1

)

Ф

ijj

j

x

=

.

: ,

n

i

if xx

λ

∀=

∑

183

f

Функция в данной модели имее слт смы функции полезности

на множестве

X

, и объекты предлагается упорядочивать по

убыванию ее значений. Коэффициенты

j

λ

– весовые, и если их

заранее определить невозможно, то можно выбрать

n

j

1=

. Тогда

λ

()( )()

1

ij it jt i j

t=

В силу (1 ) следует, что если

,:Ф ,

n

ij xx a a n s s n∀=−=−

∑

. (13)

3

(

)

,: /ij f x s n∀=

, то данна

полностью сводится к турнирной

ii

я модель

модел

Ес

ью.

Минимаксные модели спортивного типа. Для

«спортивных» моделей можно ввести минимаксный критерий, в

котором сила объекта оценивается по наиболее крупному

проигрышу. В модели функции доминируемости, ориентированной

на обработку нечетких предпочтений, выбор строится на основе

следующих рассуждений. ли

[

]

10,a

ij

∈

– степень принадлежности

пары

(, )

ij

xx

к нечеткому отношению предпочтения, заданному на

X

, то «функция доминируемости»

()

ij

ix

axl

*

≠

= max

Δ

(14)

теризует максимальную «силу», с которой объект

x

доминируется остальными объектами мно

харак

жества

i

X

. При

()

0

=

ix

xl

объект

i

x

абсолютно не доминируется; при

(

)

1

=

ix

xl

– абсолютно

доминируется; при

(

)

10

<

ix

xl

– слабо доминируется. Для

ранжирования объе функции

рассм енную функцию

ктов вместо

()

удобно

ix

xl

атривать двойств недоминируемости

()

(

)

ixix

xlxm

−

=

1

, (15)

упорядочивая объекты по убыванию соответствующих ей значений.

184

Модель функций доминирований предназначена для обработки

матриц в вероятностной калибровке.

Многоступенчатые модели. Естественной альтернативой

турнирной модели являются многоступенчатые модели, например,

модель последовательного выч енения идера (по Льюсу). В

качестве наилучшего об

л л

ъекта выбирается объект с наибольшей

суммой, он помещается на первое место в строящемся

упор соответствующие столбе з ядочении, а далее ц и строка и

матрицы

A

вычеркиваются, с рочные суммы пересчитываются,

вновь выбирается лидер и т.д.

т

Модель Бредли-Терри. Эта модель для простых структур без

равно и целочисленных .

Каждому объекту в модели Бредли-Терри сопоставляется его сила

предполагается, о вероятность превосходства в

ом сравнении прямо пропорциональная :

ценных элементов турнирных матриц

i

π

, причем чт

парн

()

Px x>

ij

i

π

()()1().

ij iij ji

Px x Px x

π

ππ

= +=− >

(16)

Допуская, что для каждой пары

(,

>

)i

j

проводится

n

парных

сравнений и все парные сравнения независимы, выпишем овную

вероя рицы

усл

A

(тность мат функцию пра доподобия):

в

1

()

ij

ii

K

ij ij

ijn

Lc

π

ππ

()

i

ij

n

s

aa

i

j

ij

c

π

ππ ππ

=

⎞

⎟

+

∏

ππ

≤< ≤

⎛⎞⎛

==

⎜⎟⎜

⎜⎟⎜⎟

++

⎝⎠⎝⎠

∏

, (17)

где

1

()

k

ij

ijn

Ca

≤< ≤

=

∏

; а

i

S

– строчные суммы (10).

Для вычисления нормализованного вектора

π

:

1

n

i

π

=

∑

,

максимизирующего функц правдоподобия

()

ию

L

π

,

прологарифмируем (17), и после вычисления частных производных

и приравнивания их нулю, получим:

185

1

(),1,;

n

ii i j

j

n

SK in

πππ

−

=

⎧

=+=

⎪

⎨

∑

1i=

⎩

1.

i

π

⎪

=

⎪

∑

(18)

ешив систему (18) численными методами, можно найти Р

i

π

,

П

у очени

которые затем упорядочиваются по убыванию. олучае

упорядочение качественно совпадает с турнирным поряд

если

ij

SS< , то и

ij

мое

ем:

π

< .

Модель Бержа и ния. Берж предложил модел для

обработки прос х структу редпочт ний. Затем ь была

обобщена Бруком и Бурковым для матриц со ст

алибровкой. При использовании модели Бержа-Брука

ее обобще ь

ты р п е эта модел

епенной

-Буркова

пред атрица

к

A

полагается, что м неразл о

связанный граф). В противном случае выделяются неразложимые

т

одели ставится в соответствие

цепо

ожима (т.е. G – сильн

подматрицы, которые обрабатываются отдельно, а получаемые

фрагмен ы оптимального упорядочения объединяются.

Каждому объекту

i

x

в данной м

чка итерированных сил

(1)

i

P ,

(2)

i

P , …, в которой сила K-го

порядка

()K

i

P определяется как сумма элементов

i

-й строки в

матрице

K

A

:

1,in∀= :

()

1

()

n

KK

iij

j

PA

=

∑

, 1,2,...,

Δ

K

=

(19)

где

()(,)

K

ij

A

ij−

элемент матрицы

K

A

. При этом, когда

K

→∞,

() ()

1

lim ( )

n

KK

iji

K

j

PP

π

→∞

=

∑

, справедливо

1,in=

, где нормализованный

собственный вектор:

(

)

1

,...,

n

π

ππ

= матрицы

A

, соответствующий

к имально у по модулю собственному числу в соответствие с

теоремой Перро ениуса, может быт

ма с м

на-Фроб ь выбран

положительным. Далее объекты упорядочиваются по убыванию

186

соответствующих компонент вектора

π

.

кова Стохастическая модель Уша . В данном методе

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

калибровках. Матрица

A

преобразуется в вероятностую матрицу P,

произвольный элем которой определен как вероятность

превосходства

ент

j

x

над

i

x

. Если

A

енно

задана в р й

калибровке, то , в степ й, то

ве оятностно

Т

PA= а если

1

(1 ) 1

ij ji ji ij

p

aa

−

p

=

+=−

()

n n

.

Далее строится матр стохастическая ица

ij

pp

×

=

:

(1), 1;

ij ij

p

pn i−≠

1

1,,1

ij ij

j

ppij

≠

=− =,,n

∑

=

(20)

которая имеет смысл переходных вероятностей марковской цепи.

объек й дится по

щих формул:

Упорядочение тов в данно модели произво

убыванию компонент финального распределения вероятностей,

вычисляемых по совокупности следую

1

,1,

n

iii jj

j

,

p

in

=

=Δ Δ =

∑

где – минор, полученный из

(21)

ii

Δ



det ( )EP

−

исключением го

стол

i

-

бца и

i

-ой строки. Положительность всех

i

p

заведомо

гарантируется только для неразложимых атриц м



P , т. для сильно

связных графов

е.



G

, а если это условие не выполнено, некоторые

компоненты могут оказаться нулевыми.

н о

с

х

Модель равномерного сглаживания. Эта модель

предложена Киселевым для обработки положительных матриц с

калибровкой турнир ог типа и опирается на аксиому Льюса,

устанавливающую однозначное оответствие между неявно

заданными «силами» отдельны объектов. Если

A

– турнирная

матрица, то по аксиоме Льюса

:(),

i j ij ji ij ij

iaaaca

π

∀==− (22)

187

– «сила» объекта ,

ij ji

ca a

i

x

где

i

π

=

+

– турнирная константа. Тогда

11

,

nn n

ii j ji ij

b

ππ π ππ

11 1jj j

−

⎛⎞⎛⎞

== =

⎜⎟⎜⎟

∑∑ ∑

(23)

== =

⎝⎠⎝⎠

где

B

ij ji ij

baa=

– элементы матрицы , имеющей степенную

калибровку чив , можно 2)

(24)

так что матрица обладает известной избыточностью и

а цели ю

й

. Обозна

∀=

видеть, что из (2

,: ln

ij ij

ij z b

следует

,, : ,∀==−+

может быть восстано ком по л бой своей строке.

Реальные матрицы редко удовлетворяют аксиоме Льюса. Поэтому

от исходно матрицы

ij iK Kj Ki Kj

ijK z z z z z+

()

ij n n

zz

×

=

влен

A

(или

B

, ес исходн адана в

степенной калибровке) предложено перейти к матрице z и

ли ая матрица з

, полагая, что матрица построить n различных матриц

(1)

,. ,zz

( )

..

n

()

,1,n=

порождаетс

K

-й строкой матрицы z помощью (22).

Введя усредненную м рицу:

K

zK

ся

ат

1

n

i

zz

n

=

∑

, легко убедиться, что она

кососимметрич ская и удо летворяе (24), приче имеет место

е в т м

1

,: ( ).

n

ij iK Kj

K

ij z z z

n

=

∀= +

∑

(25)

ыполнив обратные преобразования: В

,: exp

ij

ij b z∀=,

1

(1 )

ij ij ij

acb b

B

и

A

−

=+, можно получить матрицы , удовлетворяющие

аксиоме Льюса и допускающие однозначное определение

ранжирующего вектора

π

, удовлетворяющего (23):

1

11

1

exp ln(

n

nnn n

jr ri

ij

ijrri

aa

bbb

naa

π

−−

⎡⎤

⎛⎞

⎛⎞⎛ ⎞

⎛⎞

⎢

== =

⎜⎟

⎜⎟⎜ ⎟

⎜⎟

⎢

⎜⎟

∑∑∑ ∑

∏

111 1

1

, 1, .

jjr j

r

ir rj

in

=== =

=

⎥

=

⎥

⎝⎠

⎝⎠⎝ ⎠

⎝⎠

⎢⎥

⎣⎦

(26)

Нетрудно убедиться, что модель равномерного сглаживания

188

инварианта (в турнирн ).

Коэффициенты

к растяжению ой калибровке

i

π

можно оценки использовать для количественной

шкале.

М асования

пр

ую

по Слейтеру

упоря

важности объектов в пропорциональной

одель максимального согл . Простейшая модель

максимального согласования первоначально едложена

Слейтером для анализа без равноценных элементов. Модель

основана на след щем определении.

Определение 6. Элементарным несогласием

дочения с матрицей

I

A

, называется с тояни когда

несогласие имеет место, если для некоторой пары объектов

(, )

ij

xx

выполнено условие

j

ос е,

i

x

x> , т.е. для матрицы

A

выполнены условия:

1

ij

a =

,

0

ji

a =

, однако

j

x

предшествует

i

x

в упоря ении

I

.

Оптимальным упорядоче

доч

нием предполагалось считать

максимальное согласованное с

A

элементарных

с

упорядочение, которое имеет

мини таких несо ас –

слейтерово число несогласий

мальное число гл ий. Если

()

A

vI

, а

()

B

I

A

– матрица

ож

линейного

порядка, задаваемая

I

, то м зать, что но пока

(, ()) 2 ().

A

BI v I

ρ

α

=

лейтерово число несогласий можно представить в виде:

(27)

С

1

11

() ,

nn

()( 1)2

r

A

iS

nn=−

ре е

записана в канонической

ляющую собой задачу

н

и п

rSr

vI ai

−

==+

−

∑∑

а задача оп д ления оптимального

упорядочения может быть форме:

(28)

*

1

11

() max,

rs

nn

Aii

II

rSr

GI a

−

Δ

∈

==+

=→

∑∑

представ поиска структуры, наиболее

совпадающей с исходной. Экстремальная задача (28) предписывает

необходимость одновременной перестановки строк и столбцов,

максимизирующей сумму аддиагональных элементов в

получаемой матрице, известна од названием задачи о

189

наилучшей приближенной уляции матрицытрианг

A

.

ь

()

A

GI

может интерпретироваться как показатель

качества аппроксимации и структуры линейным

Показател

сходной

упорядочением.

Контрольные вопросы

деи составляют основу а

принятия решений на основе обработки системных (решающих) матриц.

ие основу обобщенны

метод (р ат

К то

.

я

и риска.

Поясните сущность методов принятия решений на основе

комбинаторной аппроксимации.

Каковы основные идеи принятия решений на основе й

ортивного типа».

Какие и классического метод

Как основные принципы положены в х

ов системных ешающих) м риц.

акие принципы определяют ме ды принятия решений на

основы теории риска

Какие основные поняти теории вероятностей и

математической статистики спользуются в методах теории

моделе

«сп

190

Козлов В.Н. Системный анализ и принятие решений

Подождите немного. Документ загружается.