ВУЗ: Омский государственный технический университет
Категория: Книга
Дисциплина: Методы оптимальных решений
Добавлен: 12.02.2019
Просмотров: 13045
Скачиваний: 110
71
Символ
sup
используется для обозначения супремума. (Для конечных множеств
наибольшие элементы и верхние границы одинаковы.)
Аналогичные определения могут быть даны для множеств, ограниченных снизу –
нижняя граница и инфимум. Здесь используют символ
inf
.
Существует много способов определения иерархии. Нашим целям наиболее соот-
ветствует следующий:
Воспользуемся обозначением
{
}
| покрывает
x
y x
y
−
=
и
{
}
| покрывает
x
y y
x
+
=
для любого элемента
x
в упорядоченном множестве.
Определение 4.4. Пусть
H
– конечное частично упорядоченное множество с
наибольшим элементом
b
.
H
есть иерархия, если выполняются следующие условия.
1. Существует разбиение
H
на подмножества
,
1,
,
k
L k
h
= …
, где
{ }
1
L
b
=
.
2. Из
k
x L
∈
следует, что
1
k
x
L
−
+
⊂
,
1,
,
1
k
h
=
−
…
.
3. Из
k
x L
∈
следует, что
1
k
x
L
+
−
⊂
,
2,
,
k
h
= …
.
Для каждого
x H
∈
существует такая весовая функция (сущность ее зависит от
явления, для которого строится иерархия):
[ ]
:
0,1
x
x
ω
−
→
, что
( )
1
x
y x
y
ω
−
∈
=
∑
.
Множества
i
L
являются уровнями иерархии, а функция
x
ω
, есть функция при-
оритета элемента одного уровня относительно цели
x
. Заметим, что даже если
1
k
x
L
−
+
⊄
(для некоторого уровня
k
L
), то
x
ω
может быть определена для всех
k
L
,
если приравнять ее к нулю для всех элементов в
1
k
L
+
, не принадлежащих
x
−
.
Мы считаем, что весовая функция вносит важный вклад в применение метода
анализа иерархии.
Определение 4.5. Иерархия называется полной, если для всех
k
x L
∈
множест-
во
1
k
x
L
+
−
=
, при
2,
,
k
h
= …
.
Можно сформулировать главный вопрос:
Основная задача. Как определить для любого заданного элемента
x L
α
∈
, и
подмножества
S
L
β
⊂
,
(
)
α β
<
функцию
[ ]
,
:
0,1
x S
S
ω
→
, чтобы она отражала свой-
ства функций приоритетов
x
ω
на уровнях
k
L
,
,
,
1
k
α
β
=
−
…
. В частности, что это за
функция
[ ]
,
:
0,1
h
x L
h
L
ω
→
?
Используя менее формальную терминологию, задачу можно переформулировать
следующим образом.
Рассмотрим социальную (или экономическую) систему с главной целью
b
и мно-
жеством основных видов действий
h
L
. Пусть эту систему можно представить как ие-
рархию с максимальным элементом
b
и нижним уровнем
h
L
. Каковы приоритеты
элементов уровня
h
L
по отношению к
b
?
С точки зрения оптимизации для распределения ресурсов между элементами не-
обходимо учитывать также все взаимосвязи между ними. Аналитически взаимосвязь
может принять вид отношений типа вход–выход, например, имеющих место при вза-
имном обмене продукцией между отраслями промышленности. Отрасль с более вы-
соким приоритетом может зависеть от потока продукции, выпускаемой отраслью с
более низким приоритетом. В рамках оптимизации приоритет элементов позволяет
определить целевую функцию, которую затем следует максимизировать, а другие
72
иерархии позволяют получить информацию, касающуюся связей, например отноше-
ний типа вход–выход.
Теперь изложим наш метод решения основной задачи. Предположим, что
{
}
1
,
,
k
m
k
Y
y
y
L
=
⊂
…
и
{
}
1
1
1
,
,
k
m
k
X
x
x
L
+
+
=
⊂
…
. (Заметим, что в соответствии с заме-
чанием, следующим за определением 4.4, можно предположить, что
k
Y
L
=
,
1
k
X
L
+
=
.) Пусть также существует элемент
1
k
z L
−
∈
, такой, что
y z
−
∈
. Рассмотрим
теперь функции приоритетов
[ ]
:
0,1
x
Y
ω
→
и
[ ]
:
0,1
j
X
ω
→
,
1,
,
k
j
n
= …
.
Обозначив через
ω
,
[ ]
:
0,1
X
ω
→
«функцию приоритета элементов из
X
отно-
сительно
z
», зададим ее следующим образом:
( )
( )
( )
1
k
j
n
i
y
i
z
j
j
x
x
y
ω
ω
ω
=
=
∑
,
1
1,
,
k
i
n
+
= …
.
Очевидно, что это не что иное, как процесс взвешивания показателя влияния
элемента
i
y
на приоритет элемента
i
x
, путем умножения этого показателя на важ-
ность элемента
i
y
относительно
z
.
Соответствующие алгоритмы упростятся, если из
( )
i
y
i
x
ω
образовать матрицу
B
,
положив
( )
j
ij
y
i
b
x
ω
=
. Если обозначить далее
( )
i
i
W
x
ω
=
и
( )
'
j
z
j
W
y
ω
=
, то приве-
денная выше формула примет вид
'
1
n
i
ij
j
j
W
b W
=
=
∑
,
1
1,
,
k
i
n
+
= …
.
Итак, можно говорить о векторе приоритетов
ω
и о матрице приоритетов
B
(
)
1
k
+
-го уровня. В результате имеем окончательную формулу
'
W
BW
=
.
Предыдущая композиция приоритетов включает взвешивание и суммирование.
Это требует независимости критериев на каждом уровне, в противном случае один
элемент может получить некоторый приоритет относительно некоторого признака и
дополнительный приоритет, вызванный перекрыванием этого признака с другим
признаком, что вызовет двойной учет. В простых терминах множество признаков
или критериев называют независимым, если возможна взаимозаменяемость любой
пары безотносительно влияния других. Иными словами, критерии независимы, если
между ними нет взаимодействия. Существуют формальные определения независи-
мости и тщательно разработанные методы ее тестирования, использующие суждения
участников (см., например, [79]). Помимо неформальных обсуждений независимости
существуют строгие и требующие больших затрат времени методы проверки незави-
симости. На практике люди предпочитают полагаться на интуитивную интерпрета-
цию отсутствия взаимодействия, чем производить серию тестов. При проведении
теста с каждым признаком ассоциируется множество «уровней», например, при обу-
чении имеются уровни оценок
A
,
B
,
C
,
D
и т. д. Проверяется предпочтение в су-
ждениях между ними для определенного индивидуума, которое может быть поряд-
ковым или количественным. Если кроме обучения имеются другие признаки, то не-
обходимо зафиксировать каждый на некотором базовом уровне, прежде чем прово-
дить сравнение предпочтения
A
,
B
,
C
,
D
. Затем следует изменить уровень одного
из других признаков и провести сравнение предпочтения между разными уровнями
обучения
A
,
B
,
C
,
D
. Продолжать это нужно, меняя все уровни второго признака.
Если предпочтение между
A
,
B
,
C
,
D
остается тем же, то говорят, что обучение
73
условно независимо от второго признака. Условно оно потому, что другие признаки
зафиксированы на определенном уровне. Если имеется несколько признаков, то
процесс продолжается. Для аддитивности два вида деятельности должны быть неза-
висимыми и удовлетворять условию сокращаемости. Для трех каждая пара должна
быть независима, а также должны быть удовлетворены другие условия, и т. д. Те-
перь повторим основную идею просто в рамках теории множеств и изложим прин-
цип.
Принцип иерархической композиции: аддитивность взвешивания
Задано два конечных множества
S
и
T
. Пусть
S
– множество независимых
свойств (примеры зависимости см. в гл. 8) и
T
– множество объектов, которые в ка-
честве характеристик обладают этими свойствами. Предположим, что численный
вес, приоритет, или индекс относительной важности,
0
j
ω
>
,
1,
,
j
n
= …
, ассоцииру-
ется с каждым
j
s
S
∈
, так что
1
1
n
j
j
ω
=
=
∑
. Пусть
0
ij
ω
>
,
1,
,
i
m
= …
, удовлетворяющие
условию
1
1
m
ij
i
ω
=
=
∑
, есть веса, ассоциируемые с
i
t
T
∈
,
1,
,
i
m
= …
, относительно
j
s
.
Тогда выпуклая комбинация
ij
ω
,
1,
,
j
n
= …
,
1
n
ij
j
j
ω ω
=
∑
,
1,
,
i
m
= …
представляет собой численный приоритет или относительную важность
i
t
относи-
тельно
S
. Заметим, что принцип распространяется на цепь множеств. Аксиоматиза-
ция принципа иерархической композиции была бы полезной.
Замечание. «Иерархическое измерение» есть процесс взвешивания «линей-
ных» переменных, ассоциирующий каждый уровень с нелинейными коэффициента-
ми, которые являются произведениями и суммами переменных, связанных с верхни-
ми уровнями. Заметим, что линейность здесь просто означает прямое умножение чи-
сел без возведения их в степени или образования функций от них. В действительно-
сти эта величина является сложной (нелинейной) мерой приоритета.
Далее следует первый шаг к подтверждению приведенного выше принципа, по-
казывающий, что порядковые предпочтения сохраняются при композиции.
Определение 4.6. Предположим, что для каждой подцели или вида деятельно-
сти
j
e
в
k
L
существует порядковая шкала
j
o
над видами деятельности
e
α
(
)
1
1,
,
k
n
α
+
= …
в
1
k
L
+
. Определим частичный порядок на множестве
1
k
L
+
следующим
образом:
e
e
α
β
≥
тогда и только тогда, если для
1,
,
k
j
n
= …
,
j
j
o
o
α
β
≥
.
Легко доказать следующую теорему:
Теорема 4.1. Пусть
(
)
1
1
,
,
k
j
n
j
ω
ω
+
…
– вектор приоритетов для
1
k
L
+
относительно
j
e
и предположим, что он сохраняет порядок
j
o
α
. Пусть
1
1
,
,
k
n
W
W
+
…
– (составной)
вектор приоритетов для
1
k
L
+
. Тогда из
e
e
α
β
≥
следует, что
W
W
α
β
≥
. Таким образом,
иерархическая композиция сохраняет порядковое предпочтение.
Легко доказать следующую теорему.
Теорема 4.2. Пусть
H
– полная иерархия с наибольшим элементом
b
и
h
уров-
нями. Пусть далее
k
B
– матрица приоритетов
k
-го уровня,
2,
,
k
h
= …
. Если
'
W
–
74
вектор приоритетов
p
-го уровня относительно некоторого элемента
z
в
(
)
1
p
−
-м
уровне, то вектор приоритетов
W
q
-го уровня
(
)
p q
<
относительно
z
определяет-
ся как
'
1
1
q
q
p
W
B B
B W
−
+
=
…
.
Таким образом, вектор приоритетов самого низкого уровня относительно элемен-
та
b
'
1
2
h
h
W
B B
B W
−
=
…
.
Обычно
1
L
состоит из единственного элемента,
'
W
– просто скаляр; в противном
случае
'
W
– вектор.
Следующее наблюдение касается полной иерархии, однако его полезно иметь в
виду и в общем случае. Приоритет элемента любого уровня равен сумме его приори-
тетов в каждом подмножестве сравнения, которым он принадлежит; иногда каждый
из приоритетов взвешивается лишь частью элементов уровня, которые принадлежат
данному подмножеству, и приоритетом подмножества. Получающееся множество
приоритетов элементов этого уровня затем нормализуется посредством деления на
сумму приоритетов элементов. Приоритет подмножества на уровне равен приоритету
доминирующего элемента на следующем уровне.
Заметим, что композиции весов в иерархии представляют собой полилинейные
выражения вида
1
2
1, ,
1
2
p
p
i
i
i
p
i
i
x x
x
∑
…
…
,
где
j
i
обозначает
j
-й уровень иерархии, а
j
x
– приоритет элемента на этом уров-
не. По-видимому, имеется хорошая возможность исследовать связь композиции с
ковариантными тензорами и их алгебраическими свойствами.
Более конкретно, имеем ковариантный тензор
1
1 2
2 3
2
1
1 1
2
1
, ,
1
2
1
, ,
h
i
h
h
h
h
N
N
h
h
h
i
i i
i i
i
i
i i
i
i
i
ω
ω ω
ω
ω
−
−
−
−
−
−
=
≡
∑
…
…
…
,
для приоритета
i
-го элемента на
h
-м уровне иерархии. Составной вектор
h
W
для всего
h
-го уровня представлен ковариантным гипертензором (вектором с тен-
зорными компонентами). Аналогично подход к иерархии, основанный на левом соб-
ственном векторе, обусловливает контравариантный гипертензор.
Классическая проблема, относящая пространство (геометрия) и время к субъек-
тивному мышлению (см. [121]), может быть исследована, если доказано, что функ-
ции математического анализа (и, следовательно, также и законы физики) могут
быть получены как усеченные ряды приведенных выше тензоров посредством по-
строения соответствующей иерархии. Это напоминает теорему из анализа размерно-
стей, которая утверждает, что любая физическая переменная пропорциональна
произведению степеней исходных переменных.
4.3. ДЕКОМПОЗИЦИЯ И АГРЕГИРОВАНИЕ
(ПОСТРОЕНИЕ КЛАСТЕРОВ)
Существуют два фундаментальных подхода, в которых может быть использована
идея иерархии.
75
Первый подход сейчас уже ясен: реальный мир следует моделировать иерархи-
чески.
Второй подход, вероятно, является более фундаментальным, чем первый, и сви-
детельствует о реальной силе иерархий в природе. Он заключается в расчленении
рассматриваемых вещей на большие группы или кластеры, которые далее расчле-
няются на меньшие кластеры и т. д. Тогда целью будет получение приоритетов всех
элементов посредством группирования. Это намного более эффективный процесс,
чем обработка всех элементов совместно. Следовательно, несущественно, думаем ли
мы, что иерархии внутренне присущи природе, как утверждают некоторые исследо-
ватели, либо мы просто используем их из-за ограниченной способности обрабаты-
вать информацию. В любом случае они представляют собой очень эффективный
способ исследования сложных проблем.
Полезным способом исследования большого числа элементов, попадающих на
один из уровней иерархии, является группирование их в кластеры в соответствии с
их относительной важностью. Таким образом, можно иметь кластер самых важных
(самых подобных, или близких) элементов, другой кластер элементов умеренной
важности, и третий – элементов с малой важностью. Затем сравниваются попарно
относительное воздействие кластеров на соответствующий критерий из располо-
женного выше уровня. Группирование в кластеры может различаться от критерия к
критерию. После анализа кластеров элементы в каждом кластере попарно сравни-
ваются по их относительной важности в этом кластере. Если их слишком много, то
они вновь могут быть сгруппированы в кластере. Таким образом, каждый элемент
принадлежит нескольким кластерам и получает несколько весов из различных кла-
стеров. Не существует альтернативы этому процессу группирования и декомпози-
ции, особенно, когда нужно сохранить высокую согласованность. Принимая это за
факт, не следует пугаться размерности задачи, поскольку уже известно, как можно
справиться с этой проблемой. Мы весьма успешно применяли этот процесс во многих
примерах. Легко показать математически, что группировкой в кластеры можно по-
лучить те же самые результаты, что и при общем подходе.
Иерархия оценки расстояния
Теперь построим иерархическую структуру для примера оценки расстояний меж-
ду городами. Если сгруппировать города в кластеры согласно критерию расположе-
ния на почти одинаковых расстояниях от Филадельфии, то будем иметь три класса,
которые сравниваются в следующей матрице.
Филадельфия
Чикаго
Монреаль
Лондон
Сан-Франциско
Каир
Токио
Собственный
вектор
Чикаго
Монреаль
1 1/7 1/9
0,056
Лондон
Сан-Франциско
7 1 1/4
0,26
Каир
Токио
9 4 1
0,68
max
3,15
λ
=
; ИС = 0,08; ОС = 0,14
Если теперь сравнить города в каждом кластере отдельно в соответствии с их от-
носительным расстоянием от Филадельфии, то при использовании для случая
2 2
×
шкалы
1
ε
+
получим: