ВУЗ: Омский государственный технический университет
Категория: Книга
Дисциплина: Методы оптимальных решений
Добавлен: 12.02.2019
Просмотров: 13048
Скачиваний: 110
81
(
)
0,01
0,01
0,28
0,07
0,16; 0,19; 0,19; 0,05; 0,12; 0,30
0,159
0,025
0,0
0,105
M
=
+
=
и
1,24 0,58 1,82
M
=
+
=
.
Отношение согласованности иерархии будет
/
0,09
M M
=
, и более приемлемо,
чем в предыдущем примере.
4.6. ИНТЕРПРЕТАЦИЯ ПРИОРИТЕТОВ
С ПОМОЩЬЮ ТЕОРИИ ГРАФОВ
Следующая интерпретация использует теорию графов, придавая геометрический
смысл разнообразным отношениям между видами деятельности или целями уровня
иерархии (см. дополнение 2 для краткого введения в теорию графов).
На чем основывается наша уверенность в том, что «более предпочтительный»
вид деятельности в матрице парных сравнений получит большее значение приори-
тета? Хотя мы изучаем этот процесс в алгебраическом аспекте, в нем также можно
разобраться с помощью теории графов.
Определение 4.7. Обозначим узлы направленного графа
G
через
1, 2,
,
n
…
. С
каждой направленной дугой
ij
x
от узла
i
до узла
j
мы ассоциируем неотрицатель-
ное число,
0
1
ij
q
<
<
, называемое интенсивностью дуги. (Петли и кратные дуги раз-
решены.)
Определение 4.8. Маршрут в направленном графе есть чередующаяся последо-
вательность узлов и дуг, при которой каждый узел является концом дуги, находя-
щейся в последовательности непосредственно перед ним, и источником последую-
щей за ним дуги. Обе концевые точки каждой дуги находятся в последовательности.
Длина маршрута есть число дуг в последовательности. Маршрут длины
k
назовем
«
k
-маршрутом».
Определение 4.9. Интенсивность маршрута длины
k
от узла
i
до узла
j
есть
произведение интенсивностей дуг в маршруте.
Определение 4.10. Общая интенсивность всех
k
-маршрутов от узла
i
до узла
j
есть сумма интенсивностей маршрутов.
Замечание. Отметим, что для общей интенсивности 1-маршрутов берется сумма
интенсивностей всех 1-маршрутов от
i
до
j
. Это просто дуги, соединяющие
i
и
j
.
Все интенсивности вдоль дуги
i
,
j
считаются равными. Поэтому общая интенсив-
ность от
i
до
j
получается равной
ij
ij ij
t
p q
=
, где
ij
p
– число дуг от
i
до
j
, а
ij
q
–
интенсивность каждой дуги.
Определение 4.11. Для заданного направленного графа
D
матрица интенсив-
ности-инцидентности
( )
ij
U
u
=
определяется как матрица, элементами которой яв-
ляются
ij
ij
u
t
=
для всех
i
и
j
.
82
Для пояснения приведенных выше понятий представлен следующий пример. На
рис. 4.1 число рядом с каждой дугой показывает ее интенсивность.
Рис. 4.1
Матрица интенсивности-инцидентности
U
, ассоциируемая с этим графом, будет
1
3/ 2 2
2 / 3
1
3
3
2
1
U
=
.
Общая интенсивность 1-маршрутов от
i
до
j
представлена
( )
,
i j
-м элементом
этой матрицы. Например, общая интенсивность маршрута длины 2 от узла 1 до узла
3 равна сумме следующих трех величин вместе с соответствующим маршрутом, изо-
бражённым справа. (Отметим, что каждая дуга между первыми двумя узлами берет-
ся по одному разу с каждой дугой между двумя узлами.)
(
) (
) (
)
12
23
3 1/ 2 1
1/ 2 1
1/ 2 1 :1,
, 2,
, 3
x
x
× +
× +
×
11
13
, 1,
, 3
x
x
13
33
, 3,
, 3
x
x
Сумма этих величин равна 17/2. Это есть элемент (1,3) матрицы
2
U
. Таким об-
разом можно показать, что для всех
i
и
j
общая интенсивность 2-маршрутов от уз-
ла
i
до узла
j
будет
( )
,
i j
-м элементом матрицы
2
8
7
17 / 2
31/ 3
8
22 / 3
22 / 3 17 / 2
13
U
=
Этот результат может быть обобщен согласно следующей легко доказываемой
теореме.
83
Теорема 4.5.
( )
ij
u k
–
( )
,
i j
-й элемент матрицы
k
U
является общей интенсивно-
стью
k
-маршрутов от узла
i
до узла
j
.
Следствие. Если
1
ij
q
=
для всех
i
и
j
, то
( )
,
i j
-й элемент в
k
U
является чис-
лом
k
-маршрутов от
i
до
j
.
Понятие превосходства относительно свойства: обратная задача.
В предыдущем обсуждении для изучения идеи об интенсивности
k
-маршрутов
мы перешли от графа к соответствующей матрице. Для рассматриваемой проблемы
важна обратная задача интерпретации степеней матрицы для подсчета интенсивно-
сти маршрутов.
Будем ассоциировать с каждым из
n
видов деятельности нашей процедуры пар-
ных сравнений узел направленного графа
D
. В этом случае матрица интенсивно-
сти-инцидентности
U
есть не что иное, как матрица суждений, о которой говори-
лось в гл. 1. Числитель
ij
p
( )
,
i j
-го элемента такой матрицы (полагая, что он дан в
сравнительно простой дробной форме) представляет собой число дуг, направленных
от вершины
i
к вершине
j
. Интенсивность каждой дуги от
i
до
j
одна и та же и
равна обратной величине
ij
q
знаменателя элемента. Это естественный способ опре-
деления соответствующего графа, так как для
1
ij
q
=
он сводится к обычной матрице
вершин,
k
-я степень которой дает число маршрутов длины
k
.
Интерпретировать
( )
,
i j
-й элемент матрицы
A
можно как прямое превосходство,
или интенсивность важности вида деятельности
i
относительно вида деятельности
j
. Он выражает относительный вклад, который вид деятельности
i
вносит в дости-
жение определенной цели по сравнению с вкладом, вносимым видом деятельности
j
. Нормализованные суммы строк матрицы
A
представляют собой уровень вклада
соответствующих видов деятельности относительно всех других видов деятельности,
а матрицы
2
A
– индекс относительной влажности превосходства с учетом всех
2-маршрутов. Последний обеспечивает косвенное сравнение пар через одну проме-
жуточную вершину. Следовательно, уровень важности вида деятельности повыша-
ется или снижается в соответствии с его взаимосвязью с другими видами деятельно-
сти. В общем случае эффект превосходства между видами деятельности можно по-
лучить, вычисляя предельное значение суммы строк
k
A
матрицы
A
k
-й степени.
Каждое число, нормализованное посредством суммы этих величин, служит общим
индексом относительного превосходства, или приоритетом, среди видов деятельно-
сти.
Формально понятие относительного превосходства вида деятельности
i
над ви-
дом деятельности
j
за
k
-шагов можно сейчас разъяснить в терминах общей интен-
сивности всех
k
-маршрутов от узла
i
до узла
j
. Относительное превосходство вида
деятельности
i
над другим видом деятельности
j
прямо и косвенно, через проме-
жуточные виды деятельности, за
k
-шагов представлен
( )
,
i j
-м элементом матрицы
k
A
. Из-за наличия петли на каждой вершине получается, что каждый вход матрицы
k
A
является суммой всех маршрутов длины, меньшей или равной
k
. Сколько раз
включен каждый маршрут зависит от его длины и от числа перестановок его петель
при получении искомой длины маршрута. Петля сама по себе придает единичную
интенсивность маршруту. Следовательно, общая интенсивность маршрута не меня-
84
ется при прохождении вдоль петли несколько раз. Важно отметить, что предельный
результат совпадает с результатом, который был получен ранее.
Теорема 4.6. Пусть
( )
ij
A
a
=
–
n n
×
-матрица сравнений;
( )
ij
a k
–
( )
,
i j
-й эле-
мент матрицы
k
A
представляет собой относительное превосходство (или важность)
вида деятельности
i
над видом деятельности
j
за
k
-шагов.
Доказательство следует непосредственно из приведенного выше соответствия
и последней теоремы.
Определение 4.12. Индекс превосходства
( )
i
k
ω
вида деятельности
i
над все-
ми другими видами деятельности за
k
-шагов определяется как
( )
( )
( )
1
1
1
/
n
n
n
i
ij
ij
j
i
j
k
a k
a k
ω
=
=
=
=
∑
∑∑
.
Таким образом,
( )
i
k
ω
– сумма
i
-й строки
k
A
, делённая на сумму строк.
Определение 4.13. Общий индекс превосходства
i
ω
вида деятельности
i
над
всеми другими видами деятельности определяется как
( )
( )
( )
1
1
1
lim
lim
n
ij
j
i
i
n
n
k
k
ij
i
j
a k
k
a k
ω
ω
=
→∞
→∞
=
=
=
=
∑
∑∑
.
Определение 4.14. Индекс приоритета, ассоциируемый с видом деятельности
i
, является общим индексом его превосходства
i
ω
.
85
ЧАСТЬ II
ПРИЛОЖЕНИЯ
Маргинальные приоритеты – Динамические приоритеты – Взаимозави-
симость вход-выход – Размещение ресурсов – Планирование: обществен-
ный и частный секторы – Разрешение конфликтов – Энергетика.
Наша цель – довести до сведения лиц, принимающих решения, во-первых, опи-
сание МАИ, затем показать его обширные приложения и, наконец, предоставить
ученым и математикам некоторые основы теории. В данной части иногда будут по-
вторы, иллюстрирующие сферы применения, несмотря на то, что метод остается тем
же. Тем не менее приложения в основном предназначены для раскрытия возможно-
стей использования МАИ как простого и надежного метода, связанного с решением
реальных проблем, наряду с некоторыми существующими методами или зачастую
вместо них. Тема, к которой следует возвратиться: если декомпозиция и синтез –
фундаментальные процессы, характерные для мозга, которые имеют место в смыс-
ле, раскрываемом в данной книге, то могут возникнуть некоторые социальные, на-
учные и даже математические задачи, которые помогут понять их формализацию.
В наших приложениях вырабатываются приоритеты для видов деятельности,
служащих для удовлетворения определенных целей, которые, в свою очередь,
должны подчиняться другим ограничениям, как более высоким целям иерархии. Мы
занимались сравнительной формой оптимизации (без использования метрики). Этот
тип исследований продолжается. В гл. 5 рассматриваются формально представлен-
ные приложения, в то время как в гл. 6 приложения охватывают ряд ситуаций из
реальной жизни, а также представлена формальная основа двухточечного гранично-
го процесса планирования и разрешения конфликтов.